Dim0 Dim 1 Dim 2 Dim 3 Structure of Butterfly Networks Dim 1 Dim Dim 2 Switching these two row pairs converts this to 2 the ori ginal butterfly network Changing the order of stages a butterfly is the equi valent to a relabel ing of the rows(in this example, row xyz becomes row xzy 1○ Fig 15.5 Butterfly network with permuted dimensions The 16-row butterfly network Fa2010 Parallel Processing, Low-Diameter Architectures Slide 26Fall 2010 Parallel Processing, Low-Diameter Architectures Slide 26 Structure of Butterfly Networks 0 1 2 3 4 5 6 7 Dim 0 Dim 1 Dim 2 0 1 2 3 Dim 3 8 9 10 11 12 13 14 15 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 4 The 16-row butterfly network. Fig. 15.5 Butterfly network with permuted dimensions. 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 Dim 1 Dim 0 Dim 2 0 1 2 3 Switching these two row pairs converts this to the original butterfly network. Changing the order of stages in a butterfly is thus equi valent to a relabeling of the rows (in this example, row xyz becomes row xzy)