Hypergraph partitioning for VLSI CAD

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Hypergraph partitioning for VLSI CAD: methodology for heuristic development, experimentation and reporting

Full text

Pdf (109 KB)

Source

Annual ACM IEEE Design Automation Conference archive
Proceedings of the 36th annual ACM/IEEE Design Automation Conference table of contents

New Orleans, Louisiana, United States

Pages: 349 - 354

Year of Publication: 1999

ISBN:1-58133-109-7

Authors

Andrew E. Caldwell	UCLA Computer Science Department, Los Angeles, CA
Andrew B. Kahng	UCLA Computer Science Department, Los Angeles, CA
Andrew A. Kennings	Cypress Semiconductor, Beaverton, OR
Igor L. Markov	UCLA Computer Science Department, Los Angeles, CA

Sponsors

EDAC : Electronic Design Automation Consortium
IEEE-CAS : Circuits & Systems
SIGDA: ACM Special Interest Group on Design Automation

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 11, Citation Count: 12

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/309847.309955 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	C.J. Alpert, "Partitioning Benchmarks for the VLSI CAD Community, http://vls lead. cs. ucla. edu/~ cheese/benchmarks, html
	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 , 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]
	4	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]
	5	R.S. Barr, B. L. Golden, J. P. Kelly, M. G. C. Resende and W. R. Stewart, "Designing and Reporting on Computational Experiments with Heuristic Methods", technical report (extended version of J. Heuristics paper), June 27, 1995.
	6	Franc Brglez, A D&T Special Report on ACM/SIGDA Design Automation Benchmarks: Catalyst or Anathema?, IEEE Design & Test, v.10 n.3, p.87-91, July 1993
	7	F. Brglez, "Design of Experiments to Evaluate CAD Algorithms: Which Improvements Are Due to Improved Heuristic and Which are Merely Due to Chance?", technical report CBL-04-Brglez, NCSU Collaborative Benchmarking Laboratory, April 1998.
	8	Thang Nguyen Bui , F. Thomson Leighton , Soma Chaudhuri , Michael Sipser, Graph bisection algorithms with good average case behavior, Combinatorica, v.7 n.2, p.171-191, June 1, 1987 [doi>10.1007/BF02579448]
	9	Andrew E. Caldwell , Andrew B. Kahng , Igor L. Markov, Hypergraph partitioning with fixed vertices, Proceedings of the 36th ACM/IEEE conference on Design automation, p.355-359, June 21-25, 1999, New Orleans, Louisiana, United States [doi>10.1145/309847.309957]
	10	Andrew E. Caldwell , Andrew B. Kahng , Igor L. Markov, Design and Implementation of the Fiduccia-Mattheyses Heuristic for VLSI Netlist Partitioning, Selected papers from the International Workshop on Algorithm Engineering and Experimentation, p.177-193, January 15-16, 1999
	11	R K. Chan and M. D. F. Schlag and J. Y. Zien, "Spectral K-Way Ratio-Cut Partitioning and Clustering", IEEE Transactions on Computer-Aided Design, vol. 13 (8), pp. 1088-1096.
	12	Jason Cong , Honching Peter Li , Sung Kyu Lim , Toshiyuki Shibuya , Dongmin Xu, Large scale circuit partitioning with loose/stable net removal and signal flow based clustering, Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design, p.441-446, November 09-13, 1997, San Jose, California, United States
	13	W. Deng, personal communication, July 1998.
	14	A.E. Dunlop and B. W. Kemighan, "A Procedure for Placement of Standard Cell VLSI Circuits", IEEE Transactions on Computer-Aided Design 4(1) (1985), pp. 92-98
	15	Shantanu Dutt , Wenyong Deng, VLSI circuit partitioning by cluster-removal using iterative improvement techniques, Proceedings of the 1996 IEEE/ACM international conference on Computer-aided design, p.194-200, November 10-14, 1996, San Jose, California, United States
	16	Shantanu Dutt , Halim Theny, Partitioning using second-order information and stochastic-gain functions, Proceedings of the 1998 international symposium on Physical design, p.112-117, April 06-08, 1998, Monterey, California, United States [doi>10.1145/274535.274551]
	17	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
	18	Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
	19	I. P. Gent, S. A. Grant, E. MacIntyre, P. Prosser, P. Shaw, B. M. Smith and T. Walsh, "How Not To Do It", research report 97-27, Univ. of Leeds School of Computer Studies, May 1997.
	20	S. Hauck and G. Borriello, "An Evaluation of Bipartitioning Techniques", IEEE Transactions on Computer-Aided Design 16(8) (1997), pp. 849-866.
	21	Lars W. Hagen , Dennis J.-H. Huang , Andrew B. Kahng, On implementation choices for iterative improvement partitioning algorithms, Proceedings of the conference on European design automation, p.144-149, September 18-22, 1995, Brighton, England
	22	Andrew B. Kahng, Futures for partitioning in physical design (tutorial), Proceedings of the 1998 international symposium on Physical design, p.190-193, April 06-08, 1998, Monterey, California, United States [doi>10.1145/274535.274563]
	23	G. Karypis and V. Kumar, "Analysis of Multilevel Graph Partitioning", draft, 1995
	24	G. Karypis and V. Kumar, "Multilevel k-way Partitioning Scheme For Irregular Graphs", Technical Report 95-064, University of Minnesota, Computer Science Department.
	25	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]
	26	G. Karypis, R. Aggarwal, V. Kumar, and S. Shekhar, "Multilevel Hypergraph Partitioning: Applications in VLSI Domain", technical report, University of Minnesota Computer Science Department, March 27, 1998.
	27	G. Karypis and V. Kumar, "Multilevel Algorithms for Multi-Constraint Graph Partitioning", Technical Report 98-019, University of Minnesota, Department of Computer Science.
	28	G. Karypis and V. Kumar, "hMetis: A Hypergraph Partitioning Package Version 1.5", user manual, June 23, 1998.
	29	B.W. Kemighan and S. Lin, "An Efficient Heuristic Procedure for Partitioning Graphs", Bell System Tech. Journal 49 (1970), pp. 291-307.
	30	B. Krishnamurthy, "An Improved Min-cut Algorithm for Partitioning VLSI Networks", IEEE Transactions on Computers, vol. C-33, May 1984, pp. 438-446.
	31	Lung-Tien Liu , Ming-Ter Kuo , Shih-Chen Huang , Chung-Kuan Cheng, A gradient method on the initial partition of Fiduccia-Mattheyses algorithm, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.229-234, November 05-09, 1995, San Jose, California, United States
	32	Laura A. Sanchis, Multiple-Way Network Partitioning with Different Cost Functions, IEEE Transactions on Computers, v.42 n.12, p.1500-1504, December 1993 [doi>10.1109/12.260640]
	33	G.R. Schreiber and O. C. Martin, "Procedure for Ranking Heuristics Applied to Graph Partitioning", P1vc. 2nd International Conference on Metaheuristics, July 1997, pp. 1-19.
	34	G. R. Schreiber , O. C. Martin, Cut Size Statistics of Graph Bisection Heuristics, SIAM Journal on Optimization, v.10 n.1, p.231-251, 1999 [doi>10.1137/S1052623497321523]
	35	R R. Suaris and G. Kedem, "Quadrisection: A New Approach to Standard Cell Layout", P1vc. IEEE/ACM International Conference on Computer-Aided Design, 1987, pp. 474-477.
	36	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
	37	Y. C. Wei and C. K. Cheng, "Towards Efficient Design by Ratio-cut Partitioning", P1vc. IEEE International Conference on Computer-Aided Design, 1989, pp. 298-301.

