Article ID: | iaor20001090 |
Country: | United States |
Volume: | 21 |
Issue: | 2 |
Start Page Number: | 213 |
End Page Number: | 222 |
Publication Date: | Apr 1994 |
Journal: | Journal of Parallel and Distributed Computing |
Authors: | Galil Z., Park K. |
Keywords: | computational analysis: parallel computers |
We study the parallel computation of dynamic programming. We consider four important dynamic programming problems which have wide application, and that have been studied extensively in sequential computation: (1) the 1D problem, (2) the gap problem, (3) the parenthesis problem, and (4) the RNA problem. The parenthesis problem has fast parallel algorithms; almost no work has been done for parallelizing the other three. We present a unifying framework for the parallel computation of dynamic programming recurrences with more than O(1) dependency. We use two well-known methods, the closure method and the matrix product method, as general paradigms for developing parallel algorithms. Combined with various techniques, they lead to a number of new results. Our main results are optimal sublinear-time algorithms for the 1D, parenthesis, and RNA problems.