Article

Free access

An evolution-based approach to partitioning ASIC systems

Authors:

Y. Saab,

V. RaoAuthors Info & Claims

DAC '89: Proceedings of the 26th ACM/IEEE Design Automation Conference

Pages 767 - 770

https://doi.org/10.1145/74382.74525

Published: 01 June 1989 Publication History

PDF eReader

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

[1]

S. Goto and T. Matsuda, "Partiaioning, Assignment and Placement," Layou~ Design and ~'erfficarion (Ed. by T. Ohtsuki), North-Holland, 1986.

Google Scholar

[2]

Y. Perl and M. Snir, "Circuit Parlilioning witlh Size and Connection Constraints," Networks, vol. 13, pp. 365-375, 1983.

Google Scholar

[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,

Crossref

Google Scholar

[4]

Earl E. Barnes, " An Algorithm for Par~titioning the Nodes of a Graph," 1BAI Technical Report RC8 6 90, 1981.

Google Scholar

[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.

Google Scholar

[6]

C.M. Fiduccia and R. M. Ma't~hejrses, "A Linear- Time Heuristics for Improving Network Partitions," Proceedings of the 19th Design Auzorna~ion Conference, pp. 175-181, January 1982.

Digital Library

Google Scholar

[7]

D. Schweikert and B, Kernighan, "A Proper Model for the Partitioning of Electrical Circuits," Proceedings of zhe 9th Design Au~orna~ion Workshop, pp. 57-62, 1972.

Digital Library

Google Scholar

[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.

Google Scholar

[9]

Ralph-Michael Kling and Prithviraj Banerjee, "ESP: A New Standard Cell Placement Package Using Simulated Evolution," Proceedings of the 24th Design Automation Conference, June 1987.

Digital Library

Google Scholar

[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.

Google Scholar

[11]

M. Garey and D. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman and Company, New York, pp. 126, 1979.

Digital Library

Google Scholar

Cited By

View all

Andre RSchlag SSchulz CTakadama K(2018)Memetic multilevel hypergraph partitioningProceedings of the Genetic and Evolutionary Computation Conference10.1145/3205455.3205475(347-354)Online publication date: 2-Jul-2018
https://dl.acm.org/doi/10.1145/3205455.3205475
Shakoor RHassan MRaheem AWu Y(2016)Wake effect modeling: A review of wind farm layout optimization using Jensen׳s modelRenewable and Sustainable Energy Reviews10.1016/j.rser.2015.12.22958(1048-1059)Online publication date: May-2016
https://doi.org/10.1016/j.rser.2015.12.229
Khan SRehman S(2013)Iterative non-deterministic algorithms in on-shore wind farm design: A brief surveyRenewable and Sustainable Energy Reviews10.1016/j.rser.2012.11.04019(370-384)Online publication date: Mar-2013
https://doi.org/10.1016/j.rser.2012.11.040
Show More Cited By

Index Terms

An evolution-based approach to partitioning ASIC systems

Recommendations

Genetic multiway partitioning
VLSID '95: Proceedings of the 8th International Conference on VLSI Design

This research investigates a new software tool for Genetic Partitioning. The Genetic Algorithm is used to perform the partitioning with a significant improvement in result quality. Furthermore, it can optimize a cost function with multiple objectives ...
Corolla based circuit partitioning and resynthesis
DAC '90: Proceedings of the 27th ACM/IEEE Design Automation Conference

This paper introduces a circuit partitioning method based on analysis of reconvergent fanout. We consider a DAG model for a circuit. We define a corolla as a set of overlapping reconvergent fanout regions. We partition the DAG into a set of non-...
Hierarchical partitioning for field-programmable systems
ICCAD '97: Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design

This paper presents a new recursive bipartitioning algorithm for a hierarchical field-programmable system. It draws new insights into relating the quality of the bipartitioning algorithm to circuit structures by the use of the partitioning tree (Hagen ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

DAC '89: Proceedings of the 26th ACM/IEEE Design Automation Conference

June 1989

839 pages

ISBN:0897913108

DOI:10.1145/74382

Chairman:
Donald E. Thomas
Carnegie Mellon Univ., Pittsburgh, PA

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 June 1989

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

DAC89

Sponsor:

IEEE-CS\TCDA
SIGDA

DAC89: The 26th ACM/IEEE-CS Design Automation Conference

June 25 - 28, 1989

Nevada, Las Vegas, USA

Acceptance Rates

DAC '89 Paper Acceptance Rate 156 of 465 submissions, 34%;

Overall Acceptance Rate 1,770 of 5,499 submissions, 32%

Upcoming Conference

DAC '25

Sponsor:
sigda

62nd ACM/IEEE Design Automation Conference

June 22 - 26, 2025

San Francisco , CA , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

29
Total Citations
View Citations
237
Total Downloads

Downloads (Last 12 months)39
Downloads (Last 6 weeks)8

Reflects downloads up to 16 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Andre RSchlag SSchulz CTakadama K(2018)Memetic multilevel hypergraph partitioningProceedings of the Genetic and Evolutionary Computation Conference10.1145/3205455.3205475(347-354)Online publication date: 2-Jul-2018
https://dl.acm.org/doi/10.1145/3205455.3205475
Shakoor RHassan MRaheem AWu Y(2016)Wake effect modeling: A review of wind farm layout optimization using Jensen׳s modelRenewable and Sustainable Energy Reviews10.1016/j.rser.2015.12.22958(1048-1059)Online publication date: May-2016
https://doi.org/10.1016/j.rser.2015.12.229
Khan SRehman S(2013)Iterative non-deterministic algorithms in on-shore wind farm design: A brief surveyRenewable and Sustainable Energy Reviews10.1016/j.rser.2012.11.04019(370-384)Online publication date: Mar-2013
https://doi.org/10.1016/j.rser.2012.11.040
Khan SRehman S(2010)Computational intelligence techniques for placement of wind turbines: A brief plan of research in Saudi Arabian perspective2010 IEEE International Energy Conference10.1109/ENERGYCON.2010.5771736(519-523)Online publication date: Dec-2010
https://doi.org/10.1109/ENERGYCON.2010.5771736
Hung WXie YVijaykrishnan NKandemir MIrwin M(2010)Total Power Optimization for Combinational Logic Using Genetic AlgorithmsJournal of Signal Processing Systems10.1007/s11265-009-0338-358:2(145-160)Online publication date: 1-Feb-2010
https://dl.acm.org/doi/10.1007/s11265-009-0338-3
Kling RBanerjee P(2006)Empirical and theoretical studies of the simulated evolution method applied to standard cell placementIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/43.8892610:10(1303-1315)Online publication date: 1-Nov-2006
https://dl.acm.org/doi/10.1109/43.88926
Lee YWu A(2006)A performance and routability-driven router for FPGAs considering path delaysIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/43.57383216:2(179-185)Online publication date: 1-Nov-2006
https://dl.acm.org/doi/10.1109/43.573832
Mao CHu Y(2006)Analysis of convergence properties of a stochastic evolution algorithmIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/43.50394915:7(826-831)Online publication date: 1-Nov-2006
https://dl.acm.org/doi/10.1109/43.503949
Ly TMowchenko J(2006)Applying simulated evolution to high level synthesisIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/43.21500212:3(389-409)Online publication date: 1-Nov-2006
https://dl.acm.org/doi/10.1109/43.215002
Cheng CWei Y(2006)An improved two-way partitioning algorithm with stable performance [VLSI]IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/43.10350010:12(1502-1511)Online publication date: 1-Nov-2006
https://dl.acm.org/doi/10.1109/43.103500
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Genetic multiway partitioning

Corolla based circuit partitioning and resynthesis

Hierarchical partitioning for field-programmable systems