Partitioning very large circuits using analytical placement techniques

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Partitioning very large circuits using analytical placement techniques

Full text

Pdf (388 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: 646 - 651

Year of Publication: 1994

ISBN:0-89791-653-0

Authors

Bernhard M. Riess	Institute of Electronic Design Automation, Technical University of Munich, 80290 Munich, Germany
Konrad Doll	Institute of Electronic Design Automation, Technical University of Munich, 80290 Munich, Germany
Frank M. Johannes	Institute of Electronic Design Automation, Technical University of Munich, 80290 Munich, Germany

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): 3, Downloads (12 Months): 21, Citation Count: 29

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.196602 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	Donald M. Schuler , Ernst G. Ulrich, Clustering and linear placement, Proceedings of the 9th workshop on Design automation, p.50-56, June 26-28, 1972 [doi>10.1145/800153.804929]
	2	B. W. Kernighan and S. Lin, "An Efficient Heuristic Procedure for Partitioning Graphs," Bell Systems Technical Journal, pp. 291-307, 1970.
	3	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
	4	Y.-C. Wei and C.-K. Cheng, "Towards Efficient Hierarchical Designs by Ratio Cut Partitioning," IEEE/A CM Int. Conf. on Computer-Aided Design, pp. 298-301, 1989.
	5	Y.-C. Wei and C.-K. Cheng, "Ratio Cut Partitioning for Hierarchical Designs," IEEE Transactions on Computer- Aided Design, vol. 10, no. 7, pp. 911-921, 1991.
	6	Earl R. Barnes , Anthony Vannelli , James Q. Walker, A new heuristic for partitioning the nodes of a graph, SIAM Journal on Discrete Mathematics, v.1 n.3, p.299-305, Aug. 1988 [doi>10.1137/0401030]
	7	J. Frankle and R. M. Karp, "Circuit Placements and Cost Bounds by Eigenvector Decomposition," IEEE/A CM Int. Conf. on Computer-Aided Design, pp. 414-417, 1986.
	8	R. B. Boppana, "Eigenvalues and Graph Bisecion: An Average-case Analysis," IEEE Syrup. on Foundations of Computer Science, pp. 280-285, 1987.
	9	L. Hagen and A. B. Kahng, "Fast Spectral Methods for Ratio Cut Partitioning and Clustering," IEEE/A CM Int. Conf. on Computer-Aided Design, pp. 10-13, 1991.
	10	L. Hagen and A. B. Kahng, "Fast Spectral Methods for Ratio Cut Partitioning and Clustering," CS Departement Tech. Report, University of California, Los Angeles, 1991.
	11	K. M. Hall, "An r-Dimensional Quadratic Placement Algorithm," Management Science, pp. 219-229, 1970.
	12	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
	13	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]
	14	S. W. Hadley, B. L. Mark, and A. Vanelli, "An Efficient Eigenvector Approach for Finding Netlist Pattitions," IEEE Trans. on CAD, pp. 885-892, 1992.
	15	S. Areibi and A. Vanelli, "A Combined Eigenvector Tabu Search Approach for Circuit Partitioning," IEEE Proc. Custom Integrated Circuits Conf., pp. 9.7.1 - 9.7.4, 1993.
	16	J. M. Kleinhans, G. Sigl, F. M. Johannes, and K. J. Antreich, "GORDIAN: VLSI Placement by Quadratic Programming and Slicing Optimization," IEEE Trans. on Computer-Aided Design, vol. 10, no. 3, pp. 356-365, 1991.
	17	Georg Sigl , Konrad Doll , Frank M. Johannes, Analytical placement: A linear or a quadratic objective function?, Proceedings of the 28th conference on ACM/IEEE design automation, p.427-432, June 17-22, 1991, San Francisco, California, United States [doi>10.1145/127601.127707]
	18	L. Hagen and A. B. Kahng, "Improving the Quadratic Objective Function in Module Placement," Fifth Annual IEEE Int. ASIC Conference and Exhibit, pp. 42-45, 1992.
	19	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]
	20	Krzysztof Koźmiński, Benchmarks for layout synthesis—evolution and current status, Proceedings of the 28th conference on ACM/IEEE design automation, p.265-270, June 17-22, 1991, San Francisco, California, United States [doi>10.1145/127601.127678]
	21	F. Brglez, D. Bryan, and K. Kozminski, "Combinational Profiles of Sequential Benchmark Circuits," Proc. IEEE Int. Syrup. on CAS, vol. 3, no. 3, pp. 1929-1934, 1989.

