Analog placement based on novel symmetry-island formulation

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 1D 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.

REFERENCES

• 1: F. Balasa and K. Lampaert, "Symmetry within the sequence-pair representation in the context of placement for analog design," IEEE TCAD, vol. 19, no. 3, pp. 721--731, Jul. 2000.
• 2: Florin Balasa, Modeling non-slicing floorplans with binary trees, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
• 3: Florin Balasa , Sarat C. Maruvada , Karthik Krishnamoorthy, Efficient solution space exploration based on segment trees in analog placement with symmetry constraints, Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design, p.497-502, November 10-14, 2002, San Jose, California [doi>10.1145/774572.774645]
• 4: Florin Balasa , Sarat C. Maruvada , Karthik Krishnamoorthy, Using red-black interval trees in device-level analog placement with symmetry constraints, Proceedings of the 2003 conference on Asia South Pacific design automation, January 21-24, 2003, Kitakyushu, Japan [doi>10.1145/1119772.1119945]
• 5: F. Balasa, S. C. Maruvada, and K. Krishnamoorthy, "On the exploration IEEE TCAD, vol. 23, no. 2, pp. 177--191, Feb. 2004.
• 6: Yun-Chih Chang , Yao-Wen Chang , Guang-Ming Wu , Shu-Wei Wu, B*-Trees: a new representation for non-slicing floorplans, Proceedings of the 37th conference on Design automation, p.458-463, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337541]
• 7: J. M. Cohn, D. J. Garrod, R. A. Rutenbar, and L. R. Charley, "KOAN/ANAGRAM II: New tools for device-level analog placement and routing," IEEE JSSC, vol. 26, pp. 330--342, Mar. 1991.
• 8: S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, "Optimization by Simulated Annealing," Science, vol. 220, no. 4598, pp. 671--680, May 1983.
• 9: Shinichi Kouda , Chikaaki Kodama , Kunihiro Fujiyoshi, Improved method of cell placement with symmetry constraints for analog IC layout design, Proceedings of the 2006 international symposium on Physical design, April 09-12, 2006, San Jose, California, USA [doi>10.1145/1123008.1123050]
• 10: J.-M. Lin, H.-E. Yi, and Y.-W. Chang, "Module placement with boundary constraints using B*-trees," IEE Proceedings -- Circuits, Devices and Systems, vol. 149, no. 4, pp. 251--256, Aug. 2002.
• 11: Jai-Ming Lin , Guang-Ming Wu , Yao-Wen Chang , Jen-Hui Chuang, Placement with symmetry constraints for analog layout design using TCG-S, Proceedings of the 2005 conference on Asia South Pacific design automation, January 18-21, 2005, Shanghai, China [doi>10.1145/1120725.1120842]
• 12: S. C. Maruvada, A. Berkman, K. Krishnamoorthy, and F. Balasa, "Deterministic skip lists in analog topological placement," Proc. ASICON, pp. 756--759, Oct. 2005.
• 13: Yingxin Pang , Florin Balasa , Koen Lampaert , Chung-Kuan Cheng, Block placement with symmetry constraints based on the O-tree non-slicing representation, Proceedings of the 37th conference on Design automation, p.464-467, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337545]
• 14: Yiu-Cheong Tam , Evangeline F. Y. Young , Chris Chu, Analog placement with symmetry and other placement constraints, Proceedings of the 2006 IEEE/ACM international conference on Computer-aided design, November 05-09, 2006, San Jose, California [doi>10.1145/1233501.1233571]
• 15: Guang-Ming Wu , Yun-Chih Chang , Yao-Wen Chang, Rectilinear block placement using B*-trees, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.8 n.2, p.188-202, April 2003 [doi>10.1145/762488.762490]

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids

General Terms:
Algorithms, Design

Keywords:
analog placement, floorplanning, symmetry