ACM Portal
  Subscribe (Full Service)    Register (Limited Service, Free)    Login
  Search:   The ACM Digital Library   The Guide
  
ACM Home Page
Please provide us with feedback. Feedback
Multilevel k-way hypergraph partitioning
Full text PdfPdf (122 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: 343 - 348  
Year of Publication: 1999
ISBN:1-58133-109-7
Authors
George Karypis  Department of Computer Science & Engineering, University of Minnesota, Minneapolis, MN
Vipin Kumar  Department of Computer Science & Engineering, University of Minnesota, Minneapolis, MN
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): 12,   Downloads (12 Months): 65,   Citation Count: 52
Additional Information:

references   cited by   index terms   collaborative colleagues  

Tools and Actions: Request Permissions Request Permissions    Review this Article  
DOI Bookmark: Use this link to bookmark this Article: http://doi.acm.org/10.1145/309847.309954
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
B. W. Kemighan and S. Lin. An efficient heuristic procedure for partitioning graphs. The Bell System Technical Journal, 49(2):291-307, 1970.
 
2
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
 
3
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]
4
Ching-Wei Yeh , Chung-Kuan Cheng , Ting-Ting Y. Lin, A general purpose multiple way partitioning algorithm, Proceedings of the 28th conference on ACM/IEEE design automation, p.421-426, June 17-22, 1991, San Francisco, California, United States  [doi>10.1145/127601.127706]
5
Pak K. Chan , Martine D. F. Schlag , Jason Y. Zien, Spectral K-way ratio-cut partitioning and clustering, Proceedings of the 30th international conference on Design automation, p.749-754, June 14-18, 1993, Dallas, Texas, United States  [doi>10.1145/157485.165117]
 
6
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]
 
7
Horst D. Simon and Shang-Hua Teng. How good is recursive bisection? Technical Report RNR-93-012, NAS Systems Division, NASA, Moffet Field, CA, 1993.
8
C. J. Alpert , A. B. Kahng, Multi-way partitioning via spacefilling curves and dynamic programming, Proceedings of the 31st annual conference on Design automation, p.652-657, June 06-10, 1994, San Diego, California, United States  [doi>10.1145/196244.196603]
 
9
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]
 
10
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
 
11
J. Cong, W. Labio, and N. Shivakumar. Multi-way VLSI circuit partitioning based on dual net representation. IEEE Trans. on Computer-Aided Design of Integrated Cilvuits and Systems, pages 396-409, 1996.
 
12
B. Mobasher, N. Jain, E.H. Han, and J. Srivastava. Web mining: Pattern discovery from world wide web transactions. Technical Report TR-96-050, Department of Computer Science, University of Minnesota, Minneapolis, 1996.
 
13
Duen-Ren Liu , Shashi Shekhar, Partitioning similarity graphs: a framework for declustering problems, Information Systems, v.21 n.6, p.475-496, Sept. 1996  [doi>10.1016/0306-4379(96)00024-5]
14
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]
 
15
George Karypis and Vipin Kumar. A coarse-grain parallel multilevel k-way partitioning algorithm. In P1vceedings of the eighth SlAM conference on Parallel P1vcessing for Scientific Computing, 1997.
16
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]
17
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]
 
18
G. Karypis and V. Kumar. hME-gS 1.5: A hypergraph partitioning package. Technical report, Department of Computer Science, University of Minnesota, 1998. Available on the WWW at URL http://www.cs.umn.edu/'metis.
 
19
George Karypis , Vipin Kumar, Multilevel algorithms for multi-constraint graph partitioning, Proceedings of the 1998 ACM/IEEE conference on Supercomputing (CDROM), p.1-13, November 07-13, 1998, San Jose, CA
 
20
G. Karypis and V. Kumar. Multilevel k-way hypergraph partitioning. Technical Report TR 98-036, Department of Computer Science, University of Minnesota, 1998.
21
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]
 
22
C. Berge, Graphs and Hypergraphs, Elsevier Science Ltd, 1985
 
23
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
 
24
George Karypis , Rajat Aggarwal , Vipin Kumar , Shashi Shekhar, Multilevel hypergraph partitioning: applications in VLSI domain, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.7 n.1, p.69-79, March 1999  [doi>10.1109/92.748202]

