A fast algorithm for finding common multiple-vertex dominators in circuit graphs

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: José C. Costa , José C. Monteiro , Srinivas Devadas, Switching activity estimation using limited depth reconvergent path analysis, Proceedings of the 1997 international symposium on Low power electronics and design, p.184-189, August 18-20, 1997, Monterey, California, United States [doi>10.1145/263272.263323]
• 4: João P. Marques-Silva , Karem A. Sakallah, GRASP: A Search Algorithm for Propositional Satisfiability, IEEE Transactions on Computers, v.48 n.5, p.506-521, May 1999 [doi>10.1109/12.769433]
• 5: T. Kirkland , M. R. Mercer, A topological search algorithm for ATPG, Proceedings of the 24th ACM/IEEE conference on Design automation, p.502-508, June 28-July 01, 1987, Miami Beach, Florida, United States [doi>10.1145/37888.37963]
• 6: Jason Cong , Yuzheng Ding, An optimal technology mapping algorithm for delay optimization in lookup-table based FPGA designs, Proceedings of the 1992 IEEE/ACM international conference on Computer-aided design, p.48-53, November 1992, Santa Clara, California, United States
• 7: Stephen Alstrup , Jens Clausen , Kristian Jørgensen, An OV* E algorithm for finding immediate multiple-vertex dominators, Information Processing Letters, v.59 n.1, p.9-11, July 8, 1996 [doi>10.1016/0020-0190(96)00085-3]
• 8: Rajiv Gupta, Generalized dominators and post-dominators, Proceedings of the 19th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.246-257, January 19-22, 1992, Albuquerque, New Mexico, United States [doi>10.1145/143165.143216]
• 9: Edward S. Lowry , C. W. Medlock, Object code optimization, Communications of the ACM, v.12 n.1, p.13-22, Jan. 1969 [doi>10.1145/362835.362838]
• 10: Paul W. Purdom, Jr. , Edward F. Moore, Immediate predominators in a directed graph [H], Communications of the ACM, v.15 n.8, p.777-778, Aug. 1972 [doi>10.1145/361532.361566]
• 11: Alfred V. Aho , Jeffrey D. Ullman, The Theory of Parsing, Translation, and Compiling, Prentice Hall Professional Technical Reference, 1972
• 12: R. E. Tarjan, "Finding dominators in directed graphs," SIAM Journal on Computing, vol. 3, no. 1, pp. 62--89, 1974.
• 13: Thomas Lengauer , Robert Endre Tarjan, A fast algorithm for finding dominators in a flowgraph, ACM Transactions on Programming Languages and Systems (TOPLAS), v.1 n.1, p.121-141, July 1979 [doi>10.1145/357062.357071]
• 14: D Harel, A linear algorithm for finding dominators in flow graphs and related problems, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.185-194, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22166]
• 15: Adam L. Buchsbaum , Haim Kaplan , Anne Rogers , Jeffery R. Westbrook, A new, simpler linear-time dominators algorithm, ACM Transactions on Programming Languages and Systems (TOPLAS), v.20 n.6, p.1265-1296, Nov. 1998 [doi>10.1145/295656.295663]
• 16: Stephen Alstrup , Dov Harel , Peter W. Lauridsen , Mikkel Thorup, Dominators in Linear Time, SIAM Journal on Computing, v.28 n.6, p.2117-2132, Dec. 1999 [doi>10.1137/S0097539797317263]
• 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: René Krenz , Elena Dubrova , Andreas Kuehlmann, Fast Algorithm for Computing Spectral Transforms of Boolean and Multiple-Valued Functions on Circuit Representation, Proceedings of the 33rd International Symposium on Multiple-Valued Logic, p.334, May 16-19, 2003
• 19: S. Alstrup, P. W. Lauridsen, and M. Thorup, "Generalized dominators for structured programs," Algorithmica, vol. 27, no. 3, pp. 244--253, 2000.