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

Using the monotonicity property of optimal binary search trees (that we will define below), Knuth [22] derived an \({\mathcal {O}}(n^{2})\) algorithm in the same space. Yao [34] proposed an algorithm with the same complexity thanks to the quadrangle inequalities. Using the restrictive assumption of convexity, Eppstein et al. [10] obtained an algorithm which required \({\mathcal {O}}(n\log n)\) time. During the resolution of the OBST problem, the sequential nature of the evaluation (diagonal-by-diagonal processing) of the dynamic programming table prevents from its efficient parallelization in the case of the PRAM model [2]. In the case of using real target parallel machines (systolic model for example), where the communication operations are taken into account, the parallel evaluation of this table becomes more complicated, because of the strong dependence relations between the subproblems (the evaluation of an element of the level d requires the already calculated values of two elements of levels \(0, 1, \ldots , d-1\)), see [14, 18]. Although the parallelization of the classical algorithm has been widely studied by the community of researchers in parallel processing for different parallel computing models [4, 28, 29], little work is produced for the parallelization of the Knuth’s approach. It is difficult to effectively parallelize this version on an abstract model. In PRAM model, it is unknown how to use the monotonicity property to reduce the number of processors in polylogarithmic calculations time [16, 17]. The solution becomes even more difficult to design, if we want to search the OBST solutions on a bridging model as the bulk synchronous parallel model (BSP for short) [32, 33]. Precisely, the goal is to benefit from the characteristics of a large majority of current parallel machines (where local memory size \(\gg 1\)) in order to minimize the communication overhead by regrouping them in global communication rounds between pure calculation super-steps, which is the objective of the CGM model.

In this paper, our aim is to parallelize Knuth’s sequential algorithm for OBST problem on the bridging coarse grain BSP/CGM (bulk synchronous parallel model/coarse-grained multicomputer) [5‐8, 32]. CGM seems to be the best model for the design of algorithms that are not too dependent on a particular architecture. A BSP/CGM machine is a set of p processors, each having its own local memory of size s (with \({\mathcal {O}}(s)\gg {\mathcal {O}}(1)\)) and connected to each other through a router able to deliver messages in a point-to-point manner. Each BSP/CGM parallel algorithm is an alternation of local computations and global communication rounds. Each communication round consists in routing a single h-relation with \(h={\mathcal {O}}(s)\). Each CGM computation or communication round corresponds to a BSP super-step having a communication cost \(g \times s\) [4]. Here, g is the cost of a communication of a word in the BSP model. In order to produce an efficient BSP/CGM parallel algorithm, the effort of the designers must be to maximize the speed-up and minimize the number of communication rounds. (Ideally, it must be independent from the problem size and constant in the optimum.)

There are many CGM-based parallel algorithms for some dynamic programming problems, among others: The string editing problem [1], the longest common subsequence problem [2, 3, 12, 28]. The special class of problems including matrix chain ordering problem (MCOP), OBST and optimal string parenthesizing problem (OSPP) which are solved by the same dynamic programming algorithm, each with its own specification, was tackled in [15, 19, 26, 30].

In [20], the authors proposed a CGM-based parallel algorithm for MCOP that requires \({\mathcal {O}}\left( \dfrac{n^{3}}{p}\right)\) time steps and \({\mathcal {O}}(p)\) communication rounds on p processors. The one for OSPP in [30] requires \(\lceil \sqrt{2p}\rceil\) communication rounds and \({\mathcal {O}}\left( \dfrac{n^{3}}{p}\right)\) execution time on p processors. Similarly, their algorithm for OBST in [27] requires \(\lceil \sqrt{2p}\rceil\) communication rounds and \({\mathcal {O}}\left( \dfrac{n^{2}}{p}\right)\) time steps. A major drawback of these algorithms is that the loads of processors are unbalanced and they promote the idleness of processors.

Dilson and Marco [15] have proposed a CGM-based parallel algorithm for MCOP which requires \({\mathcal {O}}(1)\) communication rounds and \({\mathcal {O}}\left( \dfrac{n^3}{p^3}\right)\) time steps. Their solution is based on the graph model proposed in [4], called dynamic graph. In fact, Bradford showed that at each instance of this problem it corresponds to a one-to-all shortest path problem in this graph. Thus, their algorithm is based on the computation of shortest paths in a dynamic graph derived from the input. It would be interesting to use the properties of such type of graph for solving the OBST problem.

