High-performance CGM-based parallel algorithms for minimum cost parenthesizing problem.

Minimum cost parenthesizing problem (MPP for short) is a well-known example of the polyadic-nonserial dynamic-programming problem. This paper presents two efficient parallel algorithms on the coarse-grained multicomputer model for solving the MPP. By allowing processors to stay active as long as possible thanks to our irregular partitioning technique of dependency graph, these algorithms minimize their idle time and promote load-balancing between them. The algorithms also reduce the latency time of processors (which is the largest part of the overall communication time) by allowing them to start evaluating subproblems as soon as the data they need are available. The first algorithm runs in O n 3 / 4 k p execution time with O 2 k p communication rounds. The second runs in O n 3 / 2 k p execution time with O 4 k p communication rounds. n is the input data size, p is the number of processors, and k is a parameter used in the partitioning technique of our algorithms. The experimental results obtained show that these new algorithms are better than the most efficient previous solutions. [ABSTRACT FROM AUTHOR]