Abstract
With the advance of technology, the growing number of processors and increasing computational complexity of programs have raised the degree of difficulty in fully understanding the behavior of the whole program. Such an understanding is invaluable for research such as computer architecture design, program debugging and optimizations, protocol verification and testing, etc. A viable solution to the problem is to extract the program execution traces to observe the program behavior. The challenge is how to deduce meaningful structures and patterns from the massive trace information to represent program behavior in a concrete way. Parallel programs make this even more difficult because of the complex interactions between the multiple threads of executions. It is thus necessary to develop more efficient solutions capturing the complicated parallel program behaviors from the massive and seemingly unstructured execution traces. This thesis presents a new approach to deducing the parallel program behavior by processing the program execution traces to derive a trace-derived finite state machine (TD-FSM). With TD-FSM, it is possible to show the program behavior in a very concise fashion. TD-FSM can also effectively compress the execution traces to reduce the trace size for ease of storage and transportation. If coupled with a replay method, it can further reproduce execution traces that are very similar to the original traces, for such applications as performance analysis and parallel program optimization. Our evaluations show that TD-FSM can reduce the trace size by 99%, achieving a compression rate compatible with popular compression algorithms and at the same time maintaining the program behavior.