ISSN:
1432-0452
Keywords:
Parallel algorithms
;
Linear systolic arrays
;
Modular arrays
;
Complexity
;
Dynamic Programming
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
Notes:
Summary In this paper we propose a novel way of deriving a family of fully-pipelined linear systolic algorithms for the computation of the solutions of a dynamic programming problem. In many instances, modularity is an important feature of these algorithms. One may simply add more processors to the array as the size of the problem increases. Each cell has a fixed amount of local storage α and the time delay between two consecutive cells of the array is constant. The time complexity and the number of cells in our array tend ton 2+O(n) andn 2/α +O(n), respectively, as α increases. This represents the best known performance for such an algorithm.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF02242705
Permalink