CITED BY 29

	John M. Emmert , Sandeep Lodha , Dinesh K. Bhatia, On Using Tabu Search for Design Automation of VLSI Systems, Journal of Heuristics, v.9 n.1, p.75-90, January 2003
	Shinji Sato, Simulated quenching: a new placement method for module generation, Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design, p.538-541, November 09-13, 1997, 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
	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
	Scott Hauck , Gaetano Borriello, Logic partition orderings for multi-FPGA systems, Proceedings of the 1995 ACM third international symposium on Field-programmable gate arrays, p.32-38, February 12-14, 1995, Monterey, California, United States
	Morgan Enos , Scott Hauck , Majid Sarrafzadeh, Replication for logic bipartitioning, Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design, p.342-349, November 09-13, 1997, 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
	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
	Lung-Tien Liu , Ming-Ter Kuo , Shih-Chen Huang , Chung-Kuan Cheng, A gradient method on the initial partition of Fiduccia-Mattheyses algorithm, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.229-234, November 05-09, 1995, San Jose, California, United States
	Shantanu Dutt , Wenyong Deng, Cluster-aware iterative improvement techniques for partitioning large VLSI circuits, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.7 n.1, p.91-121, January 2002
	Vi Chi Chan , David Lewis, Hierarchical partitioning for field-programmable systems, Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design, p.428-435, November 09-13, 1997, San Jose, California, United States
	Jason Cong , Honching Peter Li , Sung Kyu Lim , Toshiyuki Shibuya , Dongmin Xu, Large scale circuit partitioning with loose/stable net removal and signal flow based clustering, Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design, p.441-446, November 09-13, 1997, 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
	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
	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, A probability-based approach to VLSI circuit partitioning, Proceedings of the 33rd annual conference on Design automation, p.100-105, June 03-07, 1996, Las Vegas, Nevada, United States
	Norbert Fröhlich , Rolf Schlagenhaft , Josef Fleischmann, A new approach for partitioning VLSI circuits on transistor level, ACM SIGSIM Simulation Digest, v.27 n.1, p.64-67, July 1997
	Charles J. Alpert , Tony F. Chan , Dennis J.-H. Huang , Andrew B. Kahng , Igor L. Markov , Pep Mulet , Kenneth Yan, Faster minimization of linear wirelength for global placement, Proceedings of the 1997 international symposium on Physical design, p.4-11, April 14-16, 1997, Napa Valley, California, United States
	Frank M. Johannes, Partitioning of VLSI circuits and systems, Proceedings of the 33rd annual conference on Design automation, p.83-87, June 03-07, 1996, Las Vegas, Nevada, United States
	Joachim Pistorius , Edmée Legai , Michel Minoux, Generation of very large circuits to benchmark the partitioning of FPGA, Proceedings of the 1999 international symposium on Physical design, p.67-73, April 12-14, 1999, Monterey, 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
	Honghua Yang , D. F. Wong, Efficient network flow based min-cut balanced partitioning, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.50-55, November 06-10, 1994, 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
	Jianmin Li , John Lillis , Chung-Kuan Cheng, Linear decomposition algorithm for VLSI design applications, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.223-228, November 05-09, 1995, San Jose, California, United States
	Shawki Areibi , Zhen Yang, Effective memetic algorithms for VLSI design automation = genetic algorithms + local search + multi-level clustering, Evolutionary Computation, v.12 n.3, p.327-353, September 2004
	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
	K. S. Seong , C. M. Kyung, Two-way partitioning based on direction vector, Proceedings of the 1997 European conference on Design and Test, p.306, March 17-20, 1997
	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