Floorplanning with abutment constraints and L-shpaed/T-shaped blocks baed on corner block list

ABSTRACT

The abutment constraint problem is one of the common constraints in practice to favor the transmission of data between blocks. Based on Corner Block List(CBL), a new algorithm to deal with abutment constraints is developed in this paper. We can obtain the abutment information by scanning the intermediate solutions represented by CBL in linear time during the simulated annealing process and fix the CBL in case the constraints are violated. Based on this algorithm, a new method to deal with L-shaped/T-shaped blocks is proposed. The shape flexibility of the soft blocks and the rotation and reflection of L-shaped/T-shaped blocks are exploited to obtain a tight packing. The experiment results are demonstrated by some benchmark data and the performance shows effectiveness of the proposed method.

REFERENCES

• 1: Hiroshi Murata, Kunihiro Fujiyoshi, S.Nakatake and Y.Kajitani, "VLSI Block Placement Based on Rectangle- Packing by the Sequence Pair" in IEEE Trans. on CAD,vol.15, NO. 15, pp 1518-1524,1996.
• 2: 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
• 3: 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]
• 4: 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]
• 5: 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
• 6: 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.
• 7: F.Y.Young,Hannah H.Yang, D.F.Wong "On extending slicing floorplans to handle L/T-shaped blocks and abutment constraints" WCC'2000, pp.269-276,2000.
• 8: Yuchun Ma , Sheqin Dong , Xianiong Hong , Yici Cai , Chung-Kuan Cheng , Jun Gu, VLSI floorplanning with boundary constraints based on corner block list, Proceedings of the 2001 conference on Asia South Pacific design automation, p.509-514, January 2001, Yokohama, Japan [doi>10.1145/370155.370521]
• 9: 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]

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Layout
  B.8 Performance and Reliability

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

General Terms:
Algorithms, Design, Experimentation, Measurement, Performance, Theory