VLSI floorplanning with boundary constraints based on corner block list

ABSTRACT

In floorplanning of typical VLSI design, some modules are required to satisfy some placement constraints in the final packing. Boudary Constraint is one kind of those placement constraints to pack some modules along one of the four sides: on the left, on the right, at the bottom or at the top of the final floorplan. We implement the boundary constraint algorithm for general floorplan by extending the Corner Block List (CBL) - a new efficient topology representation for non-slicing floorplan. Our contribution is to find the necessary and sufficient characterization of the modules along the boundary represented by Corner Block List. So that we can check the boundary constraints by scanning the intermediate solutions in the linear time during the simulated annealing process and fix the corner block list in case the constraints are violated. The experiment results are demonstrated by several examples of MCNC benchmarks and the performance is remarkable.

REFERENCES

• 1: F.Y.Young, D.F.Wong, and Hannah H.Yang, "Slicing Floorplans with Boundary Constraints," in IEEE Trans. on Computer Aided Design,vol.18, NO. 9,pp 1385-1389,1999.
• 2: Hiroshi Murata, Kunihiro Fujiyoshi, Mineo Kaneko, "VLSI/PCB Placement with Obstacles Based on Sequence Pair" in IEEE Trans. on Computer Aided Design,vol.17, NO. 1, pp 60-67,1998.
• 3: 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
• 4: F. Y. Young , D. F. Wong, Slicing floorplans with pre-placed modules, Proceedings of the 1998 IEEE/ACM international conference on Computer-aided design, p.252-258, November 08-12, 1998, San Jose, California, United States [doi>10.1145/288548.288622]
• 5: M.Kang and W.W.M.Dai, "General Floorplanning with L-shaped,T- shaped and Soft Blocks Based on Bounded Slicing Grid Structure", IEEE Asia and South Pacific Design Automation Conference, pp. 265- 270,1997.
• 6: Hiroshi Murata, Kunihiro Fujiyoshi, S.Nakatake and Y.Kajitani, "VLSI Module Placement Based on Rectangle-Packing by the Sequence Pair" in IEEE Trans. on Computer Aided Design,vol.15, NO. 15, pp 1518- 1524,1996.
• 7: 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
• 8: 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
• 9: D. F. Wong , H. W. Leong , C. L. Liu, Simulated annealing for VLSI design, Kluwer Academic Publishers, Norwell, MA, 1988
• 10: 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]

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: VLSI (very large scale integration)

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
  B.8 Performance and Reliability

  J. Computer Applications
  J.2 PHYSICAL SCIENCES AND ENGINEERING
      Subjects: Electronics

General Terms:
Design, Performance, Theory