A generalized theory based on the turn model for deadlock-free irregular networks

Ryuta Kawano, Ryota Yasudo, Hiroki Matsutani, Michihiro Koibuchi, Hideharu Amano

Research output: Contribution to journalArticlepeer-review


Recently proposed irregular networks can reduce the latency for both on-chip and off-chip systems with a large number of computing nodes and thus can improve the performance of parallel applications. However, these networks usually suffer from deadlocks in routing packets when using a naive minimal path routing algorithm. To solve this problem, we focus attention on a lately proposed theory that generalizes the turn model to maintain the network performance with deadlock-freedom. The theorems remain a challenge of applying themselves to arbitrary topologies including fully irregular networks. In this paper, we advance the theorems to completely general ones. Moreover, we provide a feasible implementation of a deadlock-free routing method based on our advanced theorem. Experimental results show that the routing method based on our proposed theorem can improve the network throughput by up to 138 % compared to a conventional deterministic minimal routing method. Moreover, when utilized as the escape path in Duato’s protocol, it can improve the throughput by up to 26.3 % compared with the conventional up*/down* routing.

Original languageEnglish
Pages (from-to)101-110
Number of pages10
JournalIEICE Transactions on Information and Systems
Issue number1
Publication statusPublished - 2020


  • Deadlock-free routing algorithm
  • High performance computing
  • Interconnection networks
  • Irregular networks
  • Virtual channels

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture
  • Computer Vision and Pattern Recognition
  • Electrical and Electronic Engineering
  • Artificial Intelligence


Dive into the research topics of 'A generalized theory based on the turn model for deadlock-free irregular networks'. Together they form a unique fingerprint.

Cite this