Computer Science Department
School of Computer Science, Carnegie Mellon University


Parallel LBA: Conherence-based Parallel Monitoring
of Multithreaded Applications

Evangelos Vlachos, Michelle Goodstein,
Michael Kozuch*, Shimin Chen*, Babak Falsafi**
Phillip B. Gibbons*, Todd C. Mowry***, Olatunji Ruwase

March 2009


Keywords: Dynamic program monitoring, deterministic replay, dataflow analysis, log-based architectures

As multicore processors become more prevalent, application performance increasingly depends upon parallel execution through multithreading. However, existing software correctness-checking techniques have focused on single-threaded applications and need to be extended to support the efficient monitoring of multithreaded applications. In particular, software lifeguards (online tools for monitoring software correctness) must be able to reason about the relative ordering of memory accesses and other events issued from different threads. Acquiring such event orderings is not trivial, and prior work has resorted to serializing application threads on a single core to manage concurrency. This paper solves the multithreaded application monitoring problem using a combination of techniques. First, it leverages cache coherence to record the interleaving of memory accesses from different threads. Second, it extends the framework to comprehend "logical races"–events involving at least two threads where the relative order may be important for particular lifeguards, but where not all events are memory accesses (e.g., a race between a malloc() and a memory write). Finally, it uses special thread-switch messages to ensure proper synchronization with cores when application threads are swapped out. Our approach enables software lifeguards not only (i) to reason efficiently about the state of the application, but also (ii) to avoid costly synchronization among lifeguard threads that are maintaining shared shadow state. Existing single-threaded lifeguards may be ported to this framework easily because the semantics of event delivery are preserved. Simulation results for a parallel dynamic information flow lifeguard on a 16 core CMP indicate that our monitoring is at least 5X faster than existing techniques.

18 pages

*Intel Research Pittsburgh
**Ecole Polytechnique Federale de Lausanne
***Carnegie Mellon University and Intel Research Pittsburgh

Return to: SCS Technical Report Collection
School of Computer Science

This page maintained by