Constraint-driven floorplan repair

ABSTRACT

Floorplanning algorithms have traditionally underperformed experienced designers, even when relatively simple interconnect metrics are concerned. However, the sheer scale of modern systems on chip makes an all-manual design flow infeasible. In this paper, we propose a new efficient automated approach to the floorplan repair problem, where a set of violated design constraints are satisfied by applying small changes to an existing rough floorplan. Such a floorplan can be produced by a human designer, by a scalable placement algorithm, or result from engineering adjustments to a pre-existing floorplan. In all cases, overlapping modules must be separated, and in some instances, modules may need to be repositioned to satisfy other requirements.The algorithmic framework we propose is built upon an expressive graph-based encoding of constraints. While capable of representing floorplans with or without overlapping modules, it can also support the outline of the core area, fixed module locations, region constraints, proximity and alignment constraints, etc. Instead of applying randomized local search in the hope of satisfying these constraints, we track all implications of imposed constraints and resolve violations by invoking gradual modifications to the floorplan.The primary focus of this paper is on a particularly efficient conflict-directed algorithm for floorplan repair and legalization. It is shown to completely eliminate overlaps from layouts produced by Capo 9.4, Feng Shui 5.1 and APlace 2.01 on IBM-HB benchmarks with hard blocks, typically requiring negligible runtime and increasing interconnect length by only several percent. Furthermore, we are able to generate legal solutions for these instances that surpass previously reported results in wirelength by an average of roughly 7%.

REFERENCES

• 1: S. N. Adya and I. L. Markov. Fixed-outline Floorplanning: Enabling Hierarchical Design. In IEEE Trans. on VLSI Systems, vol. 11(6), pages 1120--1135, 2003.
• 2: Ulrich Brenner , Anna Pauli , Jens Vygen, Almost optimum placement legalization by minimum cost flow and dynamic programming, Proceedings of the 2004 international symposium on Physical design, April 18-21, 2004, Phoenix, Arizona, USA [doi>10.1145/981066.981069]
• 3: 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]
• 4: J. Cong , M. Romesis , J. R. Shinnerl, Robust mixed-size placement under tight white-space constraints, Proceedings of the 2005 IEEE/ACM International conference on Computer-aided design, p.165-172, November 06-10, 2005, San Jose, CA
• 5: J. Cong, M. Romesis, and J. Shinnerl. Fast floorplanning by look-ahead enabled recursive bipartitioning. Technical Report TR040043, Computer Science Dept., UCLA, 2004.
• 6: Jason Cong , Michail Romesis , Joseph R. Shinnerl, Fast floorplanning by look-ahead enabled recursive bipartitioning, Proceedings of the 2005 conference on Asia South Pacific design automation, January 18-21, 2005, Shanghai, China [doi>10.1145/1120725.1120838]
• 7: Jason Cong , Min Xie, A robust detailed placement for mixed-size IC designs, Proceedings of the 2006 conference on Asia South Pacific design automation, January 24-27, 2006, Yokohama, Japan [doi>10.1145/1118299.1118353]
• 8: D. Hill. Method and system for high speed detailed placement of cells within an integrated circuit design, US Patent 6370673, April 2002.
• 9: A. B. Kahng , S. Reda , Qinke Wang, Architecture and details of a high quality, large-scale analytical placer, Proceedings of the 2005 IEEE/ACM International conference on Computer-aided design, p.891-898, November 06-10, 2005, San Jose, CA
• 10: 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]
• 11: Y. Liao and C. K. Wong. An algorithm to compact a VLSI symbolic layout with mixed constraints. In IEEE Transactions on CAD, Vol. 2, No. 2, 1983.
• 12: M. D. Moffitt and M. E. Pollack. Optimal rectangle packing: a meta-CSP approach. To appear in Proc. of ICAPS '06, 2006.
• 13: Sudip Nag , Kamal Chaudhary, Post-placement residual-overlap removal with minimal movement, Proceedings of the conference on Design, automation and test in Europe, p.116-es, January 1999, Munich, Germany [doi>10.1145/307418.307568]
• 14: Aaron N. Ng , Igor L. Markov , Rajat Aggarwal , Venky Ramachandran, Solving hard instances of floorplacement, Proceedings of the 2006 international symposium on Physical design, April 09-12, 2006, San Jose, California, USA [doi>10.1145/1123008.1123047]
• 15: 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]
• 16: Haoxing Ren , David Z. Pan , Charles J. Alpert , Paul Villarrubia, Diffusion-based placement migration, Proceedings of the 42nd annual conference on Design automation, June 13-17, 2005, San Diego, California, USA [doi>10.1145/1065579.1065712]
• 17: Jarrod A. Roy , David A. Papa , Saurabh N. Adya , Hayward H. Chan , Aaron N. Ng , James F. Lu , Igor L. Markov, Capo: robust and scalable open-source min-cut floorplacer, Proceedings of the 2005 international symposium on Physical design, April 03-06, 2005, San Francisco, California, USA [doi>10.1145/1055137.1055184]
• 18: Evangeline F. Y. Young , M. L. Ho , Chris C. N. Chu, A Unified Method to Handle Different Kinds of Placement Constraints in Floorplan Design, Proceedings of the 2002 conference on Asia South Pacific design automation/VLSI Design, p.661, January 07-11, 2002

INDEX TERMS

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

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

General Terms:
Algorithms, Design

Keywords:
constraints, floorplanning, legalization