A Generalized Theory Based on the Turn Model for Deadlock-Free Irregular Networks

Ryuta KAWANO  Ryota YASUDO  Hiroki MATSUTANI  Michihiro KOIBUCHI  Hideharu AMANO  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E103-D   No.1   pp.101-110
Publication Date: 2020/01/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.2018EDP7367
Type of Manuscript: PAPER
Category: Computer System
Keyword: 
interconnection networks,  deadlock-free routing algorithm,  high performance computing,  irregular networks,  virtual channels,  

Full Text: PDF(1.6MB)>>
Buy this Article




Summary: 
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.