An efficient algorithm for finding double-vertex dominators in circuit graphs
2005 (English)In: DESIGN, AUTOMATION AND TEST IN EUROPE CONFERENCE AND EXHIBITION, VOLS 1 AND 2, PROCEEDINGS / [ed] Wehn, N; Benini, L, 2005, 406-411 p.Conference paper (Refereed)
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.
Place, publisher, year, edition, pages
2005. 406-411 p.
, Design Automation and Test in Europe Conference and Expo, ISSN 1530-1591
Computer and Information Science
IdentifiersURN: urn:nbn:se:kth:diva-42780DOI: 10.1109/DATE.2005.53ISI: 000228086900075ScopusID: 2-s2.0-33646927539ISBN: 0-7695-2288-2OAI: oai:DiVA.org:kth-42780DiVA: diva2:447742
Design, Automation and Test in Europe Conference and Exhibition (DATE 05) Location: Munich, GERMANY Date: MAR 07-11, 2005
QC 201110132011-10-132011-10-122012-11-01Bibliographically approved