A Closed Form Formula For The Normalized Throughput of Unbuffered Multistage Interconnection Networks

Jin Jye Chou, Tsern-Huei Lee*

*Corresponding author for this work

Research output: Contribution to journalArticle

Abstract

The normalized throughput of an unbuffered multistage interconnection network (MIN) under the uniform traffic model can be computed iteratively [6] or recursively [7]. However, the asymptotic performance of such networks as the number of stages increases cannot be determined using these procedures. A closed form formula for the normalized throughput of unbuffered MINs is presented in this paper. The new formula is proved by mathematical induction on the number of stages. The major advantage of the closed form formula is that the asymptotic performance of unbuffered square MINs can be easily determined. The formula is generalized to unbuffered MINs in the presence of nonidentical input rates and non-square switch size.

Keywords

  • Asymptotic performance
  • Multistage interconnection networks
  • Normalized throughput

Fingerprint Dive into the research topics of 'A Closed Form Formula For The Normalized Throughput of Unbuffered Multistage Interconnection Networks'. Together they form a unique fingerprint.

  • Cite this