Towards a Synthesis of Direct and Indirect Cube Structures for Multiprocessors

We characterize in this paper the exact structural relationship between the hypercube and the multistage indirect n-cube networks, two popular interconnection structures for multiprocessors. We show that the multistage networks can be viewed as direct connections of nodes (each node being a processor-memory-switch combination) and that all of the performance difference between the two interconnection schemes in a stochastic environment can be attributed to the architecture of their nodes. This relationship is shown to extend to both non-binary networks and redundant path multistage networks, the latter resulting in augmented hypercube topologies. By varying the node architecture we show that there in fact exists a series of structures in between the full direct and indirect schemes with different cost and performance levels. Static performance analyses indicate that for best cost/performance ratios, an intermediate architecture (in between a full direct and a full indirect cube) needs to be chosen.