A proper model for the partitioning of electrical circuits

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A proper model for the partitioning of electrical circuits

Full text

Pdf (509 KB)

Source

Annual ACM IEEE Design Automation Conference archive
Proceedings of the 9th Design Automation Workshop table of contents

Pages: 57 - 62

Year of Publication: 1972

Authors

D. G. Schweikert
B. W. Kernighan

Sponsors

IEEE : Institute of Electrical and Electronics Engineers
ACM: Association for Computing Machinery

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 10, Downloads (12 Months): 51, Citation Count: 49

Additional Information:

abstract 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/800153.804930 What is a DOI?

ABSTRACT

Partitioning algorithms for electrical circuits are often based on the heuristic manipulation of a simple element-to-element interconnection matrix. However, the element-to-element interconnection matrix does not properly represent an electrical interconnection, or “net”, among more than two elements. This paper expands on several aspects of the discrepancy: 1) its source, 2) the circumstances under which it is likely to be significant, and its magnitude for typical circuits, and 3) the comparative difficulty and expense of using a more appropriate representation. A physically correct “net-cut” model is presented. This model is computationally straightforward and is easily adapted to the typical heuristic solution strategies. The “net-cut” model is coupled with the Kernighan-Lin partitioning algorithm [3]; using the same algorithm, comparisons with the “edge-cut” model demonstrate that the correct model reduces net-cuts by 19 to 50% for four digital logic circuits.

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. Hanan and J. M. Kurtzberg, A review placement and quadratic assignment problems. IBM Report RC-3046, 20 April 1970. (This report was the basis of a tutorial given by Hanan at the 8th Design Automation Workshop, June 1971, but did not appear in the Proceedings.)
	2	R. A. Rutman, An algorithm for placement of interconnected elements based on minimum wire length. Proc. SJCC (1964), 477-491.
	3	B. W. Kernighan and S. Lin, An efficient heuristic procedure for partitioning graphs. Bell System Tech. J. Feb. 1970, pp. 291-308. U. S. Patent 3,617,714 (Nov. 1971).
	4	A. H. Scheinman, Private communication.