Tchendji and Myoupo [27, 30] have shown that for OBST problem, load balancing of the processors and minimization of the communication time are two contradictory objectives when the corresponding tasks graph is partitioned into subgraphs (or blocks) of the same size. Indeed, as each block of the graph is fully evaluated by a single processor, we have the following two scenarios:Their solution gives to the final user the choice to optimize one criterion or another according to the parameters g (granularity of their model) and p (number of processors) [31]. Their idea is based on a task graph partitioning technique and data distribution introduced in [27, 30]. In these approaches, the task graph is partitioned in the same way (in rows and columns of blocks), and data dependencies are the same. The steps of the algorithm based on user parameters are then deduced. The performances (complexity) of the algorithm are expressed from these parameters.

Our main contribution can be summarized as follows:The remainder of this paper is organized as follows: In Sect. 2, we give the definition of the OBST problem and a short review of its sequential solution. Section 3 presents our dynamic graph model for OBST problem. In Sect. 4, we present our BSP/CGM algorithm. The experimental results are analyzed in Sect. 5. Discussion about the constraints of the parallelization of the Knuth’s sequential algorithm for the OBST problem is presented in the conclusion.

A binary search tree is a binary tree that serves to efficiently look for an element among a sorted set of elements (often called keys). Value and all the keys of the left sub-tree are less than the key at the root, and all the keys of the right sub-tree are greater than the key at the root. This property is applied recursively for the left and right sub-trees of this tree. A binary search tree completely orders its keys and is used to efficiently look for a particular key among a sorted set of keys.

The search cost of a particular key in a binary search tree depends on its depth in this tree. The example of Fig. 1 shows that the search cost of the key “n” is 1 and that of the key “l” is 5. Thus, to order a set of n keys, \(\varOmega \left( \dfrac{4^{n}}{n^{\frac{3}{2}}}\right)\) different binary trees are possible [21]. For a sequence \(\{a, b,c\}\), Fig. 2 shows the different possible trees.

Therefore, given a set of keys and their access probabilities, the optimal binary search tree problem is to search the binary search tree for that set of keys which has the smallest cost. More formally, the problem can be defined as follows: consider that we have n keys \(K_1< K_2< \cdots < K_n\), which are to be placed in a binary search tree, and \(2 n + 1\) probabilities \(p_1, p_2, \ldots , p_n, q_0,\) \(q_1, q_2,\) \(\ldots , q_n\) with \(\varSigma p_i + \varSigma q_j = 1\) where \(p_i\) is the access probability of the key \(k_i\) and \(q_j\) is that of:Let’s denote T a binary search tree for this set of keys. Let \(b_i\) be the number of edges on the path from the root to the interior node \(k_i\), and \(a_j\) be the number of edges on the path from the root to the leaf (\(k_j\), \(k_{j+1}\)). Then the expected cost induced by a search in T is given by: \(cost(T) = \varSigma (p_i \times (b_{i}+1))+ \varSigma (q_j \times a_j)\), since the access cost of key \(k_i\), is \(b_i + 1\), while for the gap (\(k_j, k_{j+1}\)) it is just \(a_j\). An optimal binary search tree for this set of keys is a binary search tree whose expected search cost is smallest. From this, the optimal binary search tree problem boils down to construct an optimal binary search tree given a set of keys and their access probabilities.

Denote by OBST(i, j) an optimal binary tree corresponding to the set of keys in the interval \(int(i,j)=[K_{i+1}, \ldots , K_j]\) and denote by Tree(i, j) the cost induced by this tree. Let \(w(i,j)= p_{i+1}+ \cdots + p_j + q_{i} + q_{i+1}+\cdots +q_j\), thus \(w(0,n)=1\) and \(w(i,i)=q_i\). The search costs Tree(i, j) of OBST(i, j) obey to the following dynamic programming recurrences for \(0 \le i \le j \le n\):The corresponding sequential generic algorithm for this class of problems requires \({\mathcal {O}}(n^3)\) time and \({\mathcal {O}}(n^2)\) space [13]. The cost values Tree(i, j) are calculated according to their tabulation in an array, often called dynamic programming table or shortest path matrix denoted here by Tree(0, n). In this table, each entry (i, j) corresponds to a subproblem and contains the value Tree(i, j) at the end of the algorithm. For example, having seven keys \((n=7)\), the corresponding dynamic programming table Tree(0, 7) (where (i, j) stands for Tree(i, j)) is represented in Fig. 3.

