PERFORMANCE ANALYSIS OF MESH INTERCONNECTION NETWORKS WITH DETERMINISTIC ROUTING

This paper develops detailed analytical performance models for k-ary n-cube networks with single-flit or infinite buffers, wormhole routing, and the nonadaptive deadlock-free routing scheme proposed by Dally and Seitz. In contrast to previous performance studies of such networks, the system is modeled as a closed queueing network that 1) includes the effects of blocking and pipelining of messages in the network, 2) allows for arbitrary source-destination probability distributions, and 3) explicitly models the virtual channels used in the deadlock-free routing algorithm. The models are used to examine several performance issues for 2-D networks with shared-memory traffic. Some results obtained are: 1) when processors are allowed to have multiple outstanding requests, system performance is bandwidth-limited, and hence network performance does not scale well with increasing system size; 2) communication locality improves system efficiency, but a very high level of locality is needed in order for system performance to scale well; 3) in contrast to previous hot-spot studies for indirect networks that assume nonblocking processors, this study finds that significant tree-saturation does not occur, even in the presence of severe hot-spots in systems with up to four outstanding requests per processor; and 4) at some plausible system operating points, there is a perceptible difference in the efficiencies of processors at different locations in the mesh because of asymmetric loads on the virtual channels by the deadlock avoidance algorithm. These results should prove useful for engineering high-performance systems based on low-dimensional k-ary n-cube networks.