A general purpose multiple way partitioning algorithm

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A general purpose multiple way partitioning algorithm

Full text

Pdf (689 KB)

Source

Annual ACM IEEE Design Automation Conference archive
Proceedings of the 28th ACM/IEEE Design Automation Conference table of contents

San Francisco, California, United States

Pages: 421 - 426

Year of Publication: 1991

ISBN:0-89791-395-7

Authors

Ching-Wei Yeh	Computer Science and Engineering Department, University of California, San Diego
Chung-Kuan Cheng	Computer Science and Engineering Department, University of California, San Diego
Ting-Ting Y. Lin	Electrical and Computer Engineering Department, University of California, San Diego

Sponsors

SIGDA: ACM Special Interest Group on Design Automation
IEEE-CS : Computer Society

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 13, Downloads (12 Months): 25, Citation Count: 18

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/127601.127706 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	M. A. Breuer, "Design Automation of Digital S yst(~'ns', Prentice-Hall, NY, 1972
	2	E. L. Lawler, IC N. Levitt and J. Turner) "Module Clustering to ~animize de.lay in Digital networks," IEEE Trans. on Computers, vol. C-18, Jan. 1969, pp. 4%57
	3	W. M. Dai and E. S. Kuh, "Hierarchical Floor Planning for Building Block Layout," IEEE Conf. on Computer-Aided Design, 1986
	4	T. C. Hu and E. S. Kuh, "VLSI Circuit Layout Theory and Design," IEEE Press, 1985
	5	B. W. Kemighan and S. IAn, "An Efficient Heuristic Procedure for Partitioning Graphs', Ball System Technical Journal, 49(2), Feb. 1970, pp.291-307
	6	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]
	7	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
	8	C. Sechen and D. Chert, "An Improved Objective Function for Mincut Circuit Partitioning", Prec. Int. ConL on Compute-Aided Design, 1988, pp.502-505
	9	B. Kfishnarnurthy, "An Improved Min-cut Algorithm for Paedtioning VLSI Networks', IEEE Trans. on Computers, Vol C-33, May 1984, pp.438-446
	10	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]
	11	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
	12	W.E. Donath, "Logic Panitioning," in "Physical Design Automation of VI~I Systems," edited by B. Preas and M. Lor(mzotti, Benjamin/Cumming Publishing Co.,1988, pp.05-86
	13	Y. Wei and C. K. Cheng, "Toward Efficient Hierarchical Designs by Ratio Cut Partitioning", Proc. Int. Conf. on Computer-Aided Design, 1989, pp.298-301
	14	Y. Wci and C. K. Cheng, "Two-way Two-level Partitioning Algorithm," to appear in IEEE Int. Conf. on Computer Aided D(~gn, 1990
	15	L. R. Ford and D. R. Fulkerson, "Flows in Networks", Princeton University Press, 1962
	16	M. V. Lomonosov, "Combinatorial Approachvs to Multiflow Problems," Discrete Applied Mathematics 1 i(I) 1985, pp.l-94
	17	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]
	18	A. B. Kahng, Fast hypergraph partition, Proceedings of the 26th ACM/IEEE conference on Design automation, p.762-766, June 25-28, 1989, Las Vegas, Nevada, United States [doi>10.1145/74382.74524]
	19	Lawrence T. Pillage , Ronald A. Rohrer, A quadratic metric with a simple solution scheme for initial placement, Proceedings of the 25th ACM/IEEE conference on Design automation, p.324-329, June 12-15, 1988, Atlantic City, New Jersey, United States

CITED BY 18

	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
	Nam Sung Woo , Jaeseok Kim, An efficient method of partitioning circuits for multiple-FPGA implementation., Proceedings of the 30th international conference on Design automation, p.202-207, June 14-18, 1993, Dallas, Texas, United States
	Helena Krupnova , Ali Abbara , Gabrièle Saucier, A hierarchy-driven FPGA partitioning method, Proceedings of the 34th annual conference on Design automation, p.522-525, June 09-13, 1997, Anaheim, California, United States
	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
	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
	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
	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 , 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
	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 , 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
	H. Krupnova , C. Rabedaoro , G. Saucier, Synthesis and floorplanning for large hierarchical FPGAs, Proceedings of the 1997 ACM fifth international symposium on Field-programmable gate arrays, p.105-111, February 09-11, 1997, Monterey, California, United States
	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
	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
	Huoy-Yu Liou , Ting-Ting Y. Lin, Area efficient pipelined pseudo-exhaustive testing with retiming, Proceedings of the 33rd annual conference on Design automation, p.274-279, June 03-07, 1996, Las Vegas, Nevada, United States
	Roman Kužnar , Franc Brglez , Krzysztof Kozminski, Cost minimization of partitions into multiple devices, Proceedings of the 30th international conference on Design automation, p.315-320, June 14-18, 1993, Dallas, Texas, 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
	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
	Shashi Shekhar , Duen-Ren Liu, CCAM: A Connectivity-Clustered Access Method for Networks and Network Computations, IEEE Transactions on Knowledge and Data Engineering, v.9 n.1, p.102-119, January 1997