The bottom-up approach of this algorithm evaluates the entries of this table diagonal-by-diagonal, starting from the central diagonal (Fig. 4). The general structure of this algorithm is presented by Algorithm 1.

When all entries of table Tree(0, n) are evaluated (corresponding to the first step, or step of calculation or search of the optimal solution), a recursive algorithm with a time complexity \({\mathcal {O}}(n^2)\) is executed for the construction of the tree (corresponding to the second step or step of construction of the optimal solution). This recursive algorithm uses a table denoted Cut(0, n), which is obtained from the table Tree(0, n). Each entry (i, j) of this table gives the value of k (in Eq. 1) that minimizes Tree(i, j). It is the first step that gives an optimal decomposition of the tree OBST(i, j) in two sub-trees. In this paper, we are only interested by the parallelization of the first step of the resolution of this problem, i.e., the search of the optimal cost.

Proposed by Knuth, the fastest sequential algorithm requires \({\mathcal {O}}(n^2)\) time and \({\mathcal {O}}(n^2)\) space [22]. The acceleration obtained with this algorithm comes from the property of monotonicity verified by some entries of the matrix Cut(0, n) [22].

In Sect. 2.2, we discuss how this acceleration can be used to derive an efficient BSP/CGM parallel algorithm for OBST. We present the Knuth’s sequential algorithm which is based on our CGM algorithm.

The Knuth’s acceleration results from his observation of a property of the matrix Cut(0, n) [22]. This property is defined as follows:This property transforms Algorithm 1 to the following (Algorithm 2).

We can see from the Algorithm 2 that the acceleration comes from the internal for loop which requires only \({\mathcal {O}}(n)\) comparison operations unlike \({\mathcal {O}}(n^2)\) for the classical version. For the calculation of an entry (i, j) of diagonal \((j-i+1)\), the number of comparison operations is reduced from \((j-i)\) to \((Cut(i+1,j)-Cut(i,j-1))\). The Knuth acceleration is not regular on all entries in the same diagonal. Indeed, the number of comparison operations defers from an entry to another. Thus, contrary to the classical version, if the entries of a diagonal are fairly distributed on different processors, nothing guarantees that these processors will have the same load. From this, a new constraint must be taken into account during the design of parallel algorithms based on Knuth’s algorithm: it is “the inequality of necessary calculation loads for entries of the same diagonal of the dynamic programming table”.

This property of Knuth’s algorithm induces a load unbalance that is difficult to manage, and can vanish the acceleration obtained. One possible solution to inherit this acceleration and eliminate the global unbalanced loads is to evaluate each diagonal of the task graph by a single processor. But this is contrary to the main source of the parallelism of this algorithm, as for the classic \({\mathcal {O}}(n^3)\) version: the independence of computations between the entries of the same diagonal in the dynamic programming table.

In the next Sect. 3, we propose a dynamic graph model and show that the OBST problem can be solved through a one-to-all shortest paths problem in this graph.

In this section, we present the basic concepts for the dynamic graph model proposed in this paper.

It is clear that when \(pc(a_{i+1} \bullet \cdots \bullet a_k, a_{k+1} \bullet \cdots \bullet a_j) = w(i,j)\), \(0 \le i \le k < j \le n\) and \(Init(i) = q_i\), \(i \in \{0,1, \ldots , n\}\), Eq. 2 is equivalent to Eq. 1 in Sect. 2.1. So, we can derive the next corollary.

We designate by \(K = (K_1, K_2,\ldots ,K_n)\) a sequence of n distinct keys sorted (so that \(K_1< K_2< \cdots < K_n\)). We want to build an optimal binary search tree from these keys. Some searches may concern values that do not belong to K, so we also have \(n + 1\) “dummy keys” \(d_0, d_1,\ldots , d_n\) representing values outside K. For each key \(K_i\) (respectively dummy key \(d_i\)), we have the probability \(p_i\) (respectively \(q_i\)) that a search concerns \(K_i\) (respectively \(d_i\)). Each key \(K_i\) is an internal node, and each dummy key \(d_i\) is a leaf. The formalization of the OBST problem is carried out in Sect. 2.1.

