Next: 1.3 Randomly-wired splitter networks Up: 1 Introduction Previous: 1.1 Dilated butterflies

## 1.2 Splitter networks

Butterfly and dilated butterfly networks belong to a larger class of networks that are often referred to as splitter networks. The switches on each level of a splitter network can be partitioned into blocks. All of the switches on level 0 belong to the same block. On level 1, there are two blocks, one consisting of the switches that are in the upper rows, and the other consisting of the switches that are in the lower rows. In general, the switches in a block B of size on level l have neighbors in two blocks, and , on level l+1, where u stands for upper and l for lower. The upper block, , contains the switches on level l+1 that are in the same rows as the upper switches of B. The lower block, , consists of the switches that are in the same rows as the lower switches of B. The edges from B to are called the up edges, and those from B to are called the down edges. The three blocks, B, , and , and the edges between them are collectively called a splitter. The switches in B are called the splitter inputs, and those in and are called the splitter outputs. In a splitter network with multiplicity d, each splitter input is incident to d outgoing up edges and d outgoing down edges, and each splitter output is incident to 2d incoming edges. In a d-dilated butterfly, the d up (and d down) edges incident to each splitter input all lead to the same splitter output, but this need not be the case in general. For example, we have illustrated an 8-input splitter network with multiplicity 2 in Figure 2.

Figure 2: An 8-input splitter network with multiplicity 2.

In a splitter network, each input and output are connected by a single logical (up-down) path through the blocks of the network. For example, Figure 3 shows the logical path from any input to output 011. In a butterfly, this logical path specifies a unique path through the network, since only one up and one down edge emanate from each switch. (In fact, a splitter network with multiplicity one is very similar to a delta network [17].) In a general splitter network with multiplicity d, however, each switch will have d up and d down edges, and each step of the logical path can be taken on any one of d edges. Hence, one logical path can be realized by a myriad of physical paths in a general splitter network.

Figure 3: The logical path from any input to output 011.

Next: 1.3 Randomly-wired splitter networks Up: 1 Introduction Previous: 1.1 Dilated butterflies

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