Next: 1.1 Dilated butterflies Up: Fast Algorithms for Routing Previous: Fast Algorithms for Routing

# 1 Introduction

Networks derived from hypercubes form the architectural basis of most parallel computers, including machines such as the BBN Butterfly, the Connection Machine, the IBM RP3 and GF11, the Intel iPSC, and the NCUBE. The butterfly, in particular, is quite popular, and has been demonstrated to perform reasonably well in practice. An example of an 8-input butterfly 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).

The primary duty of the network in a parallel machine is to route messages between its processors and/or memory modules. 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. All of the algorithms discussed in this paper route messages in a store-and-forward fashion. A store-and-forward algorithm treats messages as indivisible objects. At each step, a message can either remain at a switch or move in its entirety from one switch to another across an edge, provided that no other messages use the same edge at that step. Store-and-forward routing is also called packet switching, and messages are often referred to as packets. A related paper [2] extends the results of this paper for a different method of routing called circuit switching.

One of the nice features of the butterfly is that there is a simple algorithm for finding a path of length from any input to any output. Upon reaching switch , , a packet with destination compares r with R. If they are equal, the packet takes the edge to . If not, it takes the edge to . One problem with the butterfly is that this path is unique. As a consequence, if some switch or edge along the unique path from input i to output j (say) becomes congested or fails, then communication between input i and output j will be disrupted.

Figure 1: An 8-input butterfly network.

Next: 1.1 Dilated butterflies Up: Fast Algorithms for Routing Previous: Fast Algorithms for Routing

Bruce Maggs
Mon Jul 22 18:45:42 EDT 1996