# Efficient Algorithms for the Maximum Sum Problems
## 5 Parallel Algorithm for MCS  
We now give a parallel algorithm that corresponds to the sequential algorithm described in Section 3. Algorithm 8 is executed by the cell at the \((i,j)\) grid point. Each \(cell(i,j)\) is aware of its position \((i,j)\). Data flow is from left to right and from top to down. The control signals are fired at the left border and propagate right. When the signal arrives at \(cell(i,j)\), it starts to accumulate the column sum \(column\) and update \(top\), \(W\) and \(sol\). The value of \(W[i][j]\) at time \(k\) is to hold the maximum \(W\)-value based on the anchor column in the \(j\)-th column from position \(i+j-k\) to position \(i\). This is illustrated in Figure 8. The value of \(sol[i][j]\) is to hold the best \(W\)-value obtained at \(cell(i,j)\) so far. The role of \(top\)is to bring down the top value of anchor column to \(cell(i,j)\) in time. The role of \"\(old\_W\)\" is to provide the value of \(W\) one step before, with \(old\_W[i][0]\) being undefined. ```
1:Initialization
2:for all\(0\leq i,j\leq n\) in parallel do
3:\(column[i][j]\gets 0\)
4:\(top[i][j]\gets a[i][j]\)
5:\(control[i][j]\gets 0\)
6:\(W[i][j]\gets 0\)
7:\(old\_W[i][j]\gets 0\)
8:endfor
9:for\(0\leq i\leq n\) in parallel do
10:\(control[i][0]\gets 0\)
11:\(sol[i][0]\leftarrow-\infty\)
12:\(a[i][0]\gets 0\)
13:\(sol[0][i]\leftarrow-\infty\)
14:\(a[0][i]\gets 0\)
15:endfor
```  
**Algorithm 8** Parallel algorithm for \(W\). Main  
```
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
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:\(top[i][j]\gets top[i-1][j]\)
11:\(sol[i][j]\leftarrow\mathbb{MAX}\{sol[i-1][j],sol[i][j-1],sol[i][j],W[i][j]\}\)
12:\(control[i][j]\gets 1\)
13:endif
14:endfor
```  
**Algorithm 9** Parallel algorithm for \(W\). Figure 8: Illustration for Algorithm 8 with position indices \((i,j)\) and time index \(k\). Note that the memory requirement for each cell in Algorithm 8 is constant. When we put \(W\)-shapes and \(N\)-shapes together, however, we need \(O(n)\) space in each cell, as we will explain later on. We assume that all corresponding instructions in all cells are executed in parallel in a synchronized manner. We later make some comments regarding how synchronization is achieved in the actual implementation of the parallel algorithm. We prove the correctness of Algorithm 8 in the framework of Hoare logic [PERSON] (1966) based on a restricted form of that in [PERSON] and [PERSON] and [PERSON] (1966). The latter is too general to cover our problem. We keep the minimum extension of Hoare logic to our mesh architecture. The meaning of [PERSON]'s triple \(\{P\}S\{Q\}\) is that if \(P\) is true before program (segment) \(S\), and if \(S\) halts, then \(Q\) is true after \(S\) stops. The typical loop invariant appears as that for a while-loop; \"while B do S\". Here, \(S\) is a program, and \(B\) is a Boolean condition. If we can prove \(\{P\wedge B\}S\{P\}\), we can conclude \(\{P\}\) while \(B\) does \(S\{P\wedge\sim\)\(B\}\), where  
Parallel assignment rule:  
\[P\Rightarrow Q[y_{1}/x_{1},y_{2}/x_{2},...,y_{n}/x_{n}],\] \[\frac{\{Q[y_{1}/x_{1},y_{2}/x_{2},...,y_{n}/x_{n}]\}cell(i)\{Q\}}{ \{P\}[cell(1)||cell(2)...||cell(n)]\{Q\}}\]  
Other programming constructs such as composition (semi-colon), if-then-else statement, etc., in sequential Hoare logic can be extended to the parallel versions. Those definitions are omitted, but the following rule for the if-then and for-loop for the sequential control structure, which controls a parallel program \(S\) from outside, is needed for our verification purpose.