to infer the load imbalance of processors and the efficiency of the derived CGM-based parallel algorithm. Since the speedup of Knuth (1971) makes it impossible to predict the exact load of a block, they used the maximum load, i.e. the one obtained with the sequential algorithm of Godbole (1973).

From Equation (1.8) described in Section 1.8, the evaluation of each entry of each diagonal $d$ requires $3(d-1)$ arithmetic operations; since these $(d-1)$ treatments consist of two addition operations and a minimum operation (Fotso et al., 2010). Consider that the size of a block is $m \times m$, where $m = \theta(n, g) = \lceil(n+1)/g\rceil$. Blocks of the first diagonal will induce a load of

$$ \alpha = 3 \times \sum_{k=1}^{m} k(m-k) = 3 \times \frac{(m-1) \times m \times (m+1)}{6} $$

and blocks of a diagonal $d > 1$ will induce a load of

$$ 3 \times \left( \sum_{k=1}^{m} k((i-2)m+k) + \sum_{k=1}^{m-1} k(im-k) \right) = 3 \times (i-1)m^3. $$

Denoting by $\beta = 3 \times m^3$, the workload induced by the evaluation of a block of the first diagonal is $\alpha$, while those of diagonals $i$, such that $i > 1$, are $(i-1)\beta$. From these values, they estimated the load imbalance of processors and predicted the efficiency of the algorithm. Recall that the load imbalance of processors is the load difference between the processor that performs most of the work and the one that performs the least. For example, if the end-user chooses the alternative bidirectional projection mapping with $g = 8$ and $p = 4$ (illustrated in Figure 25a), then processor $P_2$ will have the smallest load $(2\alpha + 16\beta)$ and processor $P_3$ will have the largest $(2\alpha + 26\beta)$. The load imbalance in this case will equal to $10\beta$. On the other hand, if he chooses the snake-like mapping illustrated in Figure 25b, the load imbalance will equal to $6\beta$ since processor $P_0$ will have a load of $(2\alpha + 18\beta)$ and processor $P_3$ a load of $(2\alpha + 24\beta)$.

The main shortcoming of this simulator is that it can provide inaccurate load balancing metrics to the end-user. In fact, as mentioned earlier, this simulator takes into account the maximum load of blocks to estimate the load of processors. However, it is not possible to know the exact load of a block because it varies according to the input data due to the speedup of Knuth (1971). This shortcoming could mislead the end-user when running the derived CGM-based parallel algorithm on supercomputers.
<figure><img src="image_28.png" /><figcaption>Figure 26 - A convex polygon and two different triangulations</figcaption></figure>

## 2.4 - Triangulation of a convex polygon problem

### 2.4.1 - Overview

Computational geometry is the branch of computer science that studies algorithms for geometrical problems. Its application areas include computer graphics, robotics, geographic information systems, computer-aided design, molecular modeling, metallurgy, manufacturing, textile layout, forestry, statistics, and many others. A computational geometry problem usually takes as input a description of one or more geometric shapes, such as a set of line segments or points. It returns a response to a query such as the number of points of intersection, or perhaps a new geometric object (Cormen et al., 2009).

A polygon $P$ is a geometric object that has a structure bordered by connections between vertices $\langle v_0, v_1, \dots, v_n \rangle$. It is made up of $(n+1)$ side edges $v_i v_{i+1}$ such that $j = (i+1) \mod (n+1)$. Any line segment connecting two vertices $v_i$ and $v_{i+1}$ such that $j > (i+1)$ is called a *chord*. It splits the polygon into two smaller polygons. A polygon is said to be convex when any chord $v_i v_{i+1}$ passes either through the side edge or through the inside of the polygon, but never through the outside of the polygon<fnref n="4" /> (Bradford, 1994). A triangulation of a convex polygon (TCP) can be thought of as a set of chords that divide the polygon into triangles such that two chords never intersect except at a vertex. Figure 26 shows a convex polygon $P = \langle v_0, v_1, v_2, v_3, v_4 \rangle$ and two different ways to triangulate it.

In a weighted convex polygon $P$, a positive integer weight $w(v)$ is assigned to each vertex $v$. The cost of a triangle $v_i v_{i+1} v_{i+2}$ of $P$ is the product of the weights of its vertices, $w(v_i) \times w(v_{i+1}) \times w(v_{i+2})$. The cost of a TCP is the sum of the costs of its triangles. The problem is to find an optimal triangulation that minimizes

<footnote n="4">4. A chord always divides a convex polygon into two convex polygons (Bradford, 1994).</footnote>
<figure><img src="image_29.png" /><figcaption>**Figure 27** – Different ways of triangulating the convex polygon $P = \langle 5, 10, 3, 20, 6 \rangle$ and the corresponding parenthesis of the product of four matrices $M_1, M_2, M_3$, and $M_4$</figcaption></figure>

the cost of $P$. Denoting by $T[i, j]$ the optimal triangulation cost of a sub-polygon $P_{i,j} = \langle v_{i-1}, v_i, \dots, v_j \rangle$, this problem can be modeled by Equation (2.5):

$$ T[i, j] = \begin{cases} 0 & \text{if } 1 \le i = j \le n, \\ \min_{i \le k < j} \{T[i, k] + T[k+1, j] + w(v_{i-1}) \times w(v_k) \times w(v_j)\} & \text{if } 1 \le i < j \le n. \end{cases} \tag{2.5} $$

It is easy to see that this equation is equivalent to Equation (2.1) in Section 2.2.1. In fact, this problem is closely related to the MCOP (Hu and Shing, 1982, 1984; Yao, 1982). Consider $n$ matrices $M_1 \times M_2 \times \cdots \times M_i \times \cdots \times M_n$ where a matrix $M_i$ has dimensions $(d_{i-1} \times d_i)$. A $(n+1)$-sided convex polygon $P$ can be constructed with the matrices dimensions $\langle d_0, d_1, \dots, d_n \rangle$ such that a matrix $M_i$ corresponds to a side edge $d_{i-1}d_i$ and a product $M_i \times M_{i+1} \times \cdots \times M_j$ corresponds to a chord $d_id_j$. Thus, there exists a one-to-one correspondence between the different ways of parenthesizing $n$ matrices and the possible ways of triangulating a $(n+1)$-sided convex polygon (Hu and Shing, 1982, 1984). An example is illustrated in Figure 27. It is deducible that a solution to one remains relevant to the other; so the sequential algorithm of Godbole (1973) is relevant to the TCP problem. However, Yao (1982) improved the sequential algorithm of Godbole (1973) based on the *quadrangle inequality* property. It runs in $O(n^2)$ time and space.

## 2.4.2 - Sequential algorithm of Yao (1982)

### Recursive solution

Consider now that the vertices of a convex polygon $P$ are ordered. A particular ordering is chosen and remains fixed during the triangulation process when some weights are equal. A vertex at the rank $j$ is designated by $w_j$. So the convex polygon $P = \langle 5, 10, 3, 20, 6 \rangle$ of Figure 27 can be represented by $\langle w_2, w_4, w_1, w_5, w_3 \rangle$. A sub-polygon $P_{i,j}$ of $P$ consists of those vertices lying between $w_i$ and $w_j$ in a clock-
<caption>**Algorithm 13** Recursif algorithm of Yao (1982) to solve the TCP problem</caption>

1: **function** PARTITION(*P*)
2:     **if** |*P*| ≤ 2 **then**
3:         **return** ∅;
4:     **else if** *P* is a triangle **then**
5:         **return** *P*;
6:     **else if** *w*₁ and *w*₂ are not adjacent **then**
7:         **return** PARTITION(*P*₁,₂) ∪ PARTITION(*P*₂,₁);
8:     **else if** *w*₁ and *w*₃ are not adjacent **then**
9:         **return** PARTITION(*P*₁,₃) ∪ PARTITION(*P*₃,₁);
10:    **else**
11:     **return** better of {PARTITION (*P*₂,₃) ∪ PARTITION (*P*₃,₂), PARTITION (*P*₁,₄) ∪ PARTITION (*P*₄,₁)};

wise traversal. For example in Figure 27, $P_{2,1} = \langle w_2, w_4, w_1 \rangle$, $P_{4,3} = \langle w_4, w_1, w_5, w_3 \rangle$, and $P_{3,4} = \langle w_3, w_2, w_4 \rangle$. The term *partition* will also be used to refer to a triangulation.

Starting from a quadrilateral, Yao (1982) brought out some properties that led to Lemma 5 and set up Algorithm 13 to find an optimal triangulation from this lemma.

**Lemma 5** *Given a convex polygon* *P*, *there exists an optimal partition for which the following is true :*

1. $w_1$ and $w_2$ are adjacent either by a side edge or by a chord, similarly for $w_1$ and $w_3$;

2. if both $w_1w_2$ and $w_1w_3$ are side edges, then either $w_1w_4$ or $w_2w_3$ exists as a chord.

As the last clause "else" (line 10 in Algorithm 13) could generate two problems of size $n-c$ for a small constant $c$ in the worst case, this algorithm requires an exponential time. Yao (1982) reduces this complexity to $O(n^2)$ time and space by proposing a dynamic-programming solution divided into two steps :

1. identify and organize the $O(n^2)$ distinct sub-polygons (subproblems) into a multi-level DAG;

2. solve these subproblems in a bottom-up manner as organized in step 1.
<figure><img src="image_30.png" /><figcaption>Figure 28 - A convex polygon P and the corresponding DAG</figcaption></figure>

Dynamic-programming solution

In step 1, the constructed DAG is a forest consisting of two binary trees in which roots are designated by nodes w<sub>1</sub>w<sub>2</sub> and w<sub>2</sub>w<sub>1</sub>. Each binary tree corresponds to sub-polygons P<sub>1,2</sub> and P<sub>2,1</sub> such that P = P<sub>1,2</sub> ∪ P<sub>2,1</sub>. This DAG is structured as follows:

1 - a nonleaf node w<sub>i</sub>w<sub>j</sub> is a chord of P such that all vertices w<sub>k</sub> in P<sub>i,j</sub> fulfill
k ≥ max{i, j};

2 - any nonleaf node w<sub>i</sub>w<sub>j</sub> has exactly two child nodes, namely w<sub>i</sub>w<sub>k</sub> and w<sub>k</sub>w<sub>j</sub>
where k is the smallest index (aside from i and j) in P<sub>i,j</sub>;

3 - the leaves are the side edges of P;

4 - an order relation $\prec$ is defined on the set of nodes such that w<sub>i</sub>w<sub>j</sub> $\prec$ w<sub>i</sub>w<sub>j</sub>
implies P<sub>i',j'</sub> ⊆ P<sub>i,j</sub>.

By scanning the weights of P in a clockwise direction, Yao (1982) identifies and
generates the nodes of the DAG in a slightly modified postorder traversal. Figure
28 gives an example of a convex polygon P and the corresponding DAG. Nodes in
this graph are generated in the following order: w<sub>1</sub>w<sub>5</sub>, w<sub>5</sub>w<sub>4</sub>, w<sub>1</sub>w<sub>4</sub>, w<sub>4</sub>w<sub>2</sub>, w<sub>3</sub>w<sub>10</sub>,
w<sub>10</sub>w<sub>8</sub>, w<sub>3</sub>w<sub>8</sub>, w<sub>8</sub>w<sub>6</sub>, w<sub>6</sub>w<sub>11</sub>, w<sub>11</sub>w<sub>7</sub>, w<sub>6</sub>w<sub>7</sub>, w<sub>7</sub>w<sub>1</sub>, w<sub>2</sub>w<sub>9</sub>, w<sub>9</sub>w<sub>3</sub>, w<sub>3</sub>w<sub>6</sub>, w<sub>6</sub>w<sub>1</sub>, w<sub>2</sub>w<sub>3</sub>,
w<sub>3</sub>w<sub>1</sub>, w<sub>1</sub>w<sub>2</sub>, w<sub>2</sub>w<sub>1</sub>.

