Floorplanning algorithms for VLSI physical design automation

The increase in complexity of very large scale integrated (VLSI) systems has imposed many new challenges for physical design automation. Floorplanning is a critical phase in the physical design cycles since the overall quality of the layout, in terms of area and performance is mainly determined in this phase.; Floorplanning is to pack all the circuit elements in a chip without violating design rules, so that the circuit performs well and the production yield is high. Many existing layout design algorithms, however, are not able to scale well to match the rapid increase in design complexity. The objective of this dissertation is to develop efficient floorplanning algorithms for VLSI designs.; The O-tree representation has recently gained increasing interest: compared to other representations (slicing structure, sequence-pair, BSG), O-trees need a smaller amount of encoding storage and linear time computation effort to generate each placement configuration. In addition, the upper-bound of possible encodings is smaller, therefore, a smaller search space for any optimization algorithm. These important advantages are strong incentives for us to address the floorplanning problems in the context of the O-tree representation.; We present an efficient algorithm to handle the core floorplanning problem. Our main algorithm—the enhanced perturbing algorithm performs a greedy perturbation each time and try to reach a local optimum very quickly. It can be used to improve an existing floorplan and can be extended to carry out a complete floorplan design.; We address the problem of handling symmetry constraints. This problem arises in analog placement, where symmetry is often used to match layout-induced parasitics and to balance thermal couplings in differential circuits. We add these additional constraints in the representation of general blocks. When we explore the space of the O-trees we only consider the symmetric-feasible O-trees since only symmetric-feasible O-trees can lead to consistent placements satisfying the O-tree constraints and the symmetric constraints.; We extend the O-tree approach to handle rectilinear blocks. First we explore the properties of L-shaped blocks, then decompose arbitrarily shaped rectilinear blocks into a set of sub-L-shaped-blocks. The properties of L-shaped blocks can be applied to general rectilinear blocks.; We applied our algorithms to several test cases. The good performance of our placement tools proves the effectiveness of our technique.