Soutenance mémoire
Problème de routage intra-FPGA
La surface d’un FPGA inclut les ressources de routage et les ressources logiques. Contrairement à un circuit intégré à application spécique (ASIC), 80% de la surface totale d’un FPGA est dédiée aux ressources de routage [26]. Cependant, il est parfois impossible de router tous les signaux d’un circuit malgré que le nombre de blocs logiques ne dépasse pas la surface logique disponible sur ce FPGA. En eet, Ce problème de routage est essentiellement dû à la congestion : une répartition non étudiée des blocs logiques, peut créer, d’une part, des zones dans lesquelles les ressources de routage sont fortement demandées et qui dépassent largement les ressources disponibles, et d’autre part des zones légèrement congestionnées la ou les ressources ne sont pas toutes exploitées. Pour remédier à ce problème, des travaux ont été faits pour une meilleure gestion des ressources de routage. Des solutions architecturales ont été proposées visant à agir sur la taille de la largeur du canal de routage tout en la rendant variable selon le besoin de l’application. Dans [27], les auteurs ont estimé que la congestion est généralement localisée au centre du FPGA. Pour cette raison, ils ont proposé d’augmenter la largeur du canal seulement au milieu du FPGA et d’utiliser des canaux qui sont moins larges dans reste du circuit. Cette technique n’avait pas donné des résultats suffisants pour justifier l’effort supplémentaire nécessaire pour la conception physique d’un tel FPGA. Une technique itérative qui a été proposée et qui vise à ajuster, durant un certain nombre d’itérations, le placement des blocs logiques selon l’information sur la congestion crée par le routage [28]. Cette technique est très gourmande de point de vue temps de compilation puisque le placement et le routage se refont à chaque itération. Notre objectif est donc de développer une technique de placement intra-FPGA, qui permet de placer les blocs logiques en se basant sur l’estimation de la congestion mise à jour à fur et à mesure de l’évolution du placement. Cette technique permettra de répartir les blocs logiques dans toute la surface de l’FPGA tout en évitant de créer des zones congestionnées dans un temps relativement acceptable et ainsi, améliorer la routage du circuit.
Limitation des benchmarks de test
Les techniques de multiplexage développées dans le cadre de cette thèse seront évaluées à travers une série de tests en utilisant un ensemble de benchmarks. Par contre, le plus grand défi était de trouver des benchmarks spécifiques qui nous permettent de valider et évaluer ces techniques. En eet, nous cherchons des benchmarks suffisamment grands et dont la taille dépasse largement la capacité des FPGAs actuels, afin de pouvoir les tester sur une carte multi-FPGAs. D’autre part, nous nous intéressons aux benchmarks hétérogènes qui contiennent un mixe de différents composants. Ces circuits hétérogènes permettent de bien évaluer le degré d’adaptabilité et de flexibilité de nos algorithmes. La dernière caractéristique des benchmarks requis c’est la testabilité. En d’autres termes, nous devons toujours avoir la controlabilité et l’observabilité du circuit sous test (application software exécutée par le matériel). En menant une recherche sur ce qui existe, nous n’avons pas trouvé de benchmarks qui répondent à nos besoins. En eet, la première initiative de génération de benchmarks de test a été faite par CBL [29, 30] et MCNC [31]. Ces circuits sont des simples fonctions (pas d’application software) qui ne sont pas suffisamment grands pour cibler des opérations de partitionnement et de multiplexage. En fait, le plus grand circuit généré est le s38584 et il contient seulement 2904 blocs logiques(LUT) [32]. Plus récemment, des chercheurs ont développé un programme de génération de benchmark GNL 3 [33] qui permet de créer des netlists ayant des comportements assez réalistes. Ce programme est basé sur la règle de Rent [34] pour contrôler la complexité des interconnexions entre les taches. En eet, l’utilisateur définit le nombre de blocs logiques, le nombre de flip flop, la profondeur combinatoire, le nombre d’entrées/sortie et aussi l’exposant rent. Par la suite, le programme GNL suit une approche bottom-up. Donc il commence par établir les connexions entre un certain nombre de blocs logiques ce qui en résulte la formation de clusters. Ces clusters eux-mêmes vont être connectés ensemble jusqu’à ce que tous les clusters seront combinés en un seul circuit. A chaque niveau, le programme vérifie si l’exposant rent fixé par l’utilisateur est respecté. L’inconvénient de ce générateur réside dans le fait que les circuits générés sont composés de ressources logique homogènes (pas de DSP, Ram..), en plus aucune application n’est générée pour tester ces circuits. En 2005, la suite de benchmarks IWLS a été publiée dans le workshop IWLS (International Workshop on Logic and Synthesis)[35]. Elle contient des circuits déjà publiés dans des conférences précédentes, des circuits publiés par des communautés de développeurs de code libre et encore par des circuits industriels. Malgré la diversité et la taille relativement grande de ces circuits, mais ils n’offrent aucune solution de testabilité durant l’implémentation sur la carte multi-FPGA. Notre objectif c’était donc de développer un générateur de benchmarks, qui permet, à l’aide d’une description architecturale simple du benchmarks, de générer le circuit demandé modélisé avec le langage de description matérielle VHDL. Le générateur utilise un ensemble de composant de la bibliothèque Soclib [36], ce qui donne aux benchmarks un aspect réel semblable à celui des circuits industriels.
Simulation logique
La simulation emploie des méthodes d’exécution et de calcul sur ordinateur. Cette technique offre une grande observabilité, une grande souplesse et une grande flexibilité. Elle peut intervenir dans plusieurs niveaux puisque pour un même système, plusieurs modèles à différents niveaux d’abstraction peuvent être utilisés. Plus le modèle est précis, plus les calculs pour la simulation sont nombreux et par conséquent, plus l’exécution est lente. Dans le domaine de conception des circuits monopuces, le système peut être modélisé selon 6 niveaux d’abstraction :
• Le niveau spécification fonctionnelle modélise le comportement global du système sans aucune précision vis à vis de sa réalisation finale. Ici, on travaille à un très haut niveau d’abstraction, une simulation à ce niveau permet de très rapidement simuler une spécification fonctionnelle et permettra, par son analyse, de mettre en évidence les besoins du système.
• Le niveau architectural modélise le système comme un ensemble de modules travaillant en parallèle et communiquant entre eux. A ce niveau, les différentes tâches du système sont allouées à des sous-systèmes. Chaque sous-système est modélisé au niveau fonctionnel. La granularité concernant les interactions est au niveau transactionnel (TLM). Ce type de simulation est particulièrement utile pour l’exploration d’architecture et le développement des parties logicielles du système.
• Le niveau micro-architecture correspond à la même simulation qu’au niveau architectural sauf qu’ici, les interactions entre sous-systèmes ne sont plus des transactions mais des signaux. La précision du modèle est donc au cycle d’horloge prêt au niveau de la communication entre sous-systèmes. Ce niveau de modélisation permet la réalisation de premières mesures de performances ainsi que le développement des pilotes de bas niveau (drivers) des logiciels embarqués.
• Le niveau RTL modélise un circuit comme un ensemble de registres et de relations logiques entre registres. Ce modèle est à bas niveau d’abstraction, le système entier est simulé au cycle d’horloge prêt. Ce niveau est particulièrement utilisé pour la mise au point des sous-ensembles matériels qui composent le système. De nos jours, plusieurs outils permettant de faire la simulation à ce niveau d’abstraction, à noter le Modelsim [41] et le Isim de Xilinx [42].
• Le niveau porte logique décrit le système complet comme un assemblage de portes logiques. Ce niveau est obtenu après synthèse. De nos jours, les outils permettant le passage du niveau RTL au niveau porte logique sont automatisés et suffisamment fiables pour ne pas avoir à travailler à ce niveau pour la conception d’un ASIC. Cependant, dans les flots d’émulation qui nécessitent eux aussi une phase de synthèse, le niveau de fiabilité est moins élevé et il s’avère parfois nécessaire d’effectuer des simulations à ce niveau pour trouver une erreur de synthèse.
• Le niveau analogique est le plus bas niveau d’abstraction utilisé en simulation. A ce niveau existent des outils d’extraction de paramètres électriques à partir du plan de masse. On travaille ici avec des modèles précis des transistors, dépendant de la technologie utilisée. Pour conclure, la simulation est donc utile à toutes les phases de conception. Cette technique est très efficace de part sa grande souplesse, sa grande flexibilité, observabilité, contrôlabilité et un temps de mise en oeuvre souvent court. Cependant, plus on avance dans le processus de conception et plus la précision du modèle nécessaire augmente, ce qui implique plus de calculs et donc une vitesse d’exécution moindre. La simulation trouve donc ses limites lorsqu’il faut jouer de longues séquences de tests à un bas niveau d’abstraction.
Bloc logique de base du FPGA
Le bloc logique de base d’un FPGA, nommé BLE (Basic Logic Element) est composé d’une table de transcodage (LUT : Look Up Table) à K entrées et d’une bascule suivies d’un multiplexeur. Le BLE peut fonctionner soit en mode combinatoire si sa sortie est fournie par la LUT, soit en mode séquentiel si sa sortie vient de la bascule. Une table de transcodage à K entrées (K-LUT) contient 2 K bits de configurations. Elle est capable d’implémenter n’importe quelle fonction booléenne ayant au plus K entrées. Des études ont été menées sur le nombre d’entrées des LUTs. Les auteurs de [46] [47] ont montré que le choix de 4 entrées est un bon compromis entre les performances du circuit et les contraintes des algorithmes de placement-routage, leur complexité et leur efficacité.La 4-LUT utilise 16 bits SRAM (static random access memory) pour implémenter n’importe quelle fonction booléenne à 4 entrées. Les éléments logiques de base peuvent être rassemblés en clusters hiérarchiques afin de réduire la connectivité globale et favoriser une connectivité locale et rapide. Un cluster est caractérisé par le nombre de BLEs (N) qu’il contient et le nombre de ses entrées (I). Le nombre de BLEs N est typiquement entre 4 et 10 dans les FPGAs modernes. Chaque entrée d’un BLE peut être connectée à n’importe quelle entrée parmi les I entrées du cluster ou à n’importe quelle sortie des BLEs contenus dans le cluster. Les FPGAs ont été longtemps réalisés avec seulement des blocs logiques configurables à base de LUT. Aujourd’hui, elles peuvent contenir aussi des macro-blocs tels que de larges mémoires RAM et des coeurs de microprocesseurs
|
Table des matières
1 Introduction
1.1 Les buts de recherche et contributions
1.1.1 Problème de routage inter-FPGA
1.1.2 Problème de routage intra-FPGA
1.1.3 Limitation des benchmarks de test
1.2 Plan
2 État de l’art : Plateformes matérielles
2.1 Introduction
2.2 Vérification des SoCs
2.2.1 Simulation logique
2.2.2 Émulation matérielle
2.2.3 Prototypage matériel
2.2.4 Synthèse : Comparaison entre les différents types de vérification
2.3 Architecture FPGA
2.3.1 Bloc logique de base du FPGA
2.3.2 Ressources de routage
2.3.3 Éléments spécifiques
2.4 Exemples de FPGA industriels
2.4.1 Architecture du Virtex VI
2.4.2 Architecture du Virtex 7
2.4.3 Architecture du Stratix V
2.5 Plateformes industrielles de prototypage
2.5.1 Plateformes matérielles
2.5.2 Plateformes de prototypage complètes
2.6 Conclusion
3 État de l’art : Flot logiciel pour plateforme Multi-FPGA
3.1 Introduction
3.2 Modélisation RTL du système sur puce
3.3 Synthèse logique et mapping
3.4 Partitionnement
3.5 Routage des signaux inter-FPGA
3.5.1 Technique des fils virtuels : Avec ordonnancement
3.5.2 Technique de routage sans ordonnancement
3.6 Placement intra-FPGA
3.6.1 Placement par le recuit simulé
3.6.2 Fonction coût .
3.6.3 Réduction de la congestion
3.7 Routage Intra-FPGA
3.7.1 Algorithme de routage PathFinder
3.8 Conclusion
4 Générateur de benchmarks
4.1 Introduction
4.2 Les architectures multiprocesseurs
4.2.1 Caractéristiques des architectures multiprocesseurs
4.2.2 Caractéristiques du générateur de benchmarks
4.3 L’environnement DSX_SystemC
4.3.1 Chaine de compilation de DSX_SystemC
4.3.2 Bibliothèque SoCLib de composants
4.4 Environnement DSX_VHDL
4.4.1 Génération de la netlist synthétisable
4.4.2 Chaine de compilation de DSX_VHDL
4.4.3 Exemple de benchmark généré
4.5 Méthodologie de synthèse logique rapide
4.6 Résultats expérimentaux
4.7 Conclusion
5 Techniques de multiplexage proposées pour une plateforme de prototypage multi-FPGA
5.1 Introduction
5.2 Multiplexage des signaux
5.2.1 Signaux non qualiés pour le multiplexage
5.2.2 Routage des signaux multiplexés
5.3 Routage Inter-FPGA : Constructif OU Itératif ?
5.4 Algorithme de routage Pathfinder
5.5 Adaptation de l’algorithme de routage Pathfinder
5.5.1 Modélisation en graphe de routage
5.5.2 Conflit de direction
5.5.3 Modélisation d’un signal
5.6 Conclusion
6 Résultats expérimentaux
6.1 Introduction
6.2 Modèle de calcul de la période d’émulation
6.2.1 Architecture des IPs de multiplexage
6.2.2 Période d’émulation
6.3 Environnement d’expérimentation
6.3.1 Outil de partitionnement WASGA
6.3.2 Plateforme matérielle de prototypage
6.3.3 Comparaison des performances des IPs de multiplexage avec et sans SERDES
6.4 Comparaison des résultats de routage : Branche ou Signal ?
6.4.1 Scénario 1 : Routage de signaux multi-points sur graph unidirectionnel
6.4.2 Scénario 2 : Routage de branches sur un graphe unidirectionnel
6.4.3 Scénario 3 : Routage de signaux multi-terminaux sur un graphe bidirectionnel
6.4.4 Scénario 4 : Routage de branches sur un graphe bidirectionnel
6.4.5 Comparaison des résultats de routage de chaque scénario
6.5 Comparaison des techniques de routage : itératif ou constructif ?
6.6 Comparaison des résultats de prototypage des flots Wasga et Certify
6.6.1 Objectifs de partitionnement
6.6.2 Résultats de prototypage des flots Wasga et Certify
6.7 Conclusion
7 Insertion des IPs de multiplexage et gestion de la congestion
7.1 Introduction
7.2 Spécification des IPs de multiplexage
7.2.1 Architecture de l’IP émettrice
7.2.2 Architecture de l’IP réceptrice
7.2.3 Générateur d’horloge
7.2.4 Environnement de vérification
7.2.5 Variation de taille de l’IP de multiplexage
7.3 Technique de placement basée sur l’estimation de congestion
7.3.1 Architecture du FPGA cible
7.4 Placement avec estimation de congestion
7.4.1 Placement recuit simulé
7.4.2 Estimation de congestion
7.4.3 Qualité de l’estimation de congestion
7.4.4 Résultats
7.5 Conclusion
Conclusion et Perspectives
Liste des publications
Références Bibliographiques
Télécharger le rapport complet
