Cited By
View all- Mangassarian HVeneris ASmith DSafarpour SPhillips JHu AGraeb H(2011)Debugging with dominanceProceedings of the International Conference on Computer-Aided Design10.5555/2132325.2132460(587-594)Online publication date: 7-Nov-2011
A fast algorithm for finding common multiple-vertex dominators in circuit graphs
Authors: 
René Krenz, Elena DubrovaAuthors Info & Claims
Pages 529 - 532
Abstract
In 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 Boolean functions and power optimization. State of the art algorithms compute single-vertex dominators in linear time. However, the rare appearance of single-vertex dominators in circuit graphs requires the investigation of a broader type of dominators and the development of algorithms to compute them. We show that our new technique is faster and computes more common multiple-vertex dominators than existing techniques.
References
[1]
R. Krenz and E. Dubrova, "Probabilistic equivalence checking of large circuits," in Proceedings of Swedish System-on-Chip Conference, (Eskilstuna, Sweden), April 2003.
[2]
K. P. Parker and E. J. McCluskey, "Probabilistic treatment of general combinational networks," Transactions on Computers, pp. 668--670, June 1975.
[3]
J. Costa, J. Monteiro, and S. Devadas, "Switching activity estimation using limited depth reconvergent path analysis," in Proceedings of the International Symposium on Low Power Electronics and Design, pp. 184--189, 1997.
[4]
J. P. Marques-Silva and K. A. Sakallah, "GRASP: a search algorithm for propositional satisfiability," IEEE Transactions on Computers, vol. 48, no. 5, pp. 506--521, 1999.
[5]
T. Kirkland and M. R. Mercer, "A topological search algorithm for ATPG," in IEEE Design Automation Conf., pp. 502--508, 1987.
[6]
J. Cong and Y. Ding, "An optimal technology mapping algorithm for delay optimization in lookup-table based FPGA designs," in ICCAD, pp. 48--53, 1992.
[7]
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.
[8]
R. Gupta, "Generalized dominators and post-dominators," in Proceedings of 19th Annual ACM Symposium on Principles of Programming Languages, pp. 246--257, 1992.
[9]
E. S. Lowry and C. W. Medlock, "Object code optimization," Communications of the ACM, vol. 12, pp. 13--22, January 1969.
[10]
P. W. Purdom and E. F. Moore, "Immediate predominators in a directed graph," Communications of the ACM, vol. 15, pp. 777--778, August 1972.
[11]
A. V. Aho and J. D. Ullman, The Theory of Parsing, Translating, and Compiling, Vol. II. Englewood Cliffs, NJ: Prentice-Hall, 1972.
[12]
R. E. Tarjan, "Finding dominators in directed graphs," SIAM Journal on Computing, vol. 3, no. 1, pp. 62--89, 1974.
[13]
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.
[14]
D. Harel, "A linear time algorithm for finding dominators flow graphs and related problems," Annual ACM Symposium on theory of computing (STOC), vol. 17, no. 1, pp. 185--194, 1985.
[15]
A. L. Buchsbaum, H. Kaplan, A. Rogers, and J. R. Westbrook, "A new, simpler linear-time dominators algorithm," ACM Transactions on Programming Languages and Systems, vol. 20, no. 6, pp. 1265--1296, 1998.
[16]
S. Alstrup, D. Harel, J. Clausen, and M. Thorup, "Dominators in linear time," SIAM Journal on Computing, vol. 28, no. 6, pp. 2117--2132, 1999.
[17]
E. Dubrova, M. Teslenko, and A. Martinelli, "On relation between non-disjoint decomposition and multiple-vertex dominators," in Proceedings of International Symposium on Circuits and Systems 2004, 2004.
[18]
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.
[19]
S. Alstrup, P. W. Lauridsen, and M. Thorup, "Generalized dominators for structured programs," Algorithmica, vol. 27, no. 3, pp. 244--253, 2000.
- A fast algorithm for finding common multiple-vertex dominators in circuit graphs
Recommendations
A fast algorithm for finding dominators in a flowgraph
A fast algorithm for finding dominators in a flowgraph is presented. The algorithm uses depth-first search and an efficient method of computing functions defined on paths in trees. A simple implementation of the algorithm runs in O(m log n) time, where m ...
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 ...
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 ...
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%
Upcoming Conference
ASPDAC '25
- Sponsor:
- sigda
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 199Total Downloads
- Downloads (Last 12 months)5
- Downloads (Last 6 weeks)2
Reflects downloads up to 22 Nov 2024
Other Metrics
Citations
Cited By
View all- Mangassarian HVeneris ASmith DSafarpour SPhillips JHu AGraeb H(2011)Debugging with dominanceProceedings of the International Conference on Computer-Aided Design10.5555/2132325.2132460(587-594)Online publication date: 7-Nov-2011
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