# Efficient Algorithms for the Maximum Sum Problems
## 5 Parallel Algorithm for MCS
The times for generating uniformly-distributed random numbers, as well as loading the data onto each processor were not included in the time measurement. On Blue Gene/P, the mesh architecture can be configured into a 2D mesh or 3D mesh. The time taken to configure the mesh into a 2D mesh array for our algorithm was included in the time measurement. As we can see from the table, for small \(n\), the configuration time dominates, and increasing the number of processors does not result in a decrease in the execution time. As the size of the input array increases, however, we can see noticeable improvements in the execution times with a larger number of processors. Note that we were unable to execute the program under certain configurations as shown by 'x' in Figure 8:8 This was due to memory requirements. With large \(n\) and small \(p\), each processor must simulate a very large territory. With each cell in the territory requiring \(O(n)\) memory to store the maximal values of \(W\) and \(N\), the memory requirements can become prohibitive. This highlights the fact that parallelization is required not only to reduce the execution time, but also to handle larger input data. ## 8 Lower Bound

Algorithm 8 for \(W\) is not very efficient, as cells to the right are idling at the early stage. Suppose we are given an input array with the value \(a\) in the top-left cell and \(b\) in the bottom-right cell, while all other value are \(-\infty\). Obviously the solution is \(a\) if \(a>b\), and \(b\) otherwise. The values \(a\) and \(b\) need to meet somewhere. It is easy to see that the earliest possibility is at time \(n-1\). Our algorithm for \(W\) takes \(2n-1\) steps, meaning there is still a gap of \(n\) steps with the lower bound. This is a sharp contrast with the mesh algorithm for MSA (Algorithm 4) that completes in \(n-1\) steps. The role of Algorithm 8 is to establish an \(O(n)\) time for the MCS problem on the mesh architecture. ## 9 Concluding Remarks

We gave an \(O(n)\) time parallel algorithm for solving the MSA and MCS problem with \(n^{2}\) processors and a formal proof for the algorithm to compute the \(W\)-shape, a part of the MCS problem. The formal proof for the \(N\)-shape can be given in a similar way. The formal proof not only ensures correctness, but also clarifies what is actually going on inside the algorithm. The formal proof was simplified by assuming synchronization. The asynchronous version with (synchronize, update) in Section 7 would require about twice as much complexity for verification, since we double the number of variables. Once the correctness of the synchronized version is established, that of the asynchronous version will be acceptable without further verification. It is open whether there is a mesh algorithm for the MCS problem with the \(O(1)\) memory requirement in each cell. Mesh algorithms are inherently easy to implement on an FPGA and, thus, can be considered for practical applications. ## Appendix A Proof for Invariants

In the following, \(sum(k,...,i;j)\) is the sum of array portion \(a[k,...,i][j]\). We assume \(control[i][j-1]=1\). Proof. : For \(\{P(k-1)\}cell(i,j)\{P_{0}(k)\}\): At the beginning of the \(k\)-th iteration, \(control[i][j]=1\) for \(j=0,...,k-1\), equivalently \(control[i][j-1]=1\) for \(j=1,...,k\). \(cell(i,j)\) performs \"\(control[i][j]\gets 1\)\" for \(j=1,...,k\). Thus, we have \(\{P(k-1)\}cell(i,j)\{P_{0}(k)\}\) for \(j=1,...,k\). \begin{table}
\begin{tabular}{l c c c c c} \hline \hline  & \(p^{2}\) = 4 & **16** & **64** & **256** & **1024** \\ \hline \(n=64\) & 0.1069 & 0.0329 & 0.0258 & 0.0251 & 0.0272 \\
128 & 0.8435 & 0.2298 & 0.0989 & 0.1253 & 0.1252 \\
256 & 7.2762 & 1.7506 & 0.4783 & 0.3783 & 0.6088 \\
512 & 64.5455 & 15.8192 & 3.6038 & 1.3141 & 2.9883 \\
1024 & 332.8847 & 137.6626 & 33.9193 & 7.7712 & 7.9303 \\
2048 & x & x & 188.9598 & 87.5153 & 43.5064 \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Time measurements on BG/P(seconds). Proof.