next up previous
Next: 2.1 Dilated butterflies Up: A Parallel Algorithm for Previous: 1 Introduction

2 Butterflies and Multibutterflies


An example of an 8-input butterfly network is illustrated in Figure 1. The nodes in this graph represent switches, and the edges represent wires. Each node in the network has a distinct label tex2html_wrap_inline587 , where r is the row, and l is the level. In a butterfly with N inputs, the row is a tex2html_wrap_inline595 -bit binary number and the level is an integer between 0 and tex2html_wrap_inline599 . The nodes on level 0 and tex2html_wrap_inline603 are called the inputs and outputs, respectively. For tex2html_wrap_inline605 , a node labeled tex2html_wrap_inline607 is connected to nodes tex2html_wrap_inline609 and tex2html_wrap_inline611 , where tex2html_wrap_inline613 denotes r with bit l complemented (bit 0 is the most significant, bit tex2html_wrap_inline621 the least).

In a butterfly, messages are typically sent from the switches on level 0, called the inputs, to those on level tex2html_wrap_inline625 , called the outputs. In a one-to-one routing problem, each input is the origin of at most one message, and each output is the destination of a most one message. One-to-one routing is also called permutation routing.

Figure 1: An 8-input butterfly network.

Bruce Maggs
Mon Jul 22 19:56:03 EDT 1996