Skip to main content

PerpLE: Improving the Speed and Effectiveness of Memory Consistency Testing

Author(s): Melissaris, Themis; Markakis, Markos; Shaw, Kelly; Martonosi, Margaret

To refer to this page use:
Abstract: Even as most of today's computer systems have turned to parallelism to improve performance, their documentation often remains informal, incomplete or even incorrect regarding their memory consistency models. This leads to programmer and designer confusion and to buggy concurrent systems. Existing tools for empirical memory consistency testing rely on large numbers of iterations of simple multi-threaded litmus tests to perform conformance testing. The current approach typically employs thread synchronization at every iteration, which imposes a significant overhead and can reduce testing performance and efficiency.This paper proposes new litmus test variants called perpetual litmus tests, which allow for consistency testing without periteration synchronization. Perpetual litmus tests use arithmetic sequences in store operations to reduce the required synchronization points. We present PerpLE, a software suite that includes tools for the generation, execution, and analysis of perpetual litmus tests. We introduce an algorithm for determining the outcomes of perpetual litmus tests as well as a scalable linear heuristic algorithm. Evaluating the performance, scalability and ability of our tool to find outcomes of interest on an x86 system, we observe a wider variety of outcomes than litmus7 while experiencing runtime speedups over all litmus7 synchronization modes (8.89x over the default user mode). Compared to the default litmus7 synchronization (user) mode, PerpLE offers over four orders-of-magnitude improvement in the rate with which we detect target outcomes.
Publication Date: 2020
Citation: Melissaris, Themis, Markos Markakis, Kelly Shaw, and Margaret Martonosi. "PerpLE: Improving the Speed and Effectiveness of Memory Consistency Testing." In 53rd Annual IEEE/ACM International Symposium on Microarchitecture (MICRO) (2020): pp. 329-341. doi:10.1109/MICRO50266.2020.00037
DOI: 10.1109/MICRO50266.2020.00037
ISSN: 1072-4451
Pages: 329 - 341
Type of Material: Conference Article
Journal/Proceeding Title: 53rd Annual IEEE/ACM International Symposium on Microarchitecture (MICRO)
Version: Author's manuscript

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.