An evolution-based approach to partitioning ASIC systems

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback
Take a look at the new version of this page: [ beta version ]. Tell us what you think.

An evolution-based approach to partitioning ASIC systems

Full text

Pdf (453 KB)

Source

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

Las Vegas, Nevada, United States

Pages: 767 - 770

Year of Publication: 1989

ISBN:0-89791-310-8

Authors

Y. Saab	Coordinated Science Laboratory and Department of Electrical and Computer Engineering, University of Illinois at Urbana-Champaign, 1101 W. Springfield Avenue, Urbana, Illinois
V. Rao	Coordinated Science Laboratory and Department of Electrical and Computer Engineering, University of Illinois at Urbana-Champaign, 1101 W. Springfield Avenue, Urbana, Illinois

Sponsors

SIGDA: ACM Special Interest Group on Design Automation
IEEE-CS\TCDA : TC Design Automation

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 3, Citation Count: 5

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

ABSTRACT

In the design of application specific integrated circuits (ASIC), it is often required to partition a logic complex into smaller subcomplexes satisfying a number of constraints. Due to the complexity of the problem, most existing algorithms try to optimize on only one constraint. In this paper, we use the concept of evolution to derive a partitioning algorithm capable of handling a number of constraints. Our algorithm provides a uniform multi-way partitioning scheme, obtains good partitions, and has a fast execution time.

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	S. Goto and T. Matsuda, "Partiaioning, Assignment and Placement," Layou~ Design and ~'erfficarion (Ed. by T. Ohtsuki), North-Holland, 1986.
	2	Y. Perl and M. Snir, "Circuit Parlilioning witlh Size and Connection Constraints," Networks, vol. 13, pp. 365-375, 1983.
	3	B.W. Kernighan and S. Lin, "An Efficient Heuristic Procedure for Partitioning Graphs," Bell System Technical Journal, vol. 49, pp. 291-307, February 1970,
	4	Earl E. Barnes, " An Algorithm for Par~titioning the Nodes of a Graph," 1BAI Technical Report RC8 6 90 , 1981.
	5	T. Bui, S. Chaudhuri, T. Leighton, and M. Sipser, "Graph Bisection Algorithm with Good Average Case Behavior," Proceedings of the 25eh 1gEE Symposium on Foundations of Comptaing, pp. 181-192, 1984.
	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	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]
	8	B. Dunham, D. Fridshal, R. Fridshal, J. H. North, "Design by Natural Selection," Synthese, D. Reidel Publicalion Company, Dordrecht-Holland, pp. 254-259, 1963.
	9	R.-M. Kling , P. Banerjee, ESP: a new standard cell placement package using simulated evolution, Proceedings of the 24th ACM/IEEE conference on Design automation, p.60-66, June 28-July 01, 1987, Miami Beach, Florida, United States [doi>10.1145/37888.37897]
	10	J .P. Cohoon and W. D. Paris, "Genetic Placement," Proceedings of the 1gEE international Conference On Computer-Aided Design, pp. 422-425, 198~5.
	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

CITED BY 5

	Ralph-Michael Kling , Prithviraj Banerjee, Optimization by simulated evolution with applications to standard cell placement, Proceedings of the 27th ACM/IEEE conference on Design automation, p.20-25, June 24-27, 1990, Orlando, Florida, United States
	Youssef G. Saab , Vasant B. Rao, Stochastic evolution: a fast effective heuristic for some generic layout problems, Proceedings of the 27th ACM/IEEE conference on Design automation, p.26-31, June 24-27, 1990, Orlando, Florida, United States
	James Cohoon , John Karro , Jens Lienig, Evolutionary algorithms for the physical design of VLSI circuits, Advances in evolutionary computing: theory and applications, Springer-Verlag New York, Inc., New York, NY, 2003
	H. -J. Wunderlich , M. Herzog , J. Figueras , J. A. Carrasco , A. Calderon, Synthesis of I/sub DDQ/-testable circuits: integrating built-in current sensors, Proceedings of the 1995 European conference on Design and Test, p.573, March 06-09, 1995
	Wei-Lun Hung , Yuan Xie , Narayanan Vijaykrishnan , Mahmut Kandemir , Mary Jane Irwin, Total Power Optimization for Combinational Logic Using Genetic Algorithms, Journal of Signal Processing Systems, v.58 n.2, p.145-160, February 2010