   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 , where r is the row, and l is the level. In a butterfly with N inputs, the row is a -bit binary number and the level is an integer between 0 and . The nodes on level 0 and are called the inputs and outputs, respectively. For , a node labeled is connected to nodes and , where denotes r with bit l complemented (bit 0 is the most significant, bit the least).

In a butterfly, messages are typically sent from the switches on level 0, called the inputs, to those on level , 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