loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Design, Automation and Test in Europe (DATE'05) Volume 1
An Efficient Algorithm for Finding Double-Vertex Dominators in Circuit Graphs
Munich, Germany
March 07-March 11
ISBN: 0-7695-2288-2
Maxim Teslenko, Royal Institute of Technology, IMIT/KTH, Sweden
Elena Dubrova, Royal Institute of Technology, IMIT/KTH, Sweden
Graph 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 analysis, statistical timing analysis, cut point selection in equivalence checking, etc. Single-vertex dominators are too rare in circuit graphs to handle re-converging paths in a practical way. This paper addresses the problem of finding double-vertex dominators, which occur more frequently. First, we introduce a data structure, called dominator chain, which allows representing all possible O(n^2) double-vertex dominators of a given vertex in O(n) space, where n is the number of vertices of the circuit graph. Dominator chains can be efficiently manipulated, e.g. it takes constant time to look-up whether a given pair of vertices is a double-vertex dominator. Second, we present an efficient algorithm for finding double-vertex dominators. The experimental results show that the presented algorithm is an order of magnitude faster than existing algorithms for finding double-vertex dominators. Thus, it is suitable for running in an incremental manner during logic synthesis.
Citation:
Maxim Teslenko, Elena Dubrova, "An Efficient Algorithm for Finding Double-Vertex Dominators in Circuit Graphs," date, vol. 1, pp.406-411, Design, Automation and Test in Europe (DATE'05) Volume 1, 2005
Usage of this product signifies your acceptance of the Terms of Use.