Partitionnement de très grandes netlists sur architectures hiérarchiques multi-niveaux

J. Pistorius

LIP6 1999/031: THÈSE de DOCTORAT de l'UNIVERSITÉ PARIS 6 LIP6 / LIP6 research reports
198 pages - Novembre/November 1999 - French document.

PostScript : 550 Ko /Kb

Contact : par mail / e-mail

Thème/Team: Algorithmique Numérique et Parallélisme

Titre français : Partitionnement de très grandes netlists sur architectures hiérarchiques multi-niveaux
Titre anglais : Partitioning of Very Large Netlists on Multi-Level Hierarchical Architectures

Résumé : 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.

Abstract : The increasing size of large electronic systems has recently led to their implementation on architectures with several levels of hierarchy. The partitioning of a design into each of the hierarchical levels is one step towards its implementation on such an architecture. The main applications that motivate our research lie in the domain of rapid prototyping and hardware emulation. Therefore, we validated our approach on the hierarchical architecture of the CELARO emulator from Mentor Graphics. Todays partitioning techniques for hierarchical architectures all use the same algorithms on the different levels and optimize the partitioning results on each level of the hierarchy without taking into account the dependencies between these results. This is the context of our research. A method is proposed that improves the global partitioning result in terms of both hardware resources needed for the implementation of a design, and CPU time. This method is based on an extensive study of existing algorithms which permitted the identification of those that are well-suited for the partitioning of very large netlists on hierarchical architectures. The analysis of the performances of these algorithms is based on a set of experimental results that have been obtained by applying the chosen algorithms on a certain number of representative netlists. With this analysis, we identified various advantages and disadvantages of the existing algorithms, and were able to improve them in order to produce a better adaptation on the hierarchical structure of the architecture. Depending on the performances of the different algorithms, they were combined in order to form partitioning tools dedicated to each level of the hierarchy. An experimental comparison of these tools allowed the identification of several approaches of interest. The scheduling of these approaches also has an influence on the result. An experimental analysis of various combinations finally led to a small number of approaches that were particularly performant. This set of approaches was the basis for an extensive experimental, and comparative study on a set of very large, real, industrial netlists and very large, randomly generated netlists. The results obtained for the first three levels of the CELARO emulator show that the tools and the method developed during this work lead to significant improvements in terms of required hardware resources: we achieved an average gain of 15 to 38. In addition, the execution time decreased between 80 and 85 for the partitioning of the same netlists.

Mots-clés : Partitionnement, Architecture hiérarchique, Générateur de netlists aléatoires, Circuit programmable

Key-words : Partitioning, Hierarchical architecture, Benchmark generator, Programmable circuit

Publications internes LIP6 1999 / LIP6 research reports 1999

Responsable Éditorial / Editor :Emmanuelle.Encrenaz@lip6.fr