On efficient parallel computations for some dynamic programming problems

A general method for parallelization of some dynamic programming algorithms on VLSI was presented in [6]. We present a general method for parallelization for the same class of problems on more powerful parallel computers. The method is demonstrated on three typical dynamic programming problems: computing the optimal order of matrix multiplications, the optimal binary search tree and optimal triangulation of polygons (see[1, 2]). For these problems the dynamic programming approach gives algorithms having a similar structure. They can be viewed as straight-line programs of size O(n 3). The general method of parallelization of such programs described by Valiant et al. [16] then leads directly to algorithms working in log2 n time with O(n 9) processors. However we adopt an alternative approach and show that a special feature of dynamic programming problems can be used. They can be thought as generalized parsing problems: find a tree of the optimal decomposition of the problem into smaller subproblems. A parallel pebble game on trees [10, 11] is used to decrease the number of processors and to simplify the structure of the algorithms. We show that the dynamic programming problems considered can be computed in log2 n time using n6 log n processors on a parallel random-access machine without write conflicts (CREW P-RAM). The main operation is essentially matrix multiplication, which is easily implementable on parallel computers with a fixed interconnection network of processors (ultracomputers, in the sense of [15]). Hence the problems considered can also be computed in log2 n time using n 6 processors on a perfect shuffle computer (PSC) or a cube- connected computer (CCC). An extension of the algorithm from [14] for the recognition of context-free languages on PSC and CCC can be used. If the parallel random access machine with concurrent writes (CRCW P-RAM) is used, then the minimum of mnumbers can be determined in constant time (see [8]) and consequently the parallel time for the computation of dynamic programming problems can be reduced from log2 n to log n. We investigate also the parallel computation of trees realizing the optimal cost of dynamic programming problems.

Authors

• Wojciech Rytter

Keywords

No keywords are indexed for this paper.