CITED BY 12

	Patrick H. Madden, Reporting of standard cell placement results, Proceedings of the 2001 international symposium on Physical design, p.30-35, April 01-04, 2001, Sonoma, California, United States
	Andrew E. Caldwell , Andrew B. Kahng , Igor L. Markov, Improved algorithms for hypergraph bipartitioning, Proceedings of the 2000 conference on Asia South Pacific design automation, p.661-666, January 2000, Yokohama, Japan
	Andrew B. Kahng, Design technology productivity in the DSM era (invited talk), Proceedings of the 2001 conference on Asia South Pacific design automation, p.443-448, January 2001, Yokohama, Japan
	Andrew E. Caldwell , Igor L. Markov, Toward CAD-IP Reuse: A Web Bookshelf of Fundamental Algorithms, IEEE Design & Test, v.19 n.3, p.72-81, May 2002
	Saurabh N. Adya , Mehmet C. Yildiz , Igor L. Markov , Paul G. Villarrubia , Phiroze N. Parakh , Patrick H. Madden, Benchmarking for large-scale placement and beyond, Proceedings of the 2003 international symposium on Physical design, April 06-09, 2003, Monterey, CA, USA
	Andrew B. Kahng , Xu Xu, Local unidirectional bias for smooth cutsize-delay tradeoff in performance-driven bipartitioning, Proceedings of the 2003 international symposium on Physical design, April 06-09, 2003, Monterey, CA, USA
	Andrew B. Kahng , Qinke Wang, Implementation and extensibility of an analytic placer, Proceedings of the 2004 international symposium on Physical design, April 18-21, 2004, Phoenix, Arizona, USA
	Andrew B. Kahng, A roadmap and vision for physical design, Proceedings of the 2002 international symposium on Physical design, April 07-10, 2002, San Diego, CA, USA
	M. Y. Lanzerotti , G. Fiorenza , R. A. Rand, Predicting interconnect requirements in ultra-large-scale integrated control logic circuitry, Proceedings of the 2005 international workshop on System level interconnect prediction, April 02-03, 2005, San Francisco, California, USA
	Mary Y. Lanzerotti , Giovanni Fiorenza , R. A. Rand, Assessment of on-chip wire-length distribution models, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.12 n.10, p.1108-1112, October 2004
	A. B. Kahng , Q. Wang, An analytic placer for mixed-size placement and timing-driven placement, Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design, p.565-572, November 07-11, 2004
	Markus Olbrich , Erich Barke, Placement Using a Localization Probability Model (LPM), Proceedings of the conference on Design, automation and test in Europe, p.21412, February 16-20, 2004