A sub-polygon Q of P is called a *cone*, if $Q = P_{i,j} \cup w_i w_j w_k$ where $b = w_i w_j$
is a chord or a side edge of P, and $k \le \min\{i, j\}$. A *cone* Q is also designated by
$(b, w_k)$. The existing partial orders on the nodes of the DAG and on the weights of
P induce a natural alphabetic order on cones. In fact, a cone $Q' = (b', w_{k'})$ precedes
a cone $Q = (b, w_k)$ if either $b' \prec b$, or $b' = b$, and $k' \ge k$ (Yao, 1982).
**Algorithm 14** Dynamic-programming algorithm of Yao (1982) to solve the TCP problem

1: **for each** $b = w_i w_j \in B$ **do** ▷ B is the ordered set of nodes and consider that $i < j$
2: &nbsp;&nbsp;&nbsp;&nbsp;**if** b is a leaf **then**
3: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**for all** cones $Q = (b, w_k)$ such that $k \le i$ **do**
4: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**if** $w_k = w_i$ **then**
5: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Partition $[Q] \leftarrow \emptyset$; ▷ $Q = w_i w_j$
6: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**else**
7: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Partition $[Q] \leftarrow Q$; ▷ $Q = w_i w_j w_k$
8: &nbsp;&nbsp;&nbsp;&nbsp;**if** b is not a leaf **then**
9: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**for all** cones $Q = (b, w_k)$ such that $k \le i$ **do**
10: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**if** $w_k = w_i$ **then**
11: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Partition $[Q] \leftarrow$ Partition $[(leftChild(b), w_i)] \cup$ Partition $[(rightChild(b), w_i)]$;
12: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**else**
13: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Partition $[Q] \leftarrow$ better of 
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;\{Partition $[(b, w_i)] \cup w_i w_j w_k$, 
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Partition $[(leftChild(b), w_k)] \cup$ 
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Partition $[(rightChild(b), w_k)]$\};
14: **return** Partition $[P_{1,2}] \cup$ Partition $[P_{2,1}]$;

**Lemma 6** For a cone $Q = (b, w_k)$, any sub-polygon that may arise in the execution of Partition[$Q$] is either a triangle, or a cone $Q'$ which precedes $Q$.

Thus, step 2 of the dynamic-programming algorithm of Yao (1982) consists of computing and tabulating the solutions to all cones in accordance with their precedence order. Indeed, evaluating a node $b = w_i w_j$ of the DAG consists in computing all the cones $Q = (b, w_k)$ such that $k \le i < j$. Algorithm 14 draws the big picture. Partition[$Q$] refers to the DP table containing the optimal solution to cone $Q$. The outer for loop (line 1 in Algorithm 14) iterates over all $b$ in the order they are generated in step 1. The inner for loops (lines 3 and 9 in Algorithm 14) iterate over all $w_k$ with $k \le i$ in decreasing order. As there are at most $2n$ nodes in the DAG, and at most $n$ cones to evaluate for a given node, this algorithm runs in $O(n^2)$ time and space.

**Enhancement of Myoupo and Kengne (2014a) : additional preprocessing routine**

When evaluating a node $w_i w_j$ in Algorithm 14, the vertices of the polygon to be considered are all $w_k$ such that $k \le i$. This evaluation is made in decreasing order of these weights. Yao (1982) does not explain how to effectively identify these vertices, nor how to obtain them in decreasing order. Thus, the most natural way to look for these vertices $w_k$ is to scan the entire set of vertices located between $w_i$ and $w_j$ and compare their weights to $w_i$. However, some of them may have
weights greater than $w_i$. For example in Figure 28, to evaluate the node $w_3w_6$, the set of candidate vertices $\langle w_{11}, w_7, w_1, w_5, w_4, w_2, w_9, w_3 \rangle$ must be entirely scanned in order to select only three: $w_3$, $w_2$, and $w_1$. This leads to a huge waste of time because in this case five of the eight candidate vertices are not useful.

To solve this problem, Myoupo and Kengne (2014a) proposed an additional preprocessing routine to the sequential algorithm of Yao (1982). It consists in sorting the weights of the polygon vertices, through the quicksort algorithm, before evaluating the DAG nodes. Thus, the evaluation of the node $w_iw_j$ starts from the vertex $w_i$ since it is the vertex with the highest weight. It continues in decreasing order in the sorted weight set of the polygon vertices until the vertex with the lowest weight. In this way, Myoupo and Kengne (2014a) identify more easily the set of vertices whose weights are less than or equal to $w_i$. Experimental results showed that their proposal had a significant improvement over the sequential algorithm of Yao (1982) in terms of execution time. However, it did not change the time complexity.

### Parallelization constraint of the sequential algorithm of Yao (1982)

In contrast to the sequential algorithm of Godbole (1973) where the dependency graph is the same whatever the dimensions of matrices to be parenthesized, the DAG corresponding to the sequential algorithm of Yao (1982) is different for two products of matrices of the same length whose dimensions are not the same. Since this DAG is not known beforehand, a classical design of a CGM-based parallel solution based on the sequential algorithm of Yao (1982), like the sequential algorithm of Godbole (1973) for the MPP or the OBST problem, is not possible (Kechid and Myoupo, 2008b; Myoupo and Kengne, 2014a). Thus, Kechid and Myoupo (2008b) automated the dependency graph partitioning and the distribution scheme for each instance of dimensions of matrices.

### 2.4.3 - CGM-based parallel solution of Kechid and Myoupo (2008b)

Kechid and Myoupo (2008b) focused on parallelizing step 2 of the $O(n^2)$-time dynamic-programming solution of Yao (1982). They did not find it relevant to parallelize step 1 running in $O(n)$ time since in practice $n^2/p \gg n$. Algorithm 15 gives an overview of the CGM-based parallel solution of Kechid and Myoupo (2008b) (it is the same as the one of Myoupo and Kengne (2014a) described in Section 2.4.4). This solution is broken down into three steps:
**Algorithm 15** CGM-based parallel solution of Kechid and Myoupo (2008b) to solve the TCP problem

1: **Construction** of the DAG;

2: **Partitioning** of the DAG into subgraphs and **mapping** onto processors;

3: **Evaluation** of the subgraphs using Algorithm 14;

1. First, each processor performs step 1 of the sequential algorithm of Yao (1982), i.e. the generation of nodes of the DAG.

2. Then, each processor runs an algorithm called *dynamic design algorithm*. This algorithm consists of dividing the DAG into subgraphs called *bands*, then subdividing each band into sub-bands called *blocks*, and finally distributing each block onto processors. It ensures that blocks of the same band are independent of each other so that they can be processed in parallel, and that they have the same size to facilitate load balancing during the mapping.

3. Finally, processors evaluate the blocks assigned to them in parallel through a succession of computation and communication rounds.

**Dependency graph partitioning**

Kechid and Myoupo (2008b) partition the DAG into *S* bands from the global load of the DAG obtained by adding up the smallest indexes of the DAG nodes. They denote by $B_i$ the ith band, $i \in \{1, 2, ..., S\}$, and by $T_{cb}$ the maximum load of a band. Each band $B_i$ is then divided into $NB_i$ blocks. Algorithm 16 shows an overview of the dependency graph partitioning algorithm of Kechid and Myoupo (2008b). It determines the best value of the triplet $(S, T_{cb}, NB_i)$ that minimizes the overall computational load per processor expressed by Equation (2.6):

$$ cost = \sum_{i=1}^{S} (NB_i / p) \times T_{cb} \qquad (2.6) $$

To produce the partitioning corresponding to a given $T_{cb}$, Algorithm 16 traverses in a bottom-up fashion the original DAG (produced by step 1 of the sequential solution of Yao (1982)) from leaves to build bands one-by-one by making successive calls to a *band-building* function (line 11 in Algorithm 16), which takes as input the current DAG and $T_{cb}$, builds a band and returns the number of blocks of this band. On the first call to this function, the current DAG corresponds to the original DAG. Then, before each call of this function, the band built at the previous call
**Algorithm 16 Dependency graph partitioning algorithm of Kechid and Myoupo (2008b)**

1: $T_c \leftarrow 0$;
2: **for each** $w_i w_j \in B$ **do** ▷ $B$ is the ordered set of nodes
3: &nbsp;&nbsp;&nbsp;&nbsp;$T_c \leftarrow T_c + \min\{i, j\}$;
4: &nbsp;&nbsp;&nbsp;&nbsp;$min\_cost \leftarrow +\infty$;
5: **for** $\alpha = 2$ **to** $p$ **do**
6: &nbsp;&nbsp;&nbsp;&nbsp;$T_{cb} \leftarrow T_c / \alpha p$;
7: &nbsp;&nbsp;&nbsp;&nbsp;$S \leftarrow 0$;
8: &nbsp;&nbsp;&nbsp;&nbsp;$i \leftarrow 1$;
9: &nbsp;&nbsp;&nbsp;&nbsp;$B' \leftarrow B$;
10: **while** $B' \neq \emptyset$ **do**
11: &nbsp;&nbsp;&nbsp;&nbsp;$NB_i \leftarrow$ building the band $B_i$ from $B'$ and $T_{cb}$;
12: &nbsp;&nbsp;&nbsp;&nbsp;$S \leftarrow S + 1$;
13: &nbsp;&nbsp;&nbsp;&nbsp;$B' \leftarrow B' \setminus \{B_i\}$;
14: &nbsp;&nbsp;&nbsp;&nbsp;$i \leftarrow i + 1$;
15: &nbsp;&nbsp;&nbsp;&nbsp;$current\_cost \leftarrow$ cost of the current partitioning computed by Equation (2.6);
16: **if** $current\_cost < min\_cost$ **then**
17: &nbsp;&nbsp;&nbsp;&nbsp;$min\_cost \leftarrow current\_cost$;
18: &nbsp;&nbsp;&nbsp;&nbsp;$T_{cb_{optimal}} \leftarrow T_{cb}$;
19: **return** the partitioning corresponding to $T_{cb_{optimal}}$;

is truncated from the current DAG (line 13 in Algorithm 16). When the current DAG becomes empty, the partitioning is completed. Kechid and Myoupo (2008b) repeat this process ($p-1$) times to find the best value of the triplet ($S, T_{cb}, NB_i$) that minimizes the cost given by Equation (2.6).

**Lemma 7** *The dependency graph partitioning algorithm of Kechid and Myoupo (2008b) requires $O(n \times p)$ execution time.*

*Proof.* Nodes in the DAG are traversed ($p-1$) times to seek the partitioning that minimizes the cost in Equation (2.6). ■

**Blocks' dependency analysis**

Since the evaluation of a DAG node $(i, j)$ depends only on the already computed values of its two child nodes $(i, k)$ and $(k, j)$, the values communicated by processors are those of the root nodes of blocks they hold; and these nodes are not plentiful. Moreover, this information is used only by processors holding the father nodes of the root nodes of blocks. In other words, the values of the root nodes of blocks in the band $B_i$ are therefore only communicated to processors that own blocks in the band $B_{i+1}$.
<figure><img src="image_31.png" /><figcaption>**Figure 29** – Distribution scheme of blocks on three processors proposed by Kechid and Myoupo (2008b)</figcaption></figure>

With such dependencies, the communication time will be very low. Contrary to all the CGM-based parallel solutions presented so far, in this one, the local computation time is the main part of the total execution time.

## Mapping blocks onto processors

Once the DAG is divided into bands and blocks, Kechid and Myoupo (2008b) distribute the blocks to processors while ensuring good load balancing. The $NB_i$ blocks in the band $B_i$ are assigned to processors as follows:

* When $NB_i \ge p$, each processor evaluates $\lfloor NB_i/p \rfloor$ blocks. This mapping ensures that for each band $B_i$, blocks assigned to a processor are contiguous to minimize the amount of data to be communicated.

* When $NB_i < p$, $(NB_i - p)$ processors will be idle in the computation round $i$. To manage this idleness, Kechid and Myoupo (2008b) uses the snake-like mapping (described in Section 2.2.5, page 60).

Figure 29 depicts an example of this mapping on three processors. Nodes colored in black are those of the first band, those colored in gray are those of the second band, and uncolored nodes are those of the other bands.
**Theorem 7** In the worst case, the complexity of the CGM-based parallel solution of Kechid and Myoupo (2008b) to solve the TCP problem, given in terms of the BSP cost model, is expressed by:

$$S \times L + S \times g \times O(n^2/p) + O(n \times p) + \sum_{i=1}^{S} (NB_i/p) \times T_{cb_{optimal}}$$

### 2.4.4 - CGM-based parallel solution of Myoupo and Kengne (2014a)

Since the dynamic design algorithm (line 2 in Algorithm 15) is executed sequentially on each processor, it must be carried out with minimum time. However, the solution proposed by Kechid and Myoupo (2008b), running in $O(n \times p)$ time to parallelize the $O(n^2)$-time sequential algorithm of Yao (1982), will be time intensive when the number of processors increases (although $n \gg p$). This is not interesting because this algorithm must be scalable to the increase of the number of processors.

Myoupo and Kengne (2014a) improve this solution by making the dynamic design algorithm less dependent on the number of processors. The strength of their solution comes from the fact that processors will handle more than half of the problem without communicating. Indeed, the DAG has at most $2n$ nodes among which $(n+1)$ leaves. Since these leaves are all independent, they can be evaluated in parallel. Moreover, more than half of the computational load is induced by these leaves because the evaluation of each internal node requires less computation than that of a given leaf since the computational load induced by an internal node is smaller than that of each of its two children, and there are more leaves than internal nodes. Thus, if the first band $B_1$ contains all leaves of the DAG, then it will induce a computational load greater than half the global load of the DAG. If $NB_1 \ge p$, then each processor will evaluate at least one block of the first band. Myoupo and Kengne (2014a) propose two algorithms for dependency graph partitioning: one focused on load balancing and the other focused on minimizing the number of communication rounds. They also improved the distribution scheme proposed by Kechid and Myoupo (2008b). Their mapping ensures that processors communicate blocks after computing to start the evaluation of some blocks as soon as possible.

#### Dependency graph partitioning balancing the load of processors

To balance the load between processors, the size of blocks must be small. So if some processors have one more block than others, as blocks have a relatively small load, the load difference will be reasonable. The downside of this approach is
<caption>**Algorithm 17** Dependency graph partitioning algorithm of Myoupo and Kengne (2014a) balancing the load of processors</caption>

1: $T_{max} \leftarrow 0$;
2: **for each** $w_i w_k$ and $w_k w_j \in B$ **do** ▷ $B$ is the ordered set of nodes
3: &nbsp;&nbsp;&nbsp;&nbsp;**if** $w_i w_k$ is a leaf **then**
4: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$T_{max} \leftarrow T_{max} + \min\{i, k\}$;
5: &nbsp;&nbsp;&nbsp;&nbsp;**if** $w_k w_j$ is a leaf **then**
6: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$T_{max} \leftarrow T_{max} + \min\{k, j\}$;
7: &nbsp;&nbsp;&nbsp;&nbsp;**if** $w_i w_k$ and $w_k w_j$ are leaves **then**
8: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$T_{max} \leftarrow T_{max} + \min\{i, j\}$;
9: $T_{cb} \leftarrow T_{max}/p$;
10: $S \leftarrow 0$;
11: $i \leftarrow 1$;
12: $B' \leftarrow B$;
13: **while** $B' \neq \emptyset$ **do**
14: &nbsp;&nbsp;&nbsp;&nbsp;building the band $B_i$ from $B'$ and $T_{cb}$;
15: &nbsp;&nbsp;&nbsp;&nbsp;$S \leftarrow S + 1$;
16: &nbsp;&nbsp;&nbsp;&nbsp;$B' \leftarrow B' \setminus \{B_i\}$;
17: &nbsp;&nbsp;&nbsp;&nbsp;$i \leftarrow i + 1$;
18: **return** the partitioned DAG;

the growth of the number of blocks, which induce more communication between processors and thus increase the global communication time.

The principle of this strategy is the following: if $(i, k)$ and $(k, j)$ are two leaves of the DAG, then their father $(i, j)$ can be part of the first band. Indeed, all internal nodes whose two children are leaves are all independent, and thus can be evaluated in parallel. Denoting by $T_{max}$ the sum of loads of these internal nodes and that of all the leaves, Myoupo and Kengne (2014a) show that the best load of blocks of the first band is $T_{max}/p$. By keeping this load for blocks of next bands, they limit to two the number of blocks to be mapped onto a processor. Thus, a processor evaluates either two blocks on the first band $B_1$ (if $NB_1 > p$) and no blocks on the other bands, or one block on $B_1$ and possibly one block on all bands $\{2, \dots, S\}$. Algorithm 17 draws the big picture.

**Lemma 8** *The dependency graph partitioning algorithm of Myoupo and Kengne (2014a) balancing the load of processors runs in $O(n)$ execution time.*

**Proof.** This algorithm requires just two traverses of the DAG nodes: one to compute $T_{max}$ and another to construct the $S$ bands. ■
Dependency graph partitioning minimizing the number of
communication rounds

The blocks should be as large as possible to minimize the number of communication rounds. In this way, the number of blocks is minimized and the processors exchange little information. The drawback of this approach is the possibility of a serious load imbalance between processors if they do not have the same number of blocks.

The principle of this strategy is to find the load of the largest first band that
contains at least *p* blocks by changing the load of blocks. Formally, Myoupo and
Kengne (2014a) assume that the number of blocks of the first band is greater than
or equal to *p* when *T*<sub>cb</sub> = *T*<sub>c</sub>/2*p* to vary *T*<sub>cb</sub> in the search interval [*T*<sub>c</sub>/2*p*, ..., *T*<sub>c</sub>/p]. If
*T*<sub>c</sub>/p produces less than *p* blocks in the first band, they consider the median value
1/2 (*T*<sub>c</sub>/p + *T*<sub>c</sub>/2*p*) = 3*T*<sub>c</sub>/4*p*. They use each time using the median value between the largest
known good value of *T*<sub>cb</sub> (lower bound of the interval) and the smallest known bad
value (upper bound of the interval) to optimize the result. The process stops when
the search interval reaches the threshold *T*<sub>c</sub>/*p*<sup>*k*+1</sup>, where *k* is a positive integer;
and the lower bound of the search interval is chosen. Thus, Myoupo and Kengne
(2014a) obtain the load of the largest first band corresponding to the chosen thresh-
old. Denoting by *T*<sub>int</sub> the load of this band, the bands of the DAG are partitioned
into blocks with a load of *T*<sub>int</sub>/p. Algorithm 18 gives an overview of this strategy.

**Lemma 9** *The dependency graph partitioning algorithm of Myoupo and Kengne (2014a) that minimizes the number of communication rounds requires O*(n log p)* execution time.

*Proof*. The initial distance between the bounds of the interval in which the best value of $T_{cb}$ is found is $T_c/p - T_c/(2p) = T_c/p$. This distance is divided by two until it reaches the threshold $T_c/p^{k+1}$. Thus, the number of divisions of this interval is the largest value of $m$, such that $T_c/(2^m p) \ge T_c/p^{k+1}$, i.e. $p^k \ge 2^m$ where $k \times \ln p \ge m \ln 2$ and thus $m \le k \times \ln p / \ln 2$.

For each value of $T_{cb}$, all nodes of the DAG are traversed to compute the corre-
sponding value of $NB_1$. Thus, $O(n \log p)$ execution time are required to determine
the final value of $T_{cb}$. After the construction of the first band, a single traversal of
the rest of the graph is performed for the construction of the other bands. $\blacksquare$

Mapping blocks onto processors

Myoupo and Kengne (2014a) are based on the distribution scheme proposed by
Kechid and Myoupo (2008b). They are interested on the consecutive assignment
<caption>**Algorithm 18** Dependency graph partitioning algorithm of Myoupo and Kengne (2014a)
minimizing the number of communication rounds</caption>

1: $T_c \leftarrow 0$;
2: **for each** $w_i w_j \in B$ **do** ▷ B is the ordered set of nodes
3: &nbsp;&nbsp;&nbsp;&nbsp;$T_c \leftarrow T_c + \min\{i, j\}$;
4: &nbsp;&nbsp;&nbsp;&nbsp;$\sup \leftarrow T_c/p$;
5: &nbsp;&nbsp;&nbsp;&nbsp;$\inf \leftarrow T_c/2p$;
6: &nbsp;&nbsp;&nbsp;&nbsp;$\text{gap} \leftarrow [\sup - \inf]$;
7: &nbsp;&nbsp;&nbsp;&nbsp;$T_{cb} \leftarrow \sup$;
8: **while** $\text{gap} \ge T_c/p^2$ **do**
9: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$NB_1 \leftarrow 0$;
10: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$B' \leftarrow B$;
11: &nbsp;&nbsp;&nbsp;&nbsp;**while** no end band **do**
12: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$\text{current_block} \leftarrow$ building a block from $B'$ and $T_{cb}$;
13: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$NB_1 \leftarrow NB_1 + 1$;
14: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$B' \leftarrow B' \setminus \{\text{current_block}\}$;
15: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**if** $NB_1 \ge p$ **then**
16: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$\inf \leftarrow T_{cb}$;
17: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**else**
18: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$\sup \leftarrow T_{cb}$;
19: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$\text{gap} \leftarrow [\sup - \inf]$;
20: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$T_{cb} \leftarrow [(\sup + \inf)/2]$;
21: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$B' \leftarrow B \setminus \{B_1\}$;
22: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$T_{cb} \leftarrow \inf$;
23: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$S \leftarrow 1$;
24: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$i \leftarrow 2$;
25: **while** $B' \ne 0$ **do**
26: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$\text{building the band } B_i$ from $B'$ and $T_{cb}$;
27: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$S \leftarrow S + 1$;
28: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$B' \leftarrow B' \setminus \{B_i\}$;
29: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$i \leftarrow i + 1$;
30: **return** the partitioned DAG;

of blocks of a band $B_i$ to a processor, which minimizes the amount of data to be
communicated during communication rounds. Indeed, this strategy does not allow
processors that hold the blocks of the band $B_{i+1}$ to start the evaluation of their
blocks as soon as possible. To solve this problem, Myoupo and Kengne (2014a)
first assigns the first $p$ blocks of the band $B_1$ to $p$ processors, then they assign
the rest of the $(NB_1 - p)$ blocks to processors $P_0, \dots, P_{(NB_1-p)}$. Blocks of the band
$B_2$ are assigned to processors starting with processor $P_{(NB_1-p+1)}$. This process is
applied until the last band $S$.
<figure><img src="image_32.png" /><figcaption>**Figure 30** – Distribution scheme of blocks on four processors proposed by Myoupo and Kengne (2014a)</figcaption></figure>

So, after the evaluation of the first *p* blocks of the band *B*₁, the values of the root nodes are communicated to processors owning blocks of the band *B*₂, which can immediately start the evaluation of their blocks. At the same time, the (*NB*₁ − *p*) processors with an additional block on band *B*₁ can evaluate their second block. Figure 30 illustrates an example of this mapping on four processors.

**Theorem 8** In the worst case, to solve the TCP problem, the CGM-based parallel solution of Myoupo and Kengne (2014a) runs in O(n² × S/p) execution time with S communication rounds, such that 2 ≤ S < p.

**2.4.5 - Drawbacks of sequential and CGM-based parallel solutions**

The trade-off of minimizing the number of communication rounds and balancing the load of processors still arises despite the CGM-based parallel solutions of Kechid and Myoupo (2008b) and Myoupo and Kengne (2014a). Moreover, for this problem, the computation time represents the largest part of the execution time. Despite the improved sequential algorithm of Myoupo and Kengne (2014a), an important observation was not made on how to evaluate the nodes of the DAG.
<figure><img src="image_33.png" /><figcaption>**Figure 31** – Evaluation of the nonleaf node $a = w_3w_6$ and dependencies between its cones $(a, w_3)$, $(a, w_2)$, and $(a, w_1)$ to be computed</figcaption></figure>

In fact, neither Yao (1982), nor Kechid and Myoupo (2008b), nor Myoupo and Kengne (2014a) were interested in the dependencies between cones. They focused only on dependencies between nodes. Their solutions have the same drawback. It is about the unnecessary computation of some cones when evaluating a given node in the DAG. Figure 31 illustrates dependencies between cones of the nonleaf node $a = w_3w_6$ (see Figure 28) with its two sons $b = w_3w_8$ and $c = w_8w_6$. Let assume that all cones of nodes $b$ and $c$ are already computed. It is easy to see that the cones $(c, w_6)$, $(c, w_5)$, and $(c, w_4)$ (which are in the boxes in Figure 31) will not be useful for the evaluation of the node $a$. Indeed, according to the definition of a given node $w_iw_j$ with its children $w_iw_k$ and $w_kw_j$ such that $i < j < k$, there will always be $(j-i)$ computed cones that will not be necessary for the evaluation of the node $w_iw_j$ and therefore, disregarding this fact can lead to a significant waste of time. The solution proposed in this thesis consists in organizing the evaluation of cones following their dependencies to avoid these unnecessary computations. Section 2.4.6 describes it more precisely.

## 2.4.6 - Our fast sequential algorithm

Consider a node $b = w_iw_j$ such that $i < j$. All the descendants $a = w_i'w_{j'}$ of the node $b$ must compute a cone $Q = (a, w_i)$. It is easy to see from the dynamic-programming equation (lines 10-13 in Algorithm 14) that each descendant $a$ must first process the cone $Q' = (a, w_{i'})$ to compute $Q$. Consider that $B$ is the ordered set of nodes in the DAG. By going from $B$ in a top-down manner, i.e. from the last node $w_2w_1$ to the first, a stack $\delta_b = \{w_k\}_{k \le i}$ can be built for each node $b$. A new DAG, in which each node $b$ is associated to its stack $\delta_b$, is obtained. Thus, his evaluation will consist in computing all cones $Q = (b, w_k)$ such that $k \le i$ and $w_k \in \delta_b$. The first cone $Q = (b, w_k)$ to process is needed to compute the other cones $Q' = (b, w_{k'})$ such that $k' < k$. Depending on the nature of $b$, its stack $\delta_b$ will be constructed as follows:
<caption>**Algorithm 19 Building the stack of every node in the DAG**</caption>

1: $B' \leftarrow$ the reversed $B$ set; ▷ $B$ is the ordered set of nodes in the DAG
2: push $(\delta_{w_2w_1}, w_1)$;
3: push $(\delta_{w_1w_2}, w_1)$;
4: **for each** $b = w_iw_j \in B'$ **do** ▷ consider that $i < j$
5: &nbsp;&nbsp;&nbsp;&nbsp;**if** $b$ is not a leaf **then**
6: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$\delta_{leftChild(b)} \leftarrow \delta_b$;
7: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**if** leftChild($b$) is not a leaf **and** top $(\delta_{leftChild(b)} \neq w_i)$ **then**
8: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;push $(\delta_{leftChild(b)}, w_i)$;
9: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$\delta_{rightChild(b)} \leftarrow \delta_b$;
10: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**if** rightChild($b$) is not a leaf **and** top $(\delta_{rightChild(b)} \neq w_i)$ **then**
11: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;push $(\delta_{rightChild(b)}, w_i)$;

<figure><img src="image_34.png" /><figcaption>**Figure 32** – A convex polygon *P* and the new DAG obtained after building the stack of every node. Elements of the stack are colored red. The leftmost vertex corresponds to the top of the stack</figcaption></figure>

1. if $b$ is a leaf or not, then assign $\delta_{b'}$ to $\delta_b$, where $b'$ is the father of $b$;

2. if $b$ is not a leaf, then push the vertex $w_i$ onto $\delta_b$ if top $(\delta_b) \neq w_i$. Recall that the function top returns the top of the stack.

Algorithm 19 gives an overview. In the beginning, the vertex $w_1$ is pushed in the stacks of the last two nodes $w_1w_2$ and $w_2w_1$ since they are the root nodes of the DAG. Next, for each node $b$, $\delta_b$ is built according to its nature. This algorithm requires $O(n)$ execution time. Consider again the convex polygon *P* presented in Figure 28. Figure 32 shows the new DAG obtained after applying Algorithm 19. The overall number of operations to be performed, obtained by adding up the smallest indexes of the DAG nodes, is 62. However, when the stack size of every node in the DAG is added up, it is halved.

Our dynamic-programming solution is then divided into three steps :
<caption>**Algorithm 20** Our dynamic-programming algorithm to solve the TCP problem</caption>

1: **for each** $b = w_i w_j \in B$ **do** ▷ B is the ordered set of nodes and consider that $i < j$
2:     **while** $\delta_b$ is not empty **do**
3:         $w_k \leftarrow \text{pop}(\delta_b)$;
4:         **if** $b$ is a leaf **then**
5:             **if** $w_k = w_i$ **then**
6:                 Partition $[Q] \leftarrow \emptyset$; ▷ $Q = w_i w_j$
7:             **else**
8:                 Partition $[Q] \leftarrow Q$; ▷ $Q = w_i w_j w_k$
9:             **if** $b$ is not a leaf **then**
10:         **if** $w_k = w_i$ **then**
11:             Partition $[Q] \leftarrow \text{Partition}[(\text{leftChild}(b), w_i)] \cup \text{Partition}[(\text{rightChild}(b), w_i)]$;
12:         **else**
13:             Partition $[Q] \leftarrow \text{better of } \{\text{Partition}[(b, w_i)] \cup w_i w_j w_k, \text{Partition}[(\text{leftChild}(b), w_k)] \cup \text{Partition}[(\text{rightChild}(b), w_k)]\}$;
14:         **return** Partition $[P_{1,2}] \cup \text{Partition}[P_{2,1}]$;

1. identify and organize the 2n cones into a multi-level DAG;

2. build the stack $\delta_b$ for each cone $b$ using Algorithm 19;

3. evaluate these cones in a bottom-up manner as organized in step 1. This step is done by Algorithm 20.

**Lemma 10** *Our dynamic-programming solution requires $O(n)$ execution time in some cases.*

*Proof.* In this solution, the DAG changes according to the input data and not as a consequence of the problem size. It makes it difficult to predict exactly how many operations are to be performed on each node. However, in some cases, each node will only have to compute a constant number $c \ll 2n$ of cones. For example in Figure 33a, each node will only have to execute one cone in the best case. ■

**Theorem 9** *In the worst case, our dynamic-programming solution requires $O(n^2)$ execution time to solve the TCP problem.*

*Proof.* As there are at most $2n$ nodes in the DAG, it is deducible from Figure 33b that there are at most $(n-2)$ cones to compute for a given node in the worst case. ■
<figure><img src="image_35.png" /><figcaption>**Figure 33** – DAG in the best and the worst cases of a convex polygon P</figcaption></figure>

### 2.4.7 - Experimental results

#### Experimental setups

This section compares the proposed sequential solution with the previous best sequential and CGM-based parallel solutions. This experimentation has been performed on the Dolphin cluster of the MatriCS platform of the University of Picardie Jules Verne<fnref n="5" /> using 48 nodes called thin nodes with 48 × 128GB of RAM, and 12 named thick nodes with 12 × 512GB of RAM. Each node is made of two Intel Xeon Processor E5-2680 V4 (35M Cache, 2.40 GHz), and each of them consists of 14 cores. All nodes are interconnected with OmniPath links providing 100Gbps throughput. These algorithms have been implemented in the C programming language<fnref n="6" />, and on the operating system CentOS Linux release 7.6.1810. The MPI library (OpenMPI version 1.10.4) has been used for inter-processor communication. These algorithms have been executed on five thin nodes.

**Note 1** *This experimental environment will also be used for the CGM-based parallel solutions described in Chapter 3.*

Five random data sets have been generated and tests have been carried out on each of them. The average of these results is presented according to different values of the pair $(n, p)$. $n$ is the data size, with values in the set $\langle 512, 1024, 2048, 4096, 8192, 12288, 16384, 20480, 24576, 28672, 32768, 36864, 40960, 45056, 49152, 53248, 57344, 61440, 65536 \rangle$, and $p$ is the number of processors, with values in the set $\langle 1, 8, 16, 32 \rangle$. The proposed dynamic-programming solution is compared with the classical sequential algorithm of Yao (1982) and the improved sequential

<footnote n="5">5. https://www.u-picardie.fr/matrics</footnote>

<footnote n="6">6. The source codes are available on this URL: https://github.com/compiii/Fast-Seq-Alg-for-MCOP.</footnote>
algorithm by Myoupo and Kengne (2014a). This solution is also compared with
the CGM-based parallel solution of Kechid and Myoupo (2008b) and Myoupo and
Kengne (2014a). Table 2 gives an overview of the total execution time of these
algorithms. For the CGM-based parallel solutions, it is the sum of the partitioning
time, the computation time and the communication time. The CGM-based par-
allel solution proposed by Kechid and Myoupo (2008b) is named *Tcb*. Those of
Myoupo and Kengne (2014a) are named *Tinit sort* and *Tmax sort*. The first one
focuses on minimizing the number of communication rounds, and the second one
on load balancing (Myoupo and Kengne, 2014a). Figures 34a, 34b, 34c, 34d, and
35 are drawn from results obtained in Table 2.

Evolution of the total execution time

Figure 34a shows that the sequential solution of Myoupo and Kengne (2014a) sig-
nificantly improves the total execution time compared to the sequential algorithm
of Yao (1982). When *n* = 65536, the execution time has been reduced down to
79.55%. Nevertheless, by avoiding unnecessary computations, our solution re-
duced down to 94.72% the execution time and is ×18.93 faster than the previous
one. It is due to the drastic increase in the number of unnecessary computations
when the data size increases. Figures 34b, 34c, and 34d show that the growth in
number of processors does not outperform our solution. The execution time of *Tcb*
decreases as the number of processors increases. One of the main causes is the use
of the sequential algorithm of Yao (1982) in the local computation phases. Another
reason is the high partitioning time. Indeed, each processor executes a partitioning
algorithm requiring *O*(*n* × *p*) time. Although *Tinit sort* and *Tmax sort* reduce the
complexity of this partitioning algorithm, it uses the sequential solution of Myoupo
and Kengne (2014a) during the local computation phases.

Comparison of our solution and the best CGM-based parallel solution

In Figure 35, we compare our solution with *Tinit sort*, which is the best CGM-based
parallel solution, on large data sizes. Our solution narrows down the total execution
time to 80.31% and is ×5.07 faster than *Tinit sort* on thirty-two processors when
*n* = 65536. It is easy to see the impact that the partitioning time has on the total
execution time. When *n* = 65536, it is part of 52.67% on eight processors, 61.79%
on sixteen processors, and 68.76% on thirty-two processors. Whatever the data
size, it does not reduce as the number of processors increases. It is because this
partitioning algorithm is not parallel. The ideal partitioning algorithm should be
parallel with a complexity in *O*(*n*/*p*) execution time and *O*(1) communication
round. Algorithms proposed to date scan the 2*n* nodes of the DAG to estimate the
<table><caption>**Table 2** – Total execution time (in seconds) of sequential and CGM-based parallel solutions while solving the TCP problem</caption><thead><tr><th rowspan="3">n</th><th colspan="3">Sequential solutions</th><th colspan="6">CGM-based parallel solutions</th></tr><tr><th rowspan="2">Our sol.</th><th rowspan="2">Yao</th><th rowspan="2">Yao sort</th><th colspan="3">Tinit sort</th><th colspan="3">Tmax sort</th><th colspan="2">Tcb</th></tr><tr><th>p = 8</th><th>p = 16</th><th>p = 32</th><th>p = 8</th><th>p = 16</th><th>p = 32</th><th>p = 8</th><th>p = 16</th><th>p = 32</th></tr></thead><tbody><tr><td>512</td><td>0.001</td><td>0.01</td><td>0.001</td><td>0.001</td><td>0.004</td><td>0.008</td><td>0.009</td><td>0.02</td><td>0.02</td><td>0.006</td><td>0.03</td><td>0.06</td></tr><tr><td>1024</td><td>0.001</td><td>0.02</td><td>0.001</td><td>0.003</td><td>0.005</td><td>0.01</td><td>0.02</td><td>0.02</td><td>0.05</td><td>0.01</td><td>0.05</td><td>0.22</td></tr><tr><td>2048</td><td>0.01</td><td>0.11</td><td>0.02</td><td>0.01</td><td>0.01</td><td>0.03</td><td>0.01</td><td>0.01</td><td>0.01</td><td>0.06</td><td>0.18</td><td>0.72</td></tr><tr><td>4096</td><td>0.03</td><td>0.42</td><td>0.09</td><td>0.03</td><td>0.03</td><td>0.03</td><td>0.04</td><td>0.03</td><td>0.05</td><td>0.22</td><td>0.64</td><td>2.55</td></tr><tr><td>8192</td><td>0.07</td><td>1.68</td><td>0.37</td><td>0.12</td><td>0.12</td><td>0.15</td><td>0.16</td><td>0.14</td><td>0.14</td><td>0.86</td><td>2.25</td><td>9.02</td></tr><tr><td>12288</td><td>0.12</td><td>3.79</td><td>0.81</td><td>0.27</td><td>0.25</td><td>0.23</td><td>0.34</td><td>0.27</td><td>0.23</td><td>1.97</td><td>4.75</td><td>18.44</td></tr><tr><td>16384</td><td>0.18</td><td>6.68</td><td>1.41</td><td>0.47</td><td>0.42</td><td>0.39</td><td>0.60</td><td>0.47</td><td>0.42</td><td>3.66</td><td>7.99</td><td>28.85</td></tr><tr><td>20480</td><td>0.24</td><td>10.46</td><td>2.17</td><td>0.73</td><td>0.63</td><td>0.63</td><td>0.92</td><td>0.72</td><td>0.63</td><td>5.67</td><td>12.04</td><td>42.40</td></tr><tr><td>24576</td><td>0.32</td><td>15.07</td><td>3.13</td><td>1.03</td><td>0.89</td><td>0.85</td><td>1.31</td><td>1.01</td><td>0.87</td><td>8.08</td><td>16.76</td><td>57.81</td></tr><tr><td>28672</td><td>0.38</td><td>20.54</td><td>4.25</td><td>1.39</td><td>1.19</td><td>1.12</td><td>1.76</td><td>1.35</td><td>1.17</td><td>10.83</td><td>22.52</td><td>76.29</td></tr><tr><td>32768</td><td>0.45</td><td>26.67</td><td>5.52</td><td>1.81</td><td>1.58</td><td>1.43</td><td>2.29</td><td>1.75</td><td>1.51</td><td>14.05</td><td>29.22</td><td>98.24</td></tr><tr><td>36864</td><td>0.54</td><td>33.84</td><td>6.96</td><td>2.29</td><td>1.96</td><td>1.82</td><td>2.90</td><td>2.22</td><td>1.90</td><td>18.16</td><td>37.54</td><td>121.43</td></tr><tr><td>40960</td><td>0.62</td><td>41.90</td><td>8.60</td><td>2.83</td><td>2.41</td><td>2.20</td><td>3.59</td><td>2.75</td><td>2.34</td><td>22.64</td><td>46.13</td><td>148.44</td></tr><tr><td>45056</td><td>0.70</td><td>50.77</td><td>10.40</td><td>3.44</td><td>2.94</td><td>2.68</td><td>4.33</td><td>3.36</td><td>2.86</td><td>26.81</td><td>57.05</td><td>179.97</td></tr><tr><td>49152</td><td>0.80</td><td>60.54</td><td>12.39</td><td>4.13</td><td>3.53</td><td>3.26</td><td>5.21</td><td>3.98</td><td>3.42</td><td>34.26</td><td>70.90</td><td>221.40</td></tr><tr><td>53248</td><td>0.89</td><td>71.15</td><td>14.50</td><td>4.92</td><td>4.19</td><td>3.75</td><td>6.16</td><td>4.76</td><td>4.04</td><td>40.51</td><td>86.87</td><td>270</td></tr><tr><td>57344</td><td>0.98</td><td>82.62</td><td>16.82</td><td>5.73</td><td>4.91</td><td>4.43</td><td>7.18</td><td>5.56</td><td>4.76</td><td>49.32</td><td>108.69</td><td>336.44</td></tr><tr><td>61440</td><td>1.07</td><td>94.93</td><td>19.29</td><td>6.66</td><td>5.67</td><td>5.13</td><td>8.33</td><td>6.45</td><td>5.56</td><td>58.48</td><td>128.26</td><td>442.31</td></tr><tr><td>65536</td><td>1.16</td><td>107.40</td><td>21.96</td><td>7.74</td><td>6.49</td><td>5.89</td><td>9.55</td><td>7.34</td><td>6.31</td><td>63.90</td><td>157.93</td><td>494.87</td></tr></tbody></table>
<figure><img src="image_36.png" /><figcaption>(a) Our solution versus the sequential solutions</figcaption></figure>

