THE CROSSED CUBE ARCHITECTURE FOR PARALLEL COMPUTATION

This paper introduces a new interconnection network suitable for massively parallel architectures. The network has the same node and link complexity as the hypercube and has most of its desirable properties including regularity, recursive structure, partitionability, strong connectivity, and ability to simulate other architectures. In other respects the proposed network has better properties: Its diameter is only about half of the diameter of the hypercube. Mean distance between vertices is smaller and it can simulate a hypercube through dilation 2 embedding. After discussing the basic properties of the proposed network, optimal routing and broadcasting algorithms are developed. The capabilities of the network as an SIMD architecture are demonstrated by giving examples for semigroup computations, matrix multiplication, and sorting. Each of these algorithms requires only about half the number of communication steps compared to their hypercube implementations. Variations of the basic architecture are discussed and it is shown that by introducing simple switches to certain links, a dynamic architecture can be obtained which can be configured into a hypercube topology whenever it is better for a computation. Alternatively, the proposed architecture can be obtained from a hypercube topology by introducing switches to a subset of links. Furthermore, the dynamic reconfiguration capability of the system also improves the embedding properties of the hypercube.