Cluster refinement for block placement

ABSTRACT

We propose an iterative optimization approach for mixedmacro-cell and standard-cell placement, which minimizes the chipsize and interconnection wire length at the same time. We present abranch-and-bound algorithm which efficiently searches for the optimalsolution by evaluating all of the possible configurations on theselected cluster to minimize the gap distance between the ceilingand the floor. A virtual grid and permutation order are generateddynamically to eliminate redundant branches, which was the causeof much higher complexity in other approaches. Experimentalresults on the MCNC benchmark circuits show that the algorithmachieves very competitive results to manual design.

REFERENCES

• 1: 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.
• 2: W. M. Dai, E. S. Kuh, "Simultaneous Floor Planning and Global Routing for Hierarchical Building-Block Layout", IEEE Trans. Computer- Aided Design, vol. CAD-6, pp. 828-837, Sept. 1987.
• 3: 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]
• 4: 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
• 5: 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]
• 6: H. Shin, A. L. Sangiovanni-Vincentelli, C. H. Sequin, "'Zone-Refining' Techniques for IC Layout Compaction", IEEE Trans. Computer-Aided Design, vol. 9, pp. 167-178, Feb. 1990.
• 7: D. F. Wong , C. L. Liu, A new algorithm for floorplan design, Proceedings of the 23rd ACM/IEEE conference on Design automation, p.101-107, July 1986, Las Vegas, Nevada, United States
• 8: Takayuki Yamanouchi , Kazuo Tamakashi , Takashi Kambe, Hybrid floorplanning based on partial clustering and module restructuring, Proceedings of the 1996 IEEE/ACM international conference on Computer-aided design, p.478-483, November 10-14, 1996, San Jose, California, 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.4 INPUT/OUTPUT AND DATA COMMUNICATIONS
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: VLSI (very large scale integration)

  C. Computer Systems Organization

  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis

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