<figure><img src="image_37.png" /><figcaption>(b) Our solution versus the CGM-based parallel solutions on eight processors</figcaption></figure>

<figure><img src="image_38.png" /><figcaption>(c) Our solution versus the CGM-based parallel solutions on sixteen processors</figcaption></figure>

<figure><img src="image_39.png" /><figcaption>(d) Our solution versus the CGM-based parallel solutions on thirty-two processors</figcaption></figure>

<caption>**Figure 34** – Comparison of the total execution time between our solution versus the sequential solution of Yao (1982) and CGM-based parallel solutions of Kechid and Myoupo (2008b) and Myoupo and Kengne (2014a) while solving the TCP problem</caption>

overall computational load to distribute tasks equitably onto processors. However, in many cases our solution requires *O*(n) time. Thus, to parallelize our solution, the partitioning techniques of this DAG must be totally overhauled.

## 2.5 - Summary

In this chapter, we presented the work done on parallelization of sequential algorithms that solve the MPP, the MCOP, the TCP problem, and the OBST problem. On the CGM model, the proposed parallel solutions led to a trade-off between minimizing the number of communication rounds and balancing the load of processors. In (Kechid and Myoupo, 2008a, 2008b, 2009), the strategy consists in subdividing the DAG into small-size blocks to promote the load balancing. In (Kengne and Myoupo, 2012; Myoupo and Kengne, 2014a, 2014b), the strategy consists in subdividing the DAG into large-size blocks to minimize the number of communication rounds. Kengne et al. (2016) proposed a CGM-based parallel solution that gives the
<figure><img src="image_40.png" /><figcaption>**Figure 35** – Comparison of our solution and the best CGM-based parallel solution while solving the TCP problem</figcaption></figure>

end-user the choice to optimize one criterion according to their own goal. However, the common problem related to these criteria, regardless of the end-user's choice, is the high global communication time that is caused by the high latency time of processors.

For the MCOP and the TCP problem, we proposed a fast sequential algorithm which, while not solving this trade-off, is faster than previous sequential and CGM-based parallel algorithms (Kechid and Myoupo, 2008b; Myoupo and Kengne, 2014a; Yao, 1982). We noticed that these solutions did not take into account the dependencies of cones during their evaluations. They evaluated cones according to their order of precedence. We have constructed for each node of the DAG a stack of cones on which it depends, through an algorithm that requires $O(n)$ execution time in the worst case, and we have evaluated each node from this stack. Experimental results performed on the MatriCS platform showed that our sequential algorithm is ×18.93 faster than the sequential algorithm of Yao (1982) and ×5.07 faster than the CGM-based parallel solution of Myoupo and Kengne (2014a) on thirty-two processors. Chapter 3 will outline CGM-based parallel solutions that reconcile these conflicting objectives to solve the MPP and the OBST problem.
CHAPTER 3

# Reconciliation of the Minimization of the Number of Communication Rounds and the Load-Balancing of Processors

## CONTENTS

<table><tr><td>3.1 - Introduction</td><td>98</td></tr><tr><td>3.2 - Dynamic graph model of the OBST problem</td><td>99</td></tr><tr><td>3.3 - First dynamic graph partitioning : irregular partitioning technique</td><td>103</td></tr><tr><td>3.4 - Second dynamic graph partitioning : k-block splitting technique</td><td>121</td></tr><tr><td>3.5 - Third dynamic graph partitioning : four-splitting technique</td><td>133</td></tr><tr><td>3.6 - Summary</td><td>149</td></tr></table>

## 3.1 - Introduction

This chapter begins by designing, in Section 3.2, a dynamic graph model to solve the OBST problem and showing that each instance of this problem corresponds to a one-to-all shortest path problem in this dynamic graph (like in (Bradford, 1994) to solve the MPP). Thereafter, it describes our CGM-based parallel solutions that address the trade-off of minimizing the number of communication rounds and balancing the load of processors. In computation rounds, the sequential algorithm of Godbole (1973) is used to solve the MPP and the sequential algorithm of Knuth (1971) is used to solve the OBST problem. These solutions are respectively based on three dynamic graph partitioning techniques presented in Sections 3.3, 3.4, and 3.5 : the irregular partitioning technique, the *k*-block splitting technique, and the four-splitting technique. In these sections, experimental results are presented to show the performance of each technique.
## 3.2 - Dynamic graph model of the OBST problem

