# Efficient Algorithms for the Maximum Sum Problems
## 5 Parallel Algorithm for MCS
Rule for if-then statement:  
\[\frac{\{P\wedge B\}S\{Q\},P\wedge\
eg B\Rightarrow Q}{\{P\}}\]  
**if**\(B\)**then**\(S\{Q\}\)  
In our proof, \(P(k-1)\) corresponds to \(P\), \(control[i][j-1]=1\) to \(B\) and \(P(k)\) to \(Q\). Rule for the for-loop:  
\[\frac{\{P(0)\},\{P(k-1)\}S\{P(k)\}}{\{P(0)\}}\]  
**for**\(k=1\)**to**\(n\)**do**\(S\{P(n)\}\)  
This \(P\) represents \(P_{0}\) to \(P_{5}\) in our program. \(S\) is the parallel program \([cell(1)||cell(2)...||cell(n)]\). Each \(cell(i)\) has a few local variables and assignment statements. For an arbitrary array \(x\), we regard \(x[i][j]\) as a local variable for \(cell(i,j)\). A variable from the neighbour, \(x[i-1][j]\), for example, is imported from the upper neighbour. Updated variables are fetched in the next cycle. The proof for each \(\{P(k-1)\}cell(i,j)\{P(k)\}\) for \(P\) is given in Appendix. Theorem 1: _Algorithm 8 is correct. The result is obtained at \(cell(n,n)\) in \(2n-1\) steps._  
Proof: From the Hoare logic rule for the for-loop, we have \(P_{5}(2n-1)\) at the end. \[P_{5}(2n-1)\]  
at  
\[cell(n,n)\]  
\[\Leftrightarrow sol[n][n]\]  
is the maximum sum in  
\[scope[n+n-2n+1,...,n][1,...,n]\]  
Figure 8:0  
is the maximum sum in  
Figure 8:1  
Figure 8:2  
We used array \(W[1..n][1..n]\) to compute the maximum \(W\)-shape. The value of \(W[i][j]\) at \(cell(i,j)\) is ephemeral in the sense that its value changes as computation proceeds. That is, \(W[i][j]\) at time \(k\) holds the maximum \(W\)-shape anchored at column \(a[i+j-k,...,i][j]\), and at the next step, it changes to that value of \(W\) anchored at column \(a[i+j-k-1,...,i][j]\). In order to combine \(W\) and \(N\), we must memorize the maximum \(W\) and the maximum \(N\) for each anchor column. Thus, we need the three-dimensional array \(store\_W\), as well as the array \(store\_N\). Since in the final stage of \(WN\) computation, the same anchor column is added from \(W\) and \(N\), we need to subtract the sum of the anchor column. For that purpose, the sum of anchor column \(a[k,...,i][j]\) is stored in \(store\_column[i][k][j]\). Note that the computation of \(N\) goes from right to left. In Algorithm 9, we provide the complete algorithm that combines \(W\) and \(N\), where \(sol\) is dropped, and the initialization is omitted. The computation of \(W\) and \(N\) takes \(2n-1\) steps, and \(WN\) takes \(n\) steps. Selecting the maximum of \(WN[1..n][1..n]\) can be done in parallel. Algorithm 10 and Figure 9a illustrate how to find the maximum in a 2D mesh in \(2n\) steps, where the maximum can be retrieved at the bottom right corner. If we orchestrate the bidirectional data movement in each of four quarters of the mesh (Figure 9b), so that the maximum of each quarter can meet at the centre for the final selection, it can be done in \(n+1\) steps. Therefore, Algorithm 9 takes total of \(4n\) communication steps. ```
1:for\(k\gets 1\) to \(2n-1\)do
2:for all\(1\leq i,j\leq n\) in parallel do
3:if\(control[i][j-1]=1\)then\(\triangleright\) Compute W from left to right
4:\(column[i][j]\gets column[i-1][j]+a[i][j]\)
5:\(cand_{1}\gets W[i][j-1]+column[i][j]\)
6:\(cand_{2}\gets W[i-1][j]+a[i][j]\)
7:\(cand_{3}\gets old\_W[i][j]+top[i][j]\)
8:\(old\_W[i][j]\gets W[i][j]\)
9:\(W[i][j]\leftarrow\mathbb{MAX}\{cand_{1},cand_{2},cand_{3}\}\)
10:\(store\_column[i][i+j-k][j]\gets column[i][j]\)
11:\(store\_W[i][i+j-k][j]\gets W[i][j]\)
12:\(top[i][j]\gets top[i-1][j]\)
13:\(control[i][j]\gets 1\)
14:endif
15:if\(control[i][j+1]=1\)then\(\triangleright\) Compute N from right to left
16: Mirrored operation of lines 4-13
17:endif
18:endfor
19:endfor
20:for all\(1\leq i,j\leq n\) in parallel do
21:\(WN[i][j]\leftarrow-\infty\)
22:for\(k\gets 1\) to \(i\)do
23:\(anchor\gets store\_column[i][k][j]\)
24:\(WN[i][j]\leftarrow\mathbb{MAX}\{WN[i][j],store\_W[i][k][j]+store\_N[i][k][j]-anchor\}\)
25:endfor
26:endfor
27:endfor
28:Find the maximum of \(WN[1..n][1..n]\) by Algorithm 10
```  
**Algorithm 10** Find the maximum of \(a[1..n][1..n]\) in \(2n\) steps.