The Omega network shown in Figure F.11 on page F-31 consists of three columns of four switches, each with two inputs and two outputs. Each switch can be set to straight, which connects the upper switch input to the upper switch output and the lower input to the lower output, and to exchange, which connects the upper input to the lower output and vice versa for the lower input. For each column of switches, label the inputs and outputs 0, 1, . . . , 7 from top to bottom, to correspond with the numbering of the processors.
a. When a switch is set to exchange and a message passes through,w hat is the relationship between the label values for the switch input and output used by the message? (Hint Think in terms of operations on the digits of the binary representation of the label number.)
b. Between any two switches in adjacent columns that are connected by a link, what is the relationship between the label of the output connected to the input?
c. Based on your results in parts (a) and (b), design and describe a simple routing scheme for distributed control of the Omega network. A message will carry a routing tag computed by the sending processor. Describe how the processor computes the tag and how each switch can set itself by examining a bit of the routing tag.