Analog placement based on novel symmetry-island formulation

Po-Hung Lin*, Shyh Chang Lin


研究成果: Conference contribution同行評審

41 引文 斯高帕斯(Scopus)


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.

主出版物標題2007 44th ACM/IEEE Design Automation Conference, DAC'07
出版狀態Published - 2 八月 2007
事件2007 44th ACM/IEEE Design Automation Conference, DAC'07 - San Diego, CA, United States
持續時間: 4 六月 20078 六月 2007


名字Proceedings - Design Automation Conference


Conference2007 44th ACM/IEEE Design Automation Conference, DAC'07
國家/地區United States
城市San Diego, CA