Express Cubes: Improving the Performance of K-ary n-Cube Interconnection Networks

Interconnection networks are used to pass messages containing data and synchronization information between the nodes of concurrent computers. The messages may be sent between the processing nodes of a message-passing multicomputer or between the processors and memories of a shared-memory multiprocessor. Express cubes are k-ary n-cube interconnection networks augmented by express channels that provide a short path for non-local messages. An express cube combines the logarithmic diameter of an indirect network with the wire-efficiency and ability to exploit locality of a direct network. The insertion of express channels reduces the network diameter and thus the distance component of network latency. Wire length is increased allowing networks to operate with latencies that approach the physical speed-of-light limitation rather than being limited by node delays. Express channels increase wire bisection in a manner that allows the bisection to be controlled independent of the choice of radix, dimension, and channel width. By increasing wire bisection to saturate the available wiring media, throughput can be substantially increased. With an express cube both latency and throughput are wire-limited and within a small factor of the physical limit on performance. Express channels may be inserted into existing interconnection networks using interchanges. No changes to the local communication controllers are required.