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
우리는 낮은 설계 복잡성으로 높은 처리량을 제공하는 LEF(Long Edge First)라는 1차원 메시 기반 NoC(Networks-on-Chip)를 위한 새로운 망각 라우팅 알고리즘을 설계합니다. LEF의 기본 아이디어는 비대칭 메시 또는 토러스 상호 연결이 있는 슈퍼컴퓨터에 적합한 DOR(차원 순서 라우팅) 알고리즘을 선택하는 일반적인 통념에서 비롯됩니다. 즉, 가장 긴 차원을 먼저 라우팅하면 다른 전략보다 더 나은 성능을 제공합니다. LEF에서는 XY DOR과 YX DOR을 결합합니다. 패킷을 라우팅할 때 어떤 DOR 알고리즘이 선택되는지는 소스 노드와 대상 노드 사이의 상대적 위치에 따라 달라집니다. 적절한 DOR 알고리즘을 선택하는 결정은 네트워크 형태에 고정되지 않고 대신 패킷별로 결정됩니다. 또한 가상 채널의 사용이 기존 방법보다 더 유연한 LEF에 대한 효율적인 교착 상태 방지 방법을 제안합니다. 우리는 또 다른 효과적인 망각 라우팅 알고리즘인 O16TURN과 홀짝 회전 모델을 기반으로 하는 최소 적응형 라우팅 알고리즘에 대해 LEF를 평가합니다. 평가 결과는 통신이 비대칭 메시 내에 있을 때 LEF가 특히 효과적이라는 것을 보여줍니다. 8×4 NoC에서 LEF는 경우에 따라 적응형 라우팅 알고리즘보다 성능이 뛰어나며 O64.5TURN보다 약 1%에서 최대 약 1% 더 높은 처리량을 제공합니다. 또한 우리의 결과는 제안된 교착 상태 회피 방법이 LEF의 성능을 크게 향상시키는 데 도움이 되며 O100TURN의 성능을 향상시키는 데 사용될 수 있음을 보여줍니다. 또한 수천 개의 노드가 있는 대규모 NoC에서 LEF를 검사합니다. 우리의 결과는 NoC 크기가 증가할수록 라우팅 알고리즘의 성능은 네트워크의 자원 할당 정책에 의해 더 강하게 영향을 받으며, 그 효과는 알고리즘마다 다르다는 것을 보여줍니다. 이는 노드 수가 XNUMX개 정도인 중간 규모 NoC의 결과를 대규모 NoC에 직접 적용할 수 없다는 점에서 분명합니다.
Thiem Van CHU
Tokyo Institute of Technology
Kenji KISE
Tokyo Institute of Technology
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.
부
Thiem Van CHU, Kenji KISE, "LEF: An Effective Routing Algorithm for Two-Dimensional Meshes" in IEICE TRANSACTIONS on Information,
vol. E102-D, no. 10, pp. 1925-1941, October 2019, doi: 10.1587/transinf.2019EDP7019.
Abstract: We design a new oblivious routing algorithm for two-dimensional mesh-based Networks-on-Chip (NoCs) called LEF (Long Edge First) which offers high throughput with low design complexity. LEF's basic idea comes from conventional wisdom in choosing the appropriate dimension-order routing (DOR) algorithm for supercomputers with asymmetric mesh or torus interconnects: routing longest dimensions first provides better performance than other strategies. In LEF, we combine the XY DOR and the YX DOR. When routing a packet, which DOR algorithm is chosen depends on the relative position between the source node and the destination node. Decisions of selecting the appropriate DOR algorithm are not fixed to the network shape but instead made on a per-packet basis. We also propose an efficient deadlock avoidance method for LEF in which the use of virtual channels is more flexible than in the conventional method. We evaluate LEF against O1TURN, another effective oblivious routing algorithm, and a minimal adaptive routing algorithm based on the odd-even turn model. The evaluation results show that LEF is particularly effective when the communication is within an asymmetric mesh. In a 16×8 NoC, LEF even outperforms the adaptive routing algorithm in some cases and delivers from around 4% up to around 64.5% higher throughput than O1TURN. Our results also show that the proposed deadlock avoidance method helps to improve LEF's performance significantly and can be used to improve O1TURN's performance. We also examine LEF in large-scale NoCs with thousands of nodes. Our results show that, as the NoC size increases, the performance of the routing algorithms becomes more strongly influenced by the resource allocation policy in the network and the effect is different for each algorithm. This is evident in that results of middle-scale NoCs with around 100 nodes cannot be applied directly to large-scale NoCs.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2019EDP7019/_p
부
@ARTICLE{e102-d_10_1925,
author={Thiem Van CHU, Kenji KISE, },
journal={IEICE TRANSACTIONS on Information},
title={LEF: An Effective Routing Algorithm for Two-Dimensional Meshes},
year={2019},
volume={E102-D},
number={10},
pages={1925-1941},
abstract={We design a new oblivious routing algorithm for two-dimensional mesh-based Networks-on-Chip (NoCs) called LEF (Long Edge First) which offers high throughput with low design complexity. LEF's basic idea comes from conventional wisdom in choosing the appropriate dimension-order routing (DOR) algorithm for supercomputers with asymmetric mesh or torus interconnects: routing longest dimensions first provides better performance than other strategies. In LEF, we combine the XY DOR and the YX DOR. When routing a packet, which DOR algorithm is chosen depends on the relative position between the source node and the destination node. Decisions of selecting the appropriate DOR algorithm are not fixed to the network shape but instead made on a per-packet basis. We also propose an efficient deadlock avoidance method for LEF in which the use of virtual channels is more flexible than in the conventional method. We evaluate LEF against O1TURN, another effective oblivious routing algorithm, and a minimal adaptive routing algorithm based on the odd-even turn model. The evaluation results show that LEF is particularly effective when the communication is within an asymmetric mesh. In a 16×8 NoC, LEF even outperforms the adaptive routing algorithm in some cases and delivers from around 4% up to around 64.5% higher throughput than O1TURN. Our results also show that the proposed deadlock avoidance method helps to improve LEF's performance significantly and can be used to improve O1TURN's performance. We also examine LEF in large-scale NoCs with thousands of nodes. Our results show that, as the NoC size increases, the performance of the routing algorithms becomes more strongly influenced by the resource allocation policy in the network and the effect is different for each algorithm. This is evident in that results of middle-scale NoCs with around 100 nodes cannot be applied directly to large-scale NoCs.},
keywords={},
doi={10.1587/transinf.2019EDP7019},
ISSN={1745-1361},
month={October},}
부
TY - JOUR
TI - LEF: An Effective Routing Algorithm for Two-Dimensional Meshes
T2 - IEICE TRANSACTIONS on Information
SP - 1925
EP - 1941
AU - Thiem Van CHU
AU - Kenji KISE
PY - 2019
DO - 10.1587/transinf.2019EDP7019
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E102-D
IS - 10
JA - IEICE TRANSACTIONS on Information
Y1 - October 2019
AB - We design a new oblivious routing algorithm for two-dimensional mesh-based Networks-on-Chip (NoCs) called LEF (Long Edge First) which offers high throughput with low design complexity. LEF's basic idea comes from conventional wisdom in choosing the appropriate dimension-order routing (DOR) algorithm for supercomputers with asymmetric mesh or torus interconnects: routing longest dimensions first provides better performance than other strategies. In LEF, we combine the XY DOR and the YX DOR. When routing a packet, which DOR algorithm is chosen depends on the relative position between the source node and the destination node. Decisions of selecting the appropriate DOR algorithm are not fixed to the network shape but instead made on a per-packet basis. We also propose an efficient deadlock avoidance method for LEF in which the use of virtual channels is more flexible than in the conventional method. We evaluate LEF against O1TURN, another effective oblivious routing algorithm, and a minimal adaptive routing algorithm based on the odd-even turn model. The evaluation results show that LEF is particularly effective when the communication is within an asymmetric mesh. In a 16×8 NoC, LEF even outperforms the adaptive routing algorithm in some cases and delivers from around 4% up to around 64.5% higher throughput than O1TURN. Our results also show that the proposed deadlock avoidance method helps to improve LEF's performance significantly and can be used to improve O1TURN's performance. We also examine LEF in large-scale NoCs with thousands of nodes. Our results show that, as the NoC size increases, the performance of the routing algorithms becomes more strongly influenced by the resource allocation policy in the network and the effect is different for each algorithm. This is evident in that results of middle-scale NoCs with around 100 nodes cannot be applied directly to large-scale NoCs.
ER -