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
Nous concevons un nouvel algorithme de routage inconscient pour les réseaux sur puce (NoC) bidimensionnels basés sur un maillage appelé LEF (Long Edge First) qui offre un débit élevé avec une faible complexité de conception. L'idée de base de LEF vient de la sagesse conventionnelle consistant à choisir l'algorithme de routage par ordre de dimensions (DOR) approprié pour les supercalculateurs dotés d'interconnexions asymétriques en maillage ou en tore : le routage des dimensions les plus longues offre d'abord de meilleures performances que les autres stratégies. En LEF, on combine le XY DOR et le YX DOR. Lors du routage d'un paquet, l'algorithme DOR choisi dépend de la position relative entre le nœud source et le nœud de destination. Les décisions de sélection de l'algorithme DOR approprié ne sont pas liées à la forme du réseau mais plutôt prises par paquet. Nous proposons également une méthode efficace d'évitement des interblocages pour LEF dans laquelle l'utilisation de canaux virtuels est plus flexible que dans la méthode conventionnelle. Nous évaluons LEF par rapport à O1TURN, un autre algorithme de routage inconscient efficace, et un algorithme de routage adaptatif minimal basé sur le modèle de virage impair-pair. Les résultats de l'évaluation montrent que LEF est particulièrement efficace lorsque la communication se fait au sein d'un maillage asymétrique. Dans un NoC 16 × 8, LEF surpasse même l'algorithme de routage adaptatif dans certains cas et offre un débit d'environ 4 % à environ 64.5 % supérieur à celui d'O1TURN. Nos résultats montrent également que la méthode proposée pour éviter les blocages contribue à améliorer considérablement les performances de LEF et peut être utilisée pour améliorer les performances d'O1TURN. Nous examinons également le LEF dans les NoC à grande échelle comportant des milliers de nœuds. Nos résultats montrent que, à mesure que la taille du NoC augmente, les performances des algorithmes de routage deviennent plus fortement influencées par la politique d'allocation des ressources dans le réseau et l'effet est différent pour chaque algorithme. Cela est évident dans la mesure où les résultats des NoC à moyenne échelle comportant environ 100 nœuds ne peuvent pas être appliqués directement aux NoC à grande échelle.
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.
Copier
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
Copier
@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},}
Copier
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 -