LIP6 1999/031
- Thèse
Partitionnement de très grandes netlists sur architectures hiérarchiques multi-niveaux - J. Pistorius
- 198 pages - 16/11/1999- document en - http://www.lip6.fr/lip6/reports/1999/lip6.1999.031.ps.gz - 563 Ko
- Contact : Joachim.Pistorius (at) nulllip6.fr
- Ancien Thème : ANP
- Mots clés : Partitionnement, Architecture hiérarchique, Générateur de netlists aléatoires, Circuit programmable
- Directeur de la publication : Emmanuelle.Encrenaz (at) nulllip6.fr
Les évolutions technologiques récentes ont fait apparaître, pour le développement de grands systèmes électroniques, des architectures à plusieurs niveaux de hiérarchie. Le partitionnement sur chacun des niveaux d'une telle architecture, est une des étapes lors de la réalisation d'un design. Les principales applications qui motivent notre étude se situent dans le domaine du prototypage à l'aide de circuits programmables, ou dans le domaine de l'émulation. Ainsi, l'architecture de l'émulateur CELARO de Mentor Graphics nous a servi de modèle d'études. Les approches connues à ce jour utilisent toutes les mêmes algorithmes et optimisent le résultat du partitionnement sur chacun des niveaux de la hiérarchie sans prendre en compte l'interdépendance des résultats entre les differents niveaux. C'est précisement dans ce contexte que se place cette thèse, dans laquelle nous proposons une méthodologie permettant d'améliorer le résultat global du partitionnement en terme de ressources matérielles utilisées et en terme de temps de calcul. La méthodologie est basée sur une étude bibliographique approfondie qui a permis de sélectionner les algorithmes les plus susceptibles d'apporter les améliorations voulues. L'analyse des performances des différents algorithmes retenus est effectuée à l'aide d'un ensemble de résultats expérimentaux obtenus par l'application des algorithmes choisis sur un groupe représentatif de netlists. Grâce a cette analyse, nous avons identifié les divers avantages et inconvénients de chacun de ces algorithmes, et pu les modifier en vue d'une meilleure adaptation à leur usage dans le cadre d'une architecture hiérarchique. Selon les performances des algorithmes, ceux-ci ont été combinés afin de déterminer plusieurs outils de partitionnement dédiés à chaque niveau hiérarchique. Une comparaison expérimentale systématique de ces outils à l'aide d'un banc de test permet de déterminer les approches performantes. L'enchaînement des différents outils de partitionnement a également une influence sur le résultat. Une analyse expérimentale des différentes combinaisons possibles nous a conduit à en identifier un petit nombre particulièrement performants. A partir de cette sélection, nous avons effectué une étude expérimentale comparative systématique sur un ensemble de netlists de grandes tailles, industrielles ou générées. Les résultats obtenus sur les 3 premiers niveaux de l'émulateur CELARO montrent que la mise en oeuvre de l'ensemble des outils et de la méthodologie élaborés au cours de cette thèse conduit à des améliorations très significatives en terme de volume de matériel nécessaire : en moyenne un gain évoluant entre 15 et 38. Parallèlement, le temps de calcul a été diminué entre 80 et 85 pour les mêmes netlists.