Ordering Traces Logically to Identify Lateness in Message Passing Programs

Katherine E. Isaacs, Todd Gamblin, Abhinav Bhatele, Martin Schulz, Bernd Hamann, Peer Timo Bremer

Research output: Contribution to journalArticlepeer-review

10 Scopus citations


Event traces are valuable for understanding the behavior of parallel programs. However, automatically analyzing a large parallel trace is difficult, especially without a specific objective. We aid this endeavor by extracting a trace's logical structure, an ordering of trace events derived from happened-before relationships, while taking into account developer intent. Using this structure, we can calculate an operation's delay relative to its peers on other processes. The logical structure also serves as a platform for comparing and clustering processes as well as highlighting communication patterns in a trace visualization. We present an algorithm for determining this idealized logical structure from traces of message passing programs, and we develop metrics to quantify delays and differences among processes. We implement our techniques in Ravel, a parallel trace visualization tool that displays both logical and physical timelines. Rather than showing the duration of each operation, we display where delays begin and end, and how they propagate. We apply our approach to the traces of several message passing applications, demonstrating the accuracy of our extracted structure and its utility in analyzing these codes.

Original languageEnglish (US)
Article number7072533
Pages (from-to)829-840
Number of pages12
JournalIEEE Transactions on Parallel and Distributed Systems
Issue number3
StatePublished - Mar 1 2016


  • Trace analysis
  • performance

ASJC Scopus subject areas

  • Signal Processing
  • Hardware and Architecture
  • Computational Theory and Mathematics


Dive into the research topics of 'Ordering Traces Logically to Identify Lateness in Message Passing Programs'. Together they form a unique fingerprint.

Cite this