An effective design of deadlock-free routing algorithms based on 2D turn model for irregular networks

Akiya Jouraku, Michihiro Koibuchi, Hideharu Amano

Research output: Contribution to journalArticlepeer-review

27 Citations (Scopus)


System area networks (SANs), which usually accept arbitrary topologies, have been used to connect hosts in PC clusters. Although deadlock-free routing is often employed for low-latency communications using wormhole or virtual cut-through switching, the interconnection adaptivity introduces difficulties in establishing deadlock-free paths. An up*/down* routing algorithm, which has been widely used to avoid deadlocks in irregular networks, tends to make unbalanced paths as it employs a one-dimensional directed graph. The current study introduces a two-dimensional directed graph on which adaptive routings called left-up first turn (L-turn) routings and right-down last turn (R-turn) routings are proposed to make the paths as uniformly distributed as possible. This scheme guarantees deadlock-freedom because it uses the turn model approach, and the extra degree of freedom in the two-dimensional graph helps to ensure that the prohibited turns are well-distributed. Simulation results show that better throughput and latency results from uniformly distributing the prohibited turns by which the traffic would be more distributed toward the leaf nodes. The L-turn routings, which meet this condition, improve throughput by up to 100 percent compared with two up*/down*-based routings, and also reduce latency.

Original languageEnglish
Pages (from-to)320-333
Number of pages14
JournalIEEE Transactions on Parallel and Distributed Systems
Issue number3
Publication statusPublished - 2007 Mar


  • Adaptive routing
  • Deadlock avoidance
  • Interconnection networks
  • Irregular topologies
  • PC clusters
  • System area networks
  • Turn model

ASJC Scopus subject areas

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


Dive into the research topics of 'An effective design of deadlock-free routing algorithms based on 2D turn model for irregular networks'. Together they form a unique fingerprint.

Cite this