Multi-way partitioning using bi-partition heuristics

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Multi-way partitioning using bi-partition heuristics

Full text

Pdf (200 KB)

Source

Asia and South Pacific Design Automation Conference archive
Proceedings of the 2000 Asia and South Pacific Design Automation Conference table of contents

Yokohama, Japan

Page: 667

Year of Publication: 2000

ISBN:0-7803-5974-7

Authors

Maogang Wang	ECE Department, Northwestern University, Evanston, IL, US
Sung Lim	CS Department, UCLA, Los Angels, CA
Jason Cong	CS Department, UCLA, Los Angels, CA
Majid Sarrafzadeh	ECE Department, Northwestern University, Evanston, IL

Sponsors

IEEE-CAS : Circuits & Systems
IPSJ : Information Processing Society of Japan
SIGDA: ACM Special Interest Group on Design Automation
IEICE : Inst of Electronics, Info & Communication Engineers

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 13, Citation Count: 3

Additional Information:

references cited by collaborative colleagues

Tools and Actions:	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/368434.368865 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	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]
	2	C. J. Alpert , A. B. Kahng, Geometric embeddings for faster and better multi-way netlist partitioning, Proceedings of the 30th international conference on Design automation, p.743-748, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.165115]
	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	C. K. Cheng and Y. C. A. Wei. "An improved two-way partitioning algorithm with stable performance". IEEE Transactions on Computer Aided Design, 10(12):1502-1511, 1991.
	5	Jason Cong , Wilburt Labio , Narayanan Shivakumar, Multi-way VLSI circuit partitioning based on dual net representation, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.56-62, November 06-10, 1994, San Jose, California, United States
	6	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
	7	Jason Cong , Sung Kyu Lim, Multiway partitioning with pairwise movement, Proceedings of the 1998 IEEE/ACM international conference on Computer-aided design, p.512-516, November 08-12, 1998, San Jose, California, United States [doi>10.1145/288548.289079]
	8	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
	9	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
	10	L. Hagen and A. B. Kahng. "Fast Spectral Methods for Ratio Cut Partitioning and Clustering". In International Conference on Computer-Aided Design. IEEE, 1991.
	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	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]
	13	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 [doi>10.1145/309847.309954]
	14	B.W. Kernighan and S. Lin. "An Efficient Heuristic Procedure for Partitioning Graphs". Bell System Technical Journal, 49:291-307, Feburary 1970.
	15	Marcos A. Kiwi , Daniel A. Spielman , Shang-Hua Teng, Min-Max-Boundary Domain Decomposition, Proceedings of the 4th Annual International Conference on Computing and Combinatorics, p.137-146, August 12-14, 1998
	16	L. A. Sanchis, Multiple-Way Network Partitioning, IEEE Transactions on Computers, v.38 n.1, p.62-81, January 1989 [doi>10.1109/12.8730]
	17	Horst D. Simon , Shang-Hua Teng, How Good is Recursive Bisection?, SIAM Journal on Scientific Computing, v.18 n.5, p.1436-1445, Sept. 1997 [doi>10.1137/S1064827593255135]
	18	P. R. Suaris and G. Kedem. "Quadrisection: A New Approach to Standard Cell Layout". In Design Automation Conference, pages 474-477. IEEE/ACM, 1987.
	19	P. R.Suaris and G. Kedem. "Standard Cell Placement by Quadrisection". In International Conference on Computer-Aided Design, pages 612-615. IEEE/ACM, 1987.
	20	Nam Sung Woo , Jaeseok Kim, An efficient method of partitioning circuits for multiple-FPGA implementation., Proceedings of the 30th international conference on Design automation, p.202-207, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.164669]

CITED BY 3

	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
	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
	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

Collaborative Colleagues:

Maogang Wang: colleagues

Sung Lim: colleagues

Jason Cong: colleagues

Majid Sarrafzadeh: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player