16.3 Parallelism 547(^1234)
3
2
1
4
Figure 16.3. A crossbar switch connecting four processors. Each processor has
two I/O ports and these are connected together via the crossbar switch. Denoting
by (i,j) a connection fromitoj, the switch configuration shown is (1,4), (2,1),
(3,3), (4,2).
usingswitches. An example of an architecture with switches is acrossbar switch,
shown in Figure 16.3. On each row and on each column, only a single switch may
be connected – in this way binary connections are possible for any pair-partitioning
of the set of processors.
Another way to interconnect processors is to link them together in a grid or chain,
where each processor can communicate with its nearest neighbours on the grid or
chain. Usually, the grids and chains are periodic, so that they have the topology of
a ring or a torus. Rings and two- and three-dimensional tori have the advantage that
they arescalable: this means that with increasing budget, more processors can be
purchased and the machine performance increased accordingly. Furthermore, some
problems in physics and engineering map naturally onto these topologies, such as
a two- or three-dimensional lattice field theory with periodic boundary conditions
which maps naturally onto a torus of the same dimension.
The problem of sending data from one processor to the other in the most efficient
way is calledrouting. In older machines, this data-traffic, calledmessage passing,
was often a bottleneck for overall performance, but today this is less severe (although
still a major concern).
Another type of network is thebinary hypercube. This consists of 2dnodes, which
are labelled sequentially. If the labels of two nodes differ by only one bit, they are
connected. The hypercube is shown ford=1 to 4 in Figure 16.4. This network has
many more links than the ones which have essentially a two-dimensional layout,
and the substructures of the hypercube include multi-dimensional grids and trees.
In connection with parallel processors,Amdahl’s lawis often mentioned. This
law imposes an upper limit on the increase in performance of a program by running