FastPlace 2.0: an efficient analytical placer for mixed-mode designs

ABSTRACT

In this paper, we present FastPlace 2.0 - an extension to the efficient analytical standard-cell placer - FastPlace [15], to address the mixed-mode placement problem. The main contributions of our work are: (1) Extensions to the global placement framework of FastPlace to handle mixed-mode designs. (2) An efficient and optimal minimum perturbation macro legalization algorithm that is applied after global placement to resolve overlaps among the macros. (3) An efficient legalization scheme to legalize the standard cells among the placeable segments created after fixing the movable macros. On the ISPD 02 Mixed-Size placement benchmarks [31, our algorithm is 16.8X and 7.8X faster than state-of-the-art academic placers Capo 9.1 and Fengshui 5.0 respectively. Correspondingly, we are on average, 12% and 3% better in terms of wirelength over the respective placers.

REFERENCES

• 1: Standard performance evaluation corporation. http://www.spec.org/.
• 2: S. N. Adya , S. Chaturvedi , J. A. Roy , D. A. Papa , I. L. Markov, Unification of partitioning, placement and floorplanning, Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design, p.550-557, November 07-11, 2004 [doi>10.1109/ICCAD.2004.1382639]
• 3: S. N. Adya and I. L. Markov. ISPD02 IBM-MS Mixed-size Placement Benchmarks. http://vlsicad.eecs.umich.edu/BK/ISPD02bench/.
• 4: Saurabh N. Adya , Igor L. Markov, Consistent placement of macro-blocks using floorplanning and standard-cell placement, Proceedings of the 2002 international symposium on Physical design, April 07-10, 2002, San Diego, CA, USA [doi>10.1145/505388.505392]
• 5: S. N. Adya , I. L. Markov, Combinatorial techniques for mixed-size placement, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.10 n.1, p.58-90, January 2005 [doi>10.1145/1044111.1044116]
• 6: Ulrich Brenner , Markus Struzyna, Faster and better global placement by a new transportation algorithm, Proceedings of the 42nd annual conference on Design automation, June 13-17, 2005, San Diego, California, USA [doi>10.1145/1065579.1065733]
• 7: Chin-Chih Chang , Jason Cong , Xin Yuan, Multi-level placement for large-scale mixed-size IC designs, Proceedings of the 2003 conference on Asia South Pacific design automation, January 21-24, 2003, Kitakyushu, Japan [doi>10.1145/1119772.1119835]
• 8: Hans Eisenmann , Frank M. Johannes, Generic global placement and floorplanning, Proceedings of the 35th annual conference on Design automation, p.269-274, June 15-19, 1998, San Francisco, California, United States [doi>10.1145/277044.277119]
• 9: S. Goto. An efficient algorithm for the two-dimensional placement problem in electrical circuit layout. IEEE Trans. Circuits and Systems, CAS-28(1):12--18, 1981.
• 10: A. B. Kahng , Q. Wang, An analytic placer for mixed-size placement and timing-driven placement, Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design, p.565-572, November 07-11, 2004 [doi>10.1109/ICCAD.2004.1382641]
• 11: Ateen Khatkhate , Chen Li , Ameya R. Agnihotri , Mehmet C. Yildiz , Satoshi Ono , Cheng-Kok Koh , Patrick H. Madden, Recursive bisection based mixed block placement, Proceedings of the 2004 international symposium on Physical design, April 18-21, 2004, Phoenix, Arizona, USA [doi>10.1145/981066.981084]
• 12: H. Murata, K. Fujiyoshi, S. Nakatake, and Y. Kajitani. VLSI module placement based on rectangle-packing by the sequence pair. IEEE Trans. Computer-Aided Design, 15(12):1518--1524, December 1996.
• 13: M. Pan, N. Viswanathan, and C. Chu. An efficient and effective detailed placement algorithm. In Proc. IEEE/ACM Intl. Conf. on Computer-Aided Design, pages 48--55, 2005.
• 14: N. Viswanathan and C. C.-N. Chu. ISPD04 IBM Standard Cell Benchmarks with Pads. http://www.public.iastate.edu/~nataraj/ISPD04_Bench.html.
• 15: Natarajan Viswanathan , Chris Chong-Nuen Chu, FastPlace: efficient analytical placement using cell shifting, iterative local refinement and a hybrid net model, Proceedings of the 2004 international symposium on Physical design, April 18-21, 2004, Phoenix, Arizona, USA [doi>10.1145/981066.981072]
• 16: Kristofer Vorwerk , Andrew Kennings, An Improved Multi-Level Framework for Force-Directed Placement, Proceedings of the conference on Design, Automation and Test in Europe, p.902-907, March 07-11, 2005 [doi>10.1109/DATE.2005.59]
• 17: K. Vorwerk , A. Kennings , A. Vannelli, Engineering details of a stable force-directed placer, Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design, p.573-580, November 07-11, 2004 [doi>10.1109/ICCAD.2004.1382642]
• 18: Bo Yao , Hongyu Chen , Chung-Kuan Cheng , Nan-Chi Chou , Lung-Tien Liu , Peter Suaris, Unified quadratic programming approach for mixed mode placement, Proceedings of the 2005 international symposium on Physical design, April 03-06, 2005, San Francisco, California, USA [doi>10.1145/1055137.1055178]
• 19: Hong Yu , Xianlong Hong , Yici Cai, MMP: a novel placement algorithm for combined macro block and standard cell layout design, Proceedings of the 2000 conference on Asia South Pacific design automation, p.271-276, January 2000, Yokohama, Japan [doi>10.1145/368434.368632]

INDEX TERMS

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

Additional Classification:
  B. Hardware
  B.8 Performance and Reliability
      B.8.2 Performance Analysis and Design Aids
  B.m MISCELLANEOUS
      Subjects: Design management

  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:
Design, Performance