Improved Boolean function hashing based on multiple-vertex dominators
Authors: 
René Krenz, Elena DubrovaAuthors Info & Claims
Pages 573 - 578
Abstract
The growing complexity of today's system designs requires fast and robust verification methods. Existing BDD, SAT or ATPG-based techniques do not provide sufficient solutions for many verification instances. Boolean function hashing is a probabilistic verification approach which can complement existing formal methods in a number of applications such as equivalence checking, biased random simulation, power analysis and power optimization. The proposed hashing technique is based on the arithmetic transform, which maps a Boolean function onto a probabilistic hash value for a given input assignment. The presented algorithm uses multiple-vertex dominators in circuit graphs to progressively simplify intermediate hashing steps. The experimental results on benchmark circuits demonstrate the robustness of our approach.
References
[1]
V. Pratt, "Anatomy of the Pentium Bug," in TAP-SOFT'95: Theory and Practice of Software Development (P. D. Mosses, M. Nielsen, and M. I. Schwartzbach, eds.), no. 915, pp. 97--107, Springer Verlag, 1995.
[2]
R. Krenz, E. Dubrova, and A. Kuehlmann, "Fast algorithm for computing spectral transforms of Boolean and multiple-valued functions on circuit representation," in Proceedings of the International Symposium on Multiple-Valued Logic, (Tokyo, Japan), pp. 334--339, May 2003.
[3]
E. S. Lowry and C. W. Medlock, "Object code optimization," Communications of the ACM, vol. 12, pp. 13--22, January 1969.
[4]
T. Lengauer and R. E. Tarjan, "A fast algorithm for finding dominators in a flowgraph," Transactions of Programming Languages and Systems, vol. 1, pp. 121--141, July 1979.
[5]
M. Blum, A. K. Chandra, and M. N. Wegman, "Equivalence of free Boolean graphs can be decided probabilistically in polynomial time," Information Processing Letters, vol. 10, pp. 80--82, March 1980.
[6]
J. Jain, J. Bitner, D. S. Fussell, and J. A. Abraham, "Probabilistic verification of Boolean functions," Formal Methods in System Design, vol. 1, pp. 63--117, 1992.
[7]
W. J. Townsend, M. A. Thornton, R. Drechsler, and D. M. Miller, "Computing Walsh, arithmetics and Reed-Muller spectral decision diagrams using graph transformations," in Proceedings of GLVLSI'02, pp. 178--183, April 2002.
[8]
K. P. Parker and E. J. McCluskey, "Probabilistic treatment of general combinational networks," Transactions on Computers, pp. 668--670, June 1975.
[9]
R. Motwani and P. Raghavan, Randomized Algorithms. London, England: Cambridge University Press, 1995.
[10]
A. Ghosh, S. Devadas, K. Keutzer, and J. White, "Estimation of average switching activity in combinational and sequential circuits," in Proceedings of the 29th ACM/IEEE Design Automation Conference, (Anaheim, CA), pp. 253--259, June 1992.
[11]
P. W. Purdom and E. F. Moore, "Immediate predominators in a directed graph," Communications of the ACM, vol. 15, pp. 777--778, August 1972.
[12]
A. V. Aho and J. D. Ullman, The Theory of Parsing, Translating, and Compiling, Vol. II. Englewood Cliffs, NJ: Prentice-Hall, 1972.
[13]
S. Alstrup, J. Clausen, and K. Jorgensen, "An o(|v|*|*|e|) algorithm for finding immediate multiple-vertex dominators," Information Processing Letters, vol. 59, no. 1, pp. 9--11, 1996.
[14]
R. Gupta, "Generalized dominators and postdominators," in Proceedings of 19th Annual ACM Symposium on Principles of Programming Languages, pp. 246--257, 1992.
[15]
S. Alstrup, P. W. Lauridsen, and M. Thorup, "Generalized dominators for structured programs," Algorithmica, vol. 27, no. 3, pp. 244--253, 2000.
[16]
E. M. Clarke, K. L. McMillan, X. Zhao, M. Fujita, and J. C.-Y. Yang, "Spectral transforms for large Boolean functions with application to technology mapping," in Proceedings of the 30th ACM/IEEE Design Automation Conference, (Dallas, TX), pp. 54--60, June 1993.
[17]
R. Bahar, E. Frohm, C. Gaona, G. Hachtel, E. Macii, A. Pardo, and F. Somenzi, "Algebraic decision diagrams and their applications," in Digest of Technical Papers of the IEEE/ACM International Conference on Computer-Aided Design, (San Jose, CA), pp. 188--191, IEEE, November 1993.
[18]
F. Somenzi, CUDD: CU Decision Diagram Package, Release 2.3.1. University of Colorado at Boulder, 2001.
Recommendations
A fast algorithm for finding common multiple-vertex dominators in circuit graphs
ASP-DAC '05: Proceedings of the 2005 Asia and South Pacific Design Automation ConferenceIn this paper we present a fast algorithm for computing common multiple-vertex dominators in circuit graphs. Dominators are widely used in CAD applications such as satisfiability checking, equivalence checking, ATPG, technology mapping, decomposition of ...
Generalized dominators and post-dominators
POPL '92: Proceedings of the 19th ACM SIGPLAN-SIGACT symposium on Principles of programming languagesThe notion of dominators is generalized to include multiple-vertex dominators in addition to single-vertex dominators. A multiple-vertex dominator of a vertex is a group of vertices that collectively dominate the vertex. Existing algorithms compute ...
An Efficient Algorithm for Finding Double-Vertex Dominators in Circuit Graphs
DATE '05: Proceedings of the conference on Design, Automation and Test in Europe - Volume 1Graph dominators provide a general mechanism for identifying re-converging paths in circuits. This is useful in a number of CAD applications including computation of signal probabilities for test generation, switching activities for power and noise ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Copyright © 2005 ACM.
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]
Sponsors
- IEEE SSCS Shanghai Chapter
- IEEE Beijing Section
- SIGDA: ACM Special Interest Group on Design Automation
- Fudan University
- IEEE CAS
- Chinese Institute of Electronics
- Shanghai IC Industry Association
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 18 January 2005
Check for updates
Qualifiers
- Article
Conference
ASPDAC05
Sponsor:
Acceptance Rates
Overall Acceptance Rate 466 of 1,454 submissions, 32%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 109Total Downloads
- Downloads (Last 12 months)1
- Downloads (Last 6 weeks)0
Reflects downloads up to 05 Mar 2025
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in