Multilevel circuit partitioning

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Multilevel circuit partitioning

Full text

Pdf (107 KB)

Source

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

Anaheim, California, United States

Pages: 530 - 533

Year of Publication: 1997

ISBN:0-89791-920-3

Authors

Charles J. Alpert	UCLA Computer Science Department, Los Angeles, CA and IBM Austin Research Laboratory, Austin, TX
Jen-Hsin Huang	UCLA Computer Science Department, Los Angeles, CA and Synopsys, Inc., Mountain View, CA
Andrew B. Kahng	UCLA Computer Science Department, Los Angeles, CA and Cadence Design Systems, Inc., San Jose, 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): 4, Downloads (12 Months): 26, Citation Count: 52

Additional Information:

abstract 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/266021.266275 What is a DOI?

ABSTRACT

Recent work has illustrated the promise ofmultilevel approaches for partitioning large circuits. Multilevel partitioningrecursively clusters the instance until its size is smallerthan a given threshold, then unclusters the instance while applyinga partitioning refinement algorithm. Our multilevel partitioner usesa new technique to control the number of levels in the matching-basedclustering phase and also exploits recent innovations in classiciterative partitioning. Our heuristic outperforms numerousexisting bipartitioning heuristics, with improvements rangingfrom 6.9 to 27.9% for 100 runs and 3.0 to 20.6% for just 10 runs(while also using less CPU time).

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	Charles Jay Alpert , Andrew B. Kahng, Multi-way graph and hypergraph partitioning, 1996
	2	C. J. Alpert, L. W. Hagen, and A. B. Kahng. "A Hybrid Multilevel/ Genetic Approach for Circuit Partitioning." Physical Design Workshop, pp. 100-105, 1996.
	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	T. Bui , C. Heigham , C. Jones , T. Leighton, Improving the performance of the Kernighan-Lin and simulated annealing graph bisection algorithms, Proceedings of the 26th ACM/IEEE conference on Design automation, p.775-778, June 25-28, 1989, Las Vegas, Nevada, United States [doi>10.1145/74382.74527]
	5	Jason Cong , M'Lissa Smith, A parallel bottom-up clustering algorithm with applications to circuit partitioning in VLSI design, Proceedings of the 30th international conference on Design automation, p.755-760, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.165119]
	6	Shantanu Dutt , Wenyong Deng, A probability-based approach to VLSI circuit partitioning, Proceedings of the 33rd annual conference on Design automation, p.100-105, June 03-07, 1996, Las Vegas, Nevada, United States [doi>10.1145/240518.240538]
	7	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
	8	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
	9	A. S. Fukunaga, J.-H. Huang, and A. B. Kahng. "Large-Step Markov Chain Variants for VLSI Netlist Partitioning." Proc. of the IEEE Intl. Syrup. on Circuits and Systems, vol. IV, pp. 496-499, May 1996.
	10	L.W. Hagen, D. J.-H. Huang, and A. B. Kahng. "On Implementation Choices for Iterative Improvement Partitioning Algorithms." IEEE Trans. CAD (to appear), 1997.
	11	S. Hauck , G. Borriello, An evaluation of bipartitioning techniques, Proceedings of the 16th Conference on Advanced Research in VLSI (ARVLSI'95), p.383, March 27-29, 1995
	12	B. Hendrickson and R. Leland. "A Multilevel Algorithm for Partitioning Graphs." Proc. Supercomputing, 1995. Also see, Tech. Rep. SAND93-1301, Sandia National Laboratories, 1993.
	13	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]
	14	G. Karypis and V. Kumar. "Multilevel Graph Partitioning Schemes." P. Banerjee and P. Boca, editors, Proc. of the 1995 Intl. Conf. on Parallel Processing, vol. 3, pp. 113-122, 1995.
	15	B. Krishnamurthy. "An Improved Min-Cut Algorithm for Partitioning VLSI Networks." IEEE Trans. on Computers, 33(5):438-446, 1984.
	16	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
	17	Jianmin Li , John Lillis , Chung-Kuan Cheng, Linear decomposition algorithm for VLSI design applications, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.223-228, November 05-09, 1995, San Jose, California, United States
	18	R. Ponnusamy , N. Mansour , A. Choudhary , G. C. Fox, Graph contraction for mapping data on parallel computers: a quality-cost tradeoff, Scientific Programming, v.3 n.1, p.73-82, Spring 1994
	19	Bernhard M. Riess , Konrad Doll , Frank M. Johannes, Partitioning very large circuits using analytical placement techniques, Proceedings of the 31st annual conference on Design automation, p.646-651, June 06-10, 1994, San Diego, California, United States [doi>10.1145/196244.196602]

