ABSTRACT
In Chapter 4 we have developed algorithms on a ring of processors. In this chapter we motivate and demonstrate the use of a more complex logical topology: a two-dimensional (2-D) grid, or grid for short. Figure 5.1(a) shows an example square grid with p = q2 processors. Processors in the corners have only two neighbors, processors on the edges have three, and processors in the middle have four. Processors are indexed by their row and column in the grid, Pi,j , 0 6 i, j < q. One popular variation of the grid topology is obtained by adding loopbacks from edge to edge, forming what is commonly called a 2-D torus, or torus for short, as shown in Figure 5.1(b). In this case every processor belongs to two different rings. As in the case of a ring topology, links can be either unidirectional or bidirectional. Choosing an appropriate flavor of the grid topology is up to the parallel algorithm developer, but we will see that a bidirectional torus proves very convenient and this is the topology we will use by default. For the sake of simplicity we will always assume that the number of processors is a perfect square, leading to square grids. The algorithms presented in this chapter can be adapted to rectangular grids, which often require only more cumbersome index calculations.