CITED BY  52
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
Min Ouyang , Michel Toulouse , Krishnaiyan Thulasiraman , Fred Glover , Jitender S. Deogun, Multilevel cooperative search: application to the circuit/hypergraph partitioning problem, Proceedings of the 2000 international symposium on Physical design, p.192-198, May 2000, San Diego, California, United States
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
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
Xiaojian Yang , Maogang Wang , Kenneth Eguro , Majid Sarrafzadeh, A snap-on placement tool, Proceedings of the 2000 international symposium on Physical design, p.153-158, May 2000, San Diego, 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
Pang-Ning Tan , Hannah Blau , Steve Harp , Robert Goldman, Textual data mining of service center call records, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.417-423, August 20-23, 2000, Boston, Massachusetts, United States
Jason Cong , Sung Kyu Lim, Edge separability based circuit clustering with application to circuit partitioning, Proceedings of the 2000 conference on Asia South Pacific design automation, p.429-434, January 2000, Yokohama, Japan
Jason Cong , Xin Yuan, Multilevel global placement with retiming, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA
Sheldon X.-D. Tan , C.-J. Richard Shi, Balanced multi-level multi-way partitioning of analog integrated circuits for hierarchical symbolic analysis, Integration, the VLSI Journal, v.34 n.1-2, p.65-86, May 2003
Hsun-Cheng Lee , Yao-Wen Chang , Jer-Ming Hsu , Hannah H. Yang, Multilevel floorplanning/placement for large-scale modules using B*-trees, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, 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
Jack Dongarra , Ian Foster , Geoffrey Fox , William Gropp , Ken Kennedy , Linda Torczon , Andy White, References, Sourcebook of parallel computing, Morgan Kaufmann Publishers Inc., San Francisco, CA, 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
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
Maogang Wang , Xiaojian Yang , Majid Sarrafzadeh, Dragon2000: standard-cell placement tool for large industry circuits, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
Taraneh Taghavi , Soheil Ghiasi , Abhishek Ranjan , Salil Raje , Majid Sarrafzadeh, Innovate or perish: FPGA physical design, Proceedings of the 2004 international symposium on Physical design, April 18-21, 2004, Phoenix, Arizona, USA
Yongseok Cheon , D. F. Wong, Design hierarchy guided multilevel circuit partitioning, Proceedings of the 2002 international symposium on Physical design, April 07-10, 2002, San Diego, CA, USA
Karlton Sequeira , Mohammed Zaki , Boleslaw Szymanski , Christopher Carothers, Improving spatial locality of programs via data mining, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C.
Michael G. Wrighton , André M. DeHon, SAT-based optimal hypergraph partitioning with replication, Proceedings of the 2006 conference on Asia South Pacific design automation, January 24-27, 2006, Yokohama, Japan
Yongseok Cheon , Martin D. F. Wong, Crowdedness-balanced multilevel partitioning for uniform resource utilization, Proceedings of the 2005 conference on Asia South Pacific design automation, January 18-21, 2005, Shanghai, China
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
Chin-Chih Chang , Jason Cong , Xin Yuan, Multi-level placement for large-scale mixed-size IC designs, Proceedings of the 2003 conference on Asia South Pacific design automation, January 21-24, 2003, Kitakyushu, Japan
Nathan A. Carr , John C. Hart, Meshed atlases for real-time procedural solid texturing, ACM Transactions on Graphics (TOG), v.21 n.2, p.106-131, April 2002
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
Rob H. Bisseling , Ildikó Flesch, Mondriaan sparse matrix partitioning for attacking cryptosystems by a parallel block Lanczos algorithm: a case study, Parallel Computing, v.32 n.7, p.551-567, September 2006
Tung-Chieh Chen , Yi-Lin Chuang , Yao-Wen Chang, X-architecture placement based on effective wire models, Proceedings of the 2007 international symposium on Physical design, March 18-21, 2007, Austin, Texas, USA
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
Tan Yan , Hiroshi Murata, Fast wire length estimation by net bundling for block placement, Proceedings of the 2006 IEEE/ACM international conference on Computer-aided design, November 05-09, 2006, San Jose, California
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
Tung-Chieh Chen , Yao-Wen Chang , Shyh-Chang Lin, IMF: interconnect-driven multilevel floorplanning for large-scale building-module designs, Proceedings of the 2005 IEEE/ACM International conference on Computer-aided design, p.159-164, November 06-10, 2005, San Jose, CA
Maogang Wang , Abhishek Ranjan , Salil Raje, Multi-Million Gate FPGA Physical Design Challenges, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.891, November 09-13, 2003
Yongseok Cheon , Seokjin Lee , Martin D. F. Wong, Stable Multiway Circuit Partitioning for ECO, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.718, November 09-13, 2003
Ariel Shamir, Feature-Space Analysis of Unstructured Meshes, Proceedings of the 14th IEEE Visualization 2003 (VIS'03), p.25, October 22-24, 2003
Christophe Alexandre , Hugo Clement , Jean-Paul Chaput , Marek Sroka , Christian Masson , Remy Escassut, TSUNAMI: An Integrated Timing-Driven Place And Route Research Platform, Proceedings of the conference on Design, Automation and Test in Europe, p.920-921, March 07-11, 2005
Wonjoon Choi , Kia Bazargan, Hierarchical Global Floorplacement Using Simulated Annealing and Network Flow Area Migration, Proceedings of the conference on Design, Automation and Test in Europe, p.11104, March 03-07, 2003
Jeremy Chan , Sri Parameswaran, NoCOUT: NoC topology generation with mixed packet-switched and point-to-point networks, Proceedings of the 2008 conference on Asia and South Pacific design automation, January 21-24, 2008, Seoul, Korea
Melanie Elm , Hans-Joachim Wunderlich , Michael E. Imhof , Christian G. Zoellin , Jens Leenstra , Nicolas Maeding, Scan chain clustering for test power reduction, Proceedings of the 45th annual conference on Design automation, June 08-13, 2008, Anaheim, California
Jackey Z. Yan , Chris Chu, DeFer: deferred decision making enabled fixed-outline floorplanner, Proceedings of the 45th annual conference on Design automation, June 08-13, 2008, Anaheim, California
Marrakchi Zied , Mrabet Hayder , Amouri Emna , Mehrez Habib, Efficient tree topology for FPGA interconnect network, Proceedings of the 18th ACM Great Lakes symposium on VLSI, May 04-06, 2008, Orlando, Florida, USA
Costas Vassilakis , George Lepouras , Stathis Rouvas , Panagiotis Georgiadis, Exploiting form semantics and validation checks to improve e-form layout, International Journal of Web Engineering and Technology, v.2 n.1, p.81-96, July 2005
Wonhong Nam , P. Madhusudan , Rajeev Alur, Automatic symbolic compositional verification by learning assumptions, Formal Methods in System Design, v.32 n.3, p.207-234, June 2008
Melanie Elm , Hans-Joachim Wunderlich, Scan chain organization for embedded diagnosis, Proceedings of the conference on Design, automation and test in Europe, March 10-14, 2008, Munich, Germany
Jason Cong , Guojie Luo, A multilevel analytical placement for 3D ICs, Proceedings of the 2009 Conference on Asia and South Pacific Design Automation, January 19-22, 2009, Yokohama, Japan
Guoliang Li , Shengyue Ji , Chen Li , Jianhua Feng, Efficient type-ahead search on relational data: a TASTIER approach, Proceedings of the 35th SIGMOD international conference on Management of data, June 29-July 02, 2009, Providence, Rhode Island, USA
Kensuke Onuma , Hanghang Tong , Christos Faloutsos, TANGENT: a novel, 'Surprise me', recommendation algorithm, Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining, June 28-July 01, 2009, Paris, France
Cheng-Yu Wang , Wai-Kei Mak, Signal skew aware floorplanning and bumper signal assignment technique for flip-chip, Proceedings of the 2009 Conference on Asia and South Pacific Design Automation, January 19-22, 2009, Yokohama, Japan
Hui Zhang , Guofei Jiang , Kenji Yoshihira , Haifeng Chen , Akhilesh Saxena, Resilient workload manager: taming bursty workload of scaling internet applications, Proceedings of the 6th international conference industry session on Autonomic computing and communications industry session, June 15-15, 2009, Barcelona, Spain
Sherief Reda, Using circuit structural analysis techniques for networks in systems biology, Proceedings of the 11th international workshop on System level interconnect prediction, July 26-27, 2009, San Francisco, CA, USA
Zied Marrakchi , Hayder Mrabet , Christian Masson , Habib Mehrez, Mesh of Tree: Unifying Mesh and MFPGA for Better Device Performances, Proceedings of the First International Symposium on Networks-on-Chip, p.243-252, May 07-09, 2007

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS


General Terms:
Design, Experimentation, Measurement, Theory

Collaborative Colleagues:
George Karypis: colleagues
Vipin Kumar: colleagues

The ACM Portal is published by the Association for Computing Machinery. Copyright © 2009 ACM, Inc.
Terms of Usage   Privacy Policy   Code of Ethics   Contact Us

Useful downloads: Adobe Acrobat    QuickTime    Windows Media Player    Real Player