Rectilinear block placement using sequence-pair

ABSTRACT

With the recent advent of deep sub-micron technology and new packaging schemes such as Multi-Chip Modules(MCMs), integrated circuit components are often not rectangular. Most existing block placement approaches, however, only deal with rectangular blocks, resulting in inefficient area utilization. New approaches which can handle arbitrarily shaped blocks are essential to achieve high performance design. In this paper, we present an approach extending the sequence-pair approach for rectangular block placement to arbitrarily sized and shaped rectilinear blocks. Experimental results show that our algorithm achieves results with excellent area utilization.

REFERENCES

• 1: Hiroshi Murata , Kunihiro Fujiyoshi , Shigetoshi Nakatake , Yoji Kajitani, Rectangle-packing-based module placement, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.472-479, November 05-09, 1995, San Jose, California, United States
• 2: Jin Xu , Pei-Ning Guo , Chung-Kuan Cheng, Cluster refinement for block placement, Proceedings of the 34th annual conference on Design automation, p.762-765, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266366]
• 3: M. Kang, W. W.-M. Dai, "General Floorplanning with L-shaped, T-shaped and Soft Blocks Based on Bounded Slicing Grid Structure", Proc. 1997 ASP-DAC, pp. 265- 270, 1997.
• 4: S. Nakatake, H. Murata, K. Fujiyoshi, Y. Kajitani, "Bounded-Slicing Structure for Module Placement", Technical Report of the Institute of Electronics, Information and Communication Engineers of Japan, vol. VLD94, pp. 19-24, 1994.
• 5: Tsu-chang Lee, A bounded 2D contour searching algorithm for floorplan design with arbitrarily shaped rectilinear and soft modules, Proceedings of the 30th international conference on Design automation, p.525-530, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.165014]
• 6: C.K. Cheng, E.S. Kuh, "Module Placement based on Resistive Network Optimization", IEEE Trans. Computer-Aided Design, vol. CAD-3, pp. 218-225, July 1984.
• 7: Hidetoshi Onodera , Yo Taniguchi , Keikichi Tamaru, Branch-and-bound placement for building block layout, Proceedings of the 28th conference on ACM/IEEE design automation, p.433-439, June 17-22, 1991, San Francisco, California, United States [doi>10.1145/127601.127708]
• 8: H. Shin, A. L. Sangiovanni-Vincentelli, C. H. Sequin, 'Zone-Refining' Techniques for IC Layout Compaction", IEEE Trans. Computer-Aided Design, vol. 9, Feb. 1990.
• 9: D.F. Wong, C.L. Liu, "Floorplan Design for Rectangular and L-shaped Modules", Proc. IEEE International Conf. on Computer-Aided Design, pp. 520-523, 1987.
• 10: B. T. Preas , W. M. vanCleemput, Placement algorithms for arbitrarily shaped blocks, Proceedings of the 16th Conference on Design automation, p.474-480, June 25-27, 1979, San Diego, CA, United States

INDEX TERMS

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

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Layout
  B.8 Performance and Reliability

General Terms:
Algorithms, Design, Experimentation, Performance, Theory