Algorithms for compacting error traces

ABSTRACT

In this paper, we present a concept of compacting the error traces generated by pseudo-random/random simulations. The new shorter error trace not only decreases the time of user's debugging process but also reduces the simulation time required to verify the bug fixes. Two algorithms CET1 and CET2 are presented to perform the task of compacting the error trace. Both algorithms first use an efficient approach to eliminate the redundant states to generate the unique states of the error trace. Then, CET1 build the connected graph of these unique states by computing the reachable states by one cycle for each unique state, and then apply Dijkstra's shortest path algorithm to find out the shortest error trace in the connected graph. Compared with CET1, CET2 computes the reachable states by one cycle for those unique states, when they are needed in Dijkstra's shortest path algorithm to find the shortest error trace. After finding the shorter trace, the corresponding input/output test vectors are generated. The experimental results show that both algorithms can reduce the length of error traces dramatically for most cases using reasonable memory. For cases required longer CPU time to find the shortest trace, CET2 is up to 37 times faster than CET1.

REFERENCES

• 1: R. I. Bahar , E. A. Frohm , C. M. Gaona , G. D. Hachtel , E. Macii , A. Pardo , F. Somenzi, Algebric Decision Diagrams and Their Applications, Formal Methods in System Design, v.10 n.2-3, p.171-206, April -May 1997 [doi>10.1023/A:1008699807402]
• 2: Mike Benjamin , Daniel Geist , Alan Hartman , Gerard Mas , Ralph Smeets , Yaron Wolfsthal, A study in coverage-driven test generation, Proceedings of the 36th ACM/IEEE conference on Design automation, p.970-975, June 21-25, 1999, New Orleans, Louisiana, United States [doi>10.1145/309847.310108]
• 3: Randal E. Bryant, Graph-based algorithms for Boolean function manipulation, IEEE Transactions on Computers, v.35 n.8, p.677-691, Aug. 1986 [doi>10.1109/TC.1986.1676819]
• 4: E. M. Clarke , O. Grumberg , K. L. McMillan , X. Zhao, Efficient generation of counterexamples and witnesses in symbolic model checking, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.427-432, June 12-16, 1995, San Francisco, California, United States [doi>10.1145/217474.217565]
• 5: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 6: Daniel Geist , Monica Farkas , Avner Landver , Yossi Lichtenstein , Shmuel Ur , Yaron Wolfsthal, Coverage-Directed Test Generation Using Symbolic Techniques, Proceedings of the First International Conference on Formal Methods in Computer-Aided Design, p.143-158, November 06-08, 1996
• 7: Aarti Gupta , Sharad Malik , Pranav Ashar, Toward formalizing a validation methodology using simulation coverage, Proceedings of the 34th annual conference on Design automation, p.740-745, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266359]
• 8: Pei Hsin Ho , Thomas Shiple , Kevin Harer , James Kukula , Robert Damiano , Valeria Bertacco , Jerry Taylor , Jiang Long, Smart simulation using collaborative formal and simulation engines, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
• 9: HoonSang Jin , Kavita Ravi , Fabio Somenzi, Fate and Free Will in Error Traces, Proceedings of the 8th International Conference on Tools and Algorithms for the Construction and Analysis of Systems, p.445-459, April 08-12, 2002
• 10: Kenneth L. McMillan, Symbolic Model Checking, Kluwer Academic Publishers, Norwell, MA, 1993
• 11: F. Somenzi, "CUDD: CU decision diagram package - Release 1.0.4", Tech, Rep., Dept. Elect. Comput. Eng., Univ. Colorado, Boulder, Nov. 1995.