Hardware Reference
In-Depth Information
illustrated in Fig. 8-31. Here we have connected eight CPUs to eight memories
using 12 switches. More generally, for
n
CPUs and
n
memories we would need
log
2
n
stages, with
n
/2 switches per stage, for a total of (
n
/2) log
2
n
switches,
which is a lot better than
n
2
crosspoints, especially for large values of
n
.
3 Stages
CPUs
Memories
000
000
1A
2A
3A
b
b
001
001
b
010
010
1B
2B
3B
011
011
b
100
100
1C
2C
3C
101
110
101
110
a
a
1D
2D
3D
111
111
a
a
Figure 8-31.
An omega switching network.
The wiring pattern of the omega network is often called the
perfect shuffle
,
since the mixing of the signals at each stage resembles a deck of cards being cut in
half and then mixed card-for-card. To see how the omega network works, suppose
that CPU 011 wants to read a word from memory module 110. The CPU sends a
READ message to switch 1D containing 110 in the
Module
field. The switch takes
the first (i.e., leftmost) bit of 110 and uses it for routing. A 0 routes to the upper
output and a 1 routes to the lower one. Since this bit is a 1, the message is routed
via the lower output to 2D.
All the second-stage switches, including 2D, use the second bit for routing.
This, too, is a 1, so the message is now forwarded via the lower output to 3D. Here
the third bit is tested and found to be a 0. Consequently, the message goes out on
the upper output and arrives at memory 110, as desired. The path followed by this
message is marked in Fig. 8-31 by the letter
a
.
As the message moves through the switching network, the bits at the left-hand
end of the module number are no longer needed. They can be put to good use by
recording the incoming line number there, so the reply can find its way back. For
path
a
, the incoming lines are 0 (upper input to 1D), 1 (lower input to 2D), and 1
(lower input to 3D), respectively. The reply is routed back using 011, only reading
it from right to left this time.
While all this is going on, CPU 001 wants to write a word to memory module
001. An analogous process happens here, with the message routed via the upper,
upper, and lower outputs, respectively, marked by the letter
b
. When it arrives, its
