Paper Info
Title
Accelerating schedule space exploration of multi-threaded programs with GPUs.
Abstract
Given an input that can trigger a concurrency bug, only a subset of possible thread schedules satisfying certain constraints can actually cause such a bug to manifest. Recent proposals on controlled randomization of thread schedules with concrete guarantees on bug detection probabilities have opened promising avenues in this direction. However, to boost the bug detection probability, these techniques typically require a significant number of schedules to be explored. As a result, it is, in general, beneficial to accelerate the schedule space exploration of the multi-threaded programs. In this paper, we introduce Simultaneous Interleaving Exploration with Controlled Sequencing (SINECOSEQ), a generic framework that leverages the high-performance graphics processing units (GPUs) to significantly accelerate schedule space navigation of general-purpose multi-threaded programs. The SINE framework accepts POSIX compliant multi-threaded programs, instruments them to intercept all shared memory accesses, and automatically generates CUDA (Compute Unified Device Architecture) compliant code that navigates the schedule space of the input multi-threaded program on an NVIDIA GPU. Each GPU thread typically explores one schedule of the input program. The COSEQ framework decides how the schedule space is navigated by architecting the schedules on the fly. While it is straightforward to construct and navigate a different schedule on each GPU thread, the performance of the resulting technique can be very poor due to disparate pieces of codes executed by each GPU thread leading to full control divergence. In this paper, we demonstrate one application of SINECOSEQ by proposing a new GPU-friendly scheduler for accelerated concurrency testing (ACT), which is inspired by the recently proposed randomized scheduler of probabilistic concurrency testing (PCT). Compared to the state-of-the-art parallel PCT (PPCT) implementation on a twelve-core CPU, our proposal implemented on an NVIDIA Kepler K20c GPU card significantly speeds up schedule space exploration for eight multi-threaded applications and kernels drawn from the Phoenix and the PARSEC suites.
Year
DOI
Venue
2016
10.1109/MEMCOD.2016.7797754
MEMOCODE
Keywords
Field
DocType
schedule space exploration acceleration,bug detection probabilities,simultaneous interleaving exploration with controlled sequencing,SINECOSEQ,high-performance graphics processing units,general-purpose multithreaded programs,CUDA,SINE framework,POSIX compliant multithreaded programs,compute unified device architecture,COSEQ framework,GPU thread,GPU-friendly scheduler,accelerated concurrency testing,ACT,probabilistic concurrency testing,parallel PCT,PPCT,twelve-core CPU,NVIDIA Kepler K20c GPU card,PARSEC suites
Shared memory,Instruction set,Concurrency,CUDA,Computer science,Software bug,Parallel computing,Real-time computing,Thread (computing),Schedule,Concurrent computing
Conference
ISBN
Citations 
PageRank 
978-1-5090-2792-7
0
0.34
References 
Authors
10
4
Name
Order
Citations
PageRank
Prakhar Banga100.34
Atul Pai200.34
Subhajit Roy34510.84
Mainak Chaudhuri430018.86