CITED BY 49

	T. Kambe , T. Chiba , S. Kimura , T. Inufushi , N. Okuda , I. Nishioka, A placement algorithm for polycell LSI and ITS evaluation, Proceedings of the 19th conference on Design automation, p.655-662, January 1982
	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
	W. M. Vancleemput , J. G. Linders, An improved graph-theoretic model for the circuit layout problem, Proceedings of the 11th workshop on Design automation, p.82-90, January 1974
	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
	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
	Hiroshi Shiraishi , Fumiyasu Hirose, Efficient placement and routing techniques for master slice LSI, Proceedings of the 17th conference on Design automation, p.458-464, June 23-25, 1980, Minneapolis, Minnesota, United States
	T. J. Kowalski , D. E. Thomas, The VLSI design automation assistant: what's in a knowledge base, Proceedings of the 22nd ACM/IEEE conference on Design automation, p.252-258, June 1985, Las Vegas, Nevada, United States
	A. J. Goldstein , A. B. Lesk, Common feature techniques for discrete optimization, Proceedings of the 13th conference on Design automation, p.232-244, June 28-30, 1976, San Francisco, California, United States
	J.-S. Yih , P. Mazumder, A neural network design for circuit partitioning, Proceedings of the 26th ACM/IEEE conference on Design automation, p.406-411, June 25-28, 1989, Las Vegas, Nevada, United States
	Maurice Hanan , Peter K. Wolff, Sr. , Barbara J. Agule, Some experimental results on placement techniques, Proceedings of the 13th conference on Design automation, p.214-224, June 28-30, 1976, San Francisco, California, United States
	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
	Steven T. Healey , Daniel D. Gajski, Decomposition of logic networks into silicon, Proceedings of the 22nd ACM/IEEE conference on Design automation, p.162-168, June 1985, Las Vegas, Nevada, United States
	Tokinori Kozawa , Hiroshi Horino , Tadakatu Ishiga , Junya Sakemi , Shoji Sato, Advanced LILAC - an Automated Layout Generation system for MOS/LSIs, Proceedings of the 11th workshop on Design automation, p.26-46, January 1974
	William R. Heller , G. Sorkin , Klim Maling, The planar package planner for system designers, Proceedings of the 19th conference on Design automation, p.253-260, January 1982
	X. Zhang , T. L. Pillage , R. A. Rohrer, Efficient final placement based on nets-as-points, Proceedings of the 26th ACM/IEEE conference on Design automation, p.578-581, June 25-28, 1989, Las Vegas, Nevada, United States
	C. M. Fiduccia , R. M. Mattheyses, A linear-time heuristic for improving network partitions, Papers on Twenty-five years of electronic design automation, p.241-247, June 1988
	Y. Saab , V. Rao, An evolution-based approach to partitioning ASIC systems, Proceedings of the 26th ACM/IEEE conference on Design automation, p.767-770, June 25-28, 1989, Las Vegas, Nevada, United States
	G. J. Wipfler , M. Wiesel , D. A. Mlynski, A combined force and cut algorithm for hierarchical VLSI layout, Proceedings of the 19th conference on Design automation, p.671-677, January 1982
	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
	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
	I. H. Kirk , P. D. Crowhurst , J. A. Skingley , J. D. Bowman , G. L. Taylor, Placement of irregular circuit elements on non-uniform gate arrays, Proceedings of the 20th conference on Design automation, p.637-643, June 27-29, 1983, Miami Beach, Florida, United States
	D. G. Schweikert, A 2-dimensional placement algorithm for the layout of electrical circuits, Papers on Twenty-five years of electronic design automation, p.102-110, June 1988
	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
	G. Persky , H. K. Gummel, GRAFOS - A symbolic routing language, Proceedings of the 10th workshop on Design automation, p.173-181, June 25-27, 1973
	Michael C. McFarland S.J., Computer-aided partitioning of behavioral hardware descriptions, Proceedings of the 20th conference on Design automation, p.472-478, June 27-29, 1983, Miami Beach, Florida, United States
	U. Lauther, A min-cut placement algorithm for general cell assemblies based on a graph representation, Papers on Twenty-five years of electronic design automation, p.182-191, June 1988
	Bryan T. Preas , Patrick G. Karger, Automatic placement a review of current techniques (tutorial session), Proceedings of the 23rd ACM/IEEE conference on Design automation, p.622-629, July 1986, Las Vegas, Nevada, United States
	Daniel G. Schweikert, A 2-dimensional placement algorithm for the layout of electrical circuits., Proceedings of the 13th conference on Design automation, p.408-416, June 28-30, 1976, San Francisco, California, United States
	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
	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
	Sungho Kang, Linear ordering and application to placement, Proceedings of the 20th conference on Design automation, p.457-464, June 27-29, 1983, Miami Beach, Florida, United States
	M. Hanan , P. K. Wolff , B. J. Agule, Some experimental results on placement techniques, Papers on Twenty-five years of electronic design automation, p.73-83, June 1988
	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
	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
	Steve Meyer, A data structure for circuit net lists, Proceedings of the 25th ACM/IEEE conference on Design automation, p.613-616, June 12-15, 1988, Atlantic City, New Jersey, United States
	Krishna Rao Valavala , Mahmoud A. Manzoul, A Fuzzy Partitioning System, IEEE Micro, v.15 n.6, p.76.50-76.57, December 1995
	K. Shahookar , P. Mazumder, VLSI cell placement techniques, ACM Computing Surveys (CSUR), v.23 n.2, p.143-220, June 1991
	R. P. Goré , K. Ramaamohanarao, Automatic synthesis of Boolean equations using programmable array logic, Proceedings of the 26th ACM/IEEE conference on Design automation, p.283-289, June 25-28, 1989, Las Vegas, Nevada, United States
	Melvin A. Breuer, A class of min-cut placement algorithms, Proceedings of the 14th conference on Design automation, p.284-290, January 1977
	Laura A. Sanchis, Multiple-Way Network Partitioning with Different Cost Functions, IEEE Transactions on Computers, v.42 n.12, p.1500-1504, December 1993
	Umit Catalyurek , Cevdet Aykanat, Hypergraph-Partitioning-Based Decomposition for Parallel Sparse-Matrix Vector Multiplication, IEEE Transactions on Parallel and Distributed Systems, v.10 n.7, p.673-693, July 1999
	Douglas C. Schmidt , Lawrence E. Druffel, An iterative algorithm for placement and assignment of integrated circuits, Proceedings of the 12th conference on Design automation, p.361-368, January 1975
	Tadakatsu Ishiga , Tokinori Kozawa , Shoji Sato, A logic partitioning procedure by interchanging clusters, Proceedings of the 12th conference on Design automation, p.369-377, January 1975
	Pao-Tsin Wang, A partitioning technique for LSI chips, ACM SIGDA Newsletter, v.4 n.3, p.29-35, September 1974
	L. A. Sanchis, Multiple-Way Network Partitioning, IEEE Transactions on Computers, v.38 n.1, p.62-81, January 1989
	Tarek F. Abdelzaher , Kang G. Shin, Period-Based Load Partitioning and Assignment for Large Real-Time Applications, IEEE Transactions on Computers, v.49 n.1, p.81-87, January 2000
	Aleksandar Trifunović , William J. Knottenbelt, Parallel multilevel algorithms for hypergraph partitioning, Journal of Parallel and Distributed Computing, v.68 n.5, p.563-581, May, 2008
	Ulrich Lauther, A min-cut placement algorithm for general cell assemblies based on a graph representation, Proceedings of the 16th Conference on Design automation, p.1-10, June 25-27, 1979, San Diego, CA, United States
	Cevdet Aykanat , B. Barla Cambazoglu , Bora Uçar, Multi-level direct K-way hypergraph partitioning with multiple constraints and fixed vertices, Journal of Parallel and Distributed Computing, v.68 n.5, p.609-625, May, 2008