An Efficient CGM-Based Parallel Algorithm for Solving the Optimal Binary Search Tree Problem Through One-to-All Shortest Paths in a Dynamic Graph

Abstract

Abstract The coarse-grained multicomputer parallel model (CGM for short) has been used for solving several classes of dynamic programming problems. In this paper, we propose a parallel algorithm on the CGM model, with p processors, for solving the optimal binary search tree problem (OBST problem), which is a polyadic non-serial dynamic programming problem. Firstly, we propose a dynamic graph model for solving the OBST problem and show that each instance of this problem corresponds to a one-to-all shortest path problem in this graph. Secondly, we propose a CGM parallel algorithm based on our dynamic graph to solve the OBST problem through one-to-all shortest paths in this graph. It uses our new technique of irregular partitioning of the dynamic graph to try to bring a solution to the well-known contradictory objectives of the minimization of the communication time and the load balancing of the processors in this type of graph. Our solution is based on Knuth’s sequential solution and required $${\mathcal {O}}\left( \dfrac{n^2}{p} \right)$$ On2p time steps per processor and $$\lceil \sqrt{2p} \rceil + k \times \left( {\left\lceil \dfrac{\lceil \sqrt{2p} \rceil }{2} \right\rceil } + 1 \right)$$ ⌈2p⌉+k×⌈2p⌉2+1 communication rounds. Integer k is a parameter used in the partitioning technique of our algorithm. This new CGM algorithm performs better than the previously most efficient solution, which uses regular partitioning of the tasks graph.

Keywords

• Coarse-grained multicomputer
• Optimal binary search tree
• Dynamic graph model
• Irregular partitioning