An Efficient Static Trace Simplification Technique for Debugging Concurrent Programs Conference Paper uri icon

abstract

  • One of the major difficulties in debugging concurrent programs is that the programmer usually experiences frequent thread context switches, which perplexes the reasoning process. This problem can be alleviated by trace simplification techniques, which produce the same computation process but with much fewer number of context switches. The state of the art trace simplification technique takes a dynamic approach and does not scale well to large traces, hampering its practicality. We present a static trace simplification approach, SimTrace, that dramatically improves the efficiency of trace simplification through reasoning about the computation equivalence of traces offline. By constructing a dependence graph model of events, our trace simplification algorithm scales linearly to the trace size and quadratic to the number of nodes in the dependence graph. Underpinned by a trace equivalence theorem, we guarantee that the results generated by SimTrace are sound and no dynamic program re-execution is required to validate the trace equivalence. Our experiments show that SimTrace scales well to traces with more than 1M events, making it attractive to practical use. 2011 Springer-Verlag Berlin Heidelberg.

published proceedings

  • Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

author list (cited authors)

  • Huang, J., & Zhang, C.

citation count

  • 8

complete list of authors

  • Huang, Jeff||Zhang, Charles

publication date

  • September 2011