Slicing floorplan with clustering constraints

ABSTRACT

In floorplan design it is useful to allow users to specify placement constraints in the final packing. Clustering constraint is one kind of placement constraint in which a given set of modules are restricted to be geometrically adjacent to one another. The wiring cost can be reduced by putting modules with a lot of connections closely together. Designers may also need this type of placement constraint to pack the modules according to their functionality. In this paper, a method addressing clustering constraint in slicing floorplan is presented. A linear time algorithm is deviced to locate neighboring modules in a normalized Polish expression and re-arrange the modules in order to satisfy the constraints. Experiments were performed on some benchmarks and the results are promising.

REFERENCES

• 1: Ralph H.J.M. Otten, Automatic floorplan design, Proceedings of the 19th conference on Design automation, p.261-267, January 1982
• 2: 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
• 3: [3] H. Murata, K. Fujiyoshi, and M. Kaneko, "VLSI/PCB placement with obstacles based on sequence-pair," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 17, pp. 60-68, Jan. 1998.
• 4: 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
• 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: 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]
• 7: 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
• 8: Habib Youssef , Sadiq M. Sait , Khalid J. Al-Farra, Timing influenced force directed floorplanning, Proceedings of the conference on European design automation, p.156-161, September 18-22, 1995, Brighton, England
• 9: Vinod Narayananan , David LaPotin , Rajesh Gupta , Gopal Vijayan, PEPPER-a timing driven early floorplanner, Proceedings of the 1995 International Conference on Computer Design: VLSI in Computers and Processors, p.230-235, October 02-04, 1995
• 10: Takayuki Yamanouchi , Kazuo Tamakashi , Takashi Kambe, Hybrid floorplanning based on partial clustering and module restructuring, Proceedings of the 1996 IEEE/ACM international conference on Computer-aided design, p.478-483, November 10-14, 1996, San Jose, California, United States
• 11: F. Y. Young , D. F. Wong, Slicing floorplans with range constraint, Proceedings of the 1999 international symposium on Physical design, p.97-102, April 12-14, 1999, Monterey, California, United States [doi>10.1145/299996.300033]
• 12: [12] F.Y. Young and D. F. Wong, "Slicing floorplans with boundary constraints," in Proceeding of IEEE Asia South Pacific Design Automation Conference, pp. 17-20, 1999.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS

Additional Classification:
  B. Hardware
  B.8 Performance and Reliability

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

  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS
      K.6.2 Installation Management
          Subjects: Benchmarks

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