Cost-performance tradeoffs for interconnection networks

Clyde P. Kruskal, Marc Snir

Research output: Contribution to journalArticle

Abstract

A major component of a large-scale parallel computer is the interconnection network that connects processors to memories in a shared-memory machine, or processors to processors in a multicomputer. This paper formally studies the relationship between network topology and network performance. Rectangular banyan networks are shown to provide maximum bandwidth/cost ratio for symmetric traffic. For their cost, contracting banyan networks are shown to provide maximum bandwidth up to a constant factor for semisymmetric traffic. For a restricted class of networks, contracting banyan networks are shown to provide exactly maximum bandwidth for semisymmetric traffic. Rectangular banyan networks are shown to provide optimal delay-to-cost tradeoffs for symmetric traffic. It is shown that, in many situations, optimal bandwidth is achieved by using a unique path to route information between each input-output pair.

Original languageEnglish (US)
Pages (from-to)359-385
Number of pages27
JournalDiscrete Applied Mathematics
Volume37-38
Issue numberC
DOIs
StatePublished - Jul 15 1992
Externally publishedYes

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Cost-performance tradeoffs for interconnection networks'. Together they form a unique fingerprint.

  • Cite this