Un protocole pour réduire la latence dans le pire cas dans les réseaux sur puce basés sur la déviation

Informations de base

• ID de l'article : 2510.11361
• Titre : A protocol to reduce worst-case latency in deflection-based on-chip networks
• Auteur : Leandro Soares Indrusiak (Université de Leeds)
• Classification : cs.NI (Architecture des réseaux et Internet), cs.PF (Performance)
• Date de publication : 13 octobre 2025 (prépublication arXiv)
• Lien de l'article : https://arxiv.org/abs/2510.11361

Résumé

Cet article propose un nouveau protocole pour réduire la latence des paquets dans le pire cas dans les réseaux d'interconnexion sur puce basés sur le routage par déviation. Le protocole force la déviation de l'en-tête des paquets plutôt que de leur charge utile, réduisant ainsi le trafic réseau global et, plus important encore, diminuant la latence des paquets dans le pire cas en réduisant le délai avant injection.

Contexte et motivation de la recherche

Définition du problème

1. Problème fondamental : Dans les réseaux sur puce (NoC) basés sur le routage par déviation, les mécanismes traditionnels de déviation de paquets complets entraînent des problèmes de latence graves, particulièrement dans les systèmes embarqués temps réel où les garanties de performance sont essentielles.
2. Importance du problème :
   • Les réseaux de routage par déviation, bien que présentant des avantages en efficacité des ressources (réduction de 85 % de la surface de puce, réduction de 10 fois de la consommation énergétique), ont un impact grave sur la latence réseau
   • Les plates-formes multiprocesseurs embarquées nécessitent des garanties de performance ; l'augmentation de la latence affecte directement la performance de bout en bout
   • Les modèles d'analyse existants montrent que la déviation augmente significativement la latence dans le pire cas
3. Limitations des approches existantes :
   • Le routage par déviation traditionnel envoie le paquet complet (en-tête et charge utile) le long d'un chemin alternatif en cas de congestion
   • Cette approche augmente le trafic réseau inutile, particulièrement lorsque le paquet doit revenir au point d'injection pour une nouvelle tentative
   • Les méthodes d'optimisation existantes se concentrent principalement sur la modification du routage ou la réduction du nombre de déviations, sans considérer l'optimisation du trafic pendant le processus de déviation
4. Motivation de la recherche :
   • Observation que les paquets déviés passent toujours par leur commutateur d'injection avant d'atteindre à nouveau la destination
   • Proposition de dévier uniquement l'en-tête tout en supprimant la charge utile, puis de réinjecter la charge utile au point d'injection
   • Objectif de réduire les interférences réseau, améliorant ainsi la latence globale dans le pire cas

Contributions principales

1. Proposition d'un nouveau protocole de déviation : Séparation innovante du traitement de l'en-tête et de la charge utile, déviation de l'en-tête uniquement avec suppression de la charge utile
2. Établissement d'un modèle d'analyse théorique : Modification du cadre d'analyse de latence existant dans le pire cas, quantifiant les améliorations de performance du nouveau protocole
3. Fourniture de garanties de performance : Preuve théorique que le nouveau protocole surpasse les méthodes traditionnelles en termes de latence dans le pire cas
4. Vérification expérimentale étendue : Démonstration de l'efficacité du protocole dans différents scénarios par des évaluations spécifiques à l'application et synthétiques à grande échelle

Détails de la méthode

Définition de la tâche

Entrée : Réseau sur puce sans routeur basé sur une topologie en anneau, utilisant un mécanisme de routage par déviation de paquets complets Sortie : Protocole de déviation amélioré, réduisant la latence des paquets dans le pire cas Contraintes : Maintien de la fonctionnalité réseau existante, sans augmentation des frais de mise en mémoire tampon supplémentaires, satisfaction des exigences de performance des systèmes temps réel

Architecture du protocole

Mécanisme de déviation traditionnel

