Floorplanning with alignment and performance constraints

ABSTRACT

In this paper, we present a floorplanning algorithm based on sequence pair representation. Our floorplanner has the following important features: 1) It is explicitly designed for fixed-frame floorplanning, which is different from traditional well-researched min-area floorplanning. Moreover, we also show that it can be adapted to minimize total area. 2) It addresses the problem of handling alignment constraint which arises in bus structure. 3) It deals with performance constraint such as bounded net delay, while many existing floorplanners just minimize total wire length. 4) More importantly, even with all these constraints the algorithm is very fast in that it evaluates the feasibility of a sequence pair and translates to a floorplan in O(n log log n) time typically where n is the number of blocks and the number of constrained blocks is O(n), which is significantly faster than the O(n³) method operating on constraint graph. Our algorithm is based on computing the longest common subsequence of a pair of weighted sequences. Experimental results on MCNC benchmark for block placement show the promise of the method.

REFERENCES

• 1: Fixed-Outline Floorplanning through Better Local Search, Proceedings of the International Conference on Computer Design: VLSI in Computers & Processors, p.328, September 23-26, 2001
• 2: Yun-Chih Chang , Yao-Wen Chang , Guang-Ming Wu , Shu-Wei Wu, B*-Trees: a new representation for non-slicing floorplans, Proceedings of the 37th conference on Design automation, p.458-463, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337541]
• 3: Pinhong Chen , Ernest S. Kuh, Floorplan sizing by linear programming approximation, Proceedings of the 37th conference on Design automation, p.468-471, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337547]
• 4: Kunihiro Fujiyoshi , Hiroshi Murata, Arbitrary convex and concave rectilinear block packing using sequence-pair, Proceedings of the 1999 international symposium on Physical design, p.103-110, April 12-14, 1999, Monterey, California, United States [doi>10.1145/299996.300034]
• 5: Pei-Ning Guo , Chung-Kuan Cheng , Takeshi Yoshimura, An O-tree representation of non-slicing floorplan and its applications, Proceedings of the 36th ACM/IEEE conference on Design automation, p.268-273, June 21-25, 1999, New Orleans, Louisiana, United States [doi>10.1145/309847.309928]
• 6: Xianlong Hong , Gang Huang , Yici Cai , Jiangchun Gu , Sheqin Dong , Chung Kuan Cheng , Jun Gu, Corner block list: an effective and efficient topological representation of non-slicing floorplan, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
• 7: Andrew B. Kahng, Classical floorplanning harmful?, Proceedings of the 2000 international symposium on Physical design, p.207-213, May 2000, San Diego, California, United States [doi>10.1145/332357.332401]
• 8: Maggie Zhiwei Kang , Wayne Wei-Mingi Dai, Arbitrary rectilinear block packing based on sequence pair, Proceedings of the 1998 IEEE/ACM international conference on Computer-aided design, p.259-266, November 08-12, 1998, San Jose, California, United States [doi>10.1145/288548.288623]
• 9: M. Lai , D. Wong, Slicing tree is a complete floorplan representation, Proceedings of the conference on Design, automation and test in Europe, p.228-232, March 2001, Munich, Germany
• 10: H. Murata, K. Fujiyoshi, S. Nakatake, and Y. Kajitani. "VLSI module placement based on rectangle-packing by the sequence pair", IEEE Transaction on CAD, vol. 15:12, pp. 1518--1524, 1996
• 11: Shigetoshi Nakatake , Kunihiro Fujiyoshi , Hiroshi Murata , Yoji Kajitani, Module placement on BSG-structure and IC layout applications, Proceedings of the 1996 IEEE/ACM international conference on Computer-aided design, p.484-491, November 10-14, 1996, San Jose, California, United States
• 12: T. Ohtsuki, N. Sugiyama, and H. Kawanishi. "An optimization technique for integrated circuit layout design", ICCST Kyoto, Japan, pp. 67--68, 1970
• 13: Ralph H.J.M. Otten, Automatic floorplan design, Proceedings of the 19th conference on Design automation, p.261-267, January 1982
• 14: K. Sakanushi and Y. Kajitani. "The quarter-state sequence (Q-sequence) to represent the floorplan and applications to layout optimization", IEEE APCCAS, pp. 829--832, 2000
• 15: Xiaoping Tang , Ruiqi Tian , D. F. Wong, Fast evaluation of sequence pair in block placement by longest common subsequence computation, Proceedings of the conference on Design, automation and test in Europe, p.106-111, March 27-30, 2000, Paris, France [doi>10.1145/343647.343713]
• 16: Xiaoping Tang , D. F. Wong, FAST-SP: a fast algorithm for block placement based on sequence pair, Proceedings of the 2001 conference on Asia South Pacific design automation, p.521-526, January 2001, Yokohama, Japan [doi>10.1145/370155.370523]
• 17: 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

INDEX TERMS

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

Additional Classification:
  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING
      Subjects: Computer-aided design (CAD)

General Terms:
Algorithms, Design, Performance, Theory

Keywords:
floorplanning, longest common subsequence, sequence pair