  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 $\mathcal{O}\left(n^2\right)$ 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 $\mathcal{O}\left(n^2/\sqrt{p} \right)$ execution time with
$\mathcal{O}\left( k \sqrt{p}\right)$ 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
$\times$10.39 on one hundred and twenty-eight processors with 40960 keys when
$k = 2$, the speedup factor of this solution is up to $\times$13.12 and rises
up to $\times$14.93 when $k = 5$.
