next up previous

3.4 Topology     continued...

As is the case with the crossbar switch, there are configurations of the butterfly that will allow each processor to connect to a different memory so all processors can be active and no requests are blocked. However, the butterfly is not as flexible as the crossbar, since combinations of requests that are nonblocking in the crossbar are blocking in the butterfly. For example, if the first switch in the first column is in the straight-through configuration because processor P is making a request to memory M, processor P is constrained to communicate with memories 4 through 7 ( through ). With a crossbar P1 would be allowed to connect to M, M, or M without blocking.

Crossbar and butterfly switches have both been used to implement shared memory multiprocessors. Even though there are independent memory modules, there is a single memory space, i.e. an address i generated by one processor refers to the same cell as an address i generated by any other processor. Addresses are not interleaved, though. Instead the memory space is divided into contiguous blocks of equal size. For example, suppose there are 4 memory units and the address space has words. M would hold addresses 0 to 255, M would have 256 to 511, and so on.