CITED BY 52

	John M. Emmert , Sandeep Lodha , Dinesh K. Bhatia, On Using Tabu Search for Design Automation of VLSI Systems, Journal of Heuristics, v.9 n.1, p.75-90, January 2003
	Maogang Wang , Sung Lim , Jason Cong , Majid Sarrafzadeh, Multi-way partitioning using bi-partition heuristics, Proceedings of the 2000 conference on Asia South Pacific design automation, p.667, January 2000, Yokohama, Japan
	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
	C. J. Alpert , T. Chan , D. J.-H. Huang , I. Markov , K. Yan, Quadratic placement revisited, Proceedings of the 34th annual conference on Design automation, p.752-757, June 09-13, 1997, Anaheim, California, United States
	Ke Zhong , Shantanu Dutt, Effective partition-driven placement with simultaneous level processing and global net views, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
	C. Cheung , Y. Wu , D. Cheng, Further improve circuit partitioning using GBAW logic perturbation techniques, Proceedings of the conference on Design, automation and test in Europe, p.233-239, March 2001, Munich, Germany
	George Karypis , Vipin Kumar, Multilevel k-way hypergraph partitioning, Proceedings of the 36th ACM/IEEE conference on Design automation, p.343-348, June 21-25, 1999, New Orleans, Louisiana, United States
	Sverre Wichlund, On multilevel circuit partitioning, Proceedings of the 1998 IEEE/ACM international conference on Computer-aided design, p.505-511, November 08-12, 1998, San Jose, California, United States
	Andrew E. Caldwell , Andrew B. Kahng , Igor L. Markov, Can recursive bisection alone produce routable placements?, Proceedings of the 37th conference on Design automation, p.477-482, June 05-09, 2000, Los Angeles, California, United States
	Greg Wolfe , Jennifer L. Wong , Miodrag Potkonjak, Watermarking graph partitioning solutions, Proceedings of the 38th conference on Design automation, p.486-489, June 2001, Las Vegas, Nevada, 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
	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
	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
	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
	Shantanu Dutt , Wenyong Deng, Cluster-aware iterative improvement techniques for partitioning large VLSI circuits, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.7 n.1, p.91-121, January 2002
	C. J. Alpert , A. E. Caldwell , A. B. Kahng , I. L. Markov, Partitioning with terminals: a “new” problem and new benchmarks, Proceedings of the 1999 international symposium on Physical design, p.151-157, April 12-14, 1999, Monterey, California, United States
	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
	Jason Y. Zien , Pak K. Chan , Martine Schlag, Hybrid spectral/iterative partitioning, Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design, p.436-440, November 09-13, 1997, San Jose, California, United States
	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
	A. E. Caldwell , A. B. Kahng , I. L. Markov, Optimal partitioners and end-case placers for standard-cell layout, Proceedings of the 1999 international symposium on Physical design, p.90-96, April 12-14, 1999, Monterey, California, United States
	Wilm Donath , Prabhakar Kudva , Leon Stok , Lakshmi Reddy , Andrew Sullivan , Kanad Chakraborty , Paul Villarrubia, Transformational placement and synthesis, Proceedings of the conference on Design, automation and test in Europe, p.194-201, March 27-30, 2000, Paris, France
	Jiong Yang , Wei Wang , Richard Muntz, Collaborative Web caching based on proxy affinities, ACM SIGMETRICS Performance Evaluation Review, v.28 n.1, p.78-89, June 2000
	Youssef Saab, A new effective and efficient multi-level partitioning algorithm, Proceedings of the conference on Design, automation and test in Europe, p.112-116, March 27-30, 2000, Paris, France
	Patrick H. Madden, Partitioning by iterative deletion, Proceedings of the 1999 international symposium on Physical design, p.83-89, April 12-14, 1999, Monterey, California, United States
	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
	Sung-Woo Hur , John Lillis, Relaxation and clustering in a local search framework: application to linear placement, Proceedings of the 36th ACM/IEEE conference on Design automation, p.360-366, June 21-25, 1999, New Orleans, Louisiana, United States
	Andrew E. Caldwell , Andrew B. Kahng , Andrew A. Kennings , Igor L. Markov, Hypergraph partitioning for VLSI CAD: methodology for heuristic development, experimentation and reporting, Proceedings of the 36th ACM/IEEE conference on Design automation, p.349-354, June 21-25, 1999, New Orleans, Louisiana, United States
	Saurabh N. Adya , Igor L. Markov, Consistent placement of macro-blocks using floorplanning and standard-cell placement, Proceedings of the 2002 international symposium on Physical design, April 07-10, 2002, San Diego, CA, USA
	Eric S. H. Wong , Evangeline F. Y. Young , W. K. Mak, Clustering based acyclic multi-way partitioning, Proceedings of the 13th ACM Great Lakes symposium on VLSI, April 28-29, 2003, Washington, D. C., USA
	Yu-Liang Wu , Chak-Chung Cheung , David Ihsin Cheng , Hongbing Fan, Further improve circuit partitioning using GBAW logic perturbation techniques, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.11 n.3, p.451-460, June 2003
	R. Drechsler , W. Günther , T. Eschbach , L. Linhard , G. Angst, Recursive bi-partitioning of netlists for large number of partitions, Journal of Systems Architecture: the EUROMICRO Journal, v.49 n.12-15, p.521-528, December 2003
	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
	Qinghua Liu , Malgorzata Marek-Sadowska, A study of netlist structure and placement efficiency, Proceedings of the 2004 international symposium on Physical design, April 18-21, 2004, Phoenix, Arizona, USA
	Guoqiang Chen , Sachin Sapatnekar, Partition-driven standard cell thermal placement, Proceedings of the 2003 international symposium on Physical design, April 06-09, 2003, Monterey, CA, USA
	Charles Alpert , Andrew Kahng , Gi-Joon Nam , Sherief Reda , Paul Villarrubia, A semi-persistent clustering technique for VLSI circuit placement, Proceedings of the 2005 international symposium on Physical design, April 03-06, 2005, San Francisco, California, USA
	Andrew B. Kahng , Sherief Reda, Placement feedback: a concept and method for better min-cut placements, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA
	Navaratnasothie Selvakkumaran , Abhishek Ranjan , Salil Raje , George Karypis, Multi-resource aware partitioning algorithms for FPGAs with heterogeneous resources, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA
	Andrew E. Caldwell , Andrew B. Kahng , Igor L. Markov, Design and implementation of move-based heuristics for VLSI hypergraph partitioning, Journal of Experimental Algorithmics (JEA), 5, p.5-es, 2000
	S. N. Adya , I. L. Markov, Combinatorial techniques for mixed-size placement, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.10 n.1, p.58-90, January 2005
	Navaratnasothie Selvakkumaran , Phiroze N. Parakh , George Karypis, Perimeter-degree: a priori metric for directly measuring and homogenizing interconnection complexity in multilevel placement, Proceedings of the 2003 international workshop on System-level interconnect prediction, April 05-06, 2003, Monterey, CA, USA
	Tony Chan , Jason Congy , Kenton Sze, Multilevel generalized force-directed method for circuit placement, Proceedings of the 2005 international symposium on Physical design, April 03-06, 2005, San Francisco, California, USA
	Charles J. Alpert , Gi-Joon Nam , Paul G. Villarrubia, Free space management for cut-based placement, Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design, p.746-751, November 10-14, 2002, San Jose, California
	Youssef G. Saab, An Effective Multilevel Algorithm for Bisecting Graphs and Hypergraphs, IEEE Transactions on Computers, v.53 n.6, p.641-652, June 2004
	Chuck J. Alpert , Gi-Joon Nam , Paul Villarribua , Mehmet C. YILDIZ, Placement stability metrics, Proceedings of the 2005 conference on Asia South Pacific design automation, January 18-21, 2005, Shanghai, China
	Chanseok Hwang , Massoud Pedram, PMP: performance-driven multilevel partitioning by aggregating the preferred signal directions of I/O conduits, Proceedings of the 2005 conference on Asia South Pacific design automation, January 18-21, 2005, Shanghai, China
	Dian Zhou , Rui-Ming Li, Design and verification of high-speed VLSI physical design, Journal of Computer Science and Technology, v.20 n.2, p.147-165, March 2005
	A. B. Kahng , S. Reda , Qinke Wang, Architecture and details of a high quality, large-scale analytical placer, Proceedings of the 2005 IEEE/ACM International conference on Computer-aided design, p.891-898, November 06-10, 2005, San Jose, CA
	Mehmet Can Yildiz , Patrick H. Madden, Improved cut sequences for partitioning based placement, Proceedings of the 38th conference on Design automation, p.776-779, June 2001, Las Vegas, Nevada, United States
	Tony F. Chan , Jason Cong , Tim Kong , Joseph R. Shinnerl , Kenton Sze, An Enhanced Multilevel Algorithm for Circuit Placement, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.299, November 09-13, 2003
	Navaratnasothie Selvakkumaran , George Karypis, Multi.Objective Hypergraph Partitioning Algorithms for Cut and Maximum Subdomain Degree Minimization, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.726, November 09-13, 2003
	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
	Pierre Chardaire , Musbah Barake , Geoff P. McKeown, A PROBE-Based Heuristic for Graph Partitioning, IEEE Transactions on Computers, v.56 n.12, p.1707-1720, December 2007