Information Technology Reference
In-Depth Information
thread0
thread1
sync
sync
Time
rd addr2
rd addr1
wr addr2
RACE!
sync
sync
Fig. 1.
An example of a data race, on address
addr2
, between
thread0
and
thread1
. Figure shows
the synchronization and memory instructions in the two threads. Synchronization instructions
define the beginning and end of
epochs
. Shaded boxes mark epochs in the instruction stream.
2.1
Data Race Detection Algorithms
There are two classes of data race detection algorithms: lockset-based [4,6] and happened-
before-based [3, 5]. Lockset-based schemes track the set of locks held by threads while
accessing a shared variable, and report a data race when the accesses are not protected
by common locks. Happened-before (H-B) algorithm is based on Lamport's happened-
before relation [10]. In this scheme, memory accesses between synchronizations are
grouped into
epochs
. Epochs belonging to different threads are
concurrent
only if their
execution times overlap. H-B schemes compare memory accesses in concurrent epochs
and report a data race condition if they contain accesses to the same memory location
with at least one of the access being a write. Lockset-based schemes do not track syn-
chronizations other than locks, whereas, H-B scheme covers all types of synchroniza-
tions and hence can potentially detect more data races. For this reason, we use the H-B
algorithm as the basis for our design. However, it is equally possible to use other data
race detection algorithms, such as lockset, as the basis for GUARD.
2.2 Runtime Support for Data Race Detection
There exists a large body of work for identifying data races offline, either through static
analysis [11] or by post-mortem analysis [12]. Static analysis based approaches ana-
lyze the source code to detect data race conditions and experience high false positive
rates due to their conservative nature. Post-mortem methods that collect and analyze the
execution trace of applications have significant storage overhead and cannot identify po-
tential security risks in real-time. Due to these drawbacks, current data race detection
techniques emphasize on runtime support.
Previous work has proposed utilizing hardware transactional memory (HTM) mech-
anism for data race detection. RaceTM [13] utilizes lightweight
debug transactions
to
detect data races with the help of the conflict detection mechanism of the HTM. How-
ever, GUARD differs from such an HTM-based data race detection. RaceTM requires
the underlying HTM support for operation, whereas, GUARD requires minimal hard-
ware support for the extraction of memory access trace. The crux of GUARD's data
race detection, the signature comparison, is performed by the general purpose GPU
cores available on-chip. However, the memory access trace extraction mechanism can
potentially be shared by several functionalities, including GUARD and HTM.
