Mapping dynamic programming onto modular linear systolic arrays
The dynamic programming problem is to solve the following recurrence equation: given \[ \begin{multlined} w(i,j),\;1 \leq i<j \leq n \text{ and } c(i,i+1),\;1 \leq i<n, \\ \text{ compute } c(i,j)= w(i,j) +\min_{i<k<j}(c(i,k)+c(k,j)) \text{ for } 1\leq i<j \leq n+1.\end{multlined} \tag{1} \] This scheme can be used to solve many combinatorial optimization problems. The dynamic programming algorithm is one of those algorithms whose nonconstant dependencies are very difficult to replace with constant ones, because the calculations done by this algorithm depend recursively on previous results. All recent work on the subject tries to overcome the problem more or less formally. The dynamic programming is also one of several widely used problem-solving techniques in computer science and operations research. Parallel algorithms for these problems have been studied in the past, most of them being two-dimensional array algorithms. The weaknesses of all these (two-dimensional or linear) algorithms are that they are either nonmodular, some data must be initially stored in the array before their execution, each cell has a local memory of a bounded size, or at the end of their execution of solutions are stored in the array. The problem of designing modular linear systolic arrays for dynamic programming was raised by \textit{I. V. Ramakrishnan} and \textit{P.J. Varman} [Dynamic programming and transitive closure on linear pipelines, Proc. Int. Conf. Parallel Process 1984, 359- 364 (1984)]. In our work, we propose a novel systematic method for synthesizing linear systolic arrays from the equation (1). So, we derive a family of optimal and fully-pipelined modular linear systolic algorithms for dynamic programming problems. In many instances, modularity is an important feature of these algorithms. One may simply ad more processors to the array as the size of the problem increases. Each cell has a fixed amount of local storage \(\alpha\) 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 to \(n^ 2+ O(n)\) and \(n^ 2/ \alpha+O(n)\), respectively, as \(\alpha\) increases. This represents the best known performance for such an algorithm.
- A modular systolic linear array for gaussian elimination
- An incremental mechanical development of systolic solutions to the algebraic path problem
- Computing transitive closure on systolic arrays of fixed size
- Dynamic programming on linear pipelines
- Dynamic programming on two-dimensional systolic arrays
- scientific article; zbMATH DE number 4098617 (Why is no real title available?)
- scientific article; zbMATH DE number 3473265 (Why is no real title available?)
- Mapping dynamic programming onto a linear systolic array
- Mapping Homogeneous Graphs on Linear Arrays
- Partitioned Matrix Algorithms for VLSI Arithmetic Systems
- Partitioning and Mapping Algorithms into Fixed Size Systolic Arrays
- Synthesis of an Optimal Family of Matrix Multiplication Algorithms on Linear Arrays
- Synthesizing linear array algorithms from nested FOR loop algorithms
- Synthesizing synchronous systems by static scheduling in space-time
- The Parallel Recognition of Classes of Graphs
- The synthesis of control signals for one-dimensional systolic arrays
- Systolic processing for dynamic programming problems
- Dynamic programming on two-dimensional systolic arrays
- Systolic partitioning algorithms
- Partitioning and Mapping Algorithms into Fixed Size Systolic Arrays
- scientific article; zbMATH DE number 3958722 (Why is no real title available?)
- scientific article; zbMATH DE number 3978860 (Why is no real title available?)
- Path planning on the warp computer: using a linear systolic array in dynamic programming∗
- scientific article; zbMATH DE number 714583 (Why is no real title available?)
- From the theory to the tools: parallel dynamic programming
- Mapping dynamic programming onto a linear systolic array
This page was built for publication: Mapping dynamic programming onto modular linear systolic arrays
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2365569)
