A parallel bottom-up clustering algorithm with applications to circuit partitioning in VLSI design

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A parallel bottom-up clustering algorithm with applications to circuit partitioning in VLSI design

Full text

Pdf (752 KB)

Source

Annual ACM IEEE Design Automation Conference archive
Proceedings of the 30th international Design Automation Conference table of contents

Dallas, Texas, United States

Pages: 755 - 760

Year of Publication: 1993

ISBN:0-89791-577-1

Authors

Jason Cong
M'Lissa Smith

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): 15, Downloads (12 Months): 51, Citation Count: 31

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/157485.165119 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	R.L. Bagrodia and W. Liao. Maisie: A language and optimizing environment for distributed simulation, in Proc. of 1990 SCS Multiconference on Distributed Simulation, pages 205-210, San Diego, CA, Jan. 1990.
	2	B. Bollobas. Random Graph~. Academic Pre~5, London, 1985.
	3	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]
	4	Howard R. Charney , Donald L. Plato, Efficient partitioning of components, Proceedings of the 5th annual workshop on Design automation, p.16.1-16.21, July 15-18, 1968, Washington, D. C., United States [doi>10.1145/800167.805401]
	5	J. Cong, L. Hagen, and A. B. Kalmg. Random Walks for (3ircuit Clustering. In Proc. IEEE Intl. Conf. on ASIC, pages 14.2.1- 14.2.4, June 1991.
	6	J. Cong , L. Hagen , A. Kahng, Net partitions yield better module partitions, Proceedings of the 29th ACM/IEEE conference on Design automation, p.47-52, June 08-12, 1992, Anaheim, California, United States
	7	W.E. Donath. Logic Partitioning. In Physical Design Automation of VLSI Systems, B. Preas and M. Lorenzetti, editors, pages 65-86. Benjamln/Cummings, 1988.
	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	Harold Neil Gabow, Implementation of algorithms for maximum matching on nonbipartite graphs., 1974
	10	J. Garbers, H.J. Promel, and A. Steger. Finding Clusters in VLSI Circuits. ICCAD'90, pages 520-523, 1990.
	11	L. Hagen and A. B. Kahng. Fast Spectral Methods for Ratio Cut Partitioning and Clustering. In Proc. IEEE Intl. Conf. on Computer-Aided Design, pages 10-13, 1991.
	12	Lars Hagen , Andrew B. Kahng, A new approach to effective circuit clustering, Proceedings of the 1992 IEEE/ACM international conference on Computer-aided design, p.422-427, November 1992, Santa Clara, California, United States
	13	M. Hanan and J.M. Kurtzberg. A Review of the Placement and Quadratic Assignment Problems. SIAM Review, 14:324-342, 1972.
	14	B.W. Kernighan and S. Lin. An Efficient Heuristic Procedure for Partitioning Graphs. Bell System Technical Journal, 49:291-307, Feb, 1970.
	15	S. Kirkpatrick, (3. Gelatt Jr., and M. Vecchi. Optimization by Simulated Annealing. Science, 220:671-680, May 13 1983.
	16	Thomas Lengauer, Combinatorial algorithms for integrated circuit layout, John Wiley & Sons, Inc., New York, NY, 1990
	17	Y.C. Wet and C.K. Cheng. Towards Efficient Hierarchical Designs by Ratio Cut Partitioning. In Proc. IEEE Intl. Conf. on Computer-Aided Design, pages 298-301, 1989.

CITED BY 31

	Thang Nguyen Bui , Byung Ro Moon, A fast and stable hybrid genetic algorithm for the ratio-cut partitioning problem on hypergraphs, Proceedings of the 31st annual conference on Design automation, p.664-669, June 06-10, 1994, San Diego, California, United States
	Hong Yu , Xianlong Hong , Yici Cai, MMP: a novel placement algorithm for combined macro block and standard cell layout design, Proceedings of the 2000 conference on Asia South Pacific design automation, p.271-276, January 2000, Yokohama, Japan
	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
	Roman Kužnar , Franc Brglez, PROP: a recursive paradigm for area-efficient and performance oriented partitioning of large FPGA netlists, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.644-649, November 05-09, 1995, San Jose, California, United States
	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
	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
	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
	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
	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
	J. Song , Z. Shen , W. Zhuang, An effective general connectivity concept for clustering, Proceedings of the conference on Design, automation and test in Europe, p.398-405, February 23-26, 1998, Le Palais des Congrés de Paris, France
	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
	Jianmin Li , John Lillis , Lung-Tien Liu , Chung-Kuan Cheng, New spectral linear placement and clustering approach, Proceedings of the 33rd annual conference on Design automation, p.88-93, June 03-07, 1996, Las Vegas, Nevada, United States
	Amit Singh , Malgorzata Marek-Sadowska, Circuit clustering using graph coloring, Proceedings of the 1999 international symposium on Physical design, p.164-169, April 12-14, 1999, Monterey, California, United States
	Roman Kužnar , Franc Brglez , Baldomir Zajc, Multi-way netlist partitioning into heterogeneous FPGAs and minimization of total device cost and interconnect, Proceedings of the 31st annual conference on Design automation, p.238-243, June 06-10, 1994, San Diego, California, United States
	Jason Cong , Zheng Li , Rajive Bagrodia, Acyclic multi-way partitioning of Boolean networks, Proceedings of the 31st annual conference on Design automation, p.670-675, June 06-10, 1994, San Diego, California, United States
	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
	C. J. Alpert , A. B. Kahng, A general framework for vertex orderings, with applications to netlist clustering, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.63-67, November 06-10, 1994, San Jose, California, United States
	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
	Dirk Behrens , Klaus Harbich , Erich Barke, Hierarchical partitioning, Proceedings of the 1996 IEEE/ACM international conference on Computer-aided design, p.470-477, November 10-14, 1996, San Jose, California, United States
	Bo Hu , Malgorzata Marek-Sadowska, Fine granularity clustering for large scale placement problems, Proceedings of the 2003 international symposium on Physical design, April 06-09, 2003, Monterey, CA, USA
	Amit Singh , Malgorzata Marek-Sadowska, Efficient circuit clustering for area and power reduction in FPGAs, Proceedings of the 2002 ACM/SIGDA tenth international symposium on Field-programmable gate arrays, February 24-26, 2002, Monterey, California, USA
	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
	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
	Roman Kužnar , Baldomir Zajc , Franc Brglez, A unified cost model for min-cut partitioning with replication applied to optimization of large heterogeneous FPGA partitions, Proceedings of the conference on European design automation, p.271-276, September 19-23, 1994, Grenoble, France
	Kirk Schloegel , George Karypis , Vipin Kumar, Wavefront Diffusion and LMSR: Algorithms for Dynamic Repartitioning of Adaptive Meshes, IEEE Transactions on Parallel and Distributed Systems, v.12 n.5, p.451-466, May 2001
	C. Gil , J. Ortega , M. G. Montoya , R. Baños, A Mixed Heuristic for Circuit Partitioning, Computational Optimization and Applications, v.23 n.3, p.321-340, December 2002
	Klaus Holzapfel , Sven Kosub , Moritz G. Maaß , Hanjo Täubig, The complexity of detecting fixed-density clusters, Discrete Applied Mathematics, v.154 n.11, p.1547-1562, 1 July 2006
	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
	D. J. -H. Huang , A. B. Kahng, When clusters meet partitions: new density-based methods for circuit decomposition, Proceedings of the 1995 European conference on Design and Test, p.60, March 06-09, 1995
	Huimin Geng , Xutao Deng , Hesham H. Ali, Message Passing Clustering (MPC): a knowledge-based framework for clustering under biological constraints, International Journal of Data Mining and Bioinformatics, v.2 n.2, p.95-120, June 2008
	Xing-Zhi Wang , Zheng Yan , Li Li, An adaptive scheme for distributed dynamic security assessment of large scale power systems, WSEAS Transactions on Circuits and Systems, v.8 n.2, p.247-256, February 2009