Papers › Four-splitting based coarse-grained multicomputer parallel algorithm for the optimal...
Four-splitting based coarse-grained multicomputer parallel algorithm for the optimal binary search tree problem
Jerry Lacmou Zeutouo, Vianney Kengne Tchendji, Jean Frederic Myoupo
The archive published only this paper's code-link row. Authors, date and abstract are from arXiv's metadata (CC0), read from the Kaggle arXiv metadata snapshot of 2026-09-12 where its title matched the archive's; the title is the archive's.
This paper presents a parallel solution based on the coarse-grained multicomputer (CGM) model using the four-splitting technique to solve the optimal binary search tree problem. The well-known sequential algorithm of Knuth solves this problem in 𝒪(n²) time and space, where n is the number of keys used to build the optimal binary search tree. To parallelize this algorithm on the CGM model, the irregular partitioning technique, consisting in subdividing the dependency graph into subgraphs (or blocks) of variable size, has been proposed to tackle the trade-off of minimizing the number of communication rounds and balancing the load of processors. This technique however induces a high latency time of processors (which accounts for most of the global communication time) because varying the blocks' sizes does not enable them to start evaluating some blocks as soon as the data they need are available. The four-splitting technique proposed in this paper solves this shortcoming by evaluating a block as a sequence of computation and communication steps of four subblocks. This CGM-based parallel solution requires 𝒪(n²/√(p) ) execution time with 𝒪( k √(p)) communication rounds, where p is the number of processors and k is the number of times the size of blocks is subdivided. An experimental study conducted to evaluate the performance of this CGM-based parallel solution showed that compared to the solution based on the irregular partitioning technique where the speedup factor is up to ×10.39 on one hundred and twenty-eight processors with 40960 keys when k = 2, the speedup factor of this solution is up to ×13.12 and rises up to ×14.93 when k = 5.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections