Thumbnail
Access Restriction
Subscribed

Author Po-Hung Lin ♦ Shyh-Chang Lin
Source IEEE Xplore Digital Library
Content type Text
Publisher Institute of Electrical and Electronics Engineers, Inc. (IEEE)
File Format PDF
Copyright Year ©2007
Language English
Subject Domain (in DDC) Technology ♦ Engineering & allied operations
Subject Keyword Algorithm design and analysis ♦ Binary trees ♦ Space exploration ♦ Research and development ♦ Runtime ♦ Analog integrated circuits ♦ Integrated circuit layout ♦ Routing ♦ Voltage ♦ Thermal degradation ♦ floorplanning ♦ Algorithms ♦ Design ♦ Analog placement ♦ symmetry
Abstract 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.
Description Author affiliation: Nat. Taiwan Univ., Taipei (Po-Hung Lin)
ISBN 9781595936271
ISSN 0738100X
Educational Role Student ♦ Teacher
Age Range above 22 year
Educational Use Research ♦ Reading
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2007-06-04
Publisher Place USA
Rights Holder Association for Computing Machinery, Inc. (ACM)
Size (in Bytes) 389.32 kB
Page Count 6
Starting Page 465
Ending Page 470


Source: IEEE Xplore Digital Library