The diagram above shows a SPMD solution. All four processes are running the same
three-step program, processing different data. 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. The green points represent
locations where there is an image, the black points where there is not. The layout
on the left shows a 2-D block decomposition, on the right a 1-D block decomposition.
Data decomposition:
- Domain characteristics
- Large multidimensional matrix encoding location and color
- Homogeneous members
- All points require the same amount of calculation.
- The value calculated for each point depends on neighboring values
-
For example, a lone green point (not shown) can be identified as "noise", rather than
as part of the pattern, by recognizing that it is surrounded by black points.
- Goals for domain decomposition
- Balance computational load
- Minimize and regularize communication between processes
- 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.
- When deciding upon a decomposition geometry, the communication pattern must be considered
-
In this example, processes need to exchange their outer rows and columns with neighboring processes.
In the 2-D decomposition shown above, each process has 8 + 6 = 14 edge points which will need to be
communicated. In the 1-D decomposition, p1 and p4 each have 12 edge points, and the middle processes
have 12 + 12 = 24. Assuming communications can occur in parallel, the 2D decomposition will require
less communication for each iteration.
- Higher dimension decompositions are generally preferable,
because they minimize the surface-to-volume ratio of domains.
- What if domain members are not homogeneous?
- No simple decomposition is ideal
-
If the green points require more computation than the black, then the 1-D decomposition
is slightly more unbalanced than the 2-D.
- More sophisticated methods are needed to decompose the image optimally
