Research On Placement Algorithm Based On Less Flexibility First Principles

With the rapid development of nanometer technology, the design of VLSI meets a great deal challenge. Physical design is an important step of IC layout manufacturing and placement is one of the key technologies in VLSI physical design. VLSI placement is a quite complicated combination optimization problem, which is proved to be a NP-Hard problem. The deterministic placement algorithm based on Less Flexibility First (LFF) Principles has polynomial complexity. The results of experiment show its advantage in area usage comparing to stochastic optimization algorithm. The new technology requires placement algorithm to meet more constraints, such as area, wirelength and congestion. The placement algorithm based on LFF principles should be improved. This paper concerns several aspects of the placement algorithm.Integrated circuit components are not limited to rectangular blocks. They may be L/T shaped, even arbitrary rectilinear block. Therefore new approaches that can effectively and efficiently handle arbitrary rectilinear shaped blocks are essential in VLSI design. The flexibility of arbitrary rectilinear block is introduced and the arbitrary rectilinear block is partitioned into a set of rectangle blocks. Through mapping the rotation of rectilinear block to the rotation of point, the rotation of rectilinear block is settled based on the rotation rule of point. This method can also handle blocks with related position constraint but not connected. Experiment results demonstrate it is better than other algorithm in area usage.In placement, interconnection behavior becomes more and more important. The interconnection behavior of LFF algorithm should be enhanced.Through non-linear method, an approximate model is used to simplify the circuit and obtain the configuration with the best wirelength result. For this configuration, the original flexibility is introduced and used to instruct the latter placement procedure. The local interconnection flexibility of the original LFF algorithm is not exact. Using the local net quantity and the mean net wirelength estimates the local interconnection flexibility and improves the wirelength of placement. To avoid getting the local minimum wirelength, the global interconnection flexibility is introduced, that improves the wirelength of placement. The experiment results show our algorithm can achieve the better wirelenght and better area usage.The congestion of placement declines after introducing the congestion flexibility. In the same time, the wirelength has been improved and the area usage as good as usual.