Parallel Computation - Models of Computation: Exploring the Power of Computing - page 310

oblivious algorithm is one that sends a message from the current network node to the neigh-
boring node that is closest to the destination.

7.8.2 Global Routing Networks
In a global routing network , knowledge of the destinations of all messages is used to set the
network switches and select paths for the messages to follow. A global permutation-routing
network realizes permutations of the destination addresses. We now give an example of such a
network, the Benes permutation network.
A permutation network is constructed of two-input, two-output switches. Such a switch
either passes its inputs, labeled A and B, to its outputs, labeled X and Y, or it swaps them. That
is, the switch is set so that either X = AandY = BorX = BandY = A. A permutation
network on n inputs and n outputs is a directed acyclic graph of these switches such that for
each permutation of the n inputs, switches can be set to create n disjoint paths from the n
inputs to the n outputs.
A Benes permutation network isshowninFig. 7.20 . This graph is produced by con-
necting two copies of an FFT graph on 2 k− 1 inputs back to back and replacing the nodes
by switches and edges by pairs of edges. (FFT graphs are described in Section 6.7.3 .) It fol-
lows that a Benes permutation network on n inputs can be realized by a normal algorithm

P 8

P 4

1

1

2

2

3

3

4

4

5
6

5
6

7
8

7
8

P 8

9

9

10

10

11

11

12

12

13

13

14

14

15
16

15
16

Figure 7.20 ABenes permutation network.