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
최근 제안된 불규칙한 네트워크는 컴퓨팅 노드 수가 많은 온칩 및 오프칩 시스템 모두의 대기 시간을 줄여 병렬 애플리케이션의 성능을 향상시킬 수 있습니다. 그러나 이러한 네트워크는 일반적으로 순진한 최소 경로 라우팅 알고리즘을 사용할 때 패킷 라우팅에 교착 상태가 발생합니다. 이 문제를 해결하기 위해 우리는 교착 상태가 없는 네트워크 성능을 유지하기 위해 회전 모델을 일반화하는 최근 제안된 이론에 주목합니다. 정리는 완전히 불규칙한 네트워크를 포함하여 임의의 토폴로지에 적용하는 데 여전히 어려움을 겪고 있습니다. 이 논문에서 우리는 정리를 완전히 일반적인 정리로 발전시킵니다. 또한, 우리는 고급 정리를 기반으로 교착 상태 없는 라우팅 방법의 실행 가능한 구현을 제공합니다. 실험 결과, 제안한 정리에 기반한 라우팅 방법은 기존 결정론적 최소 라우팅 방법에 비해 네트워크 처리량을 최대 138% 향상시킬 수 있음을 보여주었다. 또한 Duato 프로토콜에서 탈출 경로로 활용하면 기존의 up*/down* 라우팅에 비해 최대 26.3%까지 처리량을 향상시킬 수 있습니다.
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.
부
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
부
@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},}
부
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 -