Proceedings - ACM IEEE Design Automation Conference · 2007 · 46 citations · 14 references
EngineeringComputational EngineeringAnalog ElectronicsOptimizationAnalog DesignAnalog Integrated CircuitsAnalog IntegrationMixed-signal Integrated Circuit DesignPhysical DesignVery-large-scale Integration LayoutAnalog Circuit DesignAnalog Layout DesignAnalog Placement OptimizationPlacementPlacement Algorithms
In this paper, we present the first amortized linear-time packing algorithm for the placement with symmetry con-straints. We first introduce the concept of a symmetry is-land which is formed by modules of the same symmetry group in a single connected placement. Based on this con-cept and the B*-tree representation, we propose automati-cally symmetric-feasible B*-trees (ASF-B*-trees) to directly model the placement of a symmetry island. Unlike the pre-vious works that can handle only 1D symmetry constraints, our ASF-B*-tree is the first in the literature to addition-ally 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 guar-antee the close proximity of symmetry modules and signifi-cantly 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.
14
Optimization by Simulated Annealing
Scott Kirkpatrick, C. D. Gelatt, M.P. Vecchi · Science · 1983 · 44.6K citations
Yun-Chih Chang, Yao‐Wen Chang, Guangming Wu et al. · 2000 · 544 citations · Full text