Placement & Constrained Placement Optimization In VLSI Physical Design

As microelectronic technology advances, integration scale increases dramatically while feature size of VLSI is shrinking to deep-submicron or even to nanometer. It makes VLSI physical design more complicate and critical than ever before. As the early stage of VLSI physical design, floorplan/placement not only determines performance of a circuit directly, but also influences the following routing stage greatly. Therefore, floorplan/placement becomes the critical stage in VLSI design.In this thesis, based on overall analysis of influential factors in floorplan and placement, some frontier fields of floorplan/placement, including placement algorithm optimization, conditions of constrainted placements, placement-based routing optimization and standard cell placement etc., are explored and investigated. Some useful characteristics of floorplan/placement are discovered and a few novel ideas are proposed.The main results are as follows:1.In the placement algorithm field, effects of employed data structures and module placement methods on efficiency of module placement algorithms are investigated in detail. A new data structure, which is named corner-contour, is proposed and its property of stairway descending in left-right direction is proved. Combining it with coding scheme of single-sequence (SS) and O-tree representations, the induced algorithms can improve corresponding module placement largely. Another data structure, which is named concave-contour, is also presented to solve the fixed-outline packing problems, which are arising in modern VLSI physical design recently. Guiding properties of bounding rectangle and its diagonal line on the placement algorithm are also studied and utilized to accelerate module placement process. Furthermore, based on boundary constraints of SS, fast evaluation of a candidate code is realized without performing whole placement process. It can reduce the exploring scope and boost convergence of the placement algorithm largely.2.In the constrained placement field, according to the detail analysis of the coding scheme of SS representation, sufficient and necessary conditions of boundary constraints of SS are proposed and proved. Their explicit expressions in numeric string modes are also been derived. Because SS is a novel floorplan/placement representation, this result will further complete it theoretically.3.In the routing field, the correspondence between an SS code and the induced floorplan is explored in detail. Based on boundary constraints of SS representation, a floorplan is structurally peeled and structure of the corresponding floorplan configuration is uncovered. This structural analysis of a floorplan can not only facilitate the module placement, but also guide the module placement to optimize the following routing purposefully. This may lead a way to solve routing-related problems from floorplan/placement perspective. Besides, based on characteristics of B*-tree, the routability between any module pair is solved smoothly by inserting dummy modules into the corresponding code. It can solve the module-pair interconnection problem and relieve local routing congestion at the after-placement design stage.4.In the standard cell placement area, a novel coding scheme of standard cell placement, which is named Ordered Single Chain Tree (OSCT), is proposed. The numeric string mode makes it facilitative to realize boundary constraints and routing optimization. Based on the OSCT coding scheme, more widely and accurately optimal searching can be implemented by utilizing any heuristics in the standard cell placement field.