Extracting Logical Structure and Identifying Stragglers in Parallel Execution Traces

We introduce a new approach to automatically extract an idealized logical structure from a parallel execution trace. We use this structure to define intuitive metrics such as the lateness of a process involved in a parallel execution. By analyzing and illustrating traces in terms of logical steps, we leverage a developer’s understanding of the happened-before relations in a parallel program. This technique can uncover dependency chains, elucidate communication patterns, and highlight sources and propagation of delays, all of which may be obscured in a traditional trace visualization. Extracting Logical Structure The logical structure of a program is the ordering of events implied by that program. We describe the logical structure by assigning a logical step to each event. Structure extraction occurs in two phases