Dans le protocole traditionnel, lorsqu'un paquet ne peut pas être extrait au commutateur de destination (par exemple, le lien d'extraction est occupé), le paquet complet est dévié et transmis le long de l'anneau jusqu'à ce qu'il atteigne à nouveau la destination.

Conception du nouveau protocole

1. Déviation de l'en-tête : Lors d'une déviation, seul l'en-tête du paquet continue à circuler dans l'anneau
2. Suppression de la charge utile : La charge utile du paquet est complètement supprimée au point de déviation
3. Réinjection de la charge utile : Lorsque l'en-tête modifié revient au commutateur d'injection, cela déclenche la réinjection de la charge utile
4. Modification de l'en-tête : Le commutateur de destination modifie les champs de l'en-tête lors de la déviation, identifiant le besoin de réinjection

Détails techniques clés

Gestion de la mise en mémoire tampon :

• La charge utile du paquet ne peut pas être supprimée immédiatement du tampon d'injection après injection
• Utilisation des techniques de mise en mémoire tampon SAFC ou SAMQ pour gérer les besoins de réinjection
• Sous les contraintes de délai limite (Di ≤ Ti), aucune mémoire tampon supplémentaire n'est nécessaire

Mécanisme d'identification de l'en-tête :

• Le commutateur d'injection doit pouvoir identifier l'en-tête dévié
• L'en-tête contient le commutateur de destination et un identifiant unique du flux de paquets
• Déclenchement de la réinjection par modification de champs

Optimisation du trafic :

Approche traditionnelle : déviation de paquet complet = en-tête(H) + charge utile(L-H)
Nouveau protocole : déviation d'en-tête uniquement = en-tête(H)
Réduction du trafic = (L-H) × nombre de déviations × longueur du chemin de retour

Points d'innovation technique

