La fonctionnalité de recherche est en construction.
La fonctionnalité de recherche est en construction.

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: An Effective Routing Algorithm for Two-Dimensional Meshes LEF : un algorithme de routage efficace pour les maillages bidimensionnels

Thiem Van CHU, Kenji KISE

  • Vues en texte intégral

    0

  • Citer

Résumé:

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.

Publication
IEICE TRANSACTIONS on Information Vol.E102-D No.10 pp.1925-1941
Date de publication
2019/10/01
Publicisé
2019/07/09
ISSN en ligne
1745-1361
DOI
10.1587/transinf.2019EDP7019
Type de manuscrit
PAPER
Catégories
Système d'ordinateur

Auteurs

Thiem Van CHU
  Tokyo Institute of Technology
Kenji KISE
  Tokyo Institute of Technology

Mots-clés

Table des matières