# Efficient Algorithms for the Maximum Sum Problems
## 5 Parallel Algorithm for MCS
```
1:for all\(1\leq i,j\leq n\) in parallel do
2:\(M[i][j]\gets a[i][j]\)
3:endfor
4:for\(k\gets 1\) to \(n\)do
5:for all\(1\leq i,j\leq n\) in parallel do
6:\(M[i][j]\leftarrow\mathbb{MAX}\{M[i-1][j],M[i][j]\}\)
7:endfor\(\triangleright\) Find the maximum in the same column
8:endfor
9:for\(k\gets 1\) to \(n\)do
10:for all\(j\) in parallel do
11:\(M[n][j]\leftarrow\mathbb{MAX}\{M[n][j-1],M[n][j]\}\)
12:endfor\(\triangleright\) Find the maximum in the \(n\)-th row
13:endfor\(\triangleright\)\(M[n][n]\) is the maximum

## 6 Computation of the Boundary

So far, we computed the maximum sum of the \(WN\)-shape. For practical purposes, we sometimes need the shape itself. This problem was solved by [PERSON] (1966) for the sequential algorithm (Algorithm 11). We show how the idea works in our parallel situation. For simplicity, we only show the boundary computation of the \(W\)-shape. We prepare the array \(store\_d[i][k][j]\) to memorize the direction from which the algorithm took one of Case 1, Case 2 or Case 3. This part of enhancement in Algorithm 9 is shown below. Figure 8:3 Figure 8:4 Figure 8:5

Let array \(boundary[i][j]=1\), if \((i,j)\) is on the boundary, and zero otherwise. Let \((i,k,j)\) denote the \(j\)-th column from position \(k\) to position \(i\), to represent the anchor column of some \(W\)-shape. Suppose the anchor column of the maximum \(W\)-shape after Algorithm 9 is \((i_{0},k_{0},j_{0})\). The following sequential algorithm goes backward from \((i_{0},k_{0},j_{0})\) guided by the data structure \(store\_d[i][k][j]\). The correctness of the algorithm is obvious. The time \(O(n)\) can be shown as follows. ```
1:\(i\gets i_{0},j\gets j_{0},k\gets k_{0}\)
2:while\(j>0\) and \(W[i][k][j]>0\)do
3:\(boundary[i][j]\gets 1\)
4:\(boundary[k][j]\gets 1\)
5:\(D\gets store\_d[i][k][j]\)
6:ifD=1 then
7:\(j\gets j-1\)
8:elseifD=2 then
9:\(i\gets i-1\)
10:elseifD=3 then
11:\(k\gets k+1\)
12:endif
13:endwhile
```
**Algorithm 11** Computing the boundary. The time is proportional to the number of changes on indices \(i\), \(j\) and \(k\). The index \(j\) can be reduced at most \(n\) times. For \(i\) and \(k\), we observe \(i-k\) decreases whenever \(i\) or \(k\) changes, resulting in \(O(n)\) time for \(i\) and \(k\). The \(O(n)\) time for the boundary can be absorbed in \(O(n)\) time of Algorithm 9. It will be easy to organize parallel computation of tracing back over array \(store\_d[i][k][j]\) by the mesh architecture. Figure 8:6 Maximum finding in 2D mesh. For example, we can convert the array index \(j\) to a processor index \(j\) and use a one-dimensional mesh architecture as shown below (Algorithm 12). This version has \(O(n)\) time, which provides no gain time-wise, but the \(O(n^{3})\) space requirement on a single processor can be eased. ```
1:receive \((i,k)\)
2:while\(j>0\) and \(W[i][k]>0\)do
3:\(boundary[i][j]\gets 1\)
4:\(boundary[k][j]\gets 1\)
5:\(D\gets store\_d[i][k]\)
6:ifD=1 then
7: send \((i,k)\)-to \(j-1\)-th processor
8:elseifD=2 then
9:\(i\gets i-1\)
10:elseifD=3 then
11:\(k\gets k+1\)
12:endif
13:endwhile Main
14:for\(1\leq j\leq n\) in parallel do send \((i_{0},k_{0})\) to \(j_{0}\)-th processor
15:endfor
```
**Algorithm 12** Computing the boundary; \(j\)-th cell. ## 7 Implementation

We implemented Algorithm 9 on the Blue Gene/P computer under the MPI/Parallel C program environment. There were many practical issues to be considered. We summarize just three issues here as representatives. Firstly, we cannot assume that each cell knows its own position within the mesh array. Depending on the architecture, additional computation is required for each cell to gather this information. Within the MPI environment, we can let each \(cell(i,j)\) know its position \((i,j)\) by the system call \"MPI_Cart_coords()\". The second issue is synchronization. We assumed the corresponding statements in all cells are executed in a synchronized manner. If we remove this assumption, that is if the execution proceeds in an asynchronous manner, the algorithm loses its correctness.