Improved algorithms for hypergraph bipartitioning

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Improved algorithms for hypergraph bipartitioning

Full text

Pdf (240 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

Pages: 661 - 666

Year of Publication: 2000

ISBN:0-7803-5974-7

Authors

Andrew E. Caldwell	UCLA Computer Science Dept., Los Angeles, CA
Andrew B. Kahng	UCLA Computer Science Dept., Los Angeles, CA
Igor L. Markov	UCLA Computer Science Dept., Los Angeles, CA

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): 2, Downloads (12 Months): 29, Citation Count: 26

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.368864 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://vlsicad.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	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.
	6	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
	7	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 [doi>10.1145/299996.300032]
	8	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 [doi>10.1145/299996.300047]
	9	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 [doi>10.1145/309847.309955]
	10	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]
	11	A. E. Caldwell, A. B. Kahng and I. L. Markov, 'MARCO/GSRC bookshelf for VLSI CAD algorithms", http://vlsicad.cs.ucla.edu/GSRC/bookshelf, 1999.
	12	J. S. Cherng, S. J. Chen, C. C. Tsai, J. M. Ho, "An Efficient Two-Level Partitioning Algorithm for CLSI Circuits", Proc. Asia and South Pacific Design Automation Conf., January 1999, pp. 69-72.
	13	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
	14	A. E. Dunlop and B. W. Kernighan, "'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 around roadblocks: tackling constraints with intermediate relaxations, Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design, p.350-355, November 09-13, 1997, San Jose, California, United States
	17	C.-K. Eem and J. Chong, "An Efficient Iterative Improvement Technique for VLSI Circuit Partitioning Using Hybrid Bucket Structures", Proc. Asia and South Pacific Design Automation Conf., January 1999, pp. 73-76. See also J. Institute of Electronics Engineers of Korea C35-C(3) (1998), pp. 16-23.
	18	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
	19	S. Hauck and G. Borriello, "An Evaluation of Bipartitioning Techniques", IEEE Transactions on Computer-Aided Design 16(8) (1997), pp. 849-866.
	20	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]
	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	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]
	23	G. Karypis and V. Kumar, "hMetis: A Hypergraph Partitioning Package Version 1.5", user manual, June 23, 1998.
	24	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]
	25	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 [doi>10.1145/288548.289078]

CITED BY 26

	Jason Cong , Michail Romesis , Min Xie, Optimality, scalability and stability study of partitioning and placement algorithms, Proceedings of the 2003 international symposium on Physical design, April 06-09, 2003, Monterey, CA, USA
	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
	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
	Jason Cong , Majid Sarrafzadeh, Incremental physical design, Proceedings of the 2000 international symposium on Physical design, p.84-92, May 2000, San Diego, 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
	Fadi A. Aloul , Igor L. Markov , Karem A. Sakallah, Faster SAT and smaller BDDs via common function structure, Proceedings of the 2001 IEEE/ACM international conference on Computer-aided design, November 04-08, 2001, San Jose, California
	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
	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
	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
	Jason Cong , Joseph R. Shinnerl , Min Xie , Tim Kong , Xin Yuan, Large-scale circuit placement, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.10 n.2, p.389-430, April 2005
	Michael deLorimier , André DeHon, Floating-point sparse matrix-vector multiply for FPGAs, Proceedings of the 2005 ACM/SIGDA 13th international symposium on Field-programmable gate arrays, February 20-22, 2005, Monterey, California, USA
	Andrew B. Kahng , Stefanus Mantik, On mismatches between incremental optimizers and instance perturbations in physical design tools, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
	Jarrod A. Roy , David A. Papa , Saurabh N. Adya , Hayward H. Chan , Aaron N. Ng , James F. Lu , Igor L. Markov, Capo: robust and scalable open-source min-cut floorplacer, Proceedings of the 2005 international symposium on Physical design, April 03-06, 2005, San Francisco, California, USA
	Hee Hwan Kwak , In-Ho Moon , James H. Kukula , Thomas R. Shiple, Combinational equivalence checking through function transformation, Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design, p.526-533, November 10-14, 2002, San Jose, California
	Jianhua Li , Laleh Behjat, Net cluster: a net-reduction based clustering preprocessing algorithm, Proceedings of the 2006 international symposium on Physical design, April 09-12, 2006, San Jose, California, USA
	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
	Sachin B. Patkar , Himanshu Sharma , H. Narayanan, Efficient network flow based ratio-cut netlist hypergraph partitioning, Proceedings of the 2nd WSEAS International Conference on Electronics, Control and Signal Processing, p.1-7, December 07-09, 2003, Singapore
	Jianhua Li , Laleh Behjat , Jie Huang, An effective clustering algorithm for mixed-size placement, Proceedings of the 2007 international symposium on Physical design, March 18-21, 2007, Austin, Texas, USA
	Aleksandar Trifunović , William J. Knottenbelt, Parallel multilevel algorithms for hypergraph partitioning, Journal of Parallel and Distributed Computing, v.68 n.5, p.563-581, May, 2008
	V. Durairaj , P. Kalla, Guiding CNF-SAT search via efficient constraint partitioning, Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design, p.498-501, November 07-11, 2004
	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
	Ameya Agnihotri , Mehmet Can YILDIZ , Ateen Khatkhate , Ajita Mathur , Satoshi Ono , Patrick H. Madden, Fractional Cut: Improved Recursive Bisection Placement, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.307, 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
	Cevdet Aykanat , B. Barla Cambazoglu , Bora Uçar, Multi-level direct K-way hypergraph partitioning with multiple constraints and fixed vertices, Journal of Parallel and Distributed Computing, v.68 n.5, p.609-625, May, 2008
	Michael D. Moffitt , Jarrod A. Roy , Igor L. Markov, The coming of age of (academic) global routing, Proceedings of the 2008 international symposium on Physical design, April 13-16, 2008, Portland, Oregon, USA
	Bahareh Fathi , Laleh Behjat , Logan M. Rakai, A pre-placement net length estimation technique for mixed-size circuits, Proceedings of the 11th international workshop on System level interconnect prediction, July 26-27, 2009, San Francisco, CA, USA

Collaborative Colleagues:

Andrew E. Caldwell: colleagues

Andrew B. Kahng: colleagues

Igor L. Markov: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player