We reference each vertex of our dynamic graph \(D_n\) by the pair of integers \((i, j)/0 \le i \le j \le n\). We say that two vertices (i, j) and (k, m) are on the same row (respectively on the same column) if \(i = k\) (respectively \(j = m\)). They are on the same diagonal \((j-i+1)\) if \((j-i) = (m-k)\). \(D_n\) contains \(n + 1\) diagonals of vertices, \(n + 1\) rows of vertices and \(n + 1\) columns of vertices. The cost of the shortest path from an added virtual vertex \((-1, -1)\) to any vertex (i, j) is sp(i, j). This is shown in Fig. 5a.

We designate the unit arcs of the dynamic graph \(D_n\) by \(\rightarrow\), \(\uparrow\) or \(\nearrow\). The unit arc \((i, j) \rightarrow (i, j+1)\) represents associative product \((K_{i+1} \bullet \cdots \bullet K_j) \bullet K_{j+1}\), which is a binary sub-tree of root \(K_{j+1}\) whose left part contains the keys \(K_{i+1} \ldots K_j\) and dummy keys \(d_i \ldots d_j\) and its right part contains the dummy key \(d_{j+1}\) and weights \(q_{j+1} + w(i,j+1)\). Similarly, the unit arc \((i, j) \uparrow (i-1, j)\) represents product \(K_{i} \bullet (K_{i+1} \bullet \cdots \bullet K_j)\), corresponding to a binary sub-tree of root \(K_i\) whose left part contains the dummy key \(d_{i-1}\) and its right part contains the keys \(K_{i+1} \ldots K_{j-1}\) and dummy keys \(d_i \ldots d_j\) and weights \(q_{i-1} + w(i-1,j)\). Also, for all \(i/0 \le i \le n\), the arrows \(\nearrow\) represent units arcs from \((-1,-1)\) to (i, i) and weights \(q_i\).

To represent the split tree,¹ we add edges to \(D_n\) called jumpers. Denote a horizontal jumper by \(\Rightarrow\) and a vertical jumper by \(\Uparrow\). The vertical jumper \((i, j) \Uparrow (s, j)\) is \((i - s)\) units long and the horizontal jumper \((i, j) \Rightarrow (i, t)\) is \((t - j)\) units long, where all non-jumper edges are of length 1. The shortest path to the node (i, j) through the jumps \((i, k) \Rightarrow (i, j)\) and \((k+1, j) \Uparrow (i, j)\), represented by the product \((K_{i+1} \bullet \cdots \bullet K_k) \bullet (K_{k+1} \bullet \cdots \bullet K_j)\), defines the same binary sub-tree of root \(K_{k+1}\) whose left part contains the keys \(K_{i+1} \ldots K_k\) and dummy keys \(d_i \ldots d_k\), and its right part contains the keys \(K_{k+2} \ldots K_j\) and dummy keys \(d_{k+1} \ldots d_j\).

The dynamic graph \(D_3\), corresponding to an OBST problem for a set of \(n = 3\) keys, is represented in Fig. 5a.

Let us note the similarity between a dynamic graph \(D_n\) and a conventional dynamic programming table, Tree, for the resolution of the OBST problem. The value of sp(i, j) in the dynamic graph \(D_n\) is identical to Tree(i, j) in the dynamic programming table.

Calculating a shortest path from \((-1,-1)\) to (i, j) gives the minimum cost of finding the OBST represented by the product \(K_{i+1} \bullet K_{i} \bullet \cdots \bullet K_j\), \(0 \le i < j \le n\). So finding a shortest path from (i, j) to (0, n) gives the minimum cost of finding the OBST represented by the product \(K_1 \bullet \cdots \bullet K_{i} \bullet P \bullet K_{j+1} \bullet \cdots \bullet K_n\) where \(P = (K_{i+1} \bullet \cdots \bullet K_j)\).

The Proof of Lemma 1 leads directly to Theorem 1.

Theorem 1 is fundamental because it makes it possible to avoid calculation redundancy when looking for the value of the shortest path for the vertices of the graph \(D_n\). Indeed, for any vertex (i, j), among all its shortest paths containing jumps, only those that contain only horizontal jumps are evaluated. The input graph of our BSP/CGM algorithm is therefore a subgraph of \(D_n\) denoted by \(D'_n\), in which the set \(A'\) of the arcs consists of the set of unit arcs of \(D_n \cup \{(i, j) \Rightarrow (i, t) : 0 \le i< j < t \le n\}\). Thus, in the graph \(D'_n\), a vertex (i, j) has jumps only to the next vertices on the same line. Figure 5b shows the dynamic graph \(D'_3\).

