In this paper we extend the O-tree approach to handle rectilinear blocks. First we explore the properties of L-shaped blocks, then decompose rectilinear blocks into a set of sub-L-shaped-blocks. The properties of L-shaped blocks can be applied to general recti?linear blocks. In order to explore the optimal search thoroughly, we generate four direction O-trees. A heuristic optimization algorithm based on the four direction O-trees produces very good experiment results.

The ordered tree (O-tree) representation has recently gained much interest in layout design automation. Different from previous topological representations of non-slicing floorplans, the O-tree representation is simpler, needs linear computation effort to generate a corresponding layout, and exhibits a smaller upper-bound of possible configurations. This paper addresses the problem of handling symmetry constraints in the context of the O-tree representation. This problem arises in analog placements, where symmetry is often used to match layout-induced parasitics and to balance thermal couplings in differential circuits. The good performance of our placement tool dealing with several analog designs taken from industry proves the effectiveness of our technique.

Recently, a deterministic algorithm based on the O-tree repre-sentation has been proposed. This method generates excellent layout results on MCNC test cases with O(n3) complexity, where n is the number of blocks. In this paper, we reduce the complexity of the deterministic algorithm to O(n2). Experimental results indicate our algorithm maintains the high quality of the deterministic algorithm at a fraction of the CPU time. 1.