skip to main content
10.1145/1118299.1118364acmconferencesArticle/Chapter ViewAbstractPublication PagesaspdacConference Proceedingsconference-collections
Article

An anytime symmetry detection algorithm for ROBDDs

Published: 24 January 2006 Publication History

Abstract

Detecting symmetries is crucial to logic synthesis, technology mapping, detecting function equivalence under unknown input correspondence, and ROBDD minimization. State-of-the-art is represented by Mishchenko's algorithm. In this paper we present an efficient anytime algorithm for detecting symmetries in Boolean functions represented as ROBDDs, that output pairs of symmetric variables until a prescribed time bound is exceeded. The algorithm is complete in that given sufficient time it is guaranteed to find all symmetric pairs. The complexity of this algorithm is in O(n4 + n|G| + |G|3) where n is the number of variables and |G| the number of nodes in the ROBDD, and it is thus competitive with Mishchenko's O (|G|3) algorithm in the worst-case since n ≪ |G|. However, our algorithm performs significantly better because the anytime approach only requires lightweight data structure support and it offers unique opportunities for optimization.

References

[1]
C. E. Shannon, "A Symbolic Analysis of Relay and Switching Circuits," AIEE Trans., vol. 57, pp. 713--723, 1938.
[2]
B. G. Kim and D. L. Dietmeyer, "Multilevel Logic Synthesis of Symmetric Switching Functions," IEEE Trans. Computer-Aided Design, vol. 10, no. 4, pp. 436--446, 1991.
[3]
C. R. Edward and S. L. Hurst, "A Digital Synthesis Procedure Under Function Symmetries and Mapping Methods," IEEE Trans. Comput., vol. C-27, no. 11, pp. 985--997, 1978.
[4]
F. Mailhot and G. De Micheli, "Technology Mapping Using Boolean Matching and Don't Care Sets," in European Design Automation Conference, 1990, pp, 212--216.
[5]
Y. T. Lai, S. Sastry, and M. Pedram, "Boolean Matching Using Binary Decision Diagrams with Applications to Logic Synthesis and Verification," in International Conference on Computer-Aided Design, 1992, pp. 452--458.
[6]
S. Panda, F. Somenzi, and B. F. Plessier, "Symmetry Detection and Dynamic Variable Ordering of Decision Diagrams," in International Conference on Computer-Aided Design, 1994, pp. 628--631.
[7]
C. Scholl, D. Möller, P. Molitor, and R. Drechsler, "BDD Minimization Using Symmetries," IEEE Trans. Computer-Aided Design, vol. 18, no. 2, pp. 81--100, 1999.
[8]
J. Mohnke and S. Malik, "Permutation and Phase Independent Boolean Comparison," INTEGRATION, The VLSI Journal, vol. 16, pp, 109--129, 1993.
[9]
D. I. Cheng and M. Marek Sadowska, "Verifying Equivalence of Functions with Unknown Input Correspondence," in European Design Automation Conference, 1993, pp. 272--277.
[10]
V. N. Kravets and K. A. Sakallah, "Generalized Symmetries in Boolean Functions," in International Conference on Computer-Aided Design, 2000, pp. 526--532.
[11]
G. D. Hachtel and F. Somenzi, Logic Synthesis and Verification Algorithms. Kluwer Academic Publishers, 1996.
[12]
D. Möller, J. Mohnke, and M. Weber, "Detection of Symmetry of Boolean functions Represented by ROBDDs," in International Conference on Computer-Aided Design, 1993, pp. 680--684.
[13]
R. E. Bryant, "Graph-based Algorithms for Boolean Function Manipulation," IEEE Trans. Comput., vol. 35, no. 8, pp. 677--691, 1986.
[14]
A. Mishchenko, "Fast Computation of Symmetries in Boolean Functions," IEEE Trans. Computer-Aided Design, vol. 22, no. 11, pp. 1588--1593, 2003.
[15]
R. Rudell, "Dynamic Variable Ordering for Ordered Binary Decision Diagrams," in International Conference on Computer-Aided Design, 1993, pp. 42--47.
[16]
D. Bochmann and B. Steinbach, Logikenwurf mit XBOOLE: Algorithmen und Programme. Berlin: Verlag Technik GmBH, 1996.
[17]
C. C. Tsai and M. Marek Sadowska, "Generalized Reed-Muller Forms as a Tool to Detect Symmetries," IEEE Trans. Comput., vol. 45, no. 1, pp. 33--40, 1996.
[18]
R. W. Floyd, "Algorithm 97: Shortest Path," Commun. ACM, vol. 5, no. 6, p. 345, 1962.
[19]
S. Warshall, "A Theorem on Boolean Matrices," Journal of the ACM, vol. 9, no. 1, pp. 11--12, 1962.
[20]
F. Somenzi, "CUDD Package, Release 2.4.0." {Online}. Available: http://vlsi.colorado.edu/~fabio/CUDD/cuddIntro.html
[21]
A. Mishchenko, "Extra Library of DD Procedures." {Online}. Available: http://www.ee.pdx.edu/~alanmi/research/extra.htm
[22]
"Lgsynth93 Benchmark Set." {Online}. Available: http://www.bddportal.org/benchmarks/
[23]
S. Minato, "Zero-Suppressed BDDs for Set Manipulation in Combinatorial Problems," in Design Automation Conference, 1993, pp. 272--277.

Cited By

View all
  • (2007)Symmetric Item Set Mining Method Using Zero-suppressed BDDs and Application to Biological DataTransactions of the Japanese Society for Artificial Intelligence10.1527/tjsai.22.15622(156-164)Online publication date: 2007
  • (2006)Symmetric item set mining based on zero-suppressed BDDsProceedings of the 9th international conference on Discovery Science10.1007/11893318_35(321-326)Online publication date: 7-Oct-2006

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
ASP-DAC '06: Proceedings of the 2006 Asia and South Pacific Design Automation Conference
January 2006
998 pages
ISBN:0780394518

Sponsors

  • IEEE Circuits and Systems Society
  • SIGDA: ACM Special Interest Group on Design Automation
  • IEICE ESS: Institute of Electronics, Information and Communication Engineers, Engineering Sciences Society
  • IPSJ SIG-SLDM: Information Processing Society of Japan, SIG System LSI Design Methodology

Publisher

IEEE Press

Publication History

Published: 24 January 2006

Permissions

Request permissions for this article.

Check for updates

Qualifiers

  • Article

Acceptance Rates

Overall Acceptance Rate 466 of 1,454 submissions, 32%

Upcoming Conference

ASPDAC '25

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)1
  • Downloads (Last 6 weeks)0
Reflects downloads up to 07 Jan 2025

Other Metrics

Citations

Cited By

View all
  • (2007)Symmetric Item Set Mining Method Using Zero-suppressed BDDs and Application to Biological DataTransactions of the Japanese Society for Artificial Intelligence10.1527/tjsai.22.15622(156-164)Online publication date: 2007
  • (2006)Symmetric item set mining based on zero-suppressed BDDsProceedings of the 9th international conference on Discovery Science10.1007/11893318_35(321-326)Online publication date: 7-Oct-2006

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