Butterfly as Multistage Interconnection Network p Processors log ,p Columns of 2-by-2 Switche Memory Banks bgP+IColumsof2by-2SwitThes 0000 0000 000 0001 000 001 0010 0010 010_2 0011 0011011 0100gC 0100 100 0101匚5 0101吕101-5 0110 0110 110[6 0111 0111 1000 8■1000 0[0 1001 a1001 1010[ 1010 010 1011〖1 1011 011[3 100 1100 100[z 1101[13 L121101 1110[z z41110 110 1111[151 F161111 111 Fig. 6. 9 EXample of a multistage Fig. 15.8 Butterfly network memory access network used to connect modules that are on the same side Generalization of the butterfly network High-radix or m-ary butterfly, built of m x m switches Has mq rows and q+ 1 columns( q if wrapped) Fa2010 Parallel Processing, Low-Diameter Architectures Slide 28Fall 2010 Parallel Processing, Low-Diameter Architectures Slide 28 Butterfly as Multistage Interconnection Network Fig. 6.9 Example of a multistage memory access network Generalization of the butterfly network High-radix or m-ary butterfly, built of m  m switches Has mq rows and q + 1 columns (q if wrapped) 0 1 2 3 p Processors log p Columns of 2-by-2 Switches p Memory Banks 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1 5 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1 5 2 Fig. 15.8 Butterfly network used to connect modules that are on the same side