Designing High-Performance Interconnection Networks with Host-Switch Graphs

Ryota Yasudo, Michihiro Koibuchi, Koji Nakano, Hiroki Matsutani, Hideharu Amano

Research output: Contribution to journalArticlepeer-review

6 Citations (Scopus)


This paper aims at establishing a method for designing high-performance network topologies to bridge a gap between theoretical and practical studies. To this end, we present a novel graph called a host-switch graph, which consists of host vertices and switch vertices with maximum degree 1 and r, respectively. This graph represents a network topology of a practical parallel/distributed computer system with host computers connected by r-port switches. We discuss important metrics for designing high-performance interconnection networks: the host-to-host average shortest path length (h-ASPL) and the bisection width (BiW). In particular, we explore a method for constructing host-switch graphs with low h-ASPL and high BiW that connect the fixed number of hosts via any number of r-port switches. We demonstrate that the number of switches that provides the minimum h-ASPL can mathematically be approximated, and the minimum number of switches that provides a certain BiW can experimentally be approximated. On the basis of the approximations, we propose a randomized algorithm for searching host-switch graphs. We then apply the graphs to interconnection networks and compare them with typical network topologies. As compared with the torus, the dragonfly, and the fat-tree, our networks attain higher performance and smaller power and costs.

Original languageEnglish
Article number8428449
Pages (from-to)315-330
Number of pages16
JournalIEEE Transactions on Parallel and Distributed Systems
Issue number2
Publication statusPublished - 2019 Feb 1


  • Network topology
  • average shortest path length
  • bisection width
  • interconnection network
  • optimization

ASJC Scopus subject areas

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


Dive into the research topics of 'Designing High-Performance Interconnection Networks with Host-Switch Graphs'. Together they form a unique fingerprint.

Cite this