Geometric embeddings for faster and better multi-way netlist partitioning

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Geometric embeddings for faster and better multi-way netlist partitioning

Full text

Pdf (719 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: 743 - 748

Year of Publication: 1993

ISBN:0-89791-577-1

Authors

C. J. Alpert
A. B. Kahng

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

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.165115 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	J P. Benz~cri, "Construction d'une Classification Ascendante Ht~rarchique par la Rechereche en Chaine des Volsms R~clproques", m Les Cah~ers de l'Analyse des Donndes (VII)2, 1982, pp. 209-218.
	2	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]
	3	P. Brucker, "On the Complexity of Clustering Problems", m Opt~m~zatzon and Operations Research, 1977, pp 45-54
	4	Pak K. Chan , Martine Schlag , Jason Y. Zien, Spectral k-way ratio-cut partitioning and clustering, Proceeding of the 1993 symposium on Research on integrated systems, p.123-142, February 1993, Seattle, Washington, United States
	5	Tomás Feder , Daniel Greene, Optimal algorithms for approximate clustering, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.434-444, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62255]
	6	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
	7	T. F Gonzalez, "Clustering to Minimize the Maximum Intercluster Distance", in TheoretscaI Computer Scsence, 38, 1985, pp. 293-306.
	8	A. Gu~noche, P. Hansen and B Jaumard, "Efficmnt Algorithms for Divisive Hierarchical Clustering with the Diameter Criterion", in Journal of Classification, 8, 1991, pp. 5-30. 1990.
	9	S. W. Hadley, B. L. Mark and A. Vanelli, "An Efficient Elgenvector Approach for Finding Netlist Partitions", in IEEE Trans. on CAD, 11(7), July 1992, pp. 885-892.
	10	L Hagen and A B Kahng, "New Spectral Methods for Ratio Cut Partitioning and Clustering", in IEEE Trans. on CAD 1I(9), Sept 1992, pp. 1074-1085.
	11	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
	12	K M Hall, "An r-dimensional Quadratic Placement Algorithm", in Manag. Sc,, 17, 1970, pp.219-229.
	13	J. Hershberger, "Minimizing the Sum of Diameters Efficmntly" in Proc, 3rd Canadian Conference on Computational Geometry, 1991, pp 62-65.
	14	S. C. Johnson, "Hierarchical Clustering Schemes", in Psychometmka 32(3), 1967, pp 241-254.
	15	Thomas Lengauer, Combinatorial algorithms for integrated circuit layout, John Wiley & Sons, Inc., New York, NY, 1990
	16	N. Megiddo and K. J. Supowit, "On the Complexity of Some Common Geometric Location Problems", in Szam Journal of Computzng, 13(1), 1984, pp. 182-196.
	17	F. P. Prep,rata and M. I. Shamos, Computational Geometry, Springer Verlag, New York, NY, 1985.
	18	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]
	19	D. G. Schweikert , B. W. Kernighan, A proper model for the partitioning of electrical circuits, Proceedings of the 9th workshop on Design automation, p.57-62, June 26-28, 1972 [doi>10.1145/800153.804930]
	20	Y C. We1 and C K. Cheng, "Ratio Cut Partitioning for Hierarchical Designs", m IEEE Trans. on CAD 10(7), July 1991, pp 911-921.
	21	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]
	22	Ching-Wei Yeh , Chung-Kuan Cheng , Ting-Ting Y. Lin, A probabilistic multicommodity-flow solution to circuit clustering problems, Proceedings of the 1992 IEEE/ACM international conference on Computer-aided design, p.428-431, November 1992, Santa Clara, California, United States
	23	J. Zien, "Spectral K-Way Ratio Cut Graph Partitiomng", M.S. Thesis, Computer Engineering Dept , UC Santa Cruz, March 1993

CITED BY 14

	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
	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
	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
	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
	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
	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
	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
	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
	Charles J. Alpert , So-Zen Yao, Spectral partitioning: the more eigenvectors, the better, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.195-200, June 12-16, 1995, San Francisco, California, United States
	Andrew B. Kahng , C.-W. Albert Tsao, Practical Bounded-Skew Clock Routing, Journal of VLSI Signal Processing Systems, v.16 n.2-3, p.199-215, June/July 1997
	Nestor F. Michelena , Panos Y. Papalambros, A Hypergraph Framework for Optimal Model-Based Decomposition ofDesign Problems, Computational Optimization and Applications, v.8 n.2, p.173-196, Sept 1997
	Romain Boulet , Bertrand Jouve , Fabrice Rossi , Nathalie Villa, Batch kernel SOM and related Laplacian methods for social network analysis, Neurocomputing, v.71 n.7-9, p.1257-1273, March, 2008
	Andrew B. Kahng , Ion Mandoiu , Sherief Reda , Xu Xu , Alex Z. Zelikovsky, Evaluation of Placement Techniques for DNA Probe Array Layout, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.262, November 09-13, 2003
	Pascale Kuntz , Dominique Snyers , Paul Layzell, A Stochastic Heuristic for Visualising Graph Clusters in a Bi-DimensionalSpace Prior to Partitioning, Journal of Heuristics, v.5 n.3, p.327-351, October 1999