Denote by $K = \langle k_1, k_2, \dots, k_n \rangle$ a set of $n$ sorted keys, such that $k_1 < k_2 < \dots < k_n$. Some searches may concern values that do not belong to $K$; so consider a set of $(n+1)$ dummy keys $D = \langle d_0, d_1, \dots, d_n \rangle$ representing values outside $K$. For each key $k_i$ (respectively dummy key $d_i$), $p_i$ (respectively $q_i$) is the probability that a search concerns $k_i$ (respectively $d_i$). The goal is to build an optimal binary search tree from these keys. Each key $k_i$ is an internal node and each dummy key $d_i$ is a leaf. The DP formalization of the OBST problem has been carried out in Section 2.3.1. Let us define the dynamic graph $D_n$ of the OBST problem by a set of vertices $(i, j)$ and a set of edges, such that $0 \le i \le j \le n$.

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$ consists of $(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 stored in $SP[i, j]$, where $SP$ is a shortest path matrix of size $(n + 1)$.

The unit edges are denoted by $\rightarrow$, $\uparrow$, and $\nwarrow$. The unit edge $(i, j) \rightarrow (i, j+1)$ has a weight equal to $q_{j+1} + w(i, j+1)$ and represents the associative product $(k_{i+1} \bullet \dots \bullet k_j) \cdot k_{j+1}$. It is a binary subtree of root $k_{j+1}$ whose the left part contains the set of keys $K_{i,j} = \langle k_{i+1}, k_{i+2}, \dots, k_j \rangle$ and the set of dummy keys $D_{i,j} = \langle d_i, d_{i+1}, \dots, d_j \rangle$, and the right part contains the dummy key $d_{j+1}$. Similarly, the unit edge $(i, j) \uparrow (i-1, j)$ has a weight equal to $q_{i-1} + w(i-1, j)$ and represents the product $k_i \bullet (k_{i+1} \bullet \dots \bullet k_j)$, corresponding to a binary subtree of root $k_i$ whose the left part contains the dummy key $d_{i-1}$, and the right part contains the set of keys $K_{i,j-1} = \langle k_{i+1}, k_{i+2}, \dots, k_{j-1} \rangle$ and the set of dummy keys $D_{i,j} = \langle d_i, d_{i+1}, \dots, d_j \rangle$. For all $i$ such that $0 \le i \le n$, the arrows $\nwarrow$ represent unit edges from $(-1, -1)$ to $(i, i)$ and their weights are equal to $q_i$.

To represent the split tree, that is, a tree splits into two subtrees, $D_n$ is made up of edges called *jumps*. Denote a horizontal jump by $\Rightarrow$, and a vertical jump by $\Uparrow$. The vertical jump $(i, j) \Uparrow (s, j)$ is $(i-s)$ units long and the horizontal jump $(i, j) \Rightarrow (i,t)$ is $(t-j)$ units long. All non-jump edges are unit edges of length 1. The shortest path to the node $(i, j)$ through the jumps $(i, a) \Rightarrow (i, j)$ and $(a+1, j) \Uparrow (i, j)$, represented by the product $(k_{i+1} \bullet \dots \bullet k_a) \bullet (k_{a+1} \bullet \dots \bullet k_j)$, define the same binary subtree of root $k_{a+1}$. The left part of this subtree contains the set of keys $K_{i,a} = \langle k_{i+1}, k_{i+2}, \dots, k_a \rangle$ and the set of dummy keys $D_{i,a} = \langle d_i, d_{i+1}, \dots, d_a \rangle$, and the right part contains the set of keys $K_{a+1,j} = \langle k_{a+2}, k_{a+3}, \dots, k_j \rangle$ and the set of
<figure><img src="image_41.png" /><figcaption>Figure 36 – Dynamic graphs $D_3$ and $D'_3$ for a problem of size $n = 3$</figcaption></figure>

dummy keys $D_{a+1,j} = \langle d_{a+1}, d_{a+2}, \dots, d_j \rangle$. Definition 5 gives the formal definition of $D_n$ and Figure 36a depicts $D_3$, which refers to a problem of size $n = 3$.

**Definition 5** Given a set of $n$ sorted keys, a dynamic graph $D_n = (V, E \cup E')$ is defined as a set of vertices,

$$V = \{(i, j) : 0 \le i \le j \le n\} \cup \{(-1, -1)\}$$

a set of unit edges,

$$E = \{(i, j) \to (i, j+1) : 0 \le i \le j < n\} \cup \{(i, j) \uparrow (i-1, j) : 0 < i \le j \le n\} \cup \{(-1, -1) \uparrow (i, i) : 0 \le i \le n\}$$

a set of jumps,

$$E' = \{(i, j) \Rightarrow (i, t) : 0 \le i < j < t \le n\} \cup \{(s, t) \uparrow (i, t) : 0 \le i < s < t \le n\}$$

a weight function $W$ such that

$$W((i, j) \to (i, j+1)) = q_{j+1} + w(i, j+1) \quad 0 \le i \le j < n$$

$$W((i, j) \uparrow (i-1, j)) = q_{i-1} + w(i-1, j) \quad 0 < i \le j \le n$$

$$W((-1, -1) \uparrow (i, i)) = q_i \quad 0 \le i \le n$$

$$W((i, k) \Rightarrow (i, j)) = SP[k+1, j] + w(i, j) \quad 0 \le i < k < j \le n$$

$$W((k+1, j) \uparrow (i, j)) = SP[i, k] + w(i, j) \quad 0 \le i \le k < j \le n$$

There exists a similarity between the shortest path matrix $SP$ and the DP table *Tree* (see Equation (2.4)) because the value of $SP[i, j]$ in the dynamic graph $D_n$ is
**Theorem 11** Each instance of an OBST problem of size *n* corresponds to a dynamic graph *D*<sub>*n*</sub>, where SP[i, j] is equal to Tree[i, j]. As a result, the shortest path from the virtual vertex (−1, −1) to the vertex (0, *n*) in *D*<sub>*n*</sub> solves Tree[0, *n*].

**Proof.** To prove this theorem, it is sufficient to show that the cost of every path from (−1, −1) to (0, *n*) in *D*<sub>*n*</sub> corresponds to the cost of construction of an OBST of *n* elements associative product. In addition, for every tree of *n* elements associative product, there is a corresponding path in *D*<sub>*n*</sub> where both the path and the associative product have the same cost.

We only show that for each path from (-1, -1) to (0, n) in Dn, there is a corresponding associative product of n elements (or n - 1 operators "•-s"). This proof is by induction on lengths of associative products. Consider D4 and the product k₁ • k₂ • k₃ • k₄. In D₄, the jump (0,2) ⇒ (0,4) has weight SP[3,4] + w(0,4). Therefore, the cost of a path using this jump corresponds to the cost of the associative product (k₁ • k₂) • (k₃ • k₄). A symmetric argument holds for the jump (3,4) ⇑ (0,4). Hence for each associative product there is a path, and for each path there is an associative product.

Now suppose that the theorem holds for all $n \le k$, where $k \ge 4$ and $n$ is the number of associative operators in a given associative product. Thus, the inductive hypothesis is for any path in $D_n$ from $(-1, -1)$ to $(0, n)$, where $n \le k$, there is a corresponding associative product of $n$ elements with the same cost. Without loss of generality, consider horizontal jumps. For $m = 2k$, let's take a path in $D_m$ from $(-1, -1)$ to $(0, m)$. In the following, it will show that for all $m \le 2k$, there is a corresponding $m$ elements associative product of the same cost (this proof holds for both even and odd length products because $D_{k-1}$ is a proper subgraph of $D_k$).

The structure of $D_m$ along with the inductive hypothesis gives:

1. The cost of a path from $(-1, -1)$ to any node $(i, j)$, such that $j - i \le k$, corresponds to the cost of a binary search tree of $k_{i+1} \bullet \cdots \bullet k_j$ by the inductive hypothesis. Since the product $k_{i+1} \bullet \cdots \bullet k_j$ contains at most $k-1$ associative operators ("•-s").

2. The cost of a path from $(i,t)$ to $(1,2k) = (0,m)$, $(1,2k) = (0,m)$, such that $k \le t - i < m$, corresponds to the cost of a binary search tree of $k_1 \bullet \cdots \bullet k_i \bullet P \bullet k_{i+1} \bullet \cdots \bullet k_m$, where $P = (k_{i+1} \bullet \cdots \bullet k_t)$, by the inductive hypothesis. Since $P$ consists of at least $k$ elements, the product $k_1 \bullet \cdots \bullet k_i \bullet P \bullet k_{i+1} \bullet \cdots \bullet k_m$ consists of at most $(k-1)$ associative operators ("•-s").

Suppose that path from $(-1, -1)$ to $(1, 2k)$ includes the jump $(i, j) \Rightarrow (i, t)$. Then assume that $j - i < k \le t - i$ (otherwise by the inductive hypothesis and the two facts
above, the proof is complete). Therefore, consider the jump $(i, j) \Rightarrow (i, t)$, where $j-i < k \le t-i$. By the inductive hypothesis and the fact 2, the cost of a path from $(i,t)$ to $(0,m)$ corresponds to the cost of a binary search tree of $k_1 \bullet \cdots \bullet k_i \bullet P \bullet k_{i+1} \bullet \cdots \bullet k_m$, where $P = (k_{i+1} \bullet \cdots \bullet k_t)$. Again by the inductive hypothesis and the fact 1 above, the cost of a path to $(i,j)$ corresponds to the cost of a binary search tree of $k_{i+1} \bullet \cdots \bullet k_j$, where $k_i \bullet \cdots \bullet k_j$ is a subproduct of $P$. Furthermore, the jump $(i,j) \Rightarrow (i,t)$ is a part of a path from $(-1, -1)$ to $(0,m)$ whose cost corresponds to the cost of the product $(k_{i+1} \bullet \cdots \bullet k_j) \bullet (k_{j+1} \bullet \cdots \bullet k_t)$. This is because its cost is $SP[j+1,t] + w(i,t)$ and because $t - (j+i) < j-i$, the inductive hypothesis can be applied. Vertical jumps follow similarly. ■

**Corollary 1** Any solution of a one-to-all shortest path problem can be used on our dynamic graph $D'_n$ to solve the OBST problem.

Figure 37 shows the dynamic graph $D'_3$ that was filled from a set of three sorted keys with probabilities given in Table 1. The weights of edges were computed using the shortest path matrix $SP$ (which is similar to the DP table *Tree*) and starting with the first diagonal containing the vertices $(0,0)$, $(1,1)$, $(2,2)$, and $(3,3)$, then the second diagonal containing the vertices $(0,1)$, $(1,2)$, and $(2,3)$, then the third diagonal containing the vertices $(0,2)$ and $(1,3)$, and finally the last diagonal containing the vertex $(0,3)$. The shortest path from $(-1, -1)$ to $(0,3)$ is colored in red in Figure 37. It is equal to $0.03 + 0.4 + 1.37 = 1.8$ (note that it is the same value as *Tree* [0,3] in Figure 23a). The optimal binary search tree corresponding to this path is also depicted. Now let's outline our first dynamic graph partitioning.

## 3.3 - First dynamic graph partitioning : irregular partitioning technique

The irregular partitioning technique consists in subdividing the shortest path matrix into submatrices (blocks) of varying size (irregular size) to allow a maximum of processors to remain active longer. The idea is to increase the number of blocks of diagonals whose this number is lower or equal to half of the first one through the block fragmentation technique. This technique aims to reduce the block size by dividing it into four subblocks. Figure 38 shows the subblock sizes obtained by fragmenting a block of arbitrary size $\alpha \times \beta$.

To minimize the number of communication rounds, it begins to subdivide the shortest path matrix with large-size blocks from the largest diagonal (the first diag-
<figure><img src="image_42.png" /><figcaption>**Figure 37** – Dynamic graph $D_3$ filled while determining the optimal binary search tree from probabilities of three sorted keys given in Table 1</figcaption></figure>

<figure><img src="image_43.png" /><figcaption>**Figure 38** – Fragmentation of a block of size $\alpha \times \beta$</figcaption></figure>

onal of blocks) to the diagonal located just before the one whose number of blocks is half of the first one. Then, since the number of blocks per diagonal quickly becomes smaller than the number of processors, to increase the number of blocks of these diagonals and allow a maximum of processors to remain active, it fragments all the blocks belonging to the next diagonal until the last one to catch up or exceed by one notch the number of blocks of the first diagonal. It reduces the idle time
of processors and promotes the load balancing. This process is repeated *k* time, after which the block sizes are no longer modify, and the rest of the partitioning becomes traditional because an excessive fragmentation would lead to a drastic rise of the number of communication rounds. After performing *k* fragmentations, a block belonging to the *l*th level of fragmentation have been subdivided *l* times, $0 \le l \le k$.

In the following, let us consider that the shortest path matrix is of size *n* for both the MPP and the OBST problem. Formally, denoting by $f(p) = \lceil \sqrt{2p} \rceil$, $\theta(n, p) = \lceil \frac{n}{f(p)} \rceil$, and $\theta(n, p, l) = \lceil \frac{\theta(n, p)}{2^l} \rceil$, we subdivide the shortest path matrix *SP* into blocks denoted by *SM*(*i*, *j*). *SM*(*i*, *j*) is a matrix of size $\theta(n, p, l) \times \theta(n, p, l)$ belonging to the *l*th level of fragmentation. Equation (3.1) shows entries of *SP* delimiting a block *SM*(*i*, *j*), such that $1 \le i \le j \le n$:

$$ SM(i, j) = \begin{pmatrix} SP[i, j - \theta(n, p, l) + 1] & \cdots & SP[i, j] \\ \vdots & \ddots & \vdots \\ SP[i + \theta(n, p, l) - 1, j - \theta(n, p, l) + 1] & \cdots & SP[i + \theta(n, p, l) - 1, j] \end{pmatrix} \quad (3.1) $$

Figures 39a, 39b, 39c, and 39d illustrate four scenarios of this partitioning for $n = 32$, $k \in \{1, 2\}$, and $p \in \{3, 4, 5, 6, 7, 8\}$. The number in each block represents the diagonal in which it belongs. In Figure 39d, there are four diagonals of blocks when no fragmentation is performed (like in Figure 18c). Since the number of blocks of the third diagonal is equal to the half of the first, the first fragmentation is performed on the block of this diagonal (the blocks of size $8 \times 8$ is divided in four blocks of size $4 \times 4$) and the number of diagonals of blocks increases up to three (see Figure 39c). Then, since the number of blocks of the sixth diagonal is equal to the half of the first, the second fragmentation is performed on the blocks of this diagonal (the blocks of size $4 \times 4$ is divided in four blocks of size $2 \times 2$) and the number of diagonals of blocks increases up to three. Finally, the shortest path matrix contains ten diagonals of blocks.

**Remark 1** Some relevant points can be noticed about this partitioning :

1. the blocks of the first diagonal are upper triangular matrices of $\theta(n, p)$ rows and $\theta(n, p)$ columns;

2. all the blocks are usually not full when $n \bmod (2^k \times f(p)) \neq 0$; for example in Figure 39b where $32 \bmod (2^2 \times 3) = 8 \neq 0$;

3. a block belonging to the *l*th level of fragmentation is full if it is a non-triangular matrix of size $\theta(n, p, l) \times \theta(n, p, l)$;
<figure><img src="image_44.png" /><figcaption>**Figure 39** – Irregular partitioning technique of the shortest path matrix for $n = 32$, $k \in \{1, 2\}$, and $p \in \{3, 4, 5, 6, 7, 8\}$. For $p \in \{3, 4\}$, SP is partitioned into fifteen blocks when $k = 1$ and into twenty-four blocks when $k = 2$. For $p \in \{5, 6, 7, 8\}$, SP is partitioned into nineteen blocks when $k = 1$ and into twenty-eight blocks when $k = 2$.</figcaption></figure>

4. one fragmentation increases up to ($\lceil f(p)/2 \rceil + 1$) the number of diagonals (see proof of Lemma 13);

5. when $f(p)$ is odd, the number of blocks in a diagonal after each fragmentation exceeds by one notch the number of blocks of the first diagonal. This is illustrated in Figure 39a, where there are three blocks in the first diagonal and four blocks in third diagonal.
**Lemma 12** The number of blocks of the shortest path matrix after partitioning is a function of k (the number of fragmentations) and is equal to:

$$C = \frac{S(S+1)}{2} + \frac{k}{2} \left[ (S+1)(S+2\Delta) - \left\lfloor \frac{S}{2} \right\rfloor \left( \left\lfloor \frac{S}{2} \right\rfloor - 1 \right) \right]$$

with $S = f(p)$ and $\Delta = (S \bmod 2)$.

**Proof.** After partitioning, there is exactly $S(S+1)/2 - \lfloor S/2 \rfloor (\lfloor S/2 \rfloor + 1)/2$ larger-size blocks. Depending on the parity of $S$, two scenarios can arise:

1. When $S$ is even, there is $(k-1) \times (S(S+1)/2 - \lfloor S/2 \rfloor (\lfloor S/2 \rfloor - 1)/2)$ blocks in diagonals from the first to the $(k-1)$th fragmentation (for example the second, the third, and the fourth diagonal on Figure 39b). This number increases up to $(S(S+1)/2 + \lfloor S/2 \rfloor)$ blocks after the $k$th fragmentation.

2. When $S$ is odd, the principle is the same as in the previous scenario, except that here the fragmentation increases up to $(S+1)$ additional blocks on the initial block numbers (see point 5 of Remark 1).

Denote by $\Delta = (S \bmod 2)$ the variable, which determines the parity of $S$. Thus, we have:

$$\begin{aligned} C &= (k-1) \times \left( \frac{S(S+1) - \left\lfloor \frac{S}{2} \right\rfloor \left( \left\lfloor \frac{S}{2} \right\rfloor - 1 \right)}{2} + \Delta(S+1) \right) + \left\lfloor \frac{S}{2} \right\rfloor + \frac{S(S+1)}{2} \\ &\quad + \Delta(S+1) + \frac{S(S+1) - \left\lfloor \frac{S}{2} \right\rfloor \left( \left\lfloor \frac{S}{2} \right\rfloor + 1 \right)}{2} \\ &= (k-1) \times \frac{(S+1)(S+2\Delta) - \left\lfloor \frac{S}{2} \right\rfloor \left( \left\lfloor \frac{S}{2} \right\rfloor - 1 \right)}{2} + (S+1)(S+\Delta) + \left\lfloor \frac{S}{2} \right\rfloor \frac{1 - \left\lfloor \frac{S}{2} \right\rfloor}{2} \\ &= \frac{S(S+1)}{2} + \frac{k}{2} \left[ (S+1)(S+2\Delta) - \left\lfloor \frac{S}{2} \right\rfloor \left( \left\lfloor \frac{S}{2} \right\rfloor - 1 \right) \right] \end{aligned}$$

<figure><img src="image_45.png" /></figure>

**Lemma 13** Our irregular partitioning technique of the dynamic graph induces $f(p) + k \times (\lfloor f(p)/2 \rfloor + 1)$ diagonal of blocks when the blocks undergo $k$ successive fragmentations.

**Proof.** If no fragmentation is performed (if $k=0$), then there are $f(p)$ diagonals. Suppose there are $k$ fragmentations. One fragmentation increases up to $(\lfloor f(p)/2 \rfloor + 1)$ the number of diagonals. Indeed, a fragmentation is performed
when the number of blocks of a diagonal is equal to ⌈f(p)/2⌋. This fragmentation, which decreases the size of blocks by 1/4, creates a diagonal of ⌈f(p)/2⌋ blocks; then the following diagonals contain successively 2 × ⌈f(p)/2⌋ blocks, (2 × ⌈f(p)/2⌋ − 1) blocks, ..., ( ⌈f(p)/2⌋ + 1) blocks. This is equal to ( ⌈f(p)/2⌋ + 1) diagonals (for example the second, the third, and the fourth diagonal on Figure 39b). At the next diagonal, another fragmentation is done. We conclude from all this that after k fragmentations, we have f(p) + k × ( ⌈f(p)/2⌋ + 1) diagonals. ■

### 3.3.1 - Blocks' dependency analysis

#### Blocks' dependency of the MPP

Dependencies between blocks is given by Theorem 12, which is derived from Lemmas 1 and 2. It shows that blocks on the same diagonal are independent.

**Theorem 12 (Blocks' dependency)** To evaluate the shortest paths of nodes of the block SM(i, j) belonging to the lth level of fragmentation, the shortest path values to every node in blocks SM(i, j − θ(n, p, l)), SM(i, j − 2 × θ(n, p, l)),...,SM(i, j − (u − 1) × θ(n, p, l)), and SM(i + θ(n, p, l), j), SM(i + 2 × θ(n, p, l), j),...,SM(i + (u − 1) × θ(n, p, l), j) are required, where $u = ⌈(j − i)/θ(n, p, l)⌋$.

Figure 40 illustrates an example of dependencies of two blocks SM(i, j) and SM(h, l) with other blocks (the most shaded blocks). Evaluating the shortest paths of nodes of blocks belonging to the same diagonal can be carried out in parallel.

#### Blocks' dependency of the OBST problem

Figures 41a and 41b respectively show an example of dependencies and extremities of a block SM(i, j) belonging to the lth level of fragmentation after applying the irregular partitioning technique. The extremities of SM(i, j) are defined by:

* the leftmost upper entry $LUE_{ij} = (i, j - \theta(n, p, l) + 1)$;

* the rightmost upper entry $RUE_{ij} = (i, j)$;

* the leftmost lower entry $LLE_{ij} = (i + \theta(n, p, l) - 1, j - \theta(n, p, l) + 1)$;

* the rightmost lower entry $RLE_{ij} = (i + \theta(n, p, l) - 1, j)$.

Figure 41a shows eight points (A, B, C, D, E, F, G, and H) that identify blocks on which the block SM(i, j) depends:

* $A = \text{Tree}[LUE_{i,j-3 \times \theta(n,p,l)-1}]$
<figure><img src="image_46.png" /><figcaption>**Figure 40** – Dependencies of two blocks SM(i, j) and SM(h, l) after applying the irregular partitioning technique</figcaption></figure>

• $B = \text{Tree}[LUE_{i,j-\theta(n,p,l)-2}]$

• $C = \text{Tree}[LLE_{i,j-\theta(n,p,l)-2}]$

• $D = \text{Tree}[LLE_{i,j-3 \times \theta(n,p,l)-1}]$

• $E = \text{Tree}[LLE_{i+\theta(n,p,l)+1,j}]$

• $F = \text{Tree}[RLE_{i+\theta(n,p,l)+1,j}]$

• $G = \text{Tree}[RLE_{i+3 \times \theta(n,p,l),j}]$

• $H = \text{Tree}[LLE_{i+3 \times \theta(n,p,l),j}]$

As in (Kengne et al., 2016), all lower blocks and subblocks (a part of a block) that are in the same row and column as the block SM(i, j) are no longer absolutely required to evaluate SM(i, j) because of the speedup of Knuth (1971), which does not allow estimating the exact load of a block before its evaluation (Kengne, 2014). The blocks on which the block SM(i, j) depends can be carried out in parallel because they are not located on the same diagonal as SM(i, j) and those belonging to the same diagonal are independent.

**Remark 2** To minimize the amount of data exchanged between processors in communication rounds, each processor must communicate only the subblock of its block, corresponding to the size of the target block.
<figure><img src="image_47.png" /><figcaption>**Figure 41** – Dependencies and extremities of a block SM(i, j) after applying the irregular partitioning technique</figcaption></figure>

### 3.3.2 - Mapping blocks onto processors

We use a snake-like mapping scheme introduced in (Kengne and Myoupo, 2012) to allow some processors to evaluate at most one block more than the others. This scheme consists of assigning all blocks of a given diagonal from the leftmost upper corner to the rightmost lower corner. This process is reiterated until a block has been assigned to each processor, starting from processor $P_0$ and traveling through the blocks with a snake-like path. Figure 42 illustrates this mapping on six processors.

This mapping allows the processors to remain active as soon as possible. It also ensures the load balancing because it distributes equally small and large size blocks among processors. However, it does not optimize communications (see more details in Section 2.2.5, page 60).

**Lemma 14** After partitioning the shortest path matrix with the irregular partitioning technique and applying the snake-like mapping, the maximum number of blocks per processor is $(3k+2)$. *k* is the number of fragmentations performed.

*Proof.* Depending on the parity of *f*(*p*), the following two scenarios can happen:
<figure><img src="image_48.png" /><figcaption>**Figure 42** – Snake-like mapping on six processors when $k = 1$</figcaption></figure>

1. when $f(p)$ is odd, each processor has to evaluate at most one larger-size block, $3(k-1)$ blocks in the diagonals from the first to the $(k-1)$th fragmentation and 4 blocks after the $k$th fragmentation; thus $1 + 3(k-1) + 4 = (3k+2)$ blocks in total;

2. when $f(p)$ is even, each processor has to evaluate at most two larger-size blocks, $2(k-1)$ blocks in the diagonals from the first to the $(k-1)$th fragmentation and 3 blocks after the $k$th fragmentation; thus $2 + 2(k-1) + 3 = (2k+3)$ blocks in total.

Since $3k+2 \ge 2k+3$ when $k \ge 1$, then each processor has to evaluate at most $(3k+2)$ blocks. ■

### 3.3.3 - CGM-based parallel algorithm for solving the MPP

To solve the MPP, our CGM-based parallel algorithm is a succession of $f(p) + k \times (\lceil f(p)/2 \rceil + 1)$ similar steps in which the blocks are evaluated in a progressive fashion as in (Kechid and Myoupo, 2009; Kengne and Myoupo, 2012). Thus, evaluating the shortest path cost of nodes of a block belonging to the diagonal $d$ starts at the diagonal $\lceil d/2 \rceil$. The overall structure is given by Algorithm 21. After the computation of blocks on diagonal $d$ (line 3 in Algorithm 21), each block is forwarded (line 4 in Algorithm 21) to processors that need these blocks for updating
**Algorithm 21** Our CGM-based parallel algorithm based on the irregular partitioning technique to solve the MPP

1: $\mathit{maxDiag} \leftarrow f(p) + k \times (\lceil f(p)/2 \rceil + 1);$

2: **for** $d = 1$ to $\mathit{maxDiag}$ **do**

3: &nbsp;&nbsp;&nbsp;&nbsp;**Finalization** of computations of the shortest path costs to nodes in blocks belonging to the diagonal $d$;

4: &nbsp;&nbsp;&nbsp;&nbsp;**Communication** of block $\mathit{SM}(i, j)$ of current diagonal to processors that hold upper and right blocks;

5: &nbsp;&nbsp;&nbsp;&nbsp;**Update** the shortest path costs to each block belonging to diagonals $(d+1, d+2, \dots, \min\{2 \times (d-1), \mathit{maxDiag}\})$;

**Algorithm 22** Finalization phase using in Algorithm 21 to evaluate blocks $\mathit{SM}(i, j)$ belonging to the $l$th level of fragmentation

1: **for** $d = (j - i - \theta(n, p, l))$ to $(j - i)$ **do**

2: &nbsp;&nbsp;&nbsp;&nbsp;**for each** node $(a, b)$ of diagonal $d$ belonging to $\mathit{SM}(i, j)$ **do**

3: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;SP$[a, b] \leftarrow \min\{\text{SP}[a, b]$, weight of paths whose final edge are jumps coming from block $\mathit{SM}(i, i + \theta(n, p, l))$, weights of paths whose final edges are internal jumps, weights of paths whose final edges are unit edges$\}$;

**Algorithm 23** Updating phase using in Algorithm 21 to refresh the shortest path costs to nodes of blocks $\mathit{SM}(i, j)$ belonging to the $l$th level of fragmentation

1: **for** $d = (j - i - \theta(n, p, l))$ to $(j - i)$ **do**

2: &nbsp;&nbsp;&nbsp;&nbsp;$M_1 \leftarrow$ matrix-multiplication$(+, \min) (\mathit{SM}(i, h + i - 1), \mathit{SM}(h + i - 1, j));$

3: &nbsp;&nbsp;&nbsp;&nbsp;$M_2 \leftarrow$ matrix-multiplication$(+, \min) (\mathit{SM}(i, j - h + 1), \mathit{SM}(j - h + 1, j));$

4: &nbsp;&nbsp;&nbsp;&nbsp;SP$[i, j] \leftarrow \min\{\text{SP}[i, j], $M_1, M_2$\};

(line 5 in Algorithm 21) or for finalizing (line 3 in Algorithm 21) the computations of values in next steps. According to Theorem 3, it is deducible that the updates for a block $\mathit{SM}(i, j)$ belonging to the $l$th level of fragmentation are equivalent to a matrix multiplication $(+, \min)$ of matrices $\mathit{SM}(i, k)$ and $\mathit{SM}(k - \theta(n, p, l) + 2, j)$. Algorithms 22 and 23 show the pseudocodes of finalization and updating phases in Algorithm 21.

**Theorem 13** *Our CGM-based parallel solution based on the irregular partitioning technique requires $O(n^3/p)$ execution time with $\lceil \sqrt{2p} \rceil + k \times (\lceil \frac{\lceil \sqrt{2p} \rceil}{2} \rceil + 1)$ communication rounds in the worst case to solve the MPP. $k$ is the number of fragmentations performed.*

**Proof.** Let $S = f(p) = \lceil 2p \rceil$. During the computation rounds, evaluating each block of a diagonal belonging to the $l$th level of fragmentation through the sequential algorithm of Godbole (1973) (used in Algorithm 22) and the sequential multiplication of two matrices (used in Algorithm 23) requires $O(\frac{n^3}{2^{3l} \times (2p)^{3/2}}) =$
**Algorithm 24** Our CGM-based parallel algorithm based on the irregular partitioning technique to solve the OBST problem

1: **for** $d = 1$ to $f(p) + k \times (\lceil f(p)/2 \rceil + 1)$ **do**

2: **Computation** of blocks belonging to the round $d$ using Algorithm 11;

3: **Communication** of entries (Tree and Cut tables) required for computing each block of rounds $\{d+1, d+2, \dots, f(p) + k \times (\lceil f(p)/2 \rceil + 1)\}$;

$O(\frac{n^3}{8^l \times p\sqrt{p}})$ local computation time. So, from the proof of Lemma 13, the evaluation of each diagonal of blocks required :

$$ 
\begin{aligned}
D &= O\left(\frac{n^3}{p\sqrt{p}}\right) \times \lfloor\frac{S}{2}\rfloor + O\left(\frac{n^3}{8 \times p\sqrt{p}}\right) \times \left(\lfloor\frac{S}{2}\rfloor + 1\right) + O\left(\frac{n^3}{8^2 \times p\sqrt{p}}\right) \times \\
&\quad \left(\lfloor\frac{S}{2}\rfloor + 1\right) + \dots + O\left(\frac{n^3}{8^k \times p\sqrt{p}}\right) \times \left(\lfloor\frac{S}{2}\rfloor + 1\right) + O\left(\frac{n^3}{8^k \times p\sqrt{p}}\right) \times \lfloor\frac{S}{2}\rfloor \\
&= O\left(\frac{n^3}{p}\right) + O\left(\frac{n^3}{p\sqrt{p}}\right) \times \left(\lfloor\frac{S}{2}\rfloor + 1\right) \left[\frac{1}{8} + \frac{1}{8^2} + \dots + \frac{1}{8^k}\right] + O\left(\frac{n^3}{8^k \times p}\right) \\
&= O\left(\frac{n^3}{p}\right)
\end{aligned}
$$

Therefore, this algorithm requires $O(n^3/p)$ execution time. The number of communication rounds is derived from Lemma 13. ■

**Remark 3** When $k = 0$, our CGM-based parallel solution based on the irregular partitioning technique to solve the MPP is reduced to the one in (Kengne and Myoupo, 2012), running in $O(n^3/p)$ execution time with $\lceil\sqrt{2p}\rceil$ communication rounds.

### 3.3.4 - CGM-based parallel algorithm for solving the OBST problem

To solve the OBST problem, our CGM-based parallel algorithm evaluates the values of shortest paths to each node of a block, starting from the first diagonal of blocks to the diagonal $f(p) + k \times (\lceil f(p)/2 \rceil + 1)$, by using the sequential algorithm of Knuth (1971) in computation rounds; although it does not allow predicting before the beginning of the computation of the block $SM(i, j)$, which will be the values necessary for its evaluation. This is why the blocks are evaluated in a non-progressive fashion, that is, the evaluation of blocks of the diagonal $d$ start after computing blocks of the diagonal $(d-1)$. Algorithm 24 draws a big picture.
**Theorem 14** *Our CGM-based parallel solution based on the irregular partitioning technique requires $O(n^2/\sqrt{p})$ execution time with $\lceil\sqrt{2p}\rceil+k \times (\lceil\frac{\sqrt{2p}}{2}\rceil+1)$ communication rounds in the worst case to solve the OBST problem. k is the number of fragmentations performed.*

*Proof.* It is deducible from Theorem 13.

<figure><img src="image_49.png" /></figure>

**Remark 4** *When $k=0$, our CGM-based parallel solution based on the irregular partitioning technique to solve the OBST problem is reduced to the one in (Myoupo and Kengne, 2014b), running in $O(n^2/\sqrt{p})$ execution time with $\lceil\sqrt{2p}\rceil$ communication rounds.*

### 3.3.5 - Experimental results

#### Experimental setups

This section outlines experimental results of our CGM-based parallel solutions to solve the MPP and the OBST problem<fnref n="1" />, and compares them with the best previous solutions (Kengne and Myoupo, 2012; Myoupo and Kengne, 2014b). These algorithms have been executed on the MatriCS platform (described in Section 2.4.7). The results are presented following the different values of $(n, p, k)$, where :

* $n$ is the data size, with values in the set $\langle 4096, 8192, 12288, 16384, 20480, 24576, 28672, 32768, 36864, 40960 \rangle$. For the MPP, we have used a random data set generated for the TCP problem in Section 2.4.7. For the OBST problem, we have generated the frequencies for each data size.

* $p$ is the number of processors, with values in the set $\langle 1, 32, 64, 96, 128 \rangle$. When $p=1$, the sequential algorithm of Godbole (1973) is carried out to solve the MPP and the sequential algorithm of Knuth (1971) to solve the OBST problem.

* $k$ is the number of fragmentations performed, with values in the set $\langle 0, 1, 2, 3, 4, 5 \rangle$. When $k=0$, our CGM-based parallel solutions solving the MPP and the OBST problem are similar to the one in (Kengne and Myoupo, 2012) and the one in (Myoupo and Kengne, 2014b), respectively (see Remarks 3 and 4).

**Note 2** *These parameters will be used in the next CGM-based parallel solutions described in Sections 3.4 and 3.5.*

<footnote n="1">1. The source codes are available on these URLs: https://github.com/compiii/CGM-Sol-for-MPP and https://github.com/compiii/CGM-Sol-for-OBST. They implement all the solutions proposed in this chapter.</footnote>
Tables 3 and 5 (respectively Tables 4 and 6) show the total execution time, the speedup, and the efficiency of our CGM-based parallel solutions to solve the MPP (respectively the OBST problem). Figures 43a, 43b, 43c, 43d, 44a, 44b, 45a, 45b, 46a, 46b, 46c, and 46d are drawn from the results obtained in Tables 3, 4, 5, and 6.

## Evolution of the global communication time

Figures 43a, 43b, 43c, and 43d illustrate the global communication time, which is composed of the latency time of processors and the effective transfer time of data. In general, the global communication time is higher while solving the MPP compared to the one that is obtained while solving the OBST problem because evaluating blocks using the sequential algorithm of Knuth (1971) minimizes the latency time of processors, since a processor waits less time to start or continue evaluating a block. However, these figures show that the global communication time gradually decreases as the number of fragmentations increases. For example, on thirty-two processors when $n = 40960$, Figures 43a and 43c (respectively Figures 43b and 43d) reveal that the global communication time is reduced down to 34.98% (respectively 3.87%) when $k = 1$, and to 45.63% (respectively 40.49%) when $k = 2$ for the MPP (respectively the OBST problem). When a fragmentation is performed, the number of blocks increases by dividing the current size of blocks into four to form the smaller-size blocks. It allows minimizing the latency time of processors and the effective transfer time of data since the smaller-size blocks take less time to evaluate and communicate compared to the larger-size blocks.

## Evolution of the load-balancing of processors

Figures 44a and 44b compare the load imbalance on thirty-two processors. The values are obtained by performing the difference between the average computation time of processors and the lowest (and highest) computation time among them. The processor with the lowest or highest computational load varies with the number of fragmentations for the MPP; for example, when $k = 0$ and $k = 2$, respectively, $P_5$ and $P_0$ have the lowest loads, and $P_2$ and $P_{13}$ have the highest. However, for the OBST problem, the speedup of Knuth (1971) does not allow obtaining the same result as the MPP (yet it is the same dependency graph and the partitioning techniques are also the same). It is due to the fact that the blocks in the same diagonal have not the same load; for example, when $k = 0$ and $k = 2$, respectively, $P_7$ and $P_{30}$ have the lowest loads, and $P_3$ and $P_{22}$ have the highest.

These figures show that the irregular partitioning technique of the dynamic graph balances the load of processors better than the regular partitioning technique
<table><caption>**Table 3** – Total execution time (in seconds), speedup, and efficiency (in %) for $n \in \{4096, \dots, 40960\}$, $p \in \{1,32\}$, and $k \in \{0,1,2\}$ while solving the MPP with the irregular partitioning technique</caption><thead><tr><th rowspan="2">n</th><th colspan="3">Total execution time</th><th colspan="3">Speedup</th><th colspan="3">Efficiency</th></tr><tr><th>k = 1</th><th>k = 0</th><th>k = 1</th><th>k = 2</th><th>k = 0</th><th>k = 1</th><th>k = 2</th><th>k = 0</th><th>k = 1</th><th>k = 2</th></tr></thead><tbody><tr><td>4096</td><td>212.84</td><td>32.19</td><td>19.29</td><td>18.54</td><td>6.61</td><td>11.03</td><td>11.48</td><td>20.66</td><td>34.48</td><td>35.87</td></tr><tr><td>8192</td><td>2238.52</td><td>285.07</td><td>162.02</td><td>157.90</td><td>7.85</td><td>13.82</td><td>14.18</td><td>24.54</td><td>43.18</td><td>44.30</td></tr><tr><td>12288</td><td>8051.53</td><td>982.42</td><td>525.23</td><td>494.04</td><td>8.20</td><td>15.33</td><td>16.30</td><td>25.61</td><td>47.90</td><td>50.93</td></tr><tr><td>16384</td><td>19423.55</td><td>2728.25</td><td>1435.73</td><td>1400.95</td><td>7.12</td><td>13.53</td><td>13.86</td><td>22.25</td><td>42.28</td><td>43.33</td></tr><tr><td>20480</td><td>37932.72</td><td>6055.91</td><td>2668.47</td><td>2546.92</td><td>6.26</td><td>14.22</td><td>14.89</td><td>19.57</td><td>44.42</td><td>46.54</td></tr><tr><td>24576</td><td>65559.28</td><td>11607.89</td><td>5067.28</td><td>5036.99</td><td>5.65</td><td>12.94</td><td>13.02</td><td>17.65</td><td>40.43</td><td>40.67</td></tr><tr><td>28672</td><td>104688.35</td><td>19221.79</td><td>8609.44</td><td>8471.21</td><td>5.45</td><td>12.16</td><td>12.36</td><td>17.02</td><td>38.00</td><td>38.62</td></tr><tr><td>32768</td><td>172834.08</td><td>28806.13</td><td>14448.27</td><td>13071.16</td><td>6.00</td><td>11.96</td><td>13.22</td><td>18.75</td><td>37.38</td><td>41.32</td></tr><tr><td>36864</td><td>243774.87</td><td>41851.26</td><td>25484.45</td><td>17496.95</td><td>5.82</td><td>9.57</td><td>13.93</td><td>18.20</td><td>29.89</td><td>43.54</td></tr><tr><td>40960</td><td>383976.51</td><td>58074.15</td><td>34112.16</td><td>25867.56</td><td>6.61</td><td>11.26</td><td>14.84</td><td>20.66</td><td>35.18</td><td>46.39</td></tr></tbody></table>

<table><caption>**Table 4** – Total execution time (in seconds), speedup, and efficiency (in %) for $n \in \{4096, \dots, 40960\}$, $p \in \{1,32\}$, and $k \in \{0,1,2\}$ while solving the OBST problem with the irregular partitioning technique</caption><thead><tr><th rowspan="2">n</th><th colspan="3">Total execution time</th><th colspan="3">Speedup</th><th colspan="3">Efficiency</th></tr><tr><th>k = 1</th><th>k = 0</th><th>k = 1</th><th>k = 2</th><th>k = 0</th><th>k = 1</th><th>k = 2</th><th>k = 0</th><th>k = 1</th><th>k = 2</th></tr></thead><tbody><tr><td>4096</td><td>62.34</td><td>20.58</td><td>16.68</td><td>13.11</td><td>3.03</td><td>3.74</td><td>4.75</td><td>9.46</td><td>11.68</td><td>14.85</td></tr><tr><td>8192</td><td>514.32</td><td>180.82</td><td>136.43</td><td>100.02</td><td>2.84</td><td>3.77</td><td>5.14</td><td>8.89</td><td>11.78</td><td>16.07</td></tr><tr><td>12288</td><td>1784.19</td><td>621.52</td><td>476.46</td><td>343.27</td><td>2.87</td><td>3.74</td><td>5.20</td><td>8.97</td><td>11.70</td><td>16.24</td></tr><tr><td>16384</td><td>4315.43</td><td>1582.57</td><td>1142.21</td><td>818.11</td><td>2.73</td><td>3.78</td><td>5.27</td><td>8.52</td><td>11.81</td><td>16.48</td></tr><tr><td>20480</td><td>8546.86</td><td>2919.91</td><td>2308.19</td><td>1600.75</td><td>2.93</td><td>3.70</td><td>5.34</td><td>9.15</td><td>11.57</td><td>16.69</td></tr><tr><td>24576</td><td>14899.60</td><td>5970.20</td><td>3920.49</td><td>2785.83</td><td>2.50</td><td>3.80</td><td>5.35</td><td>7.80</td><td>11.88</td><td>16.71</td></tr><tr><td>28672</td><td>23802.78</td><td>8527.82</td><td>6078.21</td><td>4428.91</td><td>2.79</td><td>3.92</td><td>5.37</td><td>8.72</td><td>12.24</td><td>16.80</td></tr><tr><td>32768</td><td>33263.71</td><td>12533.26</td><td>10130.78</td><td>6607.36</td><td>2.65</td><td>3.28</td><td>5.03</td><td>8.29</td><td>10.26</td><td>15.73</td></tr><tr><td>36864</td><td>48356.46</td><td>17658.48</td><td>13514.64</td><td>9451.97</td><td>2.74</td><td>3.58</td><td>5.12</td><td>8.56</td><td>11.18</td><td>15.99</td></tr><tr><td>40960</td><td>69722.12</td><td>24910.11</td><td>20933.65</td><td>12986.77</td><td>2.80</td><td>3.33</td><td>5.37</td><td>8.75</td><td>10.41</td><td>16.78</td></tr></tbody></table>
<table><caption>**Table 5** – Total execution time (in seconds), speedup, and efficiency (in %) for $n \in \{36864, 40960\}$, $p \in \{64, 96, 128\}$, and $k \in \{0, 1, 2\}$ while solving the MPP with the irregular partitioning technique</caption><thead><tr><th rowspan="2">p</th><th colspan="3">Total execution time</th><th colspan="3">Speedup</th><th colspan="3">Efficiency</th></tr><tr><th>k = 0</th><th>k = 1</th><th>k = 2</th><th>k = 0</th><th>k = 1</th><th>k = 2</th><th>k = 0</th><th>k = 1</th><th>k = 2</th></tr></thead><tbody><tr><td colspan="10" style="text-align: center;">n = 36864</td></tr><tr><td>64</td><td>19656.70</td><td>9584.39</td><td>8411.20</td><td>12.40</td><td>25.43</td><td>28.98</td><td>19.38</td><td>39.74</td><td>45.28</td></tr><tr><td>96</td><td>13729.69</td><td>7204.86</td><td>5995.95</td><td>17.76</td><td>33.83</td><td>40.66</td><td>18.50</td><td>35.24</td><td>42.35</td></tr><tr><td>128</td><td>10133.01</td><td>5393.59</td><td>4565.67</td><td>24.06</td><td>45.20</td><td>53.39</td><td>18.79</td><td>35.31</td><td>41.71</td></tr><tr><td colspan="10" style="text-align: center;">n = 40960</td></tr><tr><td>64</td><td>28392.16</td><td>13798.22</td><td>11932.76</td><td>13.52</td><td>27.83</td><td>32.18</td><td>21.13</td><td>43.48</td><td>50.28</td></tr><tr><td>96</td><td>20024.65</td><td>10160.46</td><td>8904.22</td><td>19.18</td><td>37.79</td><td>43.12</td><td>19.97</td><td>39.37</td><td>44.92</td></tr><tr><td>128</td><td>14961.59</td><td>7917.73</td><td>6785.92</td><td>25.66</td><td>48.50</td><td>56.58</td><td>20.05</td><td>37.89</td><td>44.21</td></tr></tbody></table>

<table><caption>**Table 6** – Total execution time (in seconds), speedup, and efficiency (in %) for $n \in \{36864, 40960\}$, $p \in \{64, 96, 128\}$, and $k \in \{0, 1, 2\}$ while solving the OBST problem with the irregular partitioning technique</caption><thead><tr><th rowspan="2">p</th><th colspan="3">Total execution time</th><th colspan="3">Speedup</th><th colspan="3">Efficiency</th></tr><tr><th>k = 0</th><th>k = 1</th><th>k = 2</th><th>k = 0</th><th>k = 1</th><th>k = 2</th><th>k = 0</th><th>k = 1</th><th>k = 2</th></tr></thead><tbody><tr><td colspan="10" style="text-align: center;">n = 36864</td></tr><tr><td>64</td><td>11671.40</td><td>7610.84</td><td>6586.99</td><td>4.14</td><td>6.35</td><td>7.34</td><td>6.47</td><td>9.93</td><td>11.47</td></tr><tr><td>96</td><td>10128.02</td><td>6573.25</td><td>5552.72</td><td>4.77</td><td>7.36</td><td>8.71</td><td>4.97</td><td>7.66</td><td>9.07</td></tr><tr><td>128</td><td>8951.40</td><td>5788.29</td><td>5126.66</td><td>5.40</td><td>8.35</td><td>9.43</td><td>4.22</td><td>6.53</td><td>7.37</td></tr><tr><td colspan="10" style="text-align: center;">n = 40960</td></tr><tr><td>64</td><td>16045.47</td><td>10456.06</td><td>9057.29</td><td>4.35</td><td>6.67</td><td>7.70</td><td>6.79</td><td>10.42</td><td>12.03</td></tr><tr><td>96</td><td>13928.60</td><td>9031.15</td><td>7813.92</td><td>5.01</td><td>7.72</td><td>8.92</td><td>5.21</td><td>8.04</td><td>9.29</td></tr><tr><td>128</td><td>12305.95</td><td>7949.95</td><td>6707.94</td><td>5.67</td><td>8.77</td><td>10.39</td><td>4.43</td><td>6.85</td><td>8.12</td></tr></tbody></table>

of this graph due to the gradual reduction of the block sizes that allows processors to remain active as long as possible. Indeed, the fragmentation is performed on the blocks with the largest loads. So, some small-size blocks (which are in the upper diagonals) have higher loads than the large ones (which are in the lower diagonals). Thanks to the snake-like mapping, which allows distributing blocks onto processors in an equitable way, a processor can have in the worst case one more block than another. This greatly contributes to balancing the loads of processors. When $n = 40960$ in Figure 44a, the lowest load and the highest load respectively decrease on average by 25.95% and 43.72% when $k = 1$, and on average by 51.14% and 62.29% when $k = 2$. Similar observations can be made in Figure 44b, except when $n = 40960$ and $k = 1$ where the lowest load narrows down to 27.52% and the highest load increases up to 11.89% because of the speedup of Knuth (1971). However when $k = 2$, the lowest load and the highest load reduce down to 56.63% and 42.98%.
<figure><img src="image_50.png" /><figcaption>(a) MPP for $p = 32$</figcaption></figure>

<figure><img src="image_51.png" /><figcaption>(b) OBST problem for $p = 32$</figcaption></figure>

<figure><img src="image_52.png" /><figcaption>(c) MPP for $n = 40960$</figcaption></figure>

<figure><img src="image_53.png" /><figcaption>(d) OBST problem for $n = 40960$</figcaption></figure>

**Figure 43** – Global communication time for $n \in \{4096, \dots, 40960\}$, $p \in \{32, \dots, 128\}$, and $k \in \{0, 1, 2\}$ while solving the MPP and the OBST problem with the irregular partitioning technique

<figure><img src="image_54.png" /><figcaption>(a) MPP</figcaption></figure>

<figure><img src="image_55.png" /><figcaption>(b) OBST problem</figcaption></figure>

**Figure 44** – Load imbalance of processors for $n \in \{24576, 32768, 40960\}$, $p = 32$, and $k \in \{0, 1, 2\}$ while solving the MPP and the OBST problem with the irregular partitioning technique

## Comparison of communication rate and computation rate

Figures 45a and 45b show that the communication rate is higher than the computation rate, which means that the global communication time is a significant part of the total execution time compared to the overall computation time whatever the data size and the number of fragmentations on thirty-two processors.
<figure><img src="image_56.png" /><figcaption>**Figure 45** – Computation rate versus communication rate for $n \in \{8192, 24576, 40960\}$, $p = 32$, and $k \in \{1, 2\}$ while solving the MPP and the OBST problem with the irregular partitioning technique</figcaption></figure>

When $n = 40960$, the computation rate and the communication rate respectively are 29.78% and 70.22% when $k = 0$, 22.28% and 77.72% when $k = 1$, and 14.30% and 85.70% when $k = 2$ for the MPP; and respectively are 22.05% and 77.95% when $k = 0$, 10.83% and 89.17% when $k = 1$, and 11.01% and 88.99% when $k = 2$ for the OBST problem. It is therefore deducible from this observation that the irregular partitioning technique reduces the overall computation time because the computation rate is lower and lower when the number of fragmentations increases, since the computational load of processors is more and more balanced.

## Evolution of the total execution time

Figures 46a, 46b, 46c, and 46d show that the minimization of the overall communication and computation time lead up to a reduction of the total execution time as the number of fragmentations increases. For example, on thirty-two processors when $n = 40960$ in Figures 46a and 46c, the total execution time decreases on average by 41.26% when $k = 1$, and on average by 55.46% when $k = 2$ for the MPP; in Figures 46b and 46d, the total execution time decreases on average by 15.96% when $k = 1$, and on average by 47.87% when $k = 2$ for the OBST problem. Similar observations can be made on one hundred and twenty-eight processors. The total execution time decreases on average by 47.08% when $k = 1$, and on average by 54.64% when $k = 2$ for the MPP; and it decreases on average by 35.40% when $k = 1$, and on average by 45.50% when $k = 2$ for the OBST problem.

Tables 3, 4, 5, and 6 show that since the total execution time decreases when the number of fragmentations increases, the speedup and the efficiency of our CGM-based parallel solutions increase. On thirty-two processors when $n = 40960$ in Table 3 (respectively Table 4), the speedup and the efficiency are equal to 6.61 and
<figure><img src="image_57.png" /><figcaption>(a) MPP for $p = 32$</figcaption></figure>

<figure><img src="image_58.png" /><figcaption>(b) OBST problem for $p = 32$</figcaption></figure>

<figure><img src="image_59.png" /><figcaption>(c) MPP for $n = 40960$</figcaption></figure>

<figure><img src="image_60.png" /><figcaption>(d) OBST problem for $n = 40960$</figcaption></figure>

**Figure 46** – Total execution time for $n \in \{4096, \dots, 40960\}$, $p \in \{32, \dots, 128\}$, and $k \in \{0, 1, 2\}$ while solving the MPP and the OBST problem with the irregular partitioning technique

20.66% (respectively 2.80 and 8.75%) when $k = 0$, and increase up to 11.26 and 35.18% (respectively 3.33 and 10.41%) when $k = 1$, and up to 14.84 and 46.39% (respectively 5.37 and 16.78%) when $k = 2$ for the MPP (respectively the OBST problem). From all this, we can deduce that our CGM-based parallel solutions based on the irregular partitioning technique are scalable as the data size, the number of processors, and the number of fragmentations rise.

### 3.3.6 - Drawback of the irregular partitioning technique

Although the irregular partitioning technique has good performance, it suffers from an important shortcoming. Indeed, our previous CGM-based parallel solutions do not allow processors to start evaluating small-size blocks as soon as the data they need are available. Yet, these data are usually available before the end of the evaluation of large-size blocks. Figure 47 briefly illustrates this drawback. The processors colored in yellow ($P_3$ and $P_7$) evaluate the blocks that have been assigned to them. These blocks need the data (more precisely the most shaded blocks and subblocks) from the processors colored in green ($P_0$, $P_1$, $P_2$, $P_4$, $P_5$, and $P_6$) to start or continue their evaluations. $P_3$ (respectively $P_7$) requires the data from $P_0$, $P_1$,
<figure><img src="image_61.png" /><figcaption>**Figure 47** – *Drawback of the irregular partitioning technique*</figcaption></figure>

$P_5$, and $P_6$ (respectively $P_0$, $P_2$, $P_4$, and $P_5$). However, these processors holding blocks on which $P_3$ and $P_7$ depend must completely finish their evaluations before communicating them entirely or partially (see Remark 2, page 109) to $P_3$ and $P_7$. As a result, this shortcoming induces an important latency time of processors, which is the largest part of the global communication time.

## 3.4 - Second dynamic graph partitioning : *k*-block splitting technique

The *k*-block splitting technique aims to reduce the latency time of processors by allowing them to start the evaluation of blocks as soon as possible. The goal is to give the possibility to processors which depend on them not to wait too much. This strategy consists in splitting the large-size blocks into a set of smaller-size blocks called *k-blocks* after performing *k* fragmentations. Thus, evaluating a block by a single processor will consist of computing and communicating each *k*-block contained in this block. It will allow processors to start the evaluation of *k*-blocks as soon as the data they need will available.

Let $f(p) = \lceil\sqrt{2p}\rceil$, $\theta(n, p) = \lfloor\frac{n}{f(p)}\rfloor$, and $\theta(n, p, l) = \lfloor\frac{\theta(n, p)}{2^l}\rfloor$. Formally, we partition the shortest path matrix *SP* into blocks (denoted by *SM(i, j)*), and split
<figure><img src="image_62.png" /><figcaption>**Figure 48** – k-block splitting technique of the shortest path matrix for $n = 32$, $k \in \{1,2\}$, and $p \in \{3, 4, 5, 6, 7, 8\}$. For $p \in \{3, 4\}$, SP is partitioned into fifteen blocks and twenty-one k-blocks when $k = 1$, and into twenty-four blocks and seventy-eight k-blocks when $k = 2$. For $p \in \{5, 6, 7, 8\}$, SP is partitioned into nineteen blocks and thirty-six k-blocks when $k = 1$, and into twenty-eight blocks and one hundred and thirty-six when $k = 2$</figcaption></figure>

the large-size blocks into a set of k-blocks. $SM(i, j)$ is thus a $\Theta(n, p, l) \times \Theta(n, p, l)$ matrix belonging to the $l$th level of fragmentation and is subdivided into $4^{k-l}$ k-blocks of size $\Theta(n, p, k) \times \Theta(n, p, k)$. Figures 48a, 48b, 48c, and 48d depict four scenarios of this partitioning for $n = 32$, $k \in \{1,2\}$, and $p \in \{3, 4, 5, 6, 7, 8\}$.

**Remark 5** About this partitioning, some points are similar to Remark 1. We enumerate the most relevant ones :
1. the blocks of the first diagonal are $\Theta(n,p) \times \Theta(n,p)$ upper triangular matrices splitting into $2^{k-1}(2^k + 1)$ k-blocks; this is illustrated for example in Figures 48b and 48d where, after performing two fragmentations (i.e. $k=2$), the upper triangular matrices are subdivided into ten k-blocks;

2. a block belonging to the $l$th level of fragmentation is full if it is a $\Theta(n,p,l) \times \Theta(n,p,l)$ non-triangular matrix;

3. one fragmentation increases up to $\lceil f(p)/2 \rceil + 1$ the number of diagonal of blocks (see proof in Lemma 13);

4. there are $2^k \times f(p)$ diagonals of k-blocks after performing k fragmentations. This is illustrated for example in Figures 48c and 48d where there respectively are eight diagonals of k-blocks when $k=1$ and sixteen diagonals of k-blocks when $k=2$.

The purpose of splitting the blocks into a set of *k*-blocks is to progressively evaluate and communicate them during the evaluation of blocks. The *k*-block splitting technique is essentially based on the progressive evaluation of the DAG nodes (see Theorem 3, page 57). It is therefore adequate to solve the MPP because the sequential algorithm of Godbole (1973) gives the possibility to evaluate the nodes in this way. In contrast, the sequential algorithm of Knuth (1971) does not allow performing this kind of evaluation to solve the OBST problem; this is because the speedup of Knuth (1971) does not allow knowing when to start or continue the evaluation of a node. Thus, it would not be meaningful and practical to apply the *k*-block splitting technique to solve the OBST problem because a lot of unnecessary computations could be performed and lead to poor performance.

In summary, the *k*-block splitting technique is used in this section to solve the MPP, which is the most classical and generic problem. Blocks' dependency analysis, CGM-based parallel algorithms derived from this technique, and experimental results are presented in Sections 3.4.1, 3.4.2, and 3.4.3 respectively.

### 3.4.1 - Blocks' dependency analysis of the MPP

From the blocks' dependency seen in Section 3.3.1 for the irregular partitioning technique, it is easy to analyze the *k*-blocks dependency. Indeed, if the blocks on the same diagonal are independent, then the parts of these blocks, i.e. the *k*-blocks, will also be independent. Figure 49 depicts an example of dependencies of two *k*-blocks $SM(i, j)$ and $SM(h, l)$ after applying the *k*-block splitting technique. They require the already computed values of the most shaded *k*-blocks, which are part
<figure><img src="image_63.png" /><figcaption>**Figure 49** – Dependencies of two *k*-blocks SM(i, j) and SM(h, l) after applying the *k*-block splitting technique</figcaption></figure>

or not of a same block. Evaluating the shortest paths of nodes of *k*-blocks can be
then carried out in parallel.

**3.4.2 - CGM-based parallel algorithms to solve the MPP**

Depending on how processors evaluate the *k*-blocks contained in a block, two approaches can be derived : the diagonal by diagonal evaluation approach and the *k*-block by *k*-block evaluation approach. The overall structure of our CGM-based parallel algorithms is similar to Algorithm 2, which is based on the irregular partitioning technique, since $f(p) + k \times (\lceil f(p) \rceil / 2] + 1$ diagonal of blocks must be evaluated in a progressive fashion whatever the chosen approach.

**Diagonal by diagonal evaluation approach**

The diagonal by diagonal evaluation approach consists in evaluating a block by
computing a set of *k*-blocks belonging to the same diagonal of *k*-blocks before
communicating them. This approach will minimize the number of communication
rounds. However, it will not allow processors to evaluate other *k*-blocks as soon
as the data they need are available. In fact, after performing a *k*-block, a processor
will compute other *k*-blocks of the same diagonal before communicating them.

This approach is given by Algorithm 25. Evaluating the shortest path to a node of a *k*-block of diagonal *d* starts at diagonals ⌊*d*/2⌋. The number of diagonal of *k*-blocks goes from left to right and ranges from 1 to 2^k × *f*(*p*). At the end of the computation of *k*-blocks on diagonal *d* (line 4 in Algorithm 25), each *k*-block
**Algorithm 25** Our CGM-based parallel algorithm based on the *k*-block splitting technique to solve the MPP using the diagonal by diagonal evaluation approach

1: $maxDiag \leftarrow f(p) + k \times (\lceil f(p)/2 \rceil + 1);$

2: **for** $u = 1$ to $maxDiag$ **do**

3: &nbsp;&nbsp;&nbsp;&nbsp;**for** $d = \lceil (j-i)/\theta(n,p,k) \rceil - 2^{k-l} - 2$ to $\lceil (j-i)/\theta(n,p,k) \rceil$ **do**

4: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**Finalization** of the evaluation of the block $SM(i, j)$ of diagonal $u$: compute the shortest path costs to nodes of each *k*-block of the same diagonal $d$;

5: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**Communication** of each *k*-blocks belonging to the same diagonal $d$ to processors that detain upper blocks and right blocks;

6: &nbsp;&nbsp;&nbsp;&nbsp;**for** $d = \lceil (j' - i')/\theta(n, p, k) \rceil - 2^{k-l'} - 2$ to $\lceil (j' - i')/\theta(n, p, k) \rceil$ **do**

7: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**Update** the shortest path costs to nodes of each *k*-blocks contained in the block $SM(i', j')$ of diagonals $(u+1, u+2, \dots, \min\{2 \times (u-1), maxDiag\})$;

is forwarded (line 5 in Algorithm 25) to processors that need these *k*-blocks for updating (line 7 in Algorithm 25) or for finalizing (line 4 in Algorithm 25) the computations of values in next steps.

**Theorem 15** To solve the MPP, our CGM-based parallel solution based on the *k*-block splitting technique using the diagonal by diagonal evaluation approach runs in $O(n^3/4^k p)$ execution time with $O(2^k \sqrt{p})$ communication rounds in the worst case.

**Proof.** Let $S = f(p) = \lceil \sqrt{2p} \rceil$ and $\beta = (S \bmod 2)$. Algorithm 25 evaluates $S + k \times (\lceil S/2 \rceil + 1)$ diagonals of blocks. A single processor computes and communicates:

* $2^k$ diagonals of *k*-blocks in the first diagonal of blocks;

* $(2^{k+1} - 1)$ diagonals of *k*-blocks from the diagonal of blocks 2 to $(\lceil S/2 \rceil - 1)$;

* $(2^{l+1} - 1)$ diagonals of *k*-blocks for each $(\lceil S/2 \rceil + 1)$ diagonals of blocks belonging to the $l$th level of fragmentation such that $1 \le l < k$;

* one diagonal of *k*-blocks for each $(S + \beta)$ diagonals of blocks belonging to the *k*th level of fragmentation.

Thus, the number of communication rounds is equal to:

$$ 
\begin{align*}
D &= 2^k + (2^{k+1} - 1) \left( \left\lfloor \frac{S}{2} \right\rfloor - 1 \right) + \left( \left\lceil \frac{S}{2} \right\rceil + 1 \right) \sum_{l=1}^{k-1} (2^{l+1} - 1) + S + \beta \\
&= \left\lfloor \frac{S}{2} \right\rfloor (2^{k+1} - 1) + \left\lceil \frac{S}{2} \right\rceil (2^{k+1} - k - 3) + 2^k - k - 2 + S + \beta \\
&= O(2^k \sqrt{p})
\end{align*}
$$
**Algorithm 26** Our CGM-based parallel algorithm based on the *k*-block splitting technique to solve the MPP using the *k*-block by *k*-block evaluation approach

1: $maxDiag \leftarrow f(p) + k \times (\lceil f(p)/2 \rceil + 1);$

2: **for** $u = 1$ to $maxDiag$ **do**

3: **for each** $k$-block $\rho$ belonging in the block $SM(i, j)$ **do**

4: Finalization of the evaluation of the block $SM(i, j)$ of diagonal $u$: compute the shortest path costs to nodes of the $k$-block $\rho$;

5: Communication of the $k$-block $\rho$ to the processors that detain upper blocks and right blocks;

6: **for each** $\rho' \in SM(i', j')$ of diagonals $(u+1, \dots, \min\{2 \times (u-1), maxDiag\})$ **do**

7: Update the shortest path costs to nodes of the $k$-block $\rho'$;

Therefore, this algorithm runs in $O(n^3/4^k p)$ execution time since evaluating a $k$-block requires $O(n^3/8^k p\sqrt{p})$ local computation time. ■

**k-block by k-block evaluation approach**

The *k*-block by *k*-block evaluation approach consists in evaluating a block by computing and communicating each *k*-block contained in this block. It will allow the processors to evaluate other *k*-blocks as soon as the data they need are available since a *k*-block is communicated as soon as a processor has finished computing it. However, compared to the first, this approach will involve a lot of communication between them. This approach is not different to the first one, except that we communicate a *k*-block immediately after computing it. Algorithm 26 gives an overview.

**Theorem 16** In the worst case, our CGM-based parallel solution based on the *k*-block splitting technique to solve the MPP using the *k*-block by *k*-block evaluation approach runs in $O(n^3/2^k p)$ execution time with $O(4^k \sqrt{p})$ communication rounds.

*Proof.* A single processor computes and communicates:

* $2^{k-1}(2^k - 1)$ $k$-blocks at the first diagonal of blocks;

* $4^k$ $k$-blocks from the diagonal of blocks 2 to $(\lceil S/2 \rceil - 1);$

* $4^{k-l}$ $k$-blocks for each $(\lceil S/2 \rceil + 1)$ diagonals of blocks belonging to the $l$th level of fragmentation such that $1 \le l < k$;

* one $k$-block for each $(S + \beta)$ diagonals of blocks belonging to the $k$th level of fragmentation.
Thus, the number of communication rounds is equal to :

$$D = 2^{k-1}(2^k - 1) + 4^k \left( \lfloor \frac{S}{2} \rfloor - 1 \right) + \left( \lceil \frac{S}{2} \rceil + 1 \right) \sum_{l=1}^{k-1} 4^{k-l} + S + \beta \\ = O(4^k \sqrt{p})$$

Therefore, this algorithm runs in $O(n^3/2^k p)$ execution time.

<figure><img src="image_64.png" /></figure>

### 3.4.3 - Experimental results

This section presents experimental results of our CGM-based parallel solutions based on the k-block splitting technique to solve the MPP, and compares them with the best previous solutions. Tables 7 and 8 show the total execution time, the speedup, and the efficiency of our CGM-based parallel solutions. In these tables, the solution using the diagonal by diagonal evaluation strategy is referred to *dbyd*, and the solution using the k-block by k-block evaluation strategy is referred to *kbyk*. Our previous CGM-based parallel solution based on the irregular partitioning technique (described in Sectoin 3.3) is referred to *frag*. Figures 50a, 50b, 51a, 51b, 52a, 52b, 53a, 53b, 53c, 53d, 54a, and 54b are drawn from the results obtained in Tables 3, 5, 7, 8, and 9.

#### Evolution of the global communication time

Figures 50a and 50b show that the global communication time decreases when the number of fragmentations increases. To minimize the latency time of processors, *frag* reduces the computation time of blocks by reducing their sizes. For example, on thirty-two processors when *n* = 40960, the communication time decreases on average by 34.98% when *k* = 1 and on average by 45.63% when *k* = 2. By allowing processors to receive the data they need as soon as they are available to start or continue computation, *dbyd* and *kbyk* minimize the global communication time better than *frag*. For example, on thirty-two processors when *n* = 40960, *dbyd* (respectively *kbyk*) reduces the global communication time on average by 47.67% (respectively 48.17%) when *k* = 1 and on average by 51.64% (respectively 56.97%) when *k* = 2. *kbyk* is better than *dbyd* because *kbyk* communicates a k-block as soon as a processor has finished computing it.

#### Evolution of the load-balancing of processors

Figures 51a and 51b show that on thirty-two processors, the load-balancing of processors for *frag*, *dbyd*, and *kbyk* are nearly the same. When *n* = 40960 and *k* = 1 (respectively *k* = 2), the lowest load and the highest load decrease on average by
<table><caption>**Table 7** – Total execution time (in seconds), speedup, and efficiency (in %) for $n \in \{4096, \dots, 40960\}$, $p = 32$, and $k \in \{1, 2\}$ while solving the MPP with the k-block splitting technique</caption><thead><tr><th rowspan="3">n</th><th colspan="4">Total execution time</th><th colspan="4">Speedup</th><th colspan="4">Efficiency</th></tr><tr><th colspan="2">k = 1</th><th colspan="2">k = 2</th><th colspan="2">k = 1</th><th colspan="2">k = 2</th><th colspan="2">k = 1</th><th colspan="2">k = 2</th></tr><tr><th>dbyd</th><th>kbyk</th><th>dbyd</th><th>kbyk</th><th>dbyd</th><th>kbyk</th><th>dbyd</th><th>kbyk</th><th>dbyd</th><th>kbyk</th><th>dbyd</th><th>kbyk</th></tr></thead><tbody><tr><td>4096</td><td>17.40</td><td>16.14</td><td>16.15</td><td>15.43</td><td>12.23</td><td>13.19</td><td>13.18</td><td>13.79</td><td>38.21</td><td>41.21</td><td>41.19</td><td>43.09</td></tr><tr><td>8192</td><td>146.61</td><td>135.66</td><td>138.70</td><td>131.94</td><td>15.27</td><td>16.50</td><td>16.14</td><td>16.97</td><td>47.71</td><td>51.56</td><td>50.44</td><td>53.02</td></tr><tr><td>12288</td><td>470.27</td><td>443.62</td><td>444.85</td><td>436.62</td><td>17.12</td><td>18.15</td><td>18.10</td><td>18.44</td><td>53.50</td><td>56.72</td><td>56.56</td><td>57.63</td></tr><tr><td>16384</td><td>1260.72</td><td>1220.34</td><td>1245.55</td><td>1177.73</td><td>15.41</td><td>15.92</td><td>15.59</td><td>16.49</td><td>48.15</td><td>49.74</td><td>48.73</td><td>51.54</td></tr><tr><td>20480</td><td>2428.76</td><td>2281.30</td><td>2407.38</td><td>2193.53</td><td>15.62</td><td>16.63</td><td>15.76</td><td>17.29</td><td>48.81</td><td>51.96</td><td>49.24</td><td>54.04</td></tr><tr><td>24576</td><td>4699.22</td><td>4292.97</td><td>4470.52</td><td>4205.99</td><td>13.95</td><td>15.27</td><td>14.66</td><td>15.59</td><td>43.60</td><td>47.72</td><td>45.83</td><td>48.71</td></tr><tr><td>28672</td><td>7502.89</td><td>7470.79</td><td>6692.89</td><td>6308.90</td><td>13.95</td><td>14.01</td><td>15.64</td><td>16.59</td><td>43.60</td><td>43.79</td><td>48.88</td><td>51.86</td></tr><tr><td>32768</td><td>12930.32</td><td>12343.33</td><td>11756.47</td><td>10725.43</td><td>13.37</td><td>14.00</td><td>14.70</td><td>16.11</td><td>41.77</td><td>43.76</td><td>45.94</td><td>50.36</td></tr><tr><td>36864</td><td>21796.13</td><td>20465.65</td><td>15565.01</td><td>14608.09</td><td>11.18</td><td>11.91</td><td>15.66</td><td>16.69</td><td>34.95</td><td>37.22</td><td>48.94</td><td>52.15</td></tr><tr><td>40960</td><td>29693.54</td><td>28875.73</td><td>23348.62</td><td>21175.60</td><td>12.93</td><td>13.30</td><td>16.45</td><td>18.13</td><td>40.41</td><td>41.55</td><td>51.39</td><td>56.67</td></tr></tbody></table>

<table><caption>**Table 8** – Total execution time (in seconds), speedup, and efficiency (in %) for $n \in \{36864, 40960\}$, $p \in \{64, 96, 128\}$, and $k \in \{1, 2\}$ while solving the MPP with the k-block splitting technique</caption><thead><tr><th rowspan="3">p</th><th colspan="4">Total execution time</th><th colspan="4">Speedup</th><th colspan="4">Efficiency</th></tr><tr><th colspan="2">k = 1</th><th colspan="2">k = 2</th><th colspan="2">k = 1</th><th colspan="2">k = 2</th><th colspan="2">k = 1</th><th colspan="2">k = 2</th></tr><tr><th>dbyd</th><th>kbyk</th><th>dbyd</th><th>kbyk</th><th>dbyd</th><th>kbyk</th><th>dbyd</th><th>kbyk</th><th>dbyd</th><th>kbyk</th><th>dbyd</th><th>kbyk</th></tr></thead><tbody><tr><td colspan="13" style="text-align: center;">n = 36864</td></tr><tr><td>64</td><td>8399.46</td><td>7753.09</td><td>7279.01</td><td>6784.47</td><td>29.02</td><td>31.44</td><td>33.49</td><td>35.93</td><td>45.35</td><td>49.13</td><td>52.33</td><td>56.14</td></tr><tr><td>96</td><td>6289.94</td><td>5995.56</td><td>5053.26</td><td>4663.64</td><td>38.76</td><td>40.66</td><td>48.24</td><td>52.27</td><td>40.37</td><td>42.35</td><td>50.25</td><td>54.45</td></tr><tr><td>128</td><td>4782.50</td><td>4502.34</td><td>3831.61</td><td>3507.80</td><td>50.97</td><td>54.14</td><td>63.62</td><td>69.50</td><td>39.82</td><td>42.30</td><td>49.70</td><td>54.29</td></tr><tr><td colspan="13" style="text-align: center;">n = 40960</td></tr><tr><td>64</td><td>12321.05</td><td>11724.24</td><td>10349.04</td><td>9485.96</td><td>31.16</td><td>32.75</td><td>37.10</td><td>40.48</td><td>48.69</td><td>51.17</td><td>57.97</td><td>63.25</td></tr><tr><td>96</td><td>8924.64</td><td>8569.33</td><td>7592.07</td><td>6931.47</td><td>43.02</td><td>44.81</td><td>50.58</td><td>55.40</td><td>44.82</td><td>46.68</td><td>52.68</td><td>57.70</td></tr><tr><td>128</td><td>6671.59</td><td>6317.01</td><td>5713.98</td><td>5163.69</td><td>57.55</td><td>60.78</td><td>67.20</td><td>74.36</td><td>44.96</td><td>47.49</td><td>52.50</td><td>58.09</td></tr></tbody></table>
<table><caption>**Table 9** – Total execution time (in seconds), speedup, and efficiency (in %) for n = 40960, p ∈ {32, ..., 128}, and k ∈ {3, 4} while solving the MPP with the k-block splitting technique using the k-block by k-block evaluation strategy</caption><thead><tr><th rowspan="2">p</th><th colspan="2">Total execution time</th><th colspan="2">Speedup</th><th colspan="2">Efficiency</th></tr><tr><th>k = 3</th><th>k = 4</th><th>k = 3</th><th>k = 4</th><th>k = 3</th><th>k = 4</th></tr></thead><tbody><tr><td>32</td><td>29041.75</td><td>53490.34</td><td>13.22</td><td>7.18</td><td>41.32</td><td>22.43</td></tr><tr><td>64</td><td>11301.82</td><td>18374.91</td><td>33.97</td><td>20.90</td><td>53.09</td><td>32.65</td></tr><tr><td>96</td><td>7908.40</td><td>12164.26</td><td>48.55</td><td>31.57</td><td>50.58</td><td>32.88</td></tr><tr><td>128</td><td>5765.98</td><td>8729.30</td><td>66.59</td><td>43.99</td><td>52.03</td><td>34.36</td></tr></tbody></table>

<figure><img src="image_65.png" /><figcaption>**Figure 50** – Global communication time for n ∈ {4096, ..., 40960}, p = 32, and k ∈ {0, 1, 2} while solving the MPP with the k-block splitting technique</figcaption></figure>

25.95% and 43.72% (respectively 51.14% and 62.29%) for *frag*, on average by 25.51% and 46.92% (respectively 52.51% and 63.81%) for *dbyd*, and on average by 25.16% and 46.43% (respectively 50.59% and 64.90%) for *kbyk*. These results were predictable because *frag*, *dbyd*, and *kbyk* are essentially based on the irregular partitioning technique and snake-like mapping. Recall that the irregular partitioning technique balances the load of processors better than the regular partitioning technique because of the gradual reduction of the block sizes that allows processors to remain active as long as possible. From this, we can conclude that our CGM-based parallel solutions based on the *k*-block splitting technique (*dbyd* and *kbyk*) kept the good performance of our CGM-based parallel solution based on the irregular partitioning technique (*frag*) with respect to the load-balancing of processors. They promote the load balancing when the number of fragmentations rises.

## Comparison of communication rate and computation rate

Figures 52a and 52b show that the computation rate is lower than the communication rate on thirty-two processors. It was expected because the evaluation of a block belonging to the diagonal *d* starts before the step (*d* − 1) to minimize its computation time. The computation rate is lower and lower because when the number of
<figure><img src="image_66.png" /><figcaption>**Figure 51** – Load imbalance of processors for $n \in \{24576, 32768, 40960\}$, $p = 32$, and $k \in \{0, 1, 2\}$ while solving the MPP with the k-block splitting technique</figcaption></figure>

<figure><img src="image_67.png" /><figcaption>**Figure 52** – Computation rate versus communication rate for $n \in \{8192, 24576, 40960\}$, $p = 32$, and $k \in \{1, 2\}$ while solving the MPP with the k-block splitting technique</figcaption></figure>

fragmentations increases, the computational load between processors is more and more balanced. When $n = 40960$ and $k = 1$ (respectively $k = 2$), it is 22.28% (respectively 14.30%) for *frag*, 28.14% (respectively 15.55%) for *dbyd*, and 26.82% (respectively 17.15%) for *kbyk*. Therefore, as for the load-balancing of processors, *dbyd* and *kbyk* kept the good performance of *frag*.

## Evolution of the total execution time

Figures 53a, 53b, 53c, and 53d show that the minimization of the global communication time (due to the minimization of the latency time of processors) lead up to a reduction of the total execution time as the number of fragmentations rises. For example, on thirty-two processors when $n = 40960$ and $k = 1$ (respectively $k = 2$) in Figures 53a and 53b, the total execution time decreases on average by 41.26% (respectively 55.46%) for *frag*, on average by 48.87% (respectively 59.80%) for *dbyd*, and on average by 50.28% (respectively 63.54%) for *kbyk*. Similar observations can be made on one hundred and twenty-eight processors in Figures 53c
<figure><img src="image_68.png" /><figcaption>(a) $p = 32$ and $k = 1$</figcaption></figure>

<figure><img src="image_69.png" /><figcaption>(b) $p = 32$ and $k = 2$</figcaption></figure>

<figure><img src="image_70.png" /><figcaption>(c) $n = 40960$ and $k = 1$</figcaption></figure>

<figure><img src="image_71.png" /><figcaption>(d) $n = 40960$ and $k = 2$</figcaption></figure>

**Figure 53** – Total execution time for $n \in \{4096, \dots, 40960\}$, $p \in \{32, \dots, 128\}$, and $k \in \{0, 1, 2\}$ while solving the MPP with the *k*-block splitting technique

and 53d; where when $n = 40960$ and $k = 1$ (respectively $k = 2$), the total execution time decreases on average by 47.08% (respectively 54.64%) for *frag*, on average by 55.41% (respectively 61.81%) for *dbyd*, and on average by 57.78% (respectively 65.49%) for *kbyk*.

Tables 7 and 8 show that the speedup and the efficiency of our CGM-based parallel solutions rise since the total execution time decreases as the number of fragmentations increases. On thirty-two processors when $n = 40960$ and $k = 1$ (respectively $k = 2$) in Table 7, the speedup and the efficiency are equal to 12.93 and 40.41% (respectively 16.45 and 51.39%) for *dbyd*, and increases up to 13.30 and 41.55% (respectively 18.13 and 56.67%) for *kbyk*.

### 3.4.4 - Drawback of the *k*-block splitting technique

The main target of the *k*-block splitting technique was to reduce the global communication time while keeping the good performance of the irregular partitioning technique. Experimental results have besides shown that our CGM-based parallel solutions based on the *k*-block splitting technique, among which the one using the *k*-block by *k*-block evaluation strategy was the best, are better than our solu-
<figure><img src="image_72.png" /><figcaption>**Figure 54** – Global communication time and total execution time for $n = 40960$, $p \in \{32, \dots, 128\}$, and $k \in \{0, \dots, 4\}$ while solving the MPP with the $k$-block splitting technique using the $k$-block by $k$-block evaluation strategy</figcaption></figure>

tions based on the irregular partitioning technique and that they are scalable to the increase of the data size and the number of processors.

However, these solutions are not scalable to the increase of the number of fragmentations. In fact, the blocks of the first diagonals which are not fragmented (e.g. the first and second diagonal in Figure 48d) are split either into $2^{k-1}(2^k + 1)$ $k$-blocks (for those belonging to the first diagonal), or into $4^k$ $k$-blocks. For example on thirty-two processors, after performing four fragmentations, the blocks of the first diagonal will be subdivided into $2^3(2^4 + 1) = 136$ $k$-blocks, and those of the second, third, and fourth diagonal will be divided into $4^4 = 256$ $k$-blocks. When $n = 40960$, each $k$-block will be a square matrix of size $320 \times 320$. However, the blocks on the first diagonals, and therefore the $k$-blocks that make them up, do not require a very high computational load compared to the blocks on the last diagonals. As a result, the evaluation of the $k$-blocks seen in the previous example will not take too much time and will lead to a communication overhead as a consequence of the huge amount of communication that will have to be done by the processors to exchange very small data in a short time. Recall that the communication overhead raises the latency time of processors, which accounts for most of the global communication time. Figures 54a and 54b respectively illustrate the consequences of this shortcoming on the global communication time and the total execution time when $n = 40960$. They show that the performance of our CGM-based parallel solution using the $k$-block by $k$-block evaluation strategy deteriorates from the third fragmentation.

To solve this drawback, one idea would be to fix the number of subblocks belonging to a large-size block so that this number no longer increases as the number of fragmentations rises to minimize the communication between processors and
consequently to avoid communication overhead. The partitioning strategy based on this approach should also be applied to solve the OBST problem because the *k*-block splitting technique is not suitable to solve it. Section 3.5 presents a strategy that meets these expectations.

**3.5 - Third dynamic graph partitioning : four-splitting technique**

To avoid the communication overhead caused by the *k*-block splitting technique while reducing the latency time of processors, the four-splitting technique consists of splitting the large-size blocks into four small-size blocks (or subblocks) after performing *k* fragmentations. The subblocks of the blocks belonging to the *l*th level of fragmentation must have the same size as the blocks belonging to the (*l* + 1)th level of fragmentation. The goal is the same as the *k*-block splitting technique, that is, allows processors to start the evaluation of blocks as soon as possible. Hence, evaluating a block by a single processor will consist of computing and communicating each subblock contained in this block.

By denoting $f(p) = \lceil\sqrt{2p}\rceil$, $\theta(n, p) = \left\lceil\frac{n}{f(p)}\right\rceil$, and $\theta(n, p, l) = \left\lceil\frac{\theta(n, p)}{2^l}\right\rceil$, formally, we subdivide the shortest path matrix *SP* into blocks (denoted by *SM*(*i*, *j*)), and split the large-size blocks into four subblocks. Thus, a block *SM*(*i*, *j*) belonging to the *l*th level of fragmentation, such that *l* < *k*, is a $\theta(n, p, l) \times \theta(n, p, l)$ matrix and is subdivided into four subblocks of size $\theta(n, p, l + 1) \times \theta(n, p, l + 1)$. The blocks of the *k*th level of fragmentation are not splitting into four as these are the smallest blocks. Figures 55a, 55b, 55c, and 55d depict four scenarios of this partitioning for $n = 32, k \in \{1, 2\}$, and $p \in \{3, 4, 5, 6, 7, 8\}$.

**Remark 6** Some relevant points can be noticed about this partitioning :

1. the blocks of the first diagonal are $\theta(n,p) \times \theta(n,p)$ upper triangular matrices splitting into tree subblocks;

2. when $k=1$, this partitioning technique is identical to the *k*-block splitting technique; for example, Figures 55a and 55c are the same as Figures 48a and 48c respectively where $k=1$;

3. whatever the number of fragmentations performed, the size of subblocks (which are the parts of blocks belonging to the *l*th level of fragmentation) does not change compared to the *k*-block splitting technique; for example,
<figure><img src="image_73.png" /><figcaption>**Figure 55** – Four-splitting technique of the shortest path matrix for $n = 32$, $k \in \{1, 2\}$, and $p \in \{3, 4, 5, 6, 7, 8\}$. For $p \in \{3, 4\}$, SP is partitioned into fifteen blocks and twenty-one subblocks when $k = 1$, and into twenty-four blocks and fifty-seven subblocks when $k = 2$. For $p \in \{5, 6, 7, 8\}$, SP is partitioned into nineteen blocks and thirty-six subblocks when $k = 1$, and into twenty-eight blocks and seventy-two subblocks when $k = 2$.</figcaption></figure>

the subblocks of the second diagonal are square matrix of size 4 × 4 when $k = 1$ in Figure 48c, and are square matrix of size 2 × 2 in Figure 48c when $k = 2$. But in Figures 55c and 55d, the subblocks of the second diagonal are square matrix of size 4 × 4.
**Lemma 15** After partitioning the shortest path matrix, the total number of sub-blocks is equal to:

$$C = \frac{S(S-1)}{2} - 3 \left( \Delta(S+1) + \left\lfloor \frac{S}{2} \right\rfloor \right) + 2k \left[ (S+1)(S+2\Delta) - \left\lfloor \frac{S}{2} \right\rfloor \left( \left\lfloor \frac{S}{2} \right\rfloor - 1 \right) \right]$$
with $S = f(p)$ and $\Delta = (S \bmod 2)$.

**Proof.** The proof of this lemma can be easily deduced from Lemma 12. The blocks of the first diagonal are splitting into three subblocks, and the others are splitting into four subblocks except those belonging to the $k$th level of fragmentation. By considering $\Delta = (S \bmod 2)$ the variable which determines the parity of $S$, the total number of subblocks is equal to :

$$ 
\begin{aligned}
C &= 4(k-1) \times \left( \frac{S(S+1) - \left\lfloor \frac{S}{2} \right\rfloor \left( \left\lfloor \frac{S}{2} \right\rfloor - 1 \right)}{2} + \Delta(S+1) \right) + \left\lfloor \frac{S}{2} \right\rfloor + \frac{S(S+1)}{2} \\
&\quad + \Delta(S+1) + 4 \left( \frac{S(S+1) - \left\lfloor \frac{S}{2} \right\rfloor \left( \left\lfloor \frac{S}{2} \right\rfloor + 1 \right)}{2} - S \right) + 3S \\
&= 4(k-1) \times \frac{(S+1)(S+2\Delta) - \left\lfloor \frac{S}{2} \right\rfloor \left( \left\lfloor \frac{S}{2} \right\rfloor - 1 \right)}{2} + \Delta(S+1) + \frac{S(5S+3)}{2} \\
&\quad - 2 \left\lfloor \frac{S}{2} \right\rfloor^2 - \left\lfloor \frac{S}{2} \right\rfloor \\
&= \frac{S(S-1)}{2} - 3 \left( \Delta(S+1) + \left\lfloor \frac{S}{2} \right\rfloor \right) + 2k \left[ (S+1)(S+2\Delta) - \left\lfloor \frac{S}{2} \right\rfloor \left( \left\lfloor \frac{S}{2} \right\rfloor - 1 \right) \right]
\end{aligned}
$$

The choice to split blocks into four subblocks is not trivial. Indeed, it allows keeping a coherence with the first step of this partitioning, which is to apply the irregular partitioning technique. Moreover, the four-splitting technique ensures that processors do not communicate too many subblocks to avoid communication overhead. However, the $k$-block splitting technique starts the evaluation of blocks earlier than this technique since $k$-blocks are the smallest blocks. This could have a significant impact on the latency time of processors.

The analysis of dependencies between subblocks can be derived from the two previous partitioning techniques. Unlike the $k$-block splitting technique, which was not suitable for solving the OBST problem due to the speedup of Knuth (1971), the four-splitting technique can be used to solve this problem. Indeed, the subblocks can be progressively evaluated either while solving the MPP, or non-progressively
**Algorithm 27** Our CGM-based parallel algorithm based on the four-splitting technique to solve the MPP

1: $maxDiag \leftarrow f(p) + k \times (\lceil f(p)/2 \rceil + 1)$;

2: **for** $u = 1$ to $maxDiag$ **do**

3: &nbsp;&nbsp;&nbsp;&nbsp;**for each** subblock $\rho$ belonging in the block $SM(i, j)$ **do**

4: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**Finalization** of the evaluation of the block $SM(i, j)$ of diagonal $u$: compute the shortest path costs to nodes of the subblock $\rho$;

5: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**Communication** of the subblock $\rho$ to the processors that detain upper blocks and right blocks;

6: &nbsp;&nbsp;&nbsp;&nbsp;**for each** $\rho' \in SM(i', j')$ of diagonals $(u+1, \dots, \min\{2 \times (u-1), maxDiag\})$ **do**

7: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**Update** the shortest path costs to nodes of the subblock $\rho'$;

evaluated while solving the OBST problem. The corresponding CGM-based par-
allel algorithms are described in Sections 3.5.1 and 3.5.2 respectively.

**3.5.1 - CGM-based parallel algorithm to solve the MPP**

Our CGM-based parallel algorithm based on the four-splitting technique to solve
the MPP is given by Algorithm 27. Since the *k*-block by *k*-block evaluation ap-
proach has shown the better performance than the diagonal by diagonal evaluation
approach in Section 3.4.3, a similar evaluation approach is used in Algorithm 27.
Indeed, after computing each subblock containing in a block, it is immediately
communicated to processors that need these subblocks for updating (line 7 in Al-
gorithm 27) or for finalizing (line 4 in Algorithm 27) the computations of values in
next steps.

**Theorem 17** *Our CGM-based parallel solution based on the four-splitting technique to solve the MPP runs in $O(n^3/p)$ execution time with $O(k\sqrt{p})$ communication rounds in the worst case.*

*Proof.* Let $S = f(p) = \lceil\sqrt{2p}\rceil$ and $\beta = (S \bmod 2)$. A single processor computes and communicates:

• three subblocks at the first diagonal of blocks;

• four subblocks from the diagonal of blocks 2 to $\lfloor S/2 \rfloor - 1$;

* four subblocks for each ($\lceil S/2 \rceil + 1$) diagonals of blocks belonging to the *l*th level of fragmentation such that $1 \le l < k$;

• one subblock for each ($S + \beta$) diagonals of blocks belonging to the $k$th level of fragmentation.
During the computation rounds, evaluating each subblock of a block belonging to the lth level of fragmentation requires $O(\frac{n^3}{2^{3(l+1)} \times (2p)^{3/2}}) = O(\frac{n^3}{8^{l+1} \times p\sqrt{p}})$ local computation time. So, the evaluation of each diagonal of blocks required :

$$ 
\begin{aligned}
D &= 3 \times O\left(\frac{n^3}{8 \times p\sqrt{p}}\right) + 4\left(\left\lfloor\frac{S}{2}\right\rfloor - 1\right) \times O\left(\frac{n^3}{8 \times p\sqrt{p}}\right) + 4\left(\left\lceil\frac{S}{2}\right\rceil + 1\right) \times \\
  &\quad O\left(\frac{n^3}{8^2 \times p\sqrt{p}}\right) + 4\left(\left\lfloor\frac{S}{2}\right\rfloor + 1\right) \times O\left(\frac{n^3}{8^3 \times p\sqrt{p}}\right) + \dots + 4\left(\left\lceil\frac{S}{2}\right\rceil + 1\right) \times \\
  &\quad O\left(\frac{n^3}{8^k \times p\sqrt{p}}\right) + \left(\left\lfloor\frac{S}{2}\right\rfloor + 1\right) \times O\left(\frac{n^3}{8^k \times p\sqrt{p}}\right) + (S + \beta) \times O\left(\frac{n^3}{8^k \times p\sqrt{p}}\right) \\
  &= O\left(\frac{n^3}{p}\right)
\end{aligned}
$$

The number of communication rounds is equal to :

$$ E = 3 + 4\left(\left\lfloor\frac{S}{2}\right\rfloor - 1\right) + 4(k-1)\left(\left\lceil\frac{S}{2}\right\rceil + 1\right) + S + \beta = O(k\sqrt{p}) $$

Therefore, this algorithm requires $O(n^3/p)$ execution time with $O(k\sqrt{p})$ communication rounds. ■

### 3.5.2 - CGM-based parallel algorithm to solve the OBST problem

The four-splitting technique can be adapted to evaluate the subblocks that are part of a block in a non-progressive fashion compared to the k-block splitting technique. Recall that when the latter is used, the number of subblocks (or k-blocks) grows drastically as the number of fragmentations rises. When a subblock is non-progressively evaluated by a processor, it must receive all the data of subblocks that it needs to start computations. However, since the subblocks are numerous and small, computing and communicating them to processors that need them will lead to communication overhead (see Section 3.4.4). With the four-splitting technique, the blocks are subdivided into at most four regardless of the number of fragmentations performed. This reduces the number of communication rounds and the number of steps to evaluate a whole block (it will be done in at most four steps).

Denote the four subblocks of given block by LL, LU, RL, and RU, which respectively correspond to the subblock located in the leftmost lower corner, the leftmost upper corner, the rightmost lower corner, and the rightmost upper corner. Figures 56a, 56b, 56c, 56d, 56e, and 56f illustrate the different computation and communication steps of these subblocks by a processor :

* At step 0 in Figure 56a, no subblocks have started to be evaluated. This means that the processor is still receiving data of subblocks on which LL depends.
**Algorithm 28** Our CGM-based parallel algorithm based on the four-splitting technique to solve the OBST problem

1: **for** $d = 1$ to $f(p) + k \times (\lceil f(p)/2 \rceil + 1)$ **do**

2: **Computation** of the subblocks *LL* and *LU* of blocks belonging to the round *d* using Algorithm 11;

3: **Communication** of entries (*Tree* and *Cut* tables) of *LL* and *LU* required for computing each block of rounds {$d+1, d+2, \dots, f(p)+k \times (\lceil f(p)/2 \rceil + 1)$};

4: **Computation** of the subblock *RL* using Algorithm 11;

5: **Communication** of entries of *LL* and *RL*;

6: **Computation** of the subblock *RU* using Algorithm 11;

7: **Communication** of entries of *LU*, *RL*, and *RU*;

* At step 1 in Figure 56b, *LL* is computed but it is not communicated because a communication is not necessary at this step. Indeed, the processors which will receive *LL* will not be able to start the computation as soon as possible because the evaluation is done in a non-progressive fashion. The ideal would be to wait to compute *LU* before communicating them together.

* At step 2 in Figure 56c, the processor starts by receiving the lower subblocks that are in the same row as *LU*. Then, it computes *LU*. Finally, it communicates *LL* and *LU* to processors that need them. For example, the processor $P_5$ which evaluates the block of the second diagonal in Figure 42 will send *LL* and *LU* to $P_1$ and $P_3$.

* At step 3 in Figure 56d, the processor receives the lower subblocks that are in the same column as *RL*. Then, it computes *RL*. Finally, it communicates *LL* and *RL* to processors that need them. By taking the previous example, $P_5$ will send *LL* and *RL* to $P_0$ and $P_2$.

* At step 4 in Figure 56e, the processor computes *RU*. Thereafter, it communicates *RL* and *RU* to processors that need them. By taking the previous example, $P_5$ will send *RL* and *RU* to $P_1$ and $P_4$.

* At step 5 in Figure 56f, all subblocks have been computed. The processor communicates *LU* and *RU* to processors that need them. By taking the previous example, $P_5$ will send *LU* and *RU* to $P_3$.

Our CGM-based parallel algorithm based on the four-splitting technique to solve the OBST problem is given by Algorithm 28.

**Theorem 18** *Our CGM-based parallel solution based on the four-splitting technique requires $O(n^2/\sqrt{p})$ execution time with $O(k\sqrt{p})$ communication rounds in the worst case to solve the OBST problem.*
<figure><img src="image_74.png" /><figcaption>**Figure 56** – Steps to evaluate the four subblocks of a given block while solving the OBST problem with the four-splitting technique. When a subblock is computed and needs to be communicated, it is colored in gray</figcaption></figure>

*Proof.* It is deducible from Theorem 17.

<figure><img src="image_75.png" /></figure>

### 3.5.3 - Experimental results

This section highlights the results obtained from experimentations of our CGM-based parallel solutions based on the four-splitting technique to solve the MPP and the OBST problem. These experimentations have been performed on the MatriCS platform (described in Section 2.4.7) and on our Raspberry Pi cluster (described hereunder). The execution time, the speedup, and the efficiency are recorded in Tables 10, 11, 12, 13, and 14. Figures 57a, 57b, 57c, 57d, 58a, 58b, 58c, 58d, 58e, 58f, 58g, 58h, 59a, 59b, 60a, 60b, 60c, 60d, 61a, and 61b have been drawn from these tables. Our solutions based on the irregular partitioning technique, the *k*-block by *k*-block evaluation strategy, and the four-splitting technique are denoted by *frag*, *kbyk*, and *4s* respectively. Recall that *kbyk* and *4s* are similar when *k* = 1.
<table><caption>**Table 10** – Total execution time (in seconds), speedup, and efficiency (in %) for $n \in \{4096, \dots, 40960\}$, $p = 32$, and $k \in \{2, 3, 4\}$ while solving the MPP with the four-splitting technique on the MatriCS platform</caption><thead><tr><th rowspan="2">n</th><th colspan="3">Total execution time</th><th colspan="3">Speedup</th><th colspan="3">Efficiency</th></tr><tr><th>k = 2</th><th>k = 3</th><th>k = 4</th><th>k = 2</th><th>k = 3</th><th>k = 4</th><th>k = 2</th><th>k = 3</th><th>k = 4</th></tr></thead><tbody><tr><td>4096</td><td>13.65</td><td>14.63</td><td>14.66</td><td>15.59</td><td>14.55</td><td>14.52</td><td>48.73</td><td>45.46</td><td>45.37</td></tr><tr><td>8192</td><td>107.31</td><td>115.40</td><td>119.74</td><td>20.86</td><td>19.40</td><td>18.69</td><td>65.19</td><td>60.62</td><td>58.42</td></tr><tr><td>12288</td><td>404.33</td><td>396.91</td><td>398.45</td><td>19.91</td><td>20.29</td><td>20.21</td><td>62.23</td><td>63.39</td><td>63.15</td></tr><tr><td>16384</td><td>1075.51</td><td>921.47</td><td>976.78</td><td>18.06</td><td>21.08</td><td>19.89</td><td>56.44</td><td>65.87</td><td>62.14</td></tr><tr><td>20480</td><td>2133.58</td><td>2005.46</td><td>2036.95</td><td>17.78</td><td>18.91</td><td>18.62</td><td>55.56</td><td>59.11</td><td>58.19</td></tr><tr><td>24576</td><td>3854.41</td><td>3799.59</td><td>3842.85</td><td>17.01</td><td>17.25</td><td>17.06</td><td>53.15</td><td>53.92</td><td>53.31</td></tr><tr><td>28672</td><td>6547.45</td><td>6299.63</td><td>6474.68</td><td>15.99</td><td>16.62</td><td>16.17</td><td>49.97</td><td>51.93</td><td>50.53</td></tr><tr><td>32768</td><td>10578.86</td><td>9890.23</td><td>10397.02</td><td>16.34</td><td>17.48</td><td>16.62</td><td>51.06</td><td>54.61</td><td>51.95</td></tr><tr><td>36864</td><td>15842.78</td><td>14543.44</td><td>15667.99</td><td>15.39</td><td>16.76</td><td>15.56</td><td>48.08</td><td>52.38</td><td>48.62</td></tr><tr><td>40960</td><td>23670.69</td><td>19311.50</td><td>20826.53</td><td>16.22</td><td>19.88</td><td>18.44</td><td>50.69</td><td>62.14</td><td>57.62</td></tr></tbody></table>

<table><caption>**Table 11** – Total execution time (in seconds), speedup, and efficiency (in %) for $n \in \{36864, 40960\}$, $p \in \{64, 96, 128\}$, and $k \in \{2, 3, 4\}$ while solving the MPP with the four-splitting technique on the MatriCS platform</caption><thead><tr><th rowspan="2">p</th><th colspan="3">Total execution time</th><th colspan="3">Speedup</th><th colspan="3">Efficiency</th></tr><tr><th>k = 2</th><th>k = 3</th><th>k = 4</th><th>k = 2</th><th>k = 3</th><th>k = 4</th><th>k = 2</th><th>k = 3</th><th>k = 4</th></tr></thead><tbody><tr><td colspan="10" style="text-align: center;">n = 36864</td></tr><tr><td>64</td><td>6967.70</td><td>6917.32</td><td>6994.31</td><td>34.99</td><td>35.24</td><td>34.85</td><td>54.67</td><td>55.06</td><td>54.46</td></tr><tr><td>96</td><td>4981.26</td><td>4915.05</td><td>4932.40</td><td>48.94</td><td>49.60</td><td>49.42</td><td>50.98</td><td>51.66</td><td>51.48</td></tr><tr><td>128</td><td>4083.83</td><td>3803.69</td><td>3873.38</td><td>59.69</td><td>64.09</td><td>62.94</td><td>46.63</td><td>50.07</td><td>49.17</td></tr><tr><td colspan="10" style="text-align: center;">n = 40960</td></tr><tr><td>64</td><td>9926.20</td><td>9758.72</td><td>9874.92</td><td>38.68</td><td>39.35</td><td>38.88</td><td>60.44</td><td>61.48</td><td>60.76</td></tr><tr><td>96</td><td>7439.89</td><td>7245.45</td><td>7296.02</td><td>51.61</td><td>53.00</td><td>52.63</td><td>53.76</td><td>55.20</td><td>54.82</td></tr><tr><td>128</td><td>5635.09</td><td>5449.50</td><td>5540.51</td><td>68.14</td><td>70.46</td><td>69.30</td><td>53.23</td><td>55.05</td><td>54.14</td></tr></tbody></table>
<table><caption>**Table 12** – Total execution time (in seconds), speedup, and efficiency (in %) for n ∈ {4096, ..., 40960}, p = 32, and k ∈ {1, ..., 5} while solving the OBST problem with the four-splitting technique on the MatriCS platform</caption><thead><tr><th rowspan="2">n</th><th colspan="4">Total execution time</th><th colspan="4">Speedup</th><th colspan="4">Efficiency</th></tr><tr><th>k = 1</th><th>k = 2</th><th>k = 3</th><th>k = 4</th><th>k = 5</th><th>k = 1</th><th>k = 2</th><th>k = 3</th><th>k = 4</th><th>k = 5</th><th>k = 1</th><th>k = 2</th><th>k = 3</th><th>k = 4</th><th>k = 5</th></tr></thead><tbody><tr><td>4096</td><td>11.50</td><td>9.90</td><td>8.94</td><td>8.58</td><td>8.52</td><td>5.42</td><td>6.29</td><td>6.97</td><td>7.27</td><td>7.32</td><td>16.94</td><td>19.67</td><td>21.79</td><td>22.71</td><td>22.87</td></tr><tr><td>8192</td><td>97.34</td><td>77.30</td><td>70.76</td><td>69.10</td><td>68.64</td><td>5.28</td><td>6.65</td><td>7.27</td><td>7.44</td><td>7.49</td><td>16.51</td><td>20.79</td><td>22.71</td><td>23.26</td><td>23.42</td></tr><tr><td>12288</td><td>338.27</td><td>266.48</td><td>243.43</td><td>236.72</td><td>235.48</td><td>5.27</td><td>6.70</td><td>7.33</td><td>7.54</td><td>7.58</td><td>16.48</td><td>20.92</td><td>22.90</td><td>23.55</td><td>23.68</td></tr><tr><td>16384</td><td>813.47</td><td>634.41</td><td>585.65</td><td>572.21</td><td>568.37</td><td>5.30</td><td>6.80</td><td>7.37</td><td>7.54</td><td>7.59</td><td>16.58</td><td>21.26</td><td>23.03</td><td>23.57</td><td>23.73</td></tr><tr><td>20480</td><td>1605.26</td><td>1244.97</td><td>1147.37</td><td>1123.66</td><td>1116.53</td><td>5.32</td><td>6.87</td><td>7.45</td><td>7.61</td><td>7.65</td><td>16.64</td><td>21.45</td><td>23.28</td><td>23.77</td><td>23.92</td></tr><tr><td>24576</td><td>2793.95</td><td>2151.68</td><td>1977.78</td><td>1937.93</td><td>1930.08</td><td>5.33</td><td>6.92</td><td>7.53</td><td>7.69</td><td>7.72</td><td>16.67</td><td>21.64</td><td>23.54</td><td>24.03</td><td>24.12</td></tr><tr><td>28672</td><td>4458.84</td><td>3444.42</td><td>3155.25</td><td>3089.17</td><td>3076.31</td><td>5.34</td><td>6.91</td><td>7.54</td><td>7.71</td><td>7.74</td><td>16.68</td><td>21.60</td><td>23.57</td><td>24.08</td><td>24.18</td></tr><tr><td>32768</td><td>6682.07</td><td>5153.27</td><td>4718.72</td><td>4616.36</td><td>4587.60</td><td>4.98</td><td>6.45</td><td>7.05</td><td>7.21</td><td>7.25</td><td>15.56</td><td>20.17</td><td>22.03</td><td>22.52</td><td>22.66</td></tr><tr><td>36864</td><td>9578.16</td><td>7353.35</td><td>6729.28</td><td>6572.38</td><td>6529.41</td><td>5.05</td><td>6.58</td><td>7.19</td><td>7.36</td><td>7.41</td><td>15.78</td><td>20.55</td><td>22.46</td><td>22.99</td><td>23.14</td></tr><tr><td>40960</td><td>13219.62</td><td>10120.25</td><td>9252.37</td><td>9013.49</td><td>8961.54</td><td>5.27</td><td>6.89</td><td>7.54</td><td>7.74</td><td>7.78</td><td>16.48</td><td>21.53</td><td>23.55</td><td>24.17</td><td>24.31</td></tr></tbody></table>

<table><caption>**Table 13** – Total execution time (in seconds), speedup, and efficiency (in %) for n ∈ {36864, 40960}, p ∈ {64, 96, 128}, and k ∈ {1, ..., 5} while solving the OBST problem with the four-splitting technique on the MatriCS platform</caption><thead><tr><th rowspan="2">p</th><th colspan="4">Total execution time</th><th colspan="4">Speedup</th><th colspan="4">Efficiency</th></tr><tr><th>k = 1</th><th>k = 2</th><th>k = 3</th><th>k = 4</th><th>k = 5</th><th>k = 1</th><th>k = 2</th><th>k = 3</th><th>k = 4</th><th>k = 5</th><th>k = 1</th><th>k = 2</th><th>k = 3</th><th>k = 4</th><th>k = 5</th></tr></thead><tbody><tr><td colspan="16" style="text-align: center;">n = 36864</td></tr><tr><td>64</td><td>6849.69</td><td>5268.74</td><td>4744.92</td><td>4609.23</td><td>4492.70</td><td>7.06</td><td>9.18</td><td>10.19</td><td>10.49</td><td>10.76</td><td>11.03</td><td>14.34</td><td>15.92</td><td>16.39</td><td>16.82</td></tr><tr><td>96</td><td>5811.06</td><td>4336.53</td><td>3960.81</td><td>3863.48</td><td>3846.97</td><td>8.32</td><td>11.15</td><td>12.21</td><td>12.52</td><td>12.57</td><td>8.67</td><td>11.62</td><td>12.72</td><td>13.04</td><td>13.09</td></tr><tr><td>128</td><td>5166.80</td><td>3858.00</td><td>3488.67</td><td>3407.10</td><td>3391.69</td><td>9.36</td><td>12.53</td><td>13.86</td><td>14.19</td><td>14.26</td><td>7.31</td><td>9.79</td><td>10.83</td><td>11.09</td><td>11.14</td></tr><tr><td colspan="16" style="text-align: center;">n = 40960</td></tr><tr><td>64</td><td>9564.80</td><td>7256.84</td><td>6333.78</td><td>6208.79</td><td>6177.57</td><td>7.29</td><td>9.61</td><td>11.01</td><td>11.23</td><td>11.29</td><td>11.39</td><td>15.01</td><td>17.20</td><td>17.55</td><td>17.63</td></tr><tr><td>96</td><td>7980.85</td><td>5954.35</td><td>5415.29</td><td>5299.00</td><td>5276.19</td><td>8.74</td><td>11.71</td><td>12.88</td><td>13.16</td><td>13.21</td><td>9.10</td><td>12.20</td><td>13.41</td><td>13.71</td><td>13.77</td></tr><tr><td>128</td><td>7115.22</td><td>5316.16</td><td>4815.67</td><td>4688.91</td><td>4670.79</td><td>9.80</td><td>13.12</td><td>14.48</td><td>14.87</td><td>14.93</td><td>7.66</td><td>10.25</td><td>11.31</td><td>11.62</td><td>11.66</td></tr></tbody></table>

<table><caption>**Table 14** – Total execution time (in seconds), speedup, and efficiency (in %) for n ∈ {4096, ..., 16384}, p ∈ {1, 32}, and k ∈ {1, ..., 5} while solving the OBST problem with the four-splitting technique on our Raspberry Pi cluster</caption><thead><tr><th rowspan="2">n</th><th colspan="4">Total execution time</th><th colspan="4">Speedup</th><th colspan="4">Efficiency</th></tr><tr><th>k = 1</th><th>k = 2</th><th>k = 3</th><th>k = 4</th><th>k = 5</th><th>k = 1</th><th>k = 2</th><th>k = 3</th><th>k = 4</th><th>k = 5</th><th>k = 1</th><th>k = 2</th><th>k = 3</th><th>k = 4</th><th>k = 5</th></tr></thead><tbody><tr><td>4096</td><td>152.45</td><td>70.53</td><td>61.74</td><td>50.45</td><td>51.68</td><td>52.24</td><td>2.16</td><td>2.47</td><td>3.02</td><td>2.95</td><td>2.92</td><td>6.75</td><td>7.72</td><td>9.44</td><td>9.22</td><td>9.12</td></tr><tr><td>8192</td><td>1252.78</td><td>553.87</td><td>425.86</td><td>415.23</td><td>385.80</td><td>391.02</td><td>2.26</td><td>2.94</td><td>3.02</td><td>3.25</td><td>3.20</td><td>7.07</td><td>9.19</td><td>9.43</td><td>10.15</td><td>10.01</td></tr><tr><td>12288</td><td>4384.93</td><td>2670.32</td><td>1615.90</td><td>1448.08</td><td>1318.49</td><td>1351.73</td><td>1.64</td><td>2.71</td><td>3.03</td><td>3.33</td><td>3.24</td><td>5.13</td><td>8.48</td><td>9.46</td><td>10.39</td><td>10.14</td></tr><tr><td>16384</td><td>10660.09</td><td>4856.32</td><td>4034.42</td><td>3870.51</td><td>3610.49</td><td>3464.09</td><td>2.20</td><td>2.64</td><td>2.75</td><td>2.95</td><td>3.08</td><td>6.86</td><td>8.26</td><td>8.61</td><td>9.23</td><td>9.62</td></tr></tbody></table>
<figure><img src="image_76.png" /><figcaption>(a) MPP for $p = 32$</figcaption></figure>

<figure><img src="image_77.png" /><figcaption>(b) OBST problem for $p = 32$</figcaption></figure>

<figure><img src="image_78.png" /><figcaption>(c) MPP for $n = 40960$</figcaption></figure>

<figure><img src="image_79.png" /><figcaption>(d) OBST problem for $n = 40960$</figcaption></figure>

**Figure 57** – Global communication time for $n \in \{4096, \dots, 40960\}$, $p \in \{32, \dots, 128\}$, and $k \in \{0, 1, 2\}$ while solving the MPP and the OBST problem with the four-splitting technique on the MatriCS platform

## Evolution of the global communication time

Figures 57a and 57c compare the global communication time of *kbyk* and *4s* while solving the MPP by performing one and two fragmentations. Figure 57a shows that from *n* = 4096 to 24576, the global communication time of *kbyk* and *4s* is better when performing one fragmentation than when performing two. Indeed, while solving the MPP, the evaluation of the small subblocks requires less time than the large ones; and thus requires less latency time of processors. Therefore, decreasing the size of these subblocks by performing more fragmentations will lead to increase the global communication time and minimize the overall computation time. This will lead to a better total execution time when performing more than one fragmentation. For example, on thirty-two processors when *n* = 24576 in Figure 58a, the total execution time is made up of 34.39% of computation time and 65.61% of communication time when *k* = 1, and 15.30% of computation time and 84.70% of communication time when *k* = 2. Now when comparing the global communication time of *kbyk* and *4s*, it can be noticed that *4s* is better than *kbyk*. Indeed, it is necessary to split the blocks into at most four subblocks because their sizes are not large enough. Excessive communications degrading the global communication time can
be achieved when there are more subblocks than necessary. Figure 57a also shows that from $n = 28800$, the global communication time of *kbyk* when $k = 2$ is better than that of *4s* when $k = 1$ and $k = 2$. Indeed, large subblocks require more time to be evaluated; and thus, require more than one fragmentation to minimize the latency time of processors (this observation is not true in all cases because, for example on sixty-four processors in Figure 57c, the global communication time of *kbyk* and *4s* when $k = 1$ is smaller than when $k = 2$). In addition, it is necessary to split large-size blocks into more than four subblocks to allow processors to start or continue evaluating their blocks as soon as possible. For example on thirty-two processors when $n = 40960$, *kbyk* decreases the global communication time on average by 56.97% and *4s* decreases it on average by 49.96% when $k = 2$. However, Figure 58a shows that *4s* decreases the global communication time on average by 59.87% when $k = 3$. This is due to the fact that blocks belonging to the last level of fragmentation are quite large and require an additional fragmentation when $k = 2$. In contrast, Figures 58f, 58g, and 58h show that from sixty-four to one hundred and twenty-eight processors, the global communication time of *kbyk* when $k = 2$ is better than that of *4s* when $k = 3$. This is because increasing the number of processors results in decreasing the size of blocks (as well as subblocks); therefore, applying a third fragmentation results in minimizing the global communication time, which is not enough to be better than *kbyk* when $k = 2$. Nevertheless, it would have been wise to split blocks into more than four subblocks when $k = 3$ to decrease the latency time as much as possible.

Figures 57b and 57d show that the global communication time of *4s* is smaller than *frag* while solving the OBST problem by performing one and two fragmentations. It significantly decreases when the number of fragmentations increases. For example, on thirty-two processors when $n = 40960$, the global communication time of *frag* (respectively *4s*) decreases on average by 3.87% (respectively 41.84%) when $k = 1$ and on average by 40.49% (respectively 54.83%) when $k = 2$. These results were expected because *4s* minimizes the latency time of processors by allowing them to start evaluating subblocks as soon as the data they need are available. Grouping the subblocks into two before communicating also contributes to this minimization because it limits the number of messages to be exchanged in the network.

Figures 58a and 58c (respectively 58b and 58d) show that in general the global communication time and the overall computation time of *4s* gradually decrease while solving the MPP (respectively the OBST problem) by successively performing four (respectively five) fragmentations. Nevertheless, Figures 58a and 58c
<figure><img src="image_80.png" /><figcaption>(a) MPP for $n = 32$</figcaption></figure>

<figure><img src="image_81.png" /><figcaption>(b) OBST problem for $n = 32$</figcaption></figure>

<figure><img src="image_82.png" /><figcaption>(c) MPP for $n = 40960$</figcaption></figure>

<figure><img src="image_83.png" /><figcaption>(d) OBST problem for $n = 40960$</figcaption></figure>

<figure><img src="image_84.png" /><figcaption>(e) MPP for $n = 40960$ and $p = 32$</figcaption></figure>

<figure><img src="image_85.png" /><figcaption>(f) MPP for $n = 40960$ and $p = 64$</figcaption></figure>

<figure><img src="image_86.png" /><figcaption>(g) MPP for $n = 40960$ and $p = 96$</figcaption></figure>

<figure><img src="image_87.png" /><figcaption>(h) MPP for $n = 40960$ and $p = 128$</figcaption></figure>

<caption>**Figure 58** – Comparison of the overall computation time and the global communication time for $n \in \{24576, 32768, 40960\}$, $p \in \{32, \dots, 128\}$, and $k \in \{1, \dots, 5\}$ while solving the MPP and the OBST problem with the four-splitting technique on the MatriCS platform</caption>
show that the global communication time of 4s degrades from the fourth fragmentation because on thirty-two processors when $n = 40960$, it decreases in average by 48.17% when $k = 1$, in average by 49.96% when $k = 2$, in average by 59.87% when $k = 3$, and in average by 56.12% when $k = 4$. This is due to the fact that from a certain number of fragmentations, the small subblocks which are close to the optimal solution (and thus require a high evaluation time using the sequential algorithm of Godbole (1973)) do not need to be fragmented any more because they can lead to excessive communications; and thus the latency time of processors will be increased instead of being reduced. This observation is not the same for the OBST problem as shown in Figures 58b and 58d because until the fifth fragmentation the global communication time does not deteriorate. For example, on thirty-two processors when $n = 40960$, it decreases in average by 41.84% when $k = 1$, in average by 54.83% when $k = 2$, in average by 58.18% when $k = 3$, in average by 59.43% when $k = 4$, and in average by 69.08% when $k = 5$. This is due to the sequential algorithm of Knuth (1971), which is used to evaluate small subblocks that are close to the optimal solution. Since they do not require a high evaluation time, processors that need these subblocks will not have to wait long to receive them.

## Evolution of the load-balancing of processors

Figures 59a and 59b show that while solving the OBST problem, our CGM-based parallel solution based on the four-splitting technique (4s) kept the good performance of our CGM-based parallel solution based on the irregular partitioning technique (*frag*) with respect to the load-balancing of processors since they promote the load balancing when the number of fragmentations increases. Indeed, the load-balancing of processors for *frag* and 4s are nearly the same. When $n = 40960$ and $k = 1$, the lowest load narrows down to 27.52% for *frag* and to 27.24% for 4s; and the highest load increases up to 11.89% for *frag* and to 11.60% for 4s. In the same vein when $k = 2$, the lowest load and the highest load decrease on average by 56.63% and 42.98% for *frag*, and on average by 55.73% and 42.77% for 4s. As for the MPP, these results were predictable because 4s (which is a special case of *kbyk*) are based on the irregular partitioning technique and snake-like mapping.

## Evolution of the total execution time

Figures 58a, 58b, 58c, 58d, 58e, 58f, 58g, 58h, 60a, 60b, 60c, and 60d illustrate the total execution time of *frag*, *kbyk*, and 4s while solving the MPP and the OBST problem by performing one, two, three, four, and five fragmentations. As observed in Sections 3.3.5 and 3.4.3, the global communication time (see above) has a huge
<figure><img src="image_88.png" /><figcaption>**Figure 59** – Load imbalance of processors for $n \in \{24576, 32768, 40960\}$, $p = 32$, and $k \in \{0, 1, 2\}$ while solving the OBST problem with the four-splitting technique on the MatriCS platform</figcaption></figure>

<figure><img src="image_89.png" /><figcaption>**Figure 60** – Total execution time for $n \in \{4096, \dots, 40960\}$, $p \in \{32, \dots, 128\}$, and $k \in \{0, 1, 2\}$ while solving the MPP and the OBST problem with the four-splitting technique on the MatriCS platform</figcaption></figure>

impact on the total execution time, and consequently on the speedup and the efficiency (as shown in Tables 10, 11, 12, and 13). The results are obvious while solving the MPP:

* From $n = 4096$ to 24576 on thirty-two processors, the total execution time of 4s is better than kbyk when performing two fragmentations. For example
when $n = 24576$ and $k = 2$, the speedup and the efficiency are equal to 15.59 and 48.71% for *kbyk*, and increase up to 17.01 and 53.15% for *4s*.

* From $n = 28800$ on thirty-two processors, the total execution time of *kbyk* is better than that of *4s* when performing two fragmentations. For example when $n = 40960$ and $k = 2$, the speedup and the efficiency are equal to 18.13 and 56.67% for *kbyk*, and narrow down to 16.22 and 50.69% for *4s*.

* From $n = 4096$ to $40960$ on thirty-two processors, the total execution time of *4s* when performing three fragmentations is better than that of *kbyk* when performing two fragmentations. For example when $n = 40960$ and $k = 3$, the speedup and the efficiency are equal to 19.88 and 62.14% for *4s*.

* When $n = 36864$ and $n = 40960$ on sixty-four to one hundred and twenty-eight processors, the total execution time of *kbyk* when performing two fragmentations is better than *4s* when performing three fragmentations. For example on one hundred and twenty-eight processors when $n = 40960$, the speedup and the efficiency are equal to 74.36 and 58.09% for *kbyk* when $k = 2$, and narrow down to 70.46 and 55.05% for *4s* when $k = 3$.

* From $n = 4096$ to $40960$ on thirty-two to one hundred and twenty-eight processors, the total execution time of *4s* degrades from the fourth fragmentation. For example when $n = 40960$ and $k = 4$, the speedup and the efficiency of *4s* are equal to 18.44 and 57.62% on thirty-two processors, and equal to 69.30 and 54.14% for *4s* on one hundred and twenty-eight processors.

In a nutshell, there is no better choice between *kbyk* and *4s* to solve the MPP because in some conditions *4s* is better than *kbyk* and in other conditions it is the opposite. However, we recommend to use *4s* to solve this problem since compared to *kbyk*, *4s* minimizes communication between processors and its performance does not degrade abruptly when the number of fragmentations increases.

Concerning the OBST problem, the following results can be noticed :

* From $n = 4096$ to $40960$ on thirty-two to one hundred and twenty-eight processors, the total execution time of *4s* is better than that of *frag* when performing one and two fragmentations. For example, on thirty-two processors when $n = 40960$ and $k = 1$ (respectively $k = 2$), the speedup and the efficiency are equal to 3.33 and 10.41% (respectively 5.37 and 16.78%) for *frag*, and increase up to 5.27 and 16.48% (respectively 6.89 and 21.53%) for *4s*.
* When performing three, four, and five additional fragmentations, the total execution time of 4s keeps good performance, although from the fourth fragmentation the performance gain is not meaningful anymore. For example, on thirty-two processors when $n = 40960$, the speedup and the efficiency are equal to 7.54 and 23.55% when $k = 3$, and increase up to 7.74 and 24.17% when $k = 4$, up to 7.78 and 24.31% when $k = 5$.

From all this, we can deduce that it is better to use our CGM-based parallel solution based on the four-splitting technique to solve the OBST problem since it outperforms the one using the irregular partitioning technique and it is scalable as the data size, the number of processors, and the number of fragmentations rise.

## What is the ideal number of fragmentations ?

This is a legitimate question because as shown earlier, on the MatriCS platform the total execution time of 4s degrades from the fourth fragmentation while solving the MPP but keeps good performance until the fifth fragmentation while solving the OBST problem. One idea to determine the ideal number of fragmentations would be to run our CGM-based parallel solution based on the four-splitting technique to solve the OBST problem for example on another cluster. If we obtain the same result that was archived on the MatriCS platform then this could guide us to determine this number. Otherwise, we will deduce that the ideal number of fragmentations depends on the platform where the parallel algorithm is executed.

To achieve this goal, we have built a cluster consisting of four compute nodes. Each node is a Raspberry Pi 4 computer model B composed of a 64-bit quad-core Cortex-A72 processor with 8GB of RAM and an operating system Raspbian GNU/Linux 11. All nodes are interconnected with Cat8 Ethernet cable through a TP-Link router (model TL-SG108E) providing 16Gbps throughput and the inter-processor communication has been ensured by OpenMPI version 4.1.2.

Figures 61a and 61b compare the overall computation time and global communication time of 4s on thirty-two processors while solving the OBST problem by performing one, two, three, four, and five fragmentations on the MatriCS platform and on our Raspberry Pi cluster. It is obvious to notice that whatever the cluster, 4s progressively reduces the global communication time when the number of fragmentations rises. However on the Raspberry Pi cluster, the performance of 4s degrades when adding the overall computation time at the fifth fragmentation for $n = 8192$ and $n = 12288$ because the global communication time did not reduce enough to keep the good performance. For example when $n = 12288$ in Table 14, the speedup is equal to 1.64 when $k = 1$, and increases up to 2.71 when $k = 2$,
<figure><img src="image_90.png" /><figcaption>**Figure 61** – Comparison of the overall computation time and the global communication time for $n \in \{8192, 12288, 16384\}$, $p = 32$, and $k \in \{1, \dots, 5\}$ while solving the OBST problem with the four-splitting technique on the MatriCS platform and our Raspberry Pi cluster</figcaption></figure>

up to 3.03 when $k = 3$, up to 3.33 when $k = 4$, but the speedup narrows down to 3.24 when $k = 5$. This result is due to the fact that the Raspberry Pi cluster does not have a communication network as fast as the MatriCS platform. Indeed, an additional fragmentation is no longer necessary from the fourth fragmentation. Thus, since the network is not very fast, excessive communication caused a drop in performance. In summary, we deduce that the ideal number of fragmentations depends on the architecture where the CGM-based parallel solution is executed.

Another relevant observation can be seen on the Raspberry Pi cluster in Figure 61b, where the total execution time of 4s gradually decreases after five successive fragmentations when $n = 16384$. As shown in Table 14, the speedup is equal to 2.20 when $k = 1$, and increases up to 2.64 when $k = 2$, up to 2.75 when $k = 3$, up to 2.95 when $k = 4$, and up to 3.08 when $k = 5$. This is due to the fact that when the input data size increases, fragmentations are more and more required until the performance gain is not significant or drops. However, as seen earlier, the performance of 4s degrades at the fifth fragmentation for $n = 8192$ and $n = 12288$. Consequently, we infer that the ideal number of fragmentations also depends on the input data size.

## 3.6 - Summary

This chapter presented CGM-based parallel solutions based on three dynamic graph partitioning techniques that reconcile the trade-off of minimizing the number of communication rounds and balancing the load of processors to solve the MPP and the OBST problem. First, we designed a dynamic graph model for the OBST prob-
lem, like in (Bradford, 1994) for the MPP, that can be used to solve this problem
through a one-to-all shortest path algorithm. We improved the dynamic graph pro-
posed by Bradford (1994) by removing some horizontal jumps in addition to the
vertical jumps in the dynamic graph $D'_n$ to avoid more redundant computations.

Then, we proposed an irregular partitioning technique of the dynamic graph to
tackle the conflicting objectives. It consists in subdividing the dynamic graph into
blocks of variable size. Our CGM-based parallel solutions using this technique
require $O(n^3/p)$ execution time to solve the MPP and $O(n^2/\sqrt{p})$ to solve the
OBST problem, each with $O(k\sqrt{p})$ communication rounds. Experimental results
showed that these solutions minimize the overall computation time and the latency
time, and balance better the load of processors than those using regular partitioning
technique of the dynamic graph.

Finally, we proposed two techniques based on the irregular partitioning tech-
nique to reduce the latency time of processors by allowing them to start the evalu-
ation of blocks as soon as possible. Indeed, varying the blocks' sizes does not en-
able processors to start evaluating small-size blocks as soon as the data they need
are available, although these data are available before the end of the evaluation
of large-size blocks. We first proposed the *k*-block splitting technique consisting
in splitting the large-size blocks into a set of smaller-size blocks called *k-blocks*.
Thus, evaluating a block by a single processor consists of computing and commu-
nicating each *k*-block contained in this block. Experimental results showed that
our CGM-based parallel solution using this technique is better than previous but
leads to communication overhead when *k* increases. So, we proposed the four-
splitting technique consisting in splitting the large-size blocks into four small-size
blocks. It avoids communication overhead and significantly reduces the latency
time of processors. Experimental results are showed that our CGM-based paral-
lel solutions using the four-splitting technique are scalable as the data size, the
number of processors, and the number of fragmentations rise. These solutions are
better than those using the irregular partitioning technique and the *k*-block splitting
technique (although in some cases, the *k*-block splitting technique is better than the
four-splitting technique while solving the MPP). We also conducted experiments to
determine the ideal number of times the size of the blocks must be subdivided. The
results showed that this number depends on the input data size and characteristics
of the architecture of parallel computers where the solution is executed.
# General Conclusion

## CONTENTS

<table><tr><td>Re-stating the research problem</td><td>151</td></tr><tr><td>Results obtained and critical analysis</td><td>152</td></tr><tr><td>Further work</td><td>155</td></tr></table>

## Re-stating the research problem

In this thesis, we have studied the parallelization on the coarse-grained multicomputer (CGM) model of a class of non-serial polyadic dynamic-programming problems that can be formulated by Equation (1.8). Especially, we are interested in the minimum cost parenthesizing problem (MPP), the matrix chain ordering problem (MCOP), the triangulation of a convex polygon (TCP) problem, and the optimal binary search tree (OBST) problem. The standard methodology for designing CGM-based parallel solutions to solve these problems is to partition the dependency graph into subgraphs (or blocks) of same size, then distribute these blocks fairly among processors, and finally compute them in a suitable evaluation order. Kengne et al. (2016) noticed that the execution time was related to the load balancing and the number of communication rounds. These criteria depend on the partitioning strategy and the distribution scheme strategy used when designing the CGM-based parallel solution. Kengne et al. (2016) showed that minimizing the number of communication rounds and balancing the load between processors are two conflicting objectives when the dependency graph (or the dynamic graph) is partitioned into blocks of the same size :

1. When the dependency graph is subdivided into small-size blocks (Kechid and Myoupo, 2008a, 2008b, 2009), the load difference between processors
is small if one processor has one more block than another. However, the
number of communication rounds will be high.

2. When the dependency graph is subdivided into large-size blocks (Kengne and Myoupo, 2012; Myoupo and Kengne, 2014a, 2014b), the number of communication rounds is reduced since there are few blocks. However, the load of processors will be unbalanced.

By generalizing the ideas of the dependency graph partitioning and distribution
scheme introduced in (Kechid and Myoupo, 2008a, 2009; Kengne and Myoupo,
2012; Myoupo and Kengne, 2014b), Kengne et al. (2016) proposed a CGM-based
parallel solution that gives the end-user the choice to optimize one criterion ac-
cording to their own goal.

The main drawback of this solution is the conflicting optimization criterion owing to the fact that the end-user cannot optimize more than one criterion. Moreover, these criteria have a significant impact on the latency time of processors, and consequently on the global communication time.

**Results obtained and critical analysis**

This thesis intended to design CGM-based parallel solutions that address the trade-
off of minimizing the number of communication rounds and balancing the load of
processors to solve the foregoing problems. To achieve our goal, we have proposed
three techniques.

**Irregular partitioning technique**

This technique consists in subdividing the dependency graph into blocks of variable
size. It ensures that the blocks of the first diagonals are of large sizes to minimize
the number of communication rounds. Thereafter, it decreases these sizes along the
diagonals to increase the number of blocks in these diagonals and allow processors
to stay active longer. These blocks are distributed fairly among processors to min-
imize their idle time and balance the load between them. Our CGM-based parallel
solutions using this technique require $O(n^3/p)$ execution time to solve the MPP
and $O(n^2/\sqrt{p})$ to solve the OBST problem, each with $O(k\sqrt{p})$ communication
rounds. *n* is the input data size, *p* is the number of processors, and *k* is the number
of times the size of blocks is subdivided. The sequential algorithm of Godbole
(1973) and the sequential algorithm of Knuth (1971) are respectively used in the
local computation round while solving the MPP and the OBST problem.
Experimental results showed that these solutions balance the load of processors and minimize the overall computation time and the latency time. Consequently, our solutions significantly reduced the total execution time compared the regular partitioning technique proposed in (Kechid and Myoupo, 2008a, 2009; Kengne and Myoupo, 2012; Kengne et al., 2016; Myoupo and Kengne, 2014b).

Nevertheless, this technique also induces a high latency time of processors since it does not allow processors to start evaluating small-size blocks as soon as the data they need are available. Yet, these data are usually available before the end of the evaluation of large-size blocks.

## k-block splitting technique

To reduce this latency time, the *k*-block splitting technique consists in splitting the large-size blocks into a set of smaller-size blocks called *k-blocks* after performing *k* fragmentations. Thus, to allow processors to start the evaluation of *k*-blocks as soon as possible, a single processor evaluates a block by computing and communicating each *k*-block contained in this block. This technique is essentially based on the progressive evaluation of blocks. Indeed, evaluating a block belonging to the diagonal *d* in a progressive fashion consists in starting at the diagonal $[d/2]$. Therefore, this technique is suitable to solve the MPP because the sequential algorithm of Godbole (1973) gives the possibility to evaluate the nodes of blocks in this way. The sequential algorithm of Knuth (1971) in contrast does not allow performing this kind of evaluation to solve the OBST problem because it does not allow knowing when to start or continue the evaluation of a node. Thus, it was not meaningful and practical to apply the *k*-block splitting technique to solve the OBST problem because a lot of unnecessary computations could be performed and lead to poor performance.

For the MPP, depending on how processors evaluate the *k*-blocks contained in a block, we have derived two approaches :

1. The diagonal by diagonal evaluation approach, which consists in evaluating a block by computing a set of *k*-blocks belonging to the same diagonal before communicating them. It runs in $O(n^3/4^k p)$ execution time with $O(2^k \sqrt{p})$ communication rounds.

2. The *k*-block by *k*-block evaluation approach, which consists in evaluating a block by computing and communicating each *k*-block contained in this block. It runs in $O(n^3/2^k p)$ execution time with $O(4^k \sqrt{p})$ communication rounds.
Experimental results showed that these solutions are better than those based on the irregular partitioning technique since they significantly reduce the global communication time. They also showed that the second approach is better than the first because the second approach communicates a *k*-block as soon as a processor has finished computing it.

However, this technique induces a communication overhead when the number of fragmentations rises. In fact, since the *k*-block are numerous and small when *k* increases, a huge amount of communication must be done by processors to exchange data. Experimental results showed that this shortcoming deteriorates the performance of our CGM-based parallel solution as the communication overhead raises the latency time of processors, which accounts for most of the global communication time.

## Four-splitting technique

The four-splitting technique avoids this communication overhead while reducing the latency time of processors by splitting the large-size blocks into four small-size blocks (or subblocks) after performing *k* fragmentations. Hence, evaluating a block by a single processor consists of computing and communicating each sub-block contained in this block. This technique has been used to solve the MPP and the OBST problem since the subblocks can be evaluated either progressive or non-progressive fashion unlike the *k*-block splitting technique. Our CGM-based parallel solutions using this technique have the same complexity as those using the irregular partitioning technique.

Experimental results showed a good agreement with theoretical predictions. Our CGM-based parallel solutions using this technique were better than those using the irregular partitioning technique and the *k*-block splitting technique. These results also showed that while solving the MPP, when the input data size and the number of processors is large and a number of fragmentations is small, it is preferable to use *k*-block splitting technique than the four-splitting technique. We also conducted experimentations to determine the ideal number of times the size of the blocks must be subdivided. The results showed that this number depends on the input data size and the architecture where the solution is executed.

## Our fast sequential algorithm for the MCOP and the TCP problem

CGM-based parallel solutions proposed by Kechid and Myoupo (2008b) and Myoupo and Kengne (2014a) to solve the MCOP and the TCP problem, where there is a one-to-one correspondence between them, exhibit the same trade-off addressed in
this thesis. Recall that these solutions are based on the $O(n^2)$-time sequential algo-
rithm of Yao (1982), which change the form of the dependency graph by reducing
the number of subproblems to be performed. We could easily propose CGM-based
parallel solutions using the previous techniques. Nevertheless, after noticing that
some unnecessary computations were performed by the sequential algorithm of
Yao (1982) because the subproblems were evaluated according to their precedence
order, we have begun by solving this issue. We have proposed a fast sequential
algorithm consisting in organizing the evaluation of the subproblems according to
their dependencies to avoid these unnecessary computations. It requires $O(n)$ time
in many cases but requires $O(n^2)$ time in the worst case.

Experimental results performed on the MatriCS platform showed that this se-
quential algorithm is ×18.93 faster than the sequential algorithm of Yao (1982)
and ×5.07 faster than the CGM-based parallel solution of Myoupo and Kengne
(2014a) on thirty-two processors. Therefore, it questions the core idea of partition-
ing techniques proposed by Kechid and Myoupo (2008b) and Myoupo and Kengne
(2014a), which consists in scanning the 2n subproblems of the dependency graph
to estimate the overall computational load to distribute tasks equitably onto proces-
sors (since two input data of the same size but different values have two different
forms of the dependency graph).

**Further work**

Further research can be conducted to extend this work:

**Parallelizing our fast sequential algorithm for the MCOP and the TCP problem**

It would be interesting to undertake the challenge to propose a CGM-based par-
allel solution based on our sequential algorithm. Because of its speedup, the best
partitioning technique of the dependency graph proposed in (Myoupo and Kengne,
2014a), which runs in $O(n \log p)$ time, must be completely revised. An idea can
be to parallelize it. Another idea can be to skip the step of estimating the over-
all computational load before distributing the nodes equitably onto the processors.
Distribute them randomly could be the best partitioning strategy.

**Finding the ideal number of fragmentations before starting or during computations**

It would be interesting to determine the ideal number of fragmentations before
starting or during computations since this number depends on the architecture
where the solution is executed. One idea will be to refer to machine learning tech-
niques to find it before starting according to the characteristics of parallel computer architectures. Another idea would be to create a dynamic irregular partitioning that subdivides the dynamic graph into blocks during the resolution of the problem according to the parallel computer architecture. It would also be interesting if these strategies took into account the optimization of other resources such as storage and energy consumption.

## Exploiting the dynamic graph model of the OBST problem

It would be interesting to use our dynamic graph model of the OBST problem to develop a CGM-based parallel solution running in $O(n^2/p^2)$ execution time with $O(1)$ communication round. One idea can be to inspire ourselves from the work of Bradford (1994) and Higa and Stefanes (2012) to determine the critical nodes in the dynamic graph. From these nodes, it will be possible to avoid traversing certain paths that can never lead to the optimal solution.

## Applying our partitioning techniques on other dynamic-programming problems

It would be interesting to propose CGM-based parallel solutions using our partitioning techniques to solve other non-serial polyadic dynamic-programming problems such as the context-free grammar parsing problem (Kasami, 1965; Younger, 1967) and the Nussinov RNA folding problem (Nussinov and Jacobson, 1980). To our knowledge, there is no CGM-based parallel solutions that solve these problems. Another serial monadic, serial polyadic, or non-serial monadic dynamic-programming problems can be also addressed such as the string editing problem (Alves et al., 2002; Lacmou et al., 2020) and the longest common subsequence problem (Garcia et al., 2003). The irregular partitioning technique has been applied to solve two variants of the longest common subsequence problem in (Kengne et al., 2022, 2020). It can be interesting to apply the four-splitting technique to improve this solution.

## Applying our partitioning techniques on other parallel computer architectures

It would be interesting to apply our partitioning techniques on shared-memory architectures and GPU architectures. One idea can be to inspire the irregular partitioning technique and the loop tiling transformation to create a new transformation called *irregular loop tiling* that should mitigate the workload imbalance of threads. Indeed, the loop tiling transformation is used in many parallel solutions; for example to solve the Nussinov RNA folding problem in (Palkowski and Bielecki, 2017). Another idea can be to hybridize our solutions on distributed-memory architectures and those of Mabrouk (2016) on shared-memory architectures.
Alves, C. E. R., Cáceres, E. N., and Dehne, F. (2002). Parallel Dynamic Programming for Solving the String Editing Problem on A CGM/BSP. In *Proceedings of the 14th Annual ACM Symposium on Parallel Algorithms and Architectures* (pp. 275–281). Winnipeg, Manitoba, Canada. https://doi.org/10.1145/564870.564916

Bellman, R. (1957). *Dynamic Programming* (1st ed.). Princeton University Press.

Bhattacharyya, S. S., and Murthy, P. K. (1995). Optimal Parenthesization of Lexical Orderings for DSP Block Diagrams. In *Proceedings of the IEEE Workshop on VLSI Signal Processing* (pp. 177–186). Sakai, Kansai, Japan. https://doi.org/10.1109/vlsisp.1995.527489

Bielecki, W., Blaszynski, P., and Poliwoda, M. (2021). 3D Parallel Tiled Code Implementing a Modified Knuth's Optimal Binary Search Tree Algorithm. *Journal of Computational Science, 48*(1). https://doi.org/10.1016/j.jocs.2020.101246

Biswas, G., and Mukherjee, N. (2021). Memory Optimized Dynamic Matrix Chain Multiplication Using Shared Memory in GPU. In *the 2021 International Conference on Distributed Computing and Internet Technology* (pp. 160–172). Bhubaneswar, Odisha, India. https://doi.org/10.1007/978-3-030-65621-8_10

Bradford, P. G. (1994). *Parallel Dynamic Programming* (Ph.D. Thesis). Indiana University.

Bradford, P. G., Rawlins, G. J., and Shannon, G. E. (1998). Efficient Matrix Chain Ordering In Polylog Time. *SIAM Journal on Computing, 27*(2), 466–490. https://doi.org/10.1137/s0097539794270698

Cáceres, E. N., Mongelli, H., Loureiro, L., Nishibe, C., and Song, S. W. (2010). Performance Results of Running Parallel Applications on the Integrate. *Concurrency and Computation: Practice and Experience, 22*(3), 375–393. https://doi.org/10.1002/cpe.1524
Chan, A., Dehne, F., Bose, P., and Latzel, M. (2008). Coarse Grained Parallel Algorithms for Graph Matching. *Parallel Computing*, 34(1), 47–62. https://doi.org/10.1016/j.parco.2007.11.004

Collette, Y., and Siarry, P. (2002). *Optimisation Multiobjectif* (1st ed.). Eyrolles.

Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C. (2009). *Introduction to Algorithms* (3rd ed.). The MIT Press.

Craus, M. (2002). Parallel and Distributed Solutions for the Optimal Binary Search Tree Problem. In *the 2002 International Conference on Coding and Cryptology* (pp. 103–117). Mangalia, Dobroudja, Romania. https://doi.org/10.1007/3-540-47840-x_10

Culler, D., Karp, R., Patterson, D., Sahay, A., Erik, S. K., Santos, E., ... von Eicken, T. (1993). LogP: Towards a Realistic Model of Parallel Computation. *ACM SIGPLAN Notices*, 28(7), 1–12. https://doi.org/10.1145/173284.155333

Czarnul, P. (2018). *Parallel Programming for Modern High Performance Computing Systems* (1st ed.). CRC Press.

Czech, Z. J. (2017). *Introduction to Parallel Computing* (1st ed.). Cambridge University Press.

Czumaj, A. (1993). Parallel Algorithm for the Matrix Chain Product and the Optimal Triangulation Problems. In *Proceedings of the Symposium on Theoretical Aspects of Computer Science* (pp. 294–305). New York, USA. https://doi.org/10.1007/3-540-56503-5_30

Dehne, F. (2006). Guest Editor’s Introduction. *Algorithmica*, 45(3), 263–267. https://doi.org/10.1007/s00453-006-1213-2

Dehne, F., Fabri, A., and Rau-Chaplin, A. (1993). Scalable Parallel Geometric Algorithms for Coarse Grained Multicomputers. In *Proceedings of the Ninth Annual Symposium on Computational Geometry* (pp. 298–307). San Diego, California, USA. https://doi.org/10.1145/160985.161154

Dehne, F., Ferreira, A., Cáceres, E., Song, S. W., and Roncato, A. (2002). Efficient Parallel Graph Algorithms for Coarse-Grained Multicomputers and BSP. *Algorithmica*, 33(2), 183–200. https://doi.org/10.1007/s00453-001-0109-4

Deo, N. (1974). *Graph Theory with Applications to Engineering and Computer Science* (1st ed.). Prentice-Hall, Inc.
Dijkstra, E. W. (1959). *A Note on Two Problems in Connexion With Graphs*. *Numerische Mathematik*, 1(1), 269–271. https://doi.org/10.1007/bf01386390

Diwan, T., and Tembhurne, J. (2019). *A Parallelization of Non-Serial Polyadic Dynamic Programming On GPU*. *Journal of Computing and Information Technology*, 27(2), 55–66. https://doi.org/10.20532/cit.2019.1004579

El-Qawasmeh, E. (2004). Word Prediction Using a Clustered Optimal Binary Search Tree. *Information Processing Letters*, 92(5), 257–265. https://doi.org/10.1016/j.ipl.2004.08.006

Feldmann, A., Gasser, O., Lichtblau, F., Pujol, E., Poese, I., Dietzel, C., ... Smaragdakis, G. (2020). The Lockdown Effect: Implications of the COVID-19 Pandemic on Internet Traffic. In *ACM Internet Measurement Conference* (pp. 1–18). New York, USA. https://doi.org/10.1145/3419394.3423658

Ferreira, A. (2001). Parallel Computing: Models. In *Encyclopedia of Optimization* (Vol. 547, pp. 1934–1939). Springer Boston. https://doi.org/10.1007/0-306-48332-7_380

Ferreira, A., and Morvan, M. (1997). Models for Parallel Algorithm Design: An Introduction. In *Parallel Computing in Optimization* (Vol. 7, pp. 1–26). Springer Boston. https://doi.org/10.1007/978-1-4613-3400-2_1

Floyd, R. W. (1962). Algorithm 97: Shortest Path. *Communications of the ACM*, 5(6), 345. https://doi.org/10.1145/367766.368168

Flynn, M. J. (1966). Very High-Speed Computing Systems. *Proceedings of the IEEE*, 54(12), 1901–1909. https://doi.org/10.1109/proc.1966.5273

Foster, I. (1995). *Designing and Building Parallel Programs: Concepts and Tools for Parallel Software Engineering* (1st ed.). Addison-Wesley.

Fotso, L. P., Kengne, T. V., and Myoupo, J. F. (2010). Load Balancing Schemes for Parallel Processing of Dynamic Programming on BSP/CGM Model. In *the 2010 International Conference on Parallel and Distributed Processing Techniques and Applications* (pp. 710–716). Las Vegas, Nevada, USA. https://hal.archives-ouvertes.fr/hal-01007650

Garcia, T., Myoupo, J. F., and Seme, D. (2003). A Coarse-Grained Multicomputer Algorithm for the Longest Common Subsequence Problem. In *Proceedings of the Eleventh Euromicro Conference on Parallel, Distributed and Network-Based Processing* (pp. 349–356). Genova, Liguria, Italy. https://doi.org/10.1109/empdp
.2003.1183610

Gauss, C. F. (1866). Theoria Interpolationis Methodo Nova Tractata. In *Carl Friedrich Gauss Werke* (pp. 265–327). Göttingen, Basse-Saxe, Allemagne.

Glover, F. (1989). Tabu Search - Part I. *ORSA Journal on Computing*, 1(3), 190–206. https://doi.org/10.1287/ijoc.1.3.190

Glover, F. (1990). Tabu Search - Part II. *ORSA Journal on Computing*, 2(1), 4–32.
https://doi.org/10.1287/ijoc.2.1.4

Godbole, S. S. (1973). On Efficient Computation of Matrix Chain Products.
*IEEE Transactions on Computers*, 100(9), 864–866. https://doi.org/10.1109/
tc.1973.5009182

Goudreau, M. W., Lang, K., Rao, S. B., Suel, T., and Tsantilas, T. (1999). Portable and Efficient Parallel Computing Using the BSP Model. *IEEE Transactions on Computers*, 48(7), 670–689. https://doi.org/10.1109/12.780876

Grama, A., Gupta, A., Karypis, G., and Kumar, V. (2003). *Introduction to Parallel Computing* (2nd ed.). Addison Wesley.

Guibas, L. J., Kung, H. T., and Thompson, C. D. (1979). Direct VLSI Implementation of Combinatorial Algorithms. In *Proceedings of the Caltech Conference On Very Large Scale Integration* (pp. 509–525). Pasadena, California, USA.
https://core.ac.uk/reader/9412580

Hager, G., and Wellein, G. (2010). *Introduction to High Performance Computing for Scientists and Engineers* (1st ed.). CRC Press.

Heideman, M. T., Johnson, D. H., and Burrus, C. S. (1984). Gauss and the History of the Fast Fourier Transform. *IEEE ASSP Magazine*, 1(4), 14–21. https://doi.org/10.1109/massp.1984.1162257

Higa, D. R., and Stefanes, M. A. (2012). A Coarse-Grained Parallel Algorithm for the Matrix Chain Order Problem. In *Proceedings of the 2012 Symposium on High Performance Computing* (pp. 1–8). Orlando, Florida, USA. https://doi.org/10.5555/2338816.2338817

Hill, J. M., McColl, B., Stefanescu, D. C., Goudreau, M. W., Lang, K., Rao, S. B., ... Bisseling, R. H. (1998). BSPLib: The BSP Programming Library. *Parallel Computing*, 24(14), 1947–1980. https://doi.org/10.1016/s0167-8191(98)00093-3

Hu, T. C., and Shing, M. T. (1982). Computation of Matrix Chain Products. Part I.