Performance Analysis of Mesh Interconnection Networks with Deterministic Routing

Vikram S. Adve, Mary K. Vernon

Research output: Contribution to journalArticlepeer-review


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 routine 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.

Original languageEnglish (US)
Pages (from-to)225-246
Number of pages22
JournalIEEE Transactions on Parallel and Distributed Systems
Issue number3
StatePublished - Mar 1994
Externally publishedYes


  • Approximate mean value analysis
  • closed queue
  • finite buffers
  • hot-spots
  • ing networks
  • k-ary n-cube networks
  • mesh networks
  • multiprocessor interconnection networks
  • near-neighbor communication
  • performance analysis
  • wormhole routing

ASJC Scopus subject areas

  • Signal Processing
  • Hardware and Architecture
  • Computational Theory and Mathematics


Dive into the research topics of 'Performance Analysis of Mesh Interconnection Networks with Deterministic Routing'. Together they form a unique fingerprint.

Cite this