Parallel Computer Architecture

3.1 Partitioning for Performance 133

Po

p

4

p

8

P«

Pi

p

5

p

9

Pl3

p

2

p

6

Pío

Pl4

Pa

P7J

P11

^M

n

m

«fa »

©ΟΘΟΦΟΟΘΘ

©#·#···#©

Θ···»·##Θ

Θ#·#····Θ

Φ·····ΙΙΟ

0·······Θ

Ο·······0

Θ·##····Θ

ΘΟΟΟΘΘΘΦΘ

Α/Ρ

FIGURE 3.4 The perimeter-to-area relationship of communication to computation

in a two-dimensional domain decomposition. The example shown is for an algorithm

with localized, nearest-neighbor information exchange like the simple equation solver ker-

nel.

Every point on the grid needs information from its four nearest neighbors. Thus, the

darker internal points in processor P

10

's partition do not need to communicate directly with

any points outside th