Mapping Dynamic Programming Problems on Coarse Grained Multicomputer

Abstract—Parallelization of dynamic programming algo-rithms is a very well studied topic. In this paper we are inter-ested by an important class of Dynamic Programming problems. Many results have been presented for this problems class for the fine grained parallel machines. We proposed an efficient parallel Coarse-Grained Multicomputer algorithm for a typical problem of this class. We present here the different possible execution scenarios of this algorithm and the implementation results of the most relevant one. I