Such scheme works whenever the data dependencies in the computation are fixed and simple. In our case, they are described by a four point stencil. Therefore, a one-column overlap is needed, for a 1D partition. We shall partition array A with one column overlap. No such overlap is required for array B .
Figure shows the extra columns in A and how data is transfered for each iteration.
We shall use an algorithm where all values needed from a neighbor are brought in one message. The resulting parallel algorithm is shown below. Thus, one achieves the communication pattern of Example . The modified main loop is shown below. We shall later see simpler ways of dealing with this problem.