This page shows all publications that appeared in the IASI annual research reports. Authors currently affiliated with the Institute are always listed with the full name.

You can browse through them using either the links of the following line or those associated with author names.

Show all publications of the year  1982, with author Bertolazzi P., in the category IASI Research Reports (or show them all):

---

IASI Research Report n. 38  (Previous ) 


Paola Bertolazzi, Pirozzi M.

Parallel algorithms for different classes of dynamic programming problems.

ABSTRACT

In this paper the problem of parallel execution of dynamic programming algorithms is investigated. Dynamic programming requires in general a great amount of computation, which makes it unsuitable expecially in real time applications. The advent of parallel architectures, has suggested special methods for the parallel execution of algorithms, with the goal of reducing their complexity by a factor which is a function of the number of available processors 3, 4. If T is the time of a serial algorithm for a given problem, the best speed up ratio we can obtain for the algorithm on a parallel machine with P processors, is P (the complexity will decrease to T/P); however, in general, the optimal speed us ratio is not reached because of the overhead arising from interprocessor communication. This is the case of dynamic programming algorithm if no assumptions are made on the problem: in the proposal of the literature 7 one can easily see that a near optimal speed up ratio can be reached just with P small. The reasons of the limits of the approach proposed by 7 are here briefly examined, the analysis brings to the definition of two classes (A and B) of dynamic programming problems; for these classes it is shown that the classical parallel methods of 6 or a slightly modified version of them actually reach the optimal speed up ratio. Examples of problems in class A, class B, class A class B are given.