FastPlace: an analytical placer for mixed-mode designs

ABSTRACT

Modern designs often contain a combination of a large number of standard cells and macro blocks. Traditionally large macro blocks are handled at the floorplanning level, after which their positions are fixed. The standard cells are then handled during the placement level. Current designs can have hundreds of large and medium sized macro blocks and a large number of standard cells. As a result, traditional floorplanning techniques cannot scale to this problem, both in terms of runtime and solution quality. Hence a technique is required to simultaneously handle this combination of placeable objects.In this paper, we present a combined placement and floorplanning approach for mixed-mode placement. We extend the efficient analytical placement algorithm FastPlace by integrating a simulated annealing based floorplanner to solve the global placement problem for mixed-mode designs. We also present an efficient and effective detailed placement algorithm to improve the wirelength of the global placement solution based on a greedy swapping heuristic.

REFERENCES

• 1: The International Technology Roadmap for Semiconductors. Semiconductor Industry Association, 2004.
• 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: 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]
• 4: 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]
• 5: Ameya Agnihotri , Mehmet Can YILDIZ , Ateen Khatkhate , Ajita Mathur , Satoshi Ono , Patrick H. Madden, Fractional Cut: Improved Recursive Bisection Placement, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.307, November 09-13, 2003 [doi>10.1109/ICCAD.2003.72]
• 6: 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]
• 7: S. Goto. An efficient algorithm for the two-dimensional placement problem in electrical circuit layout. IEEE Trans. on Circuits and Systems, Vol. CAS-28(1):12--18, 1981.
• 8: G. Karypis. Multilevel Optimization in VLSICAD. Kluwer Academic Publishers, 2003.
• 9: 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]
• 10: N. Viswanathan and C. C.-N. Chu. Fastplace: Efficient analytical placement using cell shifting, iterative local refinement and a hybrid net model. IEEE Trans. Computer-Aided Design, to appear, 2005.
• 11: 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

General Terms:
Algorithms, Design

Keywords:
analytical placement, floorplanning, mixed-mode placement