Mathematics for Computer Science

10.9. Bene ̆s Network 287

⎧

⎨

F

⎨

⎩

2 n Fn

⎩ 2 n1 tt

⎧

⎨

F

2 n+^1 outputs

⎨

⎩

2 n Fn

F

newinputs

⎩

Fn+1

Figure 10.2 FnC 1 , the Butterfly Net switches with 2 nC^1 inputs and outputs.

gestion is

p

NifNis an even power of 2 and

p

N=2ifNis an odd power of 2. A

simple proof of this appears in Problem10.8.

Let’s add the butterfly data to our comparison table:

network diameter switch size # switches congestion

complete binary tree 2 logNC 2 3  3 2N 1 N

2-D array 2N 2  2 N^22

butterfly logNC 2 2  2 N.log.N/C1/

p

Nor

p

N=2

The butterfly has lower congestion than the complete binary tree. And it uses fewer

switches and has lower diameter than the array. However, the butterfly does not

capture the best qualities of each network, but rather is a compromise somewhere

between the two. So our quest for the Holy Grail of routing networks goes on.

10.9 Bene ̆s Network

In the 1960’s, a researcher at Bell Labs named Benes had a remarkable idea. He ̆

obtained a marvelous communication network with congestion 1 by placingtwo

butterflies back-to-back. This amounts to recursively growingBene ̆s netsby adding