Mapping dynamic programming onto modular linear systolic arrays (Q2365569)

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.