Multi-way partitioning via spacefilling curves and dynamic programming

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Multi-way partitioning via spacefilling curves and dynamic programming

Full text

Pdf (237 KB)

Source

Annual ACM IEEE Design Automation Conference archive
Proceedings of the 31st annual Design Automation Conference table of contents

San Diego, California, United States

Pages: 652 - 657

Year of Publication: 1994

ISBN:0-89791-653-0

Authors

C. J. Alpert	UCLA Computer Science Department, Los Angeles, CA
A. B. Kahng	UCLA Computer Science Department, Los Angeles, CA

Sponsors

IEEE-CAS : Circuits & Systems
SIGDA: ACM Special Interest Group on Design Automation
EDAC : Electronic Design Automation Consortium

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 9, Downloads (12 Months): 33, Citation Count: 16

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/196244.196603 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 and A. B. Kahng, "Multi-Way Netlist Partitioning Using Spacefilling Curves," UCLA technical report 9.50016, 1993.
	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	John J. Barthholdi, III , Loren K. Platzman, Heuristics based on spacefilling curves for combinatorial problems in Euclidean space, Management Science, v.34 n.3, p.291-305, March 1988 [doi>10.1287/mnsc.34.3.291]
	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	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
	6	L. Hagen and A. B. Kahng, "New Spectral Methods for Ratio Cut Partitioning and Clustering", IEEE Trans. on CAD 11(9), Sept. 1992, pp. 1074-1085.
	7	K. M. Hall, "An r-dimensional Quadratic Placement Algorithm", Manag. Sci, 17, 1970, pp. 219-229.
	8	R. M. Karp, "Probabilistic Analysis of Partitioning Algorithms for the Traveling-Salesman Problem in the Plane", Mathematics of Operations Research 2(3), 1977, pp. 209- 224.
	9	Thomas Lengauer, Combinatorial algorithms for integrated circuit layout, John Wiley & Sons, Inc., New York, NY, 1990
	10	Alex Pothen , Horst D. Simon , Kan-Pu Liou, Partitioning sparse matrices with eigenvectors of graphs, SIAM Journal on Matrix Analysis and Applications, v.11 n.3, p.430-452, Jul. 1990 [doi>10.1137/0611030]
	11	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]
	12	D. S. Scott, "LASO2 Documentation", technical report, CS Dept., University of Texas at Austin, 1980.
	13	H. D. Simon, "Partitioning of Unstructured Problems for Parallel Processing", technical report, NAS Systems Division, NASA Ames Research Center, Feb. 1991.
	14	Y. C. Wei and C. K. Cheng, "Ratio Cut Partitioning for Hierarchical Designs", IEEE Trans. on CAD 10(7), July 1991, pp. 911-921.
	15	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]

CITED BY 16

	Dennis J.-H. Huang , Andrew B. Kahng, Multi-way system partitioning into a single type or multiple types of FPGAs, Proceedings of the 1995 ACM third international symposium on Field-programmable gate arrays, p.140-145, February 12-14, 1995, Monterey, 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
	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
	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
	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
	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
	Pak K. Chan , Martine D. F. Schlag , Jason Y. Zien, Spectral-based multi-way FPGA partitioning, Proceedings of the 1995 ACM third international symposium on Field-programmable gate arrays, p.133-139, February 12-14, 1995, Monterey, California, United States
	A. B. Kahng , I. Mandoiu , P. Pevzner , S. Reda , A. Zelikovsky, Engineering a scalable placement heuristic for DNA probe arrays, Proceedings of the seventh annual international conference on Research in computational molecular biology, p.148-156, April 10-14, 2003, Berlin, Germany
	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
	Guohua Jin , John Mellor-Crummey, SFCGen: A framework for efficient generation of multi-dimensional space-filling curves by recursion, ACM Transactions on Mathematical Software (TOMS), v.31 n.1, p.120-148, March 2005
	Jason Cong , Guoling Han , Zhiru Zhang, Architecture and compiler optimizations for data bandwidth improvement in configurable processors, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.14 n.9, p.986-997, September 2006
	Chris H. Hamilton , Andrew Rau-Chaplin, Compact Hilbert indices: Space-filling curves for domains with unequal side lengths, Information Processing Letters, v.105 n.5, p.155-163, February, 2008
	J. Cong , Guoling Han , Zhiru Zhang, Architecture and compilation for data bandwidth improvement in configurable embedded processors, Proceedings of the 2005 IEEE/ACM International conference on Computer-aided design, p.263-270, November 06-10, 2005, San Jose, CA
	Jacques M. Bahi , Abdallah Makhoul , Ahmed Mostefaoui, Localization and coverage for high density sensor networks, Computer Communications, v.31 n.4, p.770-781, March, 2008
	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
	B. M. Riess , A. A. Schoene, Architecture driven k-way partitioning for multichip modules, Proceedings of the 1995 European conference on Design and Test, p.71, March 06-09, 1995