Futures for partitioning in physical design (tutorial)

ABSTRACT

The context for partitioning in physical design is dominated by two concerns: top-down design and the focus on spatial embedding. The role of partitioning is exactly that of a facilitator of divide-and-conquer metaheuristics for floorplanning, timing and placement optimization. Formulations or optimization objectives for partitioning follow from its context and role. Finally, the available algorithm technology determines how effectively we can address a given partitioning formulation and optimize a given objective. This invited paper considers the future of partitioning for physical design in light of these factors, and proposes a list of technology needs. A living version of this paper can be found at vlsicad.cs.ucla.edu.

REFERENCES

• 1: C.J. Alpe~ personal communication, February 1998.
• 2: Charles J. Alpert, The ISPD98 circuit benchmark suite, Proceedings of the 1998 international symposium on Physical design, p.80-85, April 06-08, 1998, Monterey, California, United States [doi>10.1145/274535.274546]
• 3: Charles J. Alpert , Andrew B. Kahng, Recent directions in netlist partitioning: a survey, Integration, the VLSI Journal, v.19 n.1-2, p.1-81, Aug. 1995 [doi>10.1016/0167-9260(95)00008-4]
• 4: Charles J. Alpert , Jen-Hsin Huang , Andrew B. Kahng, Multilevel circuit partitioning, Proceedings of the 34th annual conference on Design automation, p.530-533, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266275]
• 5: K. Bazargan , S. Kim , M. Sarrafzadeh, Nostradamus: a floorplanner of uncertain design, Proceedings of the 1998 international symposium on Physical design, p.18-23, April 06-08, 1998, Monterey, California, United States [doi>10.1145/274535.274538]
• 6: Kenneth Dean Boese, Models for iterative global optimization, University of California at Los Angeles, Los Angeles, CA, 1996
• 7: A.E. Ca/dwell, A. B. Kahng and L L. Markov, manuscript, 1997.
• 8: W. E. Donath, "Logic Partitioning", in B. Preas and M. Lorenzetfi, eds., Physical Design Automation in VLSI Systems, Benjamin/Cummings, 1988.
• 9: A. E. Dunlop and B. W. Kernighan, "A Procedure for Placement of Standard Cell VLSI Circuits", IEEE Transactions on Computer-Aided Design 4(1) (19853, pp. 92-98.
• 10: C. M. Fiduccia , R. M. Mattheyses, A linear-time heuristic for improving network partitions, Proceedings of the 19th conference on Design automation, p.175-181, January 1982
• 11: S. Hauck and G. Bordello, "~n Evaluation ofBipartitioning Tcchr~qucs", IEEE Trans. on Computer-Aided Design 16 (1997), pp. 849-866.
• 12: Dennis J.-H. Huang , Andrew B. Kahng, Partitioning-based standard-cell global placement with an exact objective, Proceedings of the 1997 international symposium on Physical design, p.18-25, April 14-16, 1997, Napa Valley, California, United States [doi>10.1145/267665.267674]
• 13: Frank M. Johannes, Partitioning of VLSI circuits and systems, Proceedings of the 33rd annual conference on Design automation, p.83-87, June 03-07, 1996, Las Vegas, Nevada, United States [doi>10.1145/240518.240535]
• 14: A. B. Kahng , S. Muddu , E. Sarto , R. Sharma, Interconnect tuning strategies for high-performance ICs, Proceedings of the conference on Design, automation and test in Europe, p.471-478, February 23-26, 1998, Le Palais des Congrés de Paris, France
• 15: A. B. Kahng end R. Sharma, "Studies of Clnstedng Objectives anti Heuristics for Improved Standard-Cell Hacemenf', ~~script, 1997.
• 16: George Karypis , Rajat Aggarwal , Vipin Kumar , Shashi Shekhar, Multilevel hypergraph partitioning: application in VLSI domain, Proceedings of the 34th annual conference on Design automation, p.526-529, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266273]
• 17: Ming-Ter Kuo , Lung-Tien Liu , Chung-Kuan Cheng, Network partitioning into tree hierarchies, Proceedings of the 33rd annual conference on Design automation, p.477-482, June 03-07, 1996, Las Vegas, Nevada, United States [doi>10.1145/240518.240609]
• 18: E. L Lawler, IC N. Levitt and J. "Itnner, "Module Clustering to ~'Hn~mb'e Delay in DigitalNetwodc~", 1EEE Trans. on Computers lg (1969), pp. 47-57.
• 19: Thomas Lengauer, Combinatorial algorithms for integrated circuit layout, John Wiley & Sons, Inc., New York, NY, 1990
• 20: J. L~llis, personal communication, February 1998.
• 21: 1L X. T. Nijssen and J. A. (3. Jess, "1Veo-Dimensional Datapzth Regularity Extraction", Pro~ ACMISIGDA Physical Design Workshop, Apd11996, pp. 111-117.
• 22: Majid Sarrafzadeh , Maogang Wang, NRG: global and detailed placement, Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design, p.532-537, November 09-13, 1997, San Jose, California, United States
• 23: Semiconductor Industry Association, "The National Technology Roaflmap for Semiconductors: Technology Needs", December 1997.
• 24: Robert H. Storer , S. David Wu , Renzo Vaccari, New search spaces for sequencing problems with application to job shop scheduling, Management Science, v.38 n.10, p.1495-1509, Oct. 1992 [doi>10.1287/mnsc.38.10.1495]
• 25: P. tL Suaris and G. Ke~m, "Quaddsection: A New Approach to Standard Cell Layout," Pro~ IEEE/ACMIntemational Conferex~ce on Computer-Aided Design, 1987, pp. 474-477.
• 26: Wern-Jieh Sun , Carl Sechen, Efficient and effective placement for very large circuits, Proceedings of the 1993 IEEE/ACM international conference on Computer-aided design, p.170-177, November 07-11, 1993, Santa Clara, California, United States
• 27: Gopalakrishnan Vijayan, Generalization of Min-Cut Partitioning to Tree Structures and its Applications, IEEE Transactions on Computers, v.40 n.3, p.307-314, March 1991 [doi>10.1109/12.76407]
• 28: C.-Wo Yell, C-K. Cheng and T.-T. ~. I2n, "'Opfimiz~on by Iterative Improvement: An Experimental Evaluation on TWo-Way Peaaitioning'; IEEE Transactions on Computer-Aided Design 14 (1995), pp. 145-153.

INDEX TERMS

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

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

General Terms:
Design, Performance