Nothing Special   »   [go: up one dir, main page]

skip to main content
10.5555/2485288.2485481acmconferencesArticle/Chapter ViewAbstractPublication PagesdateConference Proceedingsconference-collections
research-article

A semi-canonical form for sequential AIGs

Published: 18 March 2013 Publication History

Abstract

In numerous EDA flows, time-consuming computations are repeatedly applied to sequential circuits. This motivates developing methods to determine what circuits have been processed already by a tool. This paper proposes an algorithm for semi-canonical labeling of nodes in a sequential AIG, allowing problems or sub-problems solved by an EDA tool to be cached with their computed results. This can speed up the tool when applied to designs with isomorphic components or design suites exhibiting substantial structural similarity.

References

[1]
F. A. Aloul, A. Ramani, I. L. Markov, and K. A. Sakallah, "Solving difficult SAT instances in the presence of symmetry", IEEE TCAD'03, vol. 22(9), pp. 1117--1137.
[2]
A. Biere, AIGER format. http://fmv.jku.at/aiger/
[3]
Berkeley Logic Synthesis and Verification Group. http://www-cad.eecs.berkeley.edu/~alanmi/abc
[4]
R. Brayton and A. Mishchenko, "ABC: An academic industrial-strength verification tool", Proc. CAV'10, LNCS 6174, pp. 24--40.
[5]
D. Chai and A. Kuehlmann, "A compositional approach to symmetry detection in circuits", Proc. IWLS'06, pp. 228--234.
[6]
D. Chai and A. Kuehlmann, "Symmetry detection for large multioutput functions", Proc. IWLS'07, pp. 305--311.
[7]
K.-H. Chang, I. L. Markov and V. Bertacco, "Post-placement rewiring by exhaustive search for functional symmetries", ACM TODAES, vol. 12(3), #32, August 2007.
[8]
P. Chauhan, P. Dasgupta, and P. P. Chakraborty, "Exploiting graph isomorphism for BDD compaction and faster simulation", Proc. VLSI'99, pp. 224--229.
[9]
P. T. Darga, K. A. Sakallah, and I. L. Markov. "Faster symmetry discovery using sparsity of symmetries". Proc. DAC'08, pp.149--154.
[10]
N. Een and A. Biere, "Effective preprocessing in SAT through variable and clause elimination", Proc. SAT'05.
[11]
N. Een, A. Mishchenko and R. Brayton, "Efficient implementation of property-directed reachability", Proc. FMCAD'11.
[12]
H. Katebi, K. A. Sakallah, and I. L. Markov, "Symmetry and satisfiability: An update", Proc. SAT'10, pp. 113--127.
[13]
H. Katebi, K. A. Sakallah, and I. L. Markov, "Conflict anticipation in the search for graph automorphisms", Proc. Int'l Conf. on Logic for Programming, Artificial Intelligence and Reasoning (LPAR), Merida, Venezuela, 2012.
[14]
B. D. McKay, "Computing automorphisms and canonical labeling of graphs", Combinatorial Mathematics, Lecture Notes in Mathematics, 686, pp. 223--232 (Springer-Verlag, Berlin, 1978).
[15]
V. N. Kravets and K. A. Sakallah, "Constructive library-aware synthesis using symmetries". Proc. DATE'00, pp. 208--213.
[16]
A. Mishchenko, "Fast computation of symmetries in Boolean functions", IEEE TCAD'03, vol. 22(11), pp.1588--1593.
[17]
S. Panda, F. Somenzi, and B. Plessier, "Symmetry detection and dynamic variable ordering of decision diagrams". Proc. ICCAD'94.
[18]
G. Wang, A. Kuehlmann, and A. Sangiovanni-Vincentelli, "Structural detection of symmetries in Boolean functions", Proc. ICCD'03, pp. 498--503.
[19]
J. S. Zhang, A. Mishchenko, R. Brayton, and M. Chrzanowska-Jeske, "Symmetry detection for large boolean functions using circuit representation, simulation, and satisfiability", DAC '06, 510--515.

Cited By

View all
  • (2014)Self-Verification as the Key Technology for Next Generation Electronic SystemsProceedings of the 27th Symposium on Integrated Circuits and Systems Design10.1145/2660540.2660983(1-4)Online publication date: 1-Sep-2014

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences
DATE '13: Proceedings of the Conference on Design, Automation and Test in Europe
March 2013
1944 pages
ISBN:9781450321532

Sponsors

Publisher

EDA Consortium

San Jose, CA, United States

Publication History

Published: 18 March 2013

Check for updates

Qualifiers

  • Research-article

Conference

DATE 13
Sponsor:
  • EDAA
  • EDAC
  • SIGDA
  • The Russian Academy of Sciences
DATE 13: Design, Automation and Test in Europe
March 18 - 22, 2013
Grenoble, France

Acceptance Rates

Overall Acceptance Rate 518 of 1,794 submissions, 29%

Upcoming Conference

DATE '25
Design, Automation and Test in Europe
March 31 - April 2, 2025
Lyon , France

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)2
  • Downloads (Last 6 weeks)1
Reflects downloads up to 19 Nov 2024

Other Metrics

Citations

Cited By

View all
  • (2014)Self-Verification as the Key Technology for Next Generation Electronic SystemsProceedings of the 27th Symposium on Integrated Circuits and Systems Design10.1145/2660540.2660983(1-4)Online publication date: 1-Sep-2014

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media