Analog placement based on novel symmetry-island formulation

Po-Hung Lin*, Shyh Chang Lin

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

41 Scopus citations


In this paper, we present the first amortized linear-time packing algorithm for the placement with symmetry constraints. We first introduce the concept of a symmetry island which is formed by modules of the same symmetry group in a single connected placement. Based on this concept and the B*-tree representation, we propose automatically symmetric-feasible B*-trees (ASF-B*-trees) to directly model the placement of a symmetry island. Unlike the previous works that can handle only ID symmetry constraints, our ASF-B*-tree is the first in the literature to additionally consider 2D symmetry. We then present hierarchical B*-trees (HB*-trees) which can simultaneously optimize the placement with both symmetry islands and non-symmetry modules. Unlike the previous works, our approach can guarantee the close proximity of symmetry modules and significantly reduce the search space based on the symmetry-island formulation. In particular, the packing time for an ASF-B*-tree or an HB*-tree is the same as that for a plain B*-tree (only amortized linear) and much faster than previous works which need at least loglinear time. Experimental results show that our approach achieves the best published quality and runtime efficiency for analog placement.

Original languageEnglish
Title of host publication2007 44th ACM/IEEE Design Automation Conference, DAC'07
Number of pages6
StatePublished - 2 Aug 2007
Event2007 44th ACM/IEEE Design Automation Conference, DAC'07 - San Diego, CA, United States
Duration: 4 Jun 20078 Jun 2007

Publication series

NameProceedings - Design Automation Conference
ISSN (Print)0738-100X


Conference2007 44th ACM/IEEE Design Automation Conference, DAC'07
CountryUnited States
CitySan Diego, CA


  • Analog placement
  • Floorplanning
  • Symmetry

Cite this