| As technology scales down to the nanometer era, parasitic effects on interconnect wires dominate the circuit performance in VLSIs, which makes interconnect optimization and physical design critical. Meanwhile, the exponential growth in the number of transistors per chip, together with heterogeneous component geometries, incurs a ultra high complexity to physical designs. A physical planning stage is crucial for the success of a VLSI design. We studied two important problems in the physical planning area: the floorplan representations, and the mixed mode placement.; In the past few years, various representations has been proposed for general floorplans, such as the sequence pair, O-tree, B*-tree, and the corner block list. Many of the representations emphasize on the completeness, thus incurring large redundancies. For the mixed mode placement, the traditional analytical approaches suffers from sub-optimal qualities because of the separation of the wire length optimization and cell spreading in their formulations.; Motivated by the gap between design challenges and the current sub-optimal methods, we proposed three new techniques: (1) A twin binary tree representation with zero redundancy is proposed for general floorplans. A one-to-one relation between general floorplans and twin binary trees is discovered, based on which the number of combinations for general floorplans is derived. Efficient linear time transformations between the representations and floorplans are also introduced.; (2) A unified quadratic programming approach for the mixed mode placement is proposed, which integrates the wire length and cell density in a single cost function for minimization. We introduced a discrete cosine transform based cell density cost function. The proposed technique achieves leading placement qualities comparing to other academia placers.; (3) A multi-level optimization framework is explored for efficient algorithms. A clustering structure based on the placement is generated and dynamically updated. The algebraic multigrid method is adopted for efficiently solving linear systems.; Combining the advanced ideas for floorplanning and placement, we provide a powerful and efficient physical planning methodology. |
