Soutenance mémoire
Conception et Implémentation d’un Nouvel Algorithme de Routage – DINRA
Problématique
Tous les réseaux sur puces ont des caractéristiques propres à eux qui les rendent plus attrayants dans certains domaines, notamment le nombre de ressources supportées, la rapidité des communications, l’énergie nécessaire, le nombre de ressources utilisées, etc. Au niveau des communications, bien que le débit soit une des métriques les plus importantes, il ne faut pas non plus oublier la fiabilité du transit des données. Les interconnexions des systèmes sur puce ne cessent de diminuer de taille également et sont maintenant rendues à l’échelle du nanomètre. Bien que la réduction de la taille des transistors et des connexions n’a cessé d’augmenter les performances des processeurs et de réduire leur coût, elle a également affecté la sûreté de fonctionnement.Quand un transistor est exposé à des rayonnements ionisants de haute énergie, des paires électron-trou sont créées. La finesse de gravure réduite ces dernières années à quelques nanomètres menace de manière significative les prochaines générations des circuits. Concernant les fautes transitoires, des circuits plus petits ont tendance à mettre en oeuvre de plus faibles charges pour maintenir les états des registres, et les rendent de ce fait plus sensibles aux bruits.
Lorsque la marge de bruit diminue, la probabilité que l’impact d’une particule de haute énergie puisse perturber la charge sur les circuits augmente, qui elle-même augmente à son tour la probabilité de fautes transitoires. Plus un circuit comporte de transistors, plus de fils sont nécessaires pour les connecter, résultant en une plus forte probabilité de fautes, tant lors de la fabrication que du fonctionnement de ces dispositifs. Les réseaux sur puces sont plus sujets aux fautes en raison d’un plus grand nombre de transistors. Par ailleurs, la température est un autre facteur de fautes transitoires ou permanentes. Plus la puce comporte de dispositifs, plus de puissance sera drainée de l’alimentation, ce qui – à surface égale – va augmenter les pertes par dissipation avec comme conséquence une augmentation de la température et de la probabilité d’erreurs.
Aujourd’hui, les architectures des circuit sont de plus en plus compliquées, ce qui augmente la probabilité d’erreurs de conception. D’autre part, cela rend également difficile le débogage des erreurs. Dans un proche avenir, changer les paramètres comme les dimensions et la taille va augmenter l’apparition de défauts dans le circuit. Pour assurer leur intégrité, la tolérance aux fautes doit être une considération importante dans la conception des circuits modernes. Un système fiable doit intégrer un mécanisme de tolérance contre les possibles erreurs. Cette diminution de taille amène les interconnexions à devenir de plus en plus sensibles et vulnérables aux fautes. Ces fautes peuvent avoir un effet permanent aussi bien que transitoire. Ces fautes peuvent être internes au circuit lui-même par exemple les variations de tension ou la diaphonie (crosstalk), comme elles peuvent également provenir de l’extérieur telles les interférences magnétiques et les effets des particules alpha. C’est pourquoi de plus en plus les réseaux sur puce sont développés dans une optique de tolérance aux fautes. Il est devenu essentiel pour rencontrer un certain niveau de fiabilité d’intégrer des techniques pour surmonter l’effet des fautes dans ces systèmes. La tolérance aux fautes n’est pas nouvelle en soi dans le domaine des réseaux sur puce et plusieurs recherches ont été menées sur ce sujet. Le but ultime est qu’aucune donnée ne soit interrompue, autrement dit, qu’aucun message lors de son transfert ne soit modifié ou, tout simplement, n’arrive pas à destination. Pour ce faire, dans la majorité des cas, l’erreur en premier lieu doit être d’abord détectée et, par la suite, isolée. Dans la littérature, les méthodes de détection d’erreur les plus utilisées sont le contrôle par redondance cyclique (Cyclic Redundancy Check, CRC) [51], le code de Hamming [51] et le bit de parité. Une fois l’erreur détectée, il faut définir de quelle manière elle sera traitée. Il est préférable d’opter seulement pour l’isolation des composants fautifs et ne pas s’intéresser à la correction d’erreur.
Résumé
La révolution technologique de ces dernières années a rendu possible la confection de systèmes embarqués de plus en plus performants. Parmi ces équipements, Les systèmes multiprocesseurs sur puce (MPSoC)sont capables d’intégrer un grand nombre de transistors et de composants hétérogènes ensemble dans une seule puce. Faire communiquer ces composants au sein d’une puce est assuré par un réseau de commutation de paquets appelé réseau sur puce (Network-on-Chip-NoC). Les NoCs sont constitués de ressources de traitement telles que des processeurs, des DSP ou des mémoires et des routeurs. Ces organes sont connectés par des liens leur permettant de communiquer les uns avec les autres en s’envoyant des messages. Cependant, le passage à des architectures matérielles de plus en plus réduites rend les circuits plus vulnérables aux pannes (fautes ou dysfonctionnements). Un réseau sur puce peut, en effet, se retrouver avec des routeurs ou des liens non opérationnels,qui ne peuvent plus être utilisés pour acheminer les messages.
Une solution potentielle à ce problème est l’introduction de mécanismes de tolérance aux pannes permettant au système de fonctionner en mode dégradé malgré la présence de composants défectueux. Le système devrait fonctionner correctement lorsque certaines erreurs se produisent dans les routeurs ou les liens. Cependant, la communication a un impact énorme sur les performances du Network on Chip, et la conception d’un algorithme de routage efficace est plus que nécessaire. L’objectif assigné à l’algorithme de routage est de trouver un nouveau chemin pour diriger les paquets de la source vers la destination dans un réseau défectueux. De nombreux algorithmes de routage tolérants aux pannes sont utilisés pour surmonter les défauts dans les Networks on chip. Cependant, ces algorithmes de routage souffrent de plusieurs problèmes, dont celui de la congestion. Dans ce travail, une approche originale inspirée de Catnap est proposée pour les NoC utilisant des mécanismes de détection de congestion locale et globale avec une architecture de sous-réseaux hiérarchiques. Avec l’aide de ces deux techniques, le NoC devient tolérant aux pannes et est capable d’utiliser efficacement le débit.
La topologie
La topologie du réseau fait référence à l’arrangement statique des noeuds et des liens du réseau. Or, la première étape dans la conception d’un réseau sur puce est la sélection de la topologie car cette-dernière va conditionner la stratégie de routage employée ainsi que la méthode de contrôle de flux[56] . La topologie est un point important de la performance des NoCs. Elle est représentée par un graphe G (N, C), où N est l’ensemble des routeurs qui composent le réseau et C l’ensemble des canaux de communication. Le NoC peut être organisé en différentes topologies. Plusieurs topologies ont été proposées et mises en oeuvre pour les systèmes multi-coeurs, y compris maille, tore, anneau, papillon et des réseaux d’interconnexion irrégulière[ 55],[61](fig.1.5). La complexité d’implémentation de la topologie dépend de deux facteurs : le nombre de liens à chaque noeud et la facilité de poser la topologie sur une puce. Comme les routeurs et les liens traversés par un paquet consomment de l’énergie, l’effet d’une topologie sur le nombre de sauts affecte ainsi directement la consommation d’énergie du réseau. Une topologie de réseau peut être classée comme étant directe, indirecte ou hybride. Pour les topologies directes (Mesh, Tore, Anneau), chaque élément de calcul (IP) est associé à un routeur ; donc tous les routeurs sont des sources et des destinations.
Les paquets sont transmis directement entre les noeuds terminaux. Dans une topologie indirecte (Papillon, Arbre élargi), les routeurs sont différents des éléments de calcul ; seuls les éléments de calcul sont les sources et les destinations du trafic ; les noeuds intermédiaires changent simplement le trafic vers et à partir des éléments de calcul[26]. Pour les réseaux hybrides, cette topologie est basée sur une combinaison entre les deux précédentes topologies (directe et indirecte). On peut aussi classer les topologies selon leur régularité ; il y a des topologies régulières et d’autres irrégulières. On dit qu’un réseau ou une topologie est régulière lorsque tous les noeuds ont le même degré (tous les noeuds ont le même nombre de voisins). Dans le cas contraire, on dit que la topologie est irrégulière. Le routage dans les réseaux irréguliers est très compliqué et difficile. Les topologies irrégulières permettent plus de liberté et ainsi de dimensionner précisément le réseau requis. Elle peut être issue d’une topologie régulière qui a été retaillée au plus juste de façon à enlever les éléments non utilisés[41]. Une topologie irrégulière nécessite en revanche une plus grande attention pour le routage car les règles à appliquer ne sont plus triviales.
|
Table des matières
Table des sigles et acronymes
Introduction Générale
1 Réseaux sur puce – Concepts de base
1.1 Les réseaux sur puce (Network on Chip)
1.2 La topologie
1.3 Classification des techniques de routage
1.4 Les problèmes de routage
1.5 Paramètres de performance du NoC
1.6 Conclusion
2 Etat de l’art sur les Algorithmes de Routage Tolérant aux Fautes dans les NoCs.
2.1 Introduction
2.2 La sureté de fonctionnement d’un système
2.3 Les caractéristiques des fautes
2.4 Congestion dans les réseaux sur puce
2.5 Algorithme de Routage Tolérant aux Fautes
2.6 Conclusion .
3 Conception et Implémentation d’un Nouvel Algorithme de Routage – DINRA
3.1 Architecture Globale du Réseau
3.2 Algorithme de Routage
3.3 Conclusion
4 Expérimentations et résultats
4.1 Plateforme d’expérimentation
4.2 Evaluation
4.3 Conclusion
Conclusion
Bibliographie
Télécharger le rapport complet
