IEICE TRANSACTIONS on Information
A Generalized Theory Based on the Turn Model for Deadlock-Free Irregular Networks
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.
- Publication
- IEICE TRANSACTIONS on Information Vol.E103-D No.1 pp.101-110
- Publication Date
- 2020/01/01
- Publicized
- 2019/10/08
- Online ISSN
- 1745-1361
- DOI
- 10.1587/transinf.2018EDP7367
- Type of Manuscript
- PAPER
- Category
- Computer System
Authors
Ryuta KAWANO
Keio University
Ryota YASUDO
Keio University
Hiroki MATSUTANI
Keio University
Michihiro KOIBUCHI
National Institute of Informatics
Hideharu AMANO
Keio University
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Ryuta KAWANO, Ryota YASUDO, Hiroki MATSUTANI, Michihiro KOIBUCHI, Hideharu AMANO, "A Generalized Theory Based on the Turn Model for Deadlock-Free Irregular Networks" in IEICE TRANSACTIONS on Information,
vol. E103-D, no. 1, pp. 101-110, January 2020, doi: 10.1587/transinf.2018EDP7367.
Abstract: 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.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2018EDP7367/_p
Copy
@ARTICLE{e103-d_1_101,
author={Ryuta KAWANO, Ryota YASUDO, Hiroki MATSUTANI, Michihiro KOIBUCHI, Hideharu AMANO, },
journal={IEICE TRANSACTIONS on Information},
title={A Generalized Theory Based on the Turn Model for Deadlock-Free Irregular Networks},
year={2020},
volume={E103-D},
number={1},
pages={101-110},
abstract={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.},
keywords={},
doi={10.1587/transinf.2018EDP7367},
ISSN={1745-1361},
month={January},}
Copy
TY - JOUR
TI - A Generalized Theory Based on the Turn Model for Deadlock-Free Irregular Networks
T2 - IEICE TRANSACTIONS on Information
SP - 101
EP - 110
AU - Ryuta KAWANO
AU - Ryota YASUDO
AU - Hiroki MATSUTANI
AU - Michihiro KOIBUCHI
AU - Hideharu AMANO
PY - 2020
DO - 10.1587/transinf.2018EDP7367
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E103-D
IS - 1
JA - IEICE TRANSACTIONS on Information
Y1 - January 2020
AB - 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.
ER -
English
