Systolic algorithms for the dynamic programming problem
Hassen Dhrif, Dilip Sarkar · International Journal of Computer Mathematics · 1992
This paper presents parallel algorithms for the dynamic programming problem on systolic arrays. The dynamic programming problem when implemented sequentially takes O(n 3) time steps. In this paper, an algorithm that runs on a linear array machine in O(n 2) time, using O(n) processors is presented. Also an algorithm that runs on a mesh connected computer in O(n) time steps, using O(n 2) processors is being studied. Both algorithms are optimal in terms of time and cost.