An efficient coarse-grain multicomputer algorithm for the minimum cost parenthesizing problem

作者：Tchendji Vianney Kengne; Myoupo Jean Frederic^*

来源：Journal of Supercomputing, 2012, 61(3): 463-480.

DOI：10.1007/s11227-011-0601-9

• Dynamic programming
• Parallel algorithms
• CGM
• BSP

Several problems modeled by dynamic programming have been solved using a coarse-grain multicomputer parallel model (CGM for short). These problems use either polyadic dynamic programming or monadic non-serial dynamic programming. In this paper, we address the general case: we propose a parallel algorithm in the CGM model with p processors for the Optimal String Parenthesizing Problem or Minimum Cost Parenthesizing Problem, which is a typical polyadic non-serial dynamic programming problem. The algorithm we obtain requires [(2p)(1/2)] communication rounds and, at most, O(n(3)/p) time-steps on p processors. This new CGM algorithm performs better than the previously most efficient solution, which uses p communication rounds.

• 出版日期2012-9