Nostradamus: a floorplanner of uncertain design

ABSTRACT

Floorplanning is an early phase in chip planning. It provides information on approximate area, delay, power, and other performance measures. Careful floorplanning is thus of extreme importance. In many applications while a good floorplan is needed, not all modules' information are available, or even w orse, part of the pro vided information is inaccurate. Floorplanning with uncertainty is the problem of obtaining a good floorplan under uncertainty. In this paper, the floorplanning problem with uncertainty is form ulated. It is established that traditional floorplanners are incapable of handling uncertainty. An effective method for dealing with uncertain data is proposed. Experiments sho w that, for example, with up to 30% input uncertainty an area estimate with less than 7% error can be obtained.

REFERENCES

• 1: J. Bhasker and S. Sahni. "A Linear Algorithm to Find a Rectangular Dual of a Planar Triangulated Graph". Algorithmica, 3(2):274-278, 1988.
• 2: I~. Dai and E. S. Kuh. "Sknultaneous Floor l~lauiug mad Global Routing for Hierarclfical Building- Block Layout'. ZEEE Transactions on Computer Aided lPes{9~, 60):828-837, 1987.
• 3: J. D. Gabbe , P. A. Subrahmanyam, A note on clustering modules for floorplanning, Proceedings of the 26th ACM/IEEE conference on Design automation, p.594-597, June 25-28, 1989, Las Vegas, Nevada, United States [doi>10.1145/74382.74483]
• 4: K. Ko~m~n~ and E. Kinnen. "Rectangular Dual of Planar Graphs". Networks, 15:145-157, 198~.
• 5: Thomas Lengauer, Combinatorial algorithms for integrated circuit layout, John Wiley & Sons, Inc., New York, NY, 1990
• 6: T. Lengauer and :EL Muller. "A Robust Framework for Hierarchical Floorplasming with Integrated Global ~Viring~. In International Conference on Computer- Aided Design, pages 148-151, 1990.
• 7: M. Pedram, M. Marek-Sadowska~ and E. Kuh. ~loorplamxing with Pin Assignment". In International Conference on Gomputer-Aided Design, pages 98-101, 1990.
• 8: Majid Sarrafzadeh, Transforming an arbitrary floorplan into a sliceable one, Proceedings of the 1993 IEEE/ACM international conference on Computer-aided design, p.386-389, November 07-11, 1993, Santa Clara, California, United States
• 9: Majid Sarrafzadeh , M. Sarrafzadeh , C. K. Wong, An Introduction to VLSI Physical Design, McGraw-Hill Higher Education, 1996
• 10: C. Sechea mad K. ~V. Lee_ ~An Improved Simulated Aroma}rag Algorithm for Row-Based Placemerit'. In Design Automation Conference, pages 180- 183. TI~EE/ACM, 1988.
• 11: Naveed A. Sherwani, Algorithms for VLSI Physical Design Automation, Kluwer Academic Publishers, Norwell, MA, 1993
• 12: S. Sutanthavibul, E. Shragowitz, and J. B. Rosen. "An Analytical Approach to Floorplan Design and Optimization". IEEE Transactions on Computer Aided Design, 10(6):761-769, 1991.
• 13: K. Ueda, H. Kitazawa, and I. Harada. "CHAMP: Chip Floorplan for Hierarchical VLSI Layout Design". In IEEE Transactions on Computer Aided Design, pages 12-22, 1986.
• 14: Ting-chi Wang , D. F. Wong, An optimal algorithm for floorplan area optimization, Proceedings of the 27th ACM/IEEE conference on Design automation, p.180-186, June 24-27, 1990, Orlando, Florida, United States [doi>10.1145/123186.123253]
• 15: T.-C. Wang , D. F. Wong, A graph theoretic technique to speed up floorplan area optimization, Proceedings of the 29th ACM/IEEE conference on Design automation, p.62-68, June 08-12, 1992, Anaheim, California, United States
• 16: D. F. Wong , H. W. Leong , C. L. Liu, Simulated annealing for VLSI design, Kluwer Academic Publishers, Norwell, MA, 1988
• 17: D. F. Wong and C. L. Liu. "Floorplan Design of VLSI Circuits". Algorithmica, 4:263-291, 1989.
• 18: D. F. Wong , P. S. Sakhamuri, Efficient floorplan area optimization, Proceedings of the 26th ACM/IEEE conference on Design automation, p.586-589, June 25-28, 1989, Las Vegas, Nevada, United States [doi>10.1145/74382.74481]
• 19: K. H. Yeap and M. Sarrafzadeh. "A Unified Approach to Flooplan Sizing and Enumeration". IEEE Transactions on Uomputer Aided Desi9n, 12(12):1858-1867, December 1993.
• 20: Kok-Hoo Yeap , Majid Sarrafzadeh, Floor-planning by graph dualization: 2-concave rectilinear modules, SIAM Journal on Computing, v.22 n.3, p.500-526, June 1993 [doi>10.1137/0222035]
• 21: Gary K. H. Yeap , Majid Sarrafzadeh, Sliceable Floorplanning by Graph Dualization, SIAM Journal on Discrete Mathematics, v.8 n.2, p.258-280, May 1995 [doi>10.1137/S0895480191266700]

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Layout

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Simulation

  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)

General Terms:
Algorithms, Design, Experimentation, Performance