# Efficient Algorithms for the Maximum Sum Problems
## 5 Parallel Algorithm for MCS
In MPI, \"MPI_Send()\", \"MPI_Recv()\" and \"MPI_Sendrecv()\" functions are used to perform synchronous blocking communications [14]. As we call these functions in each step, no further mechanisms are necessary to ensure synchronization between cells as the function calls ensure that any given cell cannot progress one or more steps further than the rest. In other words, one cell may reach the end of the given step and tries to move onto the next step before others, but then, the cell must wait for the other cells to reach the same point due to the blocking nature of the MPI communication functions. The third implementation issue is related to the number of available processors. As the number of processors is limited, for large \(n\), we need to have what is called a coarse grain parallel computer. Suppose, for example, we are given a \((1024,1024)\) input array and only 16 processors are available. The input array is divided into sixteen \((256,256)\) sub-arrays, to which the sixteen processors are assigned. Let us call the sub-array for each processor its territory. Each processor simulates one step of Algorithm 8 sequentially. These simulation processes by sixteen processors are done in parallel. At the end of each simulation, the values in the registers on the right and bottom border are sent to the left and top borders of the right neighbour and the lower neighbour, respectively. The simulation of one step takes \(O((n/p)^{2})\) time, and \(2n-1\) steps are carried out, meaning the computing time is \(O(n^{3}/p^{2})\) at the cost of \(O(p^{2})\) processors. When \(p=1\), we hit the sequential complexity of \(O(n^{3})\). If \(p=n\), we have the time complexity of Algorithm 8, which is \(O(n)\). While resolving the third implementation issue, we must again face the second issue of synchronization. For each processor to simulate the parallel computation in its own territory in a coarse-grained implementation, we must take extra care to ensure synchronization between simulated cells within each territory. Specifically, we must double the number of variables, that is we prepare variable \(x_{1}\) for every variable \(x\). Let us associate the space/time index, \((i,j,k)\) with each variable. Let us call \(x(i,j,k)\) the current variable and the variable with indices different by one a neighbour variable. For example, \(sol[i][j]\) in the right-hand side of the assignment statement is a time-wise neighbour, and that at the left-hand side is a current variable. Furthermore, \(column[i-1][j]\) in the right-hand side is a neighbour variable space-wise and time-wise, and so on. If \(x\) is a current variable, change it to \(x_{1}\). If it is a variable of a neighbour, keep it as it is. Let us call the modified program \(P_{1}\). Now, we define \"update\" to be the set of assignment statements of the form \(x\gets x_{1}\). Let \(P\) be a one-dimensional mesh program given by Algorithm 13, which shifts array \(x\) by one place. Let us suppose \(x[0]=0\) and \(x[i]\) are already given. In Algorithm 13, \(x[i]\) is the current variable, and \(x[i-1]\) is a neighbour variable space-wise and time-wise. An asynchronous computer can make all values zero. For the intended outcome, we perform \(P_{1}\), given by Algorithm 14, which includes \"synchronize\" and \"update\". ```
1:for all\(i\) in parallel do
2:\(x[i]\gets x[i-1]\)
3:endfor
4:endfor
```
**Algorithm 14** Program \(P_{1}\). For our mesh algorithm, Algorithm 8, omitting the initialization part, we make the program of the form that is given by Algorithm 15. ```
1:for\(k\gets 1\) to \(2n-1\)do
2:\(P_{1}\)
3: synchronize
4: update
5:endfor
```

**Algorithm 15** Synchronization for coarse grain. Algorithm 9 was executed on Blue Gene/P with up to 1024 cores. For the software side, the programming environment of MPI and the parallel C compiler, mpixlc, were used with Optimization Level 5. The results are shown in Figure 8:7 Arrays of size \((n,n)\) containing random integers were tested.