The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
Redes irregulares propostas recentemente podem reduzir a latência para sistemas dentro e fora do chip com um grande número de nós de computação e, assim, podem melhorar o desempenho de aplicações paralelas. No entanto, essas redes geralmente sofrem com deadlocks no roteamento de pacotes quando usam um algoritmo ingênuo de roteamento de caminho mínimo. Para resolver este problema, focamos a atenção em uma teoria proposta recentemente que generaliza o modelo de giro para manter o desempenho da rede sem deadlocks. Os teoremas continuam a ser um desafio de aplicação a topologias arbitrárias, incluindo redes totalmente irregulares. Neste artigo, avançamos os teoremas para teoremas completamente gerais. Além disso, fornecemos uma implementação viável de um método de roteamento sem deadlocks baseado em nosso teorema avançado. Resultados experimentais mostram que o método de roteamento baseado em nosso teorema proposto pode melhorar o rendimento da rede em até 138% em comparação com um método de roteamento mínimo determinístico convencional. Além disso, quando utilizado como caminho de escape no protocolo Duato, pode melhorar o rendimento em até 26.3% em comparação com o roteamento up*/down* convencional.
Ryuta KAWANO
Keio University
Ryota YASUDO
Keio University
Hiroki MATSUTANI
Keio University
Michihiro KOIBUCHI
National Institute of Informatics
Hideharu AMANO
Keio University
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.
Copiar
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
Copiar
@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},}
Copiar
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 -