Efficient Parallel Formulations for Some Dynamic Programming Algorithms: A Summary of Results
| George Karypis and Vipin Kumar |
| International Parallel Processing Symposium, 1993 |
Download Paper  |
| Abstract In this paper we are concerned with Dynamic Programming (DP) algorithms whose solution is given by a recurrence relation similar to that for the matrix parenthesization problem. Guibas, Kung and Thompson presented a systolic array algorithm for this problem that uses O(n^2) processing cells and solves the problem in O(n) time. In this paper, we present three different mappings of this systolic algorithm on a mesh connected parallel computer. The first two mappings use commonly known techniques for mapping systolic arrays to mesh computers. Both of them are able to obtain only a fraction of maximum possible performance. The primary reason for the poor performance of these formulations is that different nodes at different levels in the multistage graph in the DP formulation require different amounts of computation. Any adaptation has to take this into consideration and evenly distribute the work among the processors. Our third mapping balances the work load among processors and thus is capable of providing efficiency approximately equal to 1 ($i.e.$ speedup approximately equal to the number of processors) for any number of processors and sufficiently large problem. We present a theoretical analysis of these mappings and experimentally evaluate them on a mesh embedded onto a 256 processor nCUBE/2. It can be shown that our mapping can be used to efficiently map a wide class of two dimension systolic array algorithms onto mesh connected parallel computers. |
| Research topics: Parallel processing |