Dynamic programming on two-dimensional systolic arrays (Q1110461)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Dynamic programming on two-dimensional systolic arrays |
scientific article |
Statements
Dynamic programming on two-dimensional systolic arrays (English)
0 references
1988
0 references
Given w(i,j), \(1\leq i<j\leq n\), and \(c(i,i+1)\), \(1\leq i<n\), the problem is to compute \(c(i,j)=w(i,j)+\min_{i<k<j}\{c(i,k)+c(k,j)\}\), for \(1\leq i<j\leq n\). We show that this dynamic programming problem can be solved in optimal time \(T=2n\) on a systolic array whose size \(\frac{1}{8}n^ 2+O(n)\) is two times smaller than the number of processors required by the best previously known solution.
0 references
task allocation method
0 references
dependence graph
0 references
earliest optimal timing function
0 references
allocation function
0 references
systolic array
0 references