Une methode de multi-partitionnenment de circuits VLSI en vue d'un placement et routage

The design of integrated circuits in micro-electronics requires layout mask drawings which are obtained with two tasks: placement and routing. This work contains a first study of various automatic placement techniques. We then study the chosen placement technique: partitioning. Given as input a VLSI circuit described as a set of interconnected cells, partitioning consists of dividing the cells of the circuit into n parts guided by a given objective function. The present research paper therefore deals with the development of a new multi-partitioning method adapted to VLSI circuits.;Attempting to minimize the total length of the interconnections while maintaining parts of proportional sizes, the choice of the cells to move from one part to another is guided by alternating objectives. The method either tries to optimize the balance between the sizes of the parts or aims at optimizing the cut (number of nets that link the parts). A flexible net cost function enables a good approximation of the interconnection lengths in order to estimate the quality of the partitioning.;The partitioning method developed generates experimental results of good quality. Both the memory space needed and the execution times vary linearly with the number of parts generated. The memory space required also varies linearly with the number of cell of the circuits. The execution times, on the other hand were not clearly related to the number of cells. These time results were more clearly related to the number of improvement loops needed before the heuristic encounters the stopping criterion. Moreover, the experimental results demonstrate that the disproportion constants (final disproportion wanted, tolerated disproportion, etc.) have a great influence on the quality of the partitioning. (Abstract shortened by UMI.)...