LIP6 1999/031
- Thesis
Partitionnement de très grandes netlists sur architectures hiérarchiques multi-niveaux - J. Pistorius
- 198 pages - 11/16/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
- Keywords : Partitioning, Hierarchical architecture, Benchmark generator, Programmable circuit
- Publisher : Emmanuelle.Encrenaz (at) nulllip6.fr
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.