The dashed horizontal lines represent barriers or synchronization points. Each process must complete that step before all processes can proceed to the next step. The sketches below show an image that will be processed. Technique Block decomposition Assign each process a contiguous set of points. Since each point requires the same amount of work, points should be divided evenly between processes.
Load balancing is static since the division of work is determined at compile time.
The communication pattern must be considered when deciding upon a decomposition geometry. Higher dimension decompositions are generally preferable, since they minimize surface to volume ratio. Processes will need to exchange their outer rows and columns with neighboring processes. In the 2-D decomposition shown above, each process has 13 edge points which will need to be communicated, for a total of 52 points. In the 1-D decomposition, p1 and p4 each have 12 edge points, and the middle processes have 24, for a total of 72.