Parallel algorithms for dynamic-programming recurrences with more than O(1) dependency

Parallel algorithms for dynamic-programming recurrences with more than O(1) dependency

0.00 Avg rating0 Votes
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: ,
Keywords: computational analysis: parallel computers
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.