Efficient solution space exploration based on segment trees in analog placement with symmetry constraints

ABSTRACT

The traditional way of approaching devicelevel placement problems for analog layout is to explore a huge search space of absolute placement representations, where cells are allowed to illegally overlap during their moves [2, 7, 8]. This paper presents a novel analog placement technique operating on the set of binary tree representations of the layout [3], where the typical presence of an arbitrary number of symmetry groups of devices is directly taken into account during the exploration of the solution space. The efficiency of the novel approach is due to a data structure called segment tree, mainly used in computational geometry.

REFERENCES

• 1: F. Balasa, K. Lampaert, "Symmetry within the sequence-pair representation in the context of placement for analog design," IEEE Trans. CAD, Vol. 19, pp. 721--731, July 2000.
• 2: John M. Cohn, Analog Device-Level Layout Automation, Kluwer Academic Publishers, Norwell, MA, 2000
• 3: 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]
• 4: Pei-Ning Guo , Chung-Kuan Cheng , Takeshi Yoshimura, An O-tree representation of non-slicing floorplan and its applications, Proceedings of the 36th ACM/IEEE conference on Design automation, p.268-273, June 21-25, 1999, New Orleans, Louisiana, United States [doi>10.1145/309847.309928]
• 5: Xianlong Hong , Gang Huang , Yici Cai , Jiangchun Gu , Sheqin Dong , Chung Kuan Cheng , Jun Gu, Corner block list: an effective and efficient topological representation of non-slicing floorplan, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
• 6: Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
• 7: K. Lampaert, G. Gielen, W. Sansen, "A performance-driven placement tool for analog integrated circuits" IEEE J. of Solid-State Circ., Vol. SC-30, No. 7, pp. 773--780, July 1995.
• 8: E. Malavasi, E. Charbon, E. Felt, A. Sangiovanni-Vincentelli, "Automation of IC layout with analog constraints," IEEE Trans. CAD, Vol. 15, No. 8, pp. 923--942, Aug. 1996.
• 9: H. Murata et al., "VLSI module placement based on rectangle-packing by the sequence-pair," IEEE Trans. CAD, Vol. 15, No. 12, pp. 1518--1524, Dec. 1996.
• 10: S. Nakatake, K. Fujiyoshi, H. Murata, Y. Kajitani, "Module packing based on the BSG-structure and IC layout applications," IEEE Trans. CAD, Vol. 17, pp. 519--530, June 1998.
• 11: 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]
• 12: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
• 13: Xiaoping Tang , D. F. Wong, FAST-SP: a fast algorithm for block placement based on sequence pair, Proceedings of the 2001 conference on Asia South Pacific design automation, p.521-526, January 2001, Yokohama, Japan [doi>10.1145/370155.370523]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.3 Other Architecture Styles
          Subjects: Analog computers

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Placement and routing

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Routing and layout

General Terms:
Experimentation, Theory