Efficient Parallel Formulations for Some Dynamic Programming Algorithms: A Summary of Results

George Karypis and Vipin Kumar
International Parallel Processing Symposium, 1993
Download Paper
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