An Efficient CGM-Based Parallel Algorithm for Solving the Optimal Binary Search Tree Problem Through One-to-All Shortest Paths in a Dynamic Graph
Résumé
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)$$ time steps per processor and $$\lceil \sqrt{2p} \rceil + k \times \left( {\left\lceil \dfrac{\lceil \sqrt{2p} \rceil }{2} \right\rceil } + 1 \right)$$ 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.
Citer ce document
Exporter : BibTeX · RIS (Zotero, Mendeley, EndNote)
Accès au document
Texte intégral archivé sur SPHAERO, en accès ouvert : lisible gratuitement en ligne après connexion. Le document reste aussi disponible à sa source. Se connecter
Voir l'article sur le site de la revueLicence et provenance
Licence : CC BY
Notice moissonnée depuis OpenAlex le 02/09/2026. Le document reste hébergé par sa source.
Voir le document à la source →