1. Stratégie de déviation séparée :
   • Dépassement de la pensée traditionnelle de déviation de paquet complet
   • Exploitation des caractéristiques de la topologie en anneau (les paquets déviés passent nécessairement par le point d'injection)
   • Réutilisation sur place de la charge utile
2. Mécanisme de réduction des interférences :
   • Réduction indirecte du nombre de déviations pour les paquets individuels
   • Réduction des interférences sur les autres paquets par diminution du trafic réseau
   • Optimisation prioritaire du délai avant injection (Ipre)
3. Conception rétrocompatible :
   • Peut être combinée avec les techniques existantes de réduction de déviation
   • Maintien de la cohérence du comportement réseau existant
   • Support pour l'extension des mécanismes de confirmation de bout en bout

Configuration expérimentale

Ensembles de données

1. Évaluation spécifique à l'application :
   • Utilisation de 39 flux d'essai de véhicule autonome (AV)
   • Configuration : caméra résolution VGA, couleur 8 bits, 25 fps
   • Génération de 100 mappages aléatoires pour éviter les biais
2. Évaluation synthétique à grande échelle :
   • Chaque essai contient 100 ensembles de flux générés aléatoirement
   • Nombre de flux augmentant de 20 à 280
   • Plage de paramètres : période 1-100 microsecondes, gigue 0-50 % de la période, taille de paquet 16-48 ou 32-96 flits

Configuration du réseau

• Topologie réseau : Réseaux de cœurs 4×4, 5×5, 6×6, 7×7, 8×8, 9×9
• Paramètres techniques : Flit 32 bits, en-tête 1 flit, fréquence d'horloge 1 GHz
• Configuration de déviation : Maximum 0-3 déviations, utilisation du mécanisme de prévention de l'interblocage le plus ancien en priorité

Indicateurs d'évaluation

1. Pourcentage de réduction de la latence dans le pire cas : Amélioration de latence du nouveau protocole par rapport à la ligne de base
2. Ratio d'ordonnançabilité : Pourcentage de cas complètement ordonnançables dans l'ensemble d'essais
3. Amélioration moyenne regroupée : Amélioration moyenne sur tous les flux et mappages

Méthodes de comparaison

• Méthode de base : Protocole réseau sans routeur traditionnel proposé par Alazemi et al.
• Méthode d'analyse : Utilisation du modèle d'analyse de latence dans le pire cas d'Indrusiak et Burns

Résultats expérimentaux

Résultats principaux

Résultats de l'évaluation spécifique à l'application

Conclusions clés :

• Toutes les topologies réseau bénéficient du nouveau protocole
• L'amélioration maximale peut atteindre 93 %, apparaissant principalement dans les flux avec interférences graves avant injection
• L'amélioration moyenne diminue progressivement avec l'augmentation de la taille du réseau (distribution du trafic plus uniforme)

Résultats de l'évaluation synthétique à grande échelle

Le nouveau protocole surpasse significativement la ligne de base en termes de ratio d'ordonnançabilité :

• Scénario de déviation unique : Amélioration de l'ordonnançabilité supérieure à 20 %
• Scénario de déviations multiples : Performance optimale à charge moyenne
• Impact de la taille du réseau : Amélioration plus évidente dans les petits réseaux (4×4)
• Impact de la taille du paquet : Les paquets plus grands (32-96 flits) poussent le réseau vers la saturation

Expériences d'ablation

Analyse comparative avec différents nombres de déviations (0-3) :

• 0 déviations : Le nouveau protocole est identique à la ligne de base (vérification de la correction)
• 1 déviation : Avantage le plus évident du nouveau protocole
• Déviations multiples : Le degré d'amélioration diminue avec l'augmentation du nombre de déviations

Vérification de l'analyse théorique

Formule d'analyse du temps d'inactivité avant injection modifiée :

La formule originale implique la longueur complète du paquet Lj de tous les flux
La formule du nouveau protocole remplace la longueur de charge utile des flux déviés par la longueur de l'en-tête H
Puisque Lj > H, le nouveau protocole est théoriquement nécessairement supérieur à la méthode originale

Conclusions expérimentales

1. Conditions d'amélioration optimale : Scénarios avec interférences graves avant injection et réseau non complètement saturé
2. Effets d'échelle : L'algorithme RLrec génère plus de petits anneaux dans les grands réseaux, limitant l'espace d'amélioration
3. Sensibilité à la charge : L'effet d'amélioration est positivement corrélé à la taille du paquet et à la fréquence de déviation

Travaux connexes

Directions de recherche en routage par déviation

1. Déviation au niveau flit : Chaque flit prend des décisions de déviation indépendantes, nécessitant des mécanismes de réordonnancement
2. Déviation au niveau paquet : Déviation unifiée de l'ensemble du paquet, préservant l'ordre des flits
3. Approches hybrides : Stratégies combinant mise en mémoire tampon et déviation

Positionnement de cet article

• Trajectoire technique : Sélection de la déviation au niveau paquet pour obtenir des avantages en efficacité des ressources
• Angle d'innovation : Première proposition d'un mécanisme de déviation séparant en-tête et charge utile
• Contribution d'analyse : Extension du cadre d'analyse de latence existant dans le pire cas

Travaux d'optimisation connexes

• Optimisation du routage : Méthodes comme DARES modifiant les chemins de routage
• Optimisation matérielle : Amélioration de la conception des tampons et des stratégies d'arbitrage
• Optimisation de la topologie : Configuration en anneau et optimisation de la conception des commutateurs

Conclusions et discussion

Conclusions principales

1. Avantage théorique : Le nouveau protocole est théoriquement supérieur à toutes les méthodes existantes en termes de latence dans le pire cas
2. Efficacité pratique : Réalisation d'une réduction significative de la latence et d'une amélioration de l'ordonnançabilité dans divers scénarios
3. Faisabilité de mise en œuvre : Aucun surcoût matériel supplémentaire requis, implémentation possible avec les technologies de mise en mémoire tampon existantes
4. Valeur d'application : Particulièrement adaptée aux besoins de garanties de performance des systèmes temps réel dur

Limitations

1. Restrictions de topologie : Principalement applicable aux topologies réseau en anneau
2. Diminution des améliorations : Effet d'amélioration limité dans les grands réseaux ou à charge élevée
3. Complexité de mise en œuvre : Nécessite la modification de la gestion des tampons d'injection et des mécanismes d'identification de l'en-tête
4. Portée d'évaluation : Quantification manquante des améliorations de latence moyenne et de consommation énergétique

Directions futures

1. Extension de topologie : Exploration de la possibilité d'application dans d'autres topologies réseau
2. Quantification de performance : Évaluation des améliorations de latence moyenne et de consommation énergétique
3. Implémentation matérielle : Développement de schémas de mise en œuvre matérielle concrets et vérification de prototypes
4. Optimisation du protocole : Optimisation combinée avec d'autres techniques de réduction de déviation

Évaluation approfondie

Points forts

1. Innovation forte : L'idée de déviation séparant en-tête et charge utile possède une originalité et un pouvoir inspirant
2. Rigueur théorique : Fourniture d'un cadre d'analyse mathématique complet et de preuves théoriques
3. Expérimentation complète : Couverture de deux types de méthodes d'évaluation : spécifique à l'application et synthétique à grande échelle
4. Valeur pratique élevée : Résolution des problèmes de performance clés dans les systèmes temps réel
5. Clarté de rédaction : Description technique précise et structure logique raisonnable

Insuffisances

1. Portée d'application limitée : Principalement orientée vers les réseaux en anneau, applicabilité à d'autres topologies incertaine
2. Détails de mise en œuvre insuffisants : Manque de détails sur les méthodes d'encodage spécifiques de modification d'en-tête et les détails de mise en œuvre matérielle
3. Comparaison de base limitée : Comparaison principalement avec une seule méthode de base, manque de comparaison avec d'autres techniques d'optimisation
4. Indicateurs d'évaluation uniques : Accent principal sur la latence dans le pire cas, analyse insuffisante de l'impact sur la performance moyenne et la consommation énergétique

Impact

1. Contribution académique : Fourniture d'une nouvelle direction de recherche pour l'optimisation des réseaux de routage par déviation
2. Valeur pratique : Application directe possible à la conception de NoC pour les systèmes embarqués temps réel
3. Reproductibilité : Fourniture de modèles d'analyse détaillés et de configurations expérimentales, facilitant la reproduction et l'extension
4. Signification inspirante : L'approche de traitement séparé peut inspirer d'autres recherches en optimisation réseau

Scénarios d'application

1. Systèmes temps réel dur : Applications embarquées nécessitant des garanties de latence strictes
2. Environnements à ressources limitées : Conception de réseaux sur puce sensibles à la surface et à la consommation énergétique
3. Architecture réseau en anneau : Systèmes NoC adoptant une topologie en anneau
4. Réseaux de taille moyenne : Les réseaux de taille 4×4 à 6×6 obtiennent les meilleures améliorations

Références

Cet article cite 15 travaux connexes, incluant principalement :

• 1 Architecture réseau sans routeur d'Alazemi et al.
• 6 Analyse de latence dans le pire cas d'Indrusiak et Burns
• 8 Conception de réseau en anneau IMR de Liu et al.
• Autres travaux connexes en routage par déviation, analyse temps réel et optimisation NoC

Évaluation globale : Cet article de haute qualité en architecture système propose un protocole d'optimisation innovant du routage par déviation, possédant une base théorique solide et une vérification expérimentale complète. Bien qu'il présente certaines limitations en termes de portée d'application et de détails de mise en œuvre, son idée centrale possède une valeur académique importante et une signification pratique, fournissant une nouvelle direction pour la recherche en optimisation des réseaux sur puce.