It is easy to derive the Corollary 2.

In the next section, we use our dynamic graph \(D_n\) as task graph for construction of our CGM solution.

Formally, denote \(f(p)={\left\lceil \sqrt{2p} \right\rceil }\), \(g(n,p)={\left\lceil \dfrac{n+1}{f(p)} \right\rceil }\) and \(g(n,p,k)={\left\lceil \dfrac{g(n,p)}{2^k} \right\rceil }\), we partition the shortest path matrix into sub-matrices or blocks (Bk(i, j) for short). Bk(i, j) is a \(g(n,p,k) \times g(n,p,k)\) matrix at the \(k{\hbox {th}}\) fragmentation, i.e., at each fragmentation we divide the current size of the blocks into 4. Figure 6 shows two scenarios of this partitioning for \(n = 31\), \(k = 2\) and \(p \in \{2, 3, 4\}\). The number in each block represents the diagonal in which it belongs.

In Fig. 6a, we have two diagonals of blocks when no fragmentation is performed. Since the number of blocks of the second diagonal become equal to the half of the first, we perform the first fragmentation on the block of second diagonal (this block of \(16 \times 16\) size is divided into 4 blocks of \(8 \times 8\) size) and the number of diagonals of blocks increases to 2. We perform the second fragmentation on the block of fourth diagonal when the number of blocks of this diagonal become equal to the half of the first (this block of \(8 \times 8\) size is divided into 4 blocks of \(4 \times 4\) size) and the number of diagonals of blocks increases to 2. Finally, we obtain a task graph with six diagonals of blocks.

It is important to note the following fundamental Remarks:

This allows us to state the following Lemmas 2 and 3:

Figure 7a, b shows the dependency of \(Bk(i, j), i < j\), on the other blocks after k fragmentations.

The extremities of a block Bk(i, j) are defined as follows (see Fig. 7):The expressions of these entries are the following:The following Lemma 4 is inspired from [19]:

Due to the unbalanced load caused by the Knuth acceleration, the sizes of the rectangles ABCD and EFGH and input contents from the task graph differ from one block to another. They are different even for blocks belonging to the same diagonal. Thus, the calculation load required for the evaluation of the blocks cannot be deduced prior to the treatment. The dependent relation between blocks shows that those that are not on the same line or on the same column of blocks is independent. Consequently, they can be carried out in parallel.

In this mapping, all blocks of the main diagonal are assigned from the leftmost upper corner to the rightmost lower corner. This process is renewed until all processors have been used, starting with processor 1 and traveling through the blocks with a “snake-like” path, as shown in Fig. 8.

This mapping has several advantages:However, it has a drawback: due to the snake-like data distribution onto processors, communications are not minimized.

Our CGM algorithm evaluates the values of shortest paths to each node of a sub-matrix (or a subgraph), starting with the first diagonal of blocks to the diagonal \(f(p) + k \times ({\left\lceil f(p)/2 \right\rceil } + 1)\). But, because of the nature of the dependencies between the blocks, one cannot predict, before the beginning of the computation of the values of the entries of the block Bk(i, j), which will be the values necessary for its evaluation. In other words, the locations of the ends of the rectangles ABCD and EFGH are not known before the start of the treatments. Thus, a gradual evaluation of the blocks of a diagonal d is not possible.

The overall CGM Algorithm that is run by every processor to solve the OBST problem is as follows (Algorithm 3).

It is clear that this CGM Algorithm needs \(f(p) + k \times ({\left\lceil f(p)/2 \right\rceil } + 1)\) super-steps of computation. In each of them, the blocks of a diagonal are calculated: one block per processor. The Knuth’s sequential Algorithm is used for these local sequential calculations. Before the computation of every diagonal, entries (of Cut and Tree tables) which depend on each of its parallelograms are gathered by processors that are dedicated to this computation.

We are then ready to state Theorem 3 that gives the performances of our CGM Algorithm for OBST:

It is crucial to know the better number of fragmentations before the start of computations in order to increase as most as possible the efficiency of the Algorithm. To do this, we propose to use the cost model defined in [11] to observe the evolution of load balancing, efficiency and the number of steps of the Algorithm that will result and determine, according to the triplet (n, p, k), the better number of fragmentations to perform.