# An Efficient Algorithm for On-the-Fly Data Race Detection Using an Epoch-Based Technique

Authors: Ok-Kyoon Ha; Yong-Kee Jun
Journal: Scientific Programming
 (2015)

---

## Abstract

Data races represent the most notorious class of concurrency bugs in multithreaded programs. To detect data races precisely and efficiently during the execution of multithreaded programs, the epoch-based FastTrack technique has been employed. However, FastTrack has time and space complexities that depend on the maximum parallelism of the program to partially maintain expensive data structures, such as vector clocks. This paper presents an efficient algorithm, called iFT, that uses only the epochs of the access histories. Unlike FastTrack, our algorithm requires O
(
1
) operations to maintain an access history and locate data races, without any switching between epochs and vector clocks. We implement this algorithm on top of the Pin binary instrumentation framework and compare it with other on-the-fly detection algorithms, including FastTrack, which uses a state-of-the-art happens-before analysis algorithm. Empirical results using the PARSEC benchmark show that iFT reduces the average runtime and memory overhead to 84% and 37%, respectively, of those of FastTrack.


---

## Body

## 1. Introduction

Synchronization in parallel or multithreaded programs is an enforcing mechanism used to coordinate thread execution and manage shared data in various computational systems, including HPC (High Performance Computing). However, multithreaded programs may contain synchronization defects such as data races, which occur when two concurrent threads access a shared memory location without explicit synchronization, and at least one of them is a write. It is well known that data races are the hardest defect to handle in multithreaded programs, because of their nondeterministic interleaving of concurrent threads [1–4].Dynamic techniques for detecting data races are usually classified into postmortem methods [4, 5], which analyze traced information or replay the program after execution, and on-the-fly methods, which use one of the following techniques:happens-before analysis (like FastTrack [6], SigRace [7], Dijit+ [3], ThreadSanitizer [8], etc. [9–13]),lockset analysis (like Eraser [14]), orhybrid analysis (like VisualThread [15], Hegrind+ [16–18], MultiRace [19], AccuLock [20], RaceTrack [21], etc. [22]).The main drawback of dynamic detection techniques is the additional overhead of monitoring program execution and analyzing every conflicting memory operation. Asampling approach was introduced to solve the overhead problem of dynamic data race detection. Sampling-based techniques [23–25] can be performed efficiently when testing multithreaded programs via local thread burst-sampling [24] or a global execution time sampling strategy [23]. Although they provide significantly reduced runtime overheads, these techniques are still ineffective in detecting data races when the sampling rates are low.FastTrack is a state-of-the-art happens-before algorithm and is an improved version of the Djit+ algorithm withvector clocks (VCs) [26, 27]. This technique exploits the idea that full generality of VCs is often unnecessary for data race detection. The technique replaces heavyweight VCs with a lightweight identifier, called anepoch, that uses only the tuple of the clock value and the thread id. Epoch-based happens-before analysis decreases the runtime and memory overhead of almost all VC operations from O
(
n
) to O
(
1
) in the detection of data races, where n designates the maximum number of simultaneously active threads during an execution. However, FastTrack requires a time and space overhead of O
(
n
) for the shared read accesses to shared memory locations. Therefore, the overhead problem still exists, because the small fraction of shared read accesses make it difficult to dynamically analyze programs with a large number of concurrent threads [13].This paper presents an efficient algorithm, callediFT, that uses only epochs to detect data races. Thus, iFT represents an improvement over the FastTrack method. Our algorithm maintains only two epochs of earlier read accesses to shared memory locations, instead of the full VCs, using theleft-of-relation [11]. Thus, it requires only O
(
1
) runtime and memory overhead to maintain the access history and locate data races, without any switching between epochs and VCs, unlike FastTrack. Furthermore, the technique is guaranteed to report a subset of data races detected by FastTrack.We implement the new algorithm on top of the Pin instrumentation framework [28], which uses a just-in-time (JIT) compiler to recompile target program binaries for dynamic instrumentation. To compare the accuracy of iFT for on-the-fly data race detection, we also implement two other detection algorithms, Djit+ and FastTrack, on top of the same framework, and employ the same optimized VC primitives. We compare the efficiency of iFT with Djit+ and FastTrack, which use a happens-before analysis to detect data races. The experimental results on C/C++ benchmarks using Pthreads show that our algorithm reduces the runtime and memory overheads compared with the other algorithms, while soundly detecting similar data races to FastTrack.In summary, the contributions of our work are as follows:(i)
iFT provides a significant improvement in efficiency, exhibiting an O
(
1
) runtime and memory overhead for each access history, whereas FastTrack requires O
(
n
) VC operations.
(ii)
iFT matches the well-established precision of FastTrack, although it uses only two epochs instead of the full VCs for earlier read accesses to shared memory locations.
(iii)
iFT reduces the average runtime and memory overhead to 84% and 37%, respectively, of those of FastTrack.The remainder of this paper is organized as follows. Section2 discusses important concepts of happens-before analysis with VCs, and Section 3 introduces the FastTrack algorithm and its limitations. We present our improved algorithm in Section 4 and evaluate it empirically in Section 5 by comparing with existing techniques for data race detection. We introduce some related work in Section 6 and conclude our argument in Section 7.


## 2. Background

On-the-fly methods of detecting data races typically use VCs to precisely analyze the happens-before relation. This section presents important rules for allocating VCs to the concurrent thread segments introduced in this paper and describes how VCs represent the happens-before relation during the execution of multithreaded programs.


### 2.1. Execution of Multithreaded Programs

In this work, we consider multithreaded programs using the POSIX thread standard (Pthread) as a model of concurrent threads. Pthread is widely used not only on C/C++ applications, but also on many Unix-like operating systems (Linux, Solaris, Mac OS, FreeBSD, etc.), because it provides various APIs and libraries for creating, manipulating, and synchronizing threads.In a multithreaded program, a block of threadT that is partially serially executed is represented as athread segment, denoted by t. Thus, a thread can be represented as a set of thread segments, denoted by T
=
t
1
,
t
2
,
…
,
t
n (n
≥
1). A thread segment t is delimited bythread operations that can take one of the following forms:(i)
i
n
i
t
(
t
) models the creation of a thread segment t and the start of the execution of thread T.
(ii)
f
o
r
k
(
t
,
u
) models the creation of a thread segment u from the current thread segment t and the start of a new thread segment t
′ on the same thread T.
(iii)
j
o
i
n
(
t
,
u
) models the termination of a thread segment u and the creation of a new thread segment t
′ on the same thread T from the current thread segment t.A thread segment t contains a finite sequence σ that consists of at least one event e, denoted by σ
=
e
1
,
e
2
,
…
,
e
n. σ
t denotes the sequence of events generated on a thread segment t. An event takes one of the following forms:(i)
Access Events
r
e
a
d
(
x
) and w
r
i
t
e
(
x
). The former models the reading of a shared memory location x, and the latter simulates the updating of x.
(ii)
Mutual Exclusion Events
a
c
q
(
t
,
l
) and r
e
l
(
t
,
l
). The former models the acquisition of a lock l to enter a critical section. The latter models the release of a lock l to leave a critical section and the start of a new thread segment t
′ on the same thread T.
(iii)
Condition Variable Synchronization Events
w
a
i
t
(
t
,
v
) and s
i
g
(
u
,
v
). The former models the wait for condition variable v until another thread wakes v and the subsequent start of a new thread segment t
′ on the same thread T. The latter models the wake-up of a thread waiting on v and the start of a new thread segment u
′ on the same thread U.
(iv)
Barrier
Event  b
a
r
r
i
e
r
(
t
,
b
). This models the waiting of multiple threads until the number of waiting threads is b and the start of a new thread segment on each of the waiting threads.In this work, we consider the above thread operations and events assynchronization primitives rather than access events.


### 2.2. VC-Based Happens-Before Analysis

Happens-before analysis uses a representation of Lamport’s happens-before relation [27] to determine the logical concurrency between two thread segments. According to this relation, if a thread segment t must happen at an earlier time than another thread segment u, t
happens before
u or σ
t
happens before
σ
u, denoted by t
→
h
b
u or σ
t
→
h
b
σ
u. If neither t
→
h
b
u nor u
→
h
b
t is satisfied, we say that t isconcurrent with
u or σ
t isconcurrent with
σ
u, denoted by t
∥
u or σ
t
∥
σ
u.VCs are widely used to analyze the happens-before relation→
h
b, because they can inform the execution order of thread segments and the synchronization order of thread operations and events. A vector clock V
C:Tid
→
Nat records a clock value c for each thread while the program is executing. Thus, thread segment t maintains a VC C
t
=
〈
c
1
,
…
,
c
n
〉, which has n entries if the maximum number of active threads in the execution of a multithreaded program is n. The VC of each thread segment is partially ordered (⊑) pointwise, with a minimum element 〈
0
,
…
,
0
〉 and associated synchronization primitives that define pointwise maximums. For instance, the entry C
t
[
u
] for any thread segment u stores the latest clock value of u that happened before the current synchronization primitive of t.During program execution, the VCs of the thread segments are maintained according to the following rules:(i)
init(t)
∀
i
:
C
t
[
i
]
⟵
0;
C
t
[
t
]
⟵
1;
(ii)
fork(t
,
u)
I
n
i
t
(
u
);
∀
i
:
C
u
[
i
]
⟵
m
a
x
{
C
t
[
i
]
,
C
u
[
i
]
};
C
t
[
t
]
⟵
C
t
[
t
]
+
1;
(iii)
join(t
,
u)
∀
i
:
C
t
[
i
]
⟵
m
a
x
{
C
t
[
i
]
,
C
u
[
i
]
};
C
u
[
u
]
⟵
C
u
[
u
]
+
1;
(iv)
acq(t
,
l)
∀
i
:
C
t
[
i
]
⟵
m
a
x
{
C
t
[
i
]
,
C
l
[
i
]
},
whereC
l is a vector clock for each lock l;
(v)
rel(t
,
l)
C
t
⟵
C
t
[
t
]
+
1;
∀
i
:
C
l
[
i
]
⟵
m
a
x
{
C
t
[
i
]
,
C
l
[
i
]
}
.The other synchronization events,w
a
i
t
(
t
,
v
), s
i
g
(
u
,
v
), and b
a
r
r
i
e
r
(
t
,
b
), can be modeled with the j
o
i
n
(
) operation.Figure1 represents a multithread execution with synchronization primitives as a directed acyclic graph, called a Partial Order Execution Graph (POEG) [10, 11]. In the POEG, a vertex is either a thread operation or a synchronization event, and an arc represents a logical thread segment started by the synchronization primitives. The dashed lines indicate the synchronization order in the execution of the program. The events r and w, represented by small disks on the arcs, denote read and write events at a shared memory location, respectively. The numbers attached to each thread segment and event name indicate an observed order, and the VCs are allocated for each thread segment by the above rules.Figure 1
An example of multithread execution with synchronization primitives.Using the VCs of each thread segment, we simply analyze the happens-before relation between any two thread segments. If the clock value of a thread segmentt is less than or equal to the corresponding clock value of another thread segment u, we can conclude that t happens before u. Otherwise, t is concurrent with u. Formally,(1)
t
→
h
b
u
≡
σ
t
→
h
b
σ
u
≡
C
t
t
≤
C
u
t
t
∥
u
≡
σ
t
∥
σ
u
≡
C
t
t
>
C
u
t
∨
C
t
u
<
C
u
u
.Obviously, C
t
[
t
]
≤
C
u
[
t
] means that thread segment u was synchronized from an earlier thread segment t by one of the synchronization primitives. Then, C
t is partially ordered with C
u, denoted by C
t
⊑
C
u, and is never involved in any race. Finally, the happens-before analysis locates a data race during the execution of a multithreaded program whenever any two events on two concurrent thread segments access a shared memory location, and at least one of the events is a write.Definition 1.
Given two access eventse
t and e
u to a shared memory location from two distinct thread segments t and u, respectively, if the two events are not synchronized (i.e., neither C
t
⊑
C
u nor C
u
⊑
C
t) and at least one of the events is a write, there exists a data race between e
t and e
u.For example, in Figure1, consider two events r
3 and w
4 on two different thread segments t
3 and u
3, respectively. The two events constitute a data race, because neither C
t
3
⊑
C
u
3 nor C
u
3
⊑
C
t
3 is satisfied, as C
t
3
[
t
]
=
3
>
C
u
3
[
t
]
=
2 and C
t
3
[
u
]
=
0
<
C
u
3
[
u
]
=
3, and therefore t
3
∥
u
3.


## 2.1. Execution of Multithreaded Programs

In this work, we consider multithreaded programs using the POSIX thread standard (Pthread) as a model of concurrent threads. Pthread is widely used not only on C/C++ applications, but also on many Unix-like operating systems (Linux, Solaris, Mac OS, FreeBSD, etc.), because it provides various APIs and libraries for creating, manipulating, and synchronizing threads.In a multithreaded program, a block of threadT that is partially serially executed is represented as athread segment, denoted by t. Thus, a thread can be represented as a set of thread segments, denoted by T
=
t
1
,
t
2
,
…
,
t
n (n
≥
1). A thread segment t is delimited bythread operations that can take one of the following forms:(i)
i
n
i
t
(
t
) models the creation of a thread segment t and the start of the execution of thread T.
(ii)
f
o
r
k
(
t
,
u
) models the creation of a thread segment u from the current thread segment t and the start of a new thread segment t
′ on the same thread T.
(iii)
j
o
i
n
(
t
,
u
) models the termination of a thread segment u and the creation of a new thread segment t
′ on the same thread T from the current thread segment t.A thread segment t contains a finite sequence σ that consists of at least one event e, denoted by σ
=
e
1
,
e
2
,
…
,
e
n. σ
t denotes the sequence of events generated on a thread segment t. An event takes one of the following forms:(i)
Access Events
r
e
a
d
(
x
) and w
r
i
t
e
(
x
). The former models the reading of a shared memory location x, and the latter simulates the updating of x.
(ii)
Mutual Exclusion Events
a
c
q
(
t
,
l
) and r
e
l
(
t
,
l
). The former models the acquisition of a lock l to enter a critical section. The latter models the release of a lock l to leave a critical section and the start of a new thread segment t
′ on the same thread T.
(iii)
Condition Variable Synchronization Events
w
a
i
t
(
t
,
v
) and s
i
g
(
u
,
v
). The former models the wait for condition variable v until another thread wakes v and the subsequent start of a new thread segment t
′ on the same thread T. The latter models the wake-up of a thread waiting on v and the start of a new thread segment u
′ on the same thread U.
(iv)
Barrier
Event  b
a
r
r
i
e
r
(
t
,
b
). This models the waiting of multiple threads until the number of waiting threads is b and the start of a new thread segment on each of the waiting threads.In this work, we consider the above thread operations and events assynchronization primitives rather than access events.


## 2.2. VC-Based Happens-Before Analysis

Happens-before analysis uses a representation of Lamport’s happens-before relation [27] to determine the logical concurrency between two thread segments. According to this relation, if a thread segment t must happen at an earlier time than another thread segment u, t
happens before
u or σ
t
happens before
σ
u, denoted by t
→
h
b
u or σ
t
→
h
b
σ
u. If neither t
→
h
b
u nor u
→
h
b
t is satisfied, we say that t isconcurrent with
u or σ
t isconcurrent with
σ
u, denoted by t
∥
u or σ
t
∥
σ
u.VCs are widely used to analyze the happens-before relation→
h
b, because they can inform the execution order of thread segments and the synchronization order of thread operations and events. A vector clock V
C:Tid
→
Nat records a clock value c for each thread while the program is executing. Thus, thread segment t maintains a VC C
t
=
〈
c
1
,
…
,
c
n
〉, which has n entries if the maximum number of active threads in the execution of a multithreaded program is n. The VC of each thread segment is partially ordered (⊑) pointwise, with a minimum element 〈
0
,
…
,
0
〉 and associated synchronization primitives that define pointwise maximums. For instance, the entry C
t
[
u
] for any thread segment u stores the latest clock value of u that happened before the current synchronization primitive of t.During program execution, the VCs of the thread segments are maintained according to the following rules:(i)
init(t)
∀
i
:
C
t
[
i
]
⟵
0;
C
t
[
t
]
⟵
1;
(ii)
fork(t
,
u)
I
n
i
t
(
u
);
∀
i
:
C
u
[
i
]
⟵
m
a
x
{
C
t
[
i
]
,
C
u
[
i
]
};
C
t
[
t
]
⟵
C
t
[
t
]
+
1;
(iii)
join(t
,
u)
∀
i
:
C
t
[
i
]
⟵
m
a
x
{
C
t
[
i
]
,
C
u
[
i
]
};
C
u
[
u
]
⟵
C
u
[
u
]
+
1;
(iv)
acq(t
,
l)
∀
i
:
C
t
[
i
]
⟵
m
a
x
{
C
t
[
i
]
,
C
l
[
i
]
},
whereC
l is a vector clock for each lock l;
(v)
rel(t
,
l)
C
t
⟵
C
t
[
t
]
+
1;
∀
i
:
C
l
[
i
]
⟵
m
a
x
{
C
t
[
i
]
,
C
l
[
i
]
}
.The other synchronization events,w
a
i
t
(
t
,
v
), s
i
g
(
u
,
v
), and b
a
r
r
i
e
r
(
t
,
b
), can be modeled with the j
o
i
n
(
) operation.Figure1 represents a multithread execution with synchronization primitives as a directed acyclic graph, called a Partial Order Execution Graph (POEG) [10, 11]. In the POEG, a vertex is either a thread operation or a synchronization event, and an arc represents a logical thread segment started by the synchronization primitives. The dashed lines indicate the synchronization order in the execution of the program. The events r and w, represented by small disks on the arcs, denote read and write events at a shared memory location, respectively. The numbers attached to each thread segment and event name indicate an observed order, and the VCs are allocated for each thread segment by the above rules.Figure 1
An example of multithread execution with synchronization primitives.Using the VCs of each thread segment, we simply analyze the happens-before relation between any two thread segments. If the clock value of a thread segmentt is less than or equal to the corresponding clock value of another thread segment u, we can conclude that t happens before u. Otherwise, t is concurrent with u. Formally,(1)
t
→
h
b
u
≡
σ
t
→
h
b
σ
u
≡
C
t
t
≤
C
u
t
t
∥
u
≡
σ
t
∥
σ
u
≡
C
t
t
>
C
u
t
∨
C
t
u
<
C
u
u
.Obviously, C
t
[
t
]
≤
C
u
[
t
] means that thread segment u was synchronized from an earlier thread segment t by one of the synchronization primitives. Then, C
t is partially ordered with C
u, denoted by C
t
⊑
C
u, and is never involved in any race. Finally, the happens-before analysis locates a data race during the execution of a multithreaded program whenever any two events on two concurrent thread segments access a shared memory location, and at least one of the events is a write.Definition 1.
Given two access eventse
t and e
u to a shared memory location from two distinct thread segments t and u, respectively, if the two events are not synchronized (i.e., neither C
t
⊑
C
u nor C
u
⊑
C
t) and at least one of the events is a write, there exists a data race between e
t and e
u.For example, in Figure1, consider two events r
3 and w
4 on two different thread segments t
3 and u
3, respectively. The two events constitute a data race, because neither C
t
3
⊑
C
u
3 nor C
u
3
⊑
C
t
3 is satisfied, as C
t
3
[
t
]
=
3
>
C
u
3
[
t
]
=
2 and C
t
3
[
u
]
=
0
<
C
u
3
[
u
]
=
3, and therefore t
3
∥
u
3.


## 3. FastTrack Algorithm

VC-based happens-before techniques, such as Djit+ [3], obviously require O
(
n
) space to maintain the VCs for each thread segment and access history and also require O
(
n
) time for VC operations (e.g., join, copy, and comparison).FastTrack [6], which improves on Djit+, exploits the insight that the full generality of VCs is often unnecessary for data race detection. The key ideas behind this insight are as follows: (1) all writes to a shared memory location x are totally ordered by a happens-before analysis, which assumes no data races have been detected on x so far, and (2) writing to x could potentially conflict with the last read of x performed by any other thread, although reads are not totally ordered, even in race-free programs. By exploiting these results, FastTrack replaces heavyweight VCs with a lightweight identifier for a thread segment, called anepoch, using only the tuple of clock value c
(
≡
C
t
[
t
]
) and thread id t, denoted by c
@
t. Thus, FastTrack reduces the runtime and space overhead of almost all VC operations from O
(
n
) to O
(
1
) in the detection of data races.For a shared memory locationx, the FastTrack algorithm defines an access history using two entries:(i)
R
x: it records a VC for all concurrent read events or an epoch for the last read event of x.
(ii)
W
x: it records only an epoch for the last write event to x.FastTrack reports data races by analyzing →
h
b and simply maintains epochs or VCs by updating the access histories. For the algorithm, some notions are used to analyze →
h
b using the epoch. The function E
(
t
) is shorthand for c
@
t, and E
(
t
)
⪯
V
C denotes that the epoch E
(
t
) happens before a vector clock V
C, where E
(
t
)
⪯
V
C if and only if c
≤
V
C
[
t
].When a new evente
i occurs on thread segment t, the algorithm for reporting data races and maintaining each entry is as follows.Upon a Read Event of
x
by Thread
t
(1)
If the epoch of the currente
i is the same as that of R
x, R
x
=
E
(
t
), the algorithm takes no action.
(2)
IfR
x
≠
E
(
t
), then the algorithm checks W
x
⪯
C
t to report a data race between an earlier write event and e
i.
(3)
IfR
x
⪯
C
t is satisfied, only E
(
t
) is kept in R
x. Otherwise, C
t
[
t
] is updated to R
x, which maintains a full VC.Upon a Write Event to
x
by Thread
t
(1)
If the epoch of the currente
i is the same as that of W
x, W
x
=
E
(
t
), then the algorithm takes no action.
(2)
IfW
x
≠
E
(
t
), then the algorithm checks W
x
⪯
C
t to report a data race between an earlier write event and e
i.
(3)
If there exists only one epoch inR
x, then the algorithm checks R
x
⪯
C
t to report a data race between an earlier read event and e
i. Otherwise, the algorithm checks R
x
⊑
C
t for a full VC maintained in R
x.
(4)
The previous epoch or VC is removed fromR
x, and E
(
t
) is inserted into W
x.Table1 explains how the FastTrack algorithm reports data races and manages the access history during the execution of the program shown in Figure 1. Initially, W
x starts from ⊥
e, indicating that the shared memory location x has not yet been written. When the first read event r
1 occurs on thread segment t
2, the epoch 2
@
t
i
d is recorded in R
x instead of a full VC, where t
i
d indicates the thread id for t
2. When the second read r
2 on thread segment u
1 accesses x, r
2 shares x with the first read event r
1, because t
2
∥
u
1, where we say that x is in aRead Shared state. In this state, as read may consist of either one or more data races with a later write event, the VCs of all shared reads of x are kept in R
x. Thus, R
x switches to a VC representation 〈
2,1
,
0
,
…
〉 to record the clocks of the last reads by the two thread segments in Table 1. With this adaptive switching between epochs and VCs in R
x, FastTrack greatly reduces the overhead of the O
(
n
) VC operations.Table 1
Access history states for detecting data races in Figure1 using the Fa
stTrack algorithm.
e
i
R
x
W
x
Races
r
1
2@t
i
d
⊥
e
r
2
2,1
,
0
,
…
⊥
e
r
3
3,1
,
0
,
…
⊥
e
w
4
⊥
e
3
@
u
i
d
r
3
-
w
4
r
5
1@v
i
d
3
@
u
i
d
w
4
-
r
5
w
6
⊥
e
6
@
t
i
d
w
4
-
w
6, r
5
-
w
6When read eventr
3 occurs on t
3, C
t
[
t
]
=
3 is directly updated in the corresponding entry of R
x, although R
x maintains a VC for the Read Shared state. Thus, the updating takes O
(
1
) time. A data race {
r
3
-
w
4
} is reported because Definition 1 is satisfied (i.e., neither R
x
⊑
C
u
3 nor C
u
3
⊑
R
x is true) when a write event to x occurs. The VC of prior read events in R
x is removed by resetting R
x to ⊥
e, and the epoch for w
4, 3
@
u
i
d, is stored in W
x. When a read of x occurs on v
1, only the epoch of r
5 is kept in R
x, because the read event is not shared with any others, and a data race {
w
4
-
r
5
} is reported. Finally, three concurrent events, w
4, r
5, and w
6, give rise to two data races, {
w
4
-
w
6, r
5
-
w
6
}, because E
(
u
3
)
⪯
C
t
6 and E
(
v
1
)
⪯
C
t
6 are not satisfied.A common problem with using VCs for happens-before analysis is the space and time overhead, which depends on the number of threads in the multithreaded programs, whereas the FastTrack algorithm provides a significant performance improvement over the lockset analysis by utilizing the lightweight epoch clock. Moreover, it suggests the design of a hybrid technique with both precision and efficiency, such as AccuLock [20]. However, there is further room for improvement, because the algorithm requires O
(
n
) VC operations to guarantee no loss of precision when shared data enters the Read Shared state, such as r
2 and r
3 in Figure 1. Therefore, the overhead problem still exists, because the shared read accesses make it difficult to dynamically analyze programs with a large number of concurrent threads.


## 4. Efficient Data Race Detection

FastTrack precisely reports data races with significantly improved performance, because epochs require only a constant space and a constant time for almost all VC operations. However, the algorithm still needs VC operations whenever a shared memory location has shared read events on concurrent thread segments. As this situation makes it impossible to dynamically analyze programs with a large number of concurrent threads [13], the overhead problem potentially exists, with the space overhead being more critical than the time overhead. Thus, we efficiently improve the FastTrack algorithm to reduce this overhead problem.Our improved FastTrack (iFT) algorithm reports data races in a constant amount of time and space, even in the worst case, because it maintains only two epochs instead of full VCs for R
x using theleft-of-relation. The notion of the left-of-relation was originally suggested by Mellor-Crummey [11]. Mellor-Crummey’s technique maintains two concurrent read events in an access history to detect data races with a write event. Techniques based on the left-of-relation guarantee that a program is free of data races, although it maintains only two read events in each access history, because it locates at least one data race (if any exist). However, Mellor-Crummey’s technique does not support synchronization primitives other than fork/join operations, such as thread locking and wait-signals. Moreover, the left-of-relation does not apply to VC-based detectors, because VCs cannot analyze the logical position of thread segments, unlike Mellor-Crummey’s OS labeling [11].We simply define a left-of-relation that is a partial ordering of two concurrent thread segmentst
i and t
j for two distinct events e
i on t
i and e
j on t
j in an execution graph, such as the POEG of Figure 1, and the events are not related to e
i
⪯
e
j. To apply the left-of-relation to the iFT algorithm, we use a breadth value b instead of the thread id T
i
d of the original FastTrack algorithm. The breadth value b is produced by performing a left-to-right preorder numbering or anEnglish Order numbering of the EH labeling scheme [29] and is used to identify the position of a current thread considering its sibling threads. If a thread segment t
i precedes another thread segment t
j and t
i
∥
t
j in an execution of a multithreaded program, b
i for t
i is less than b
j for t
j.Thus, an epochE
(
t
i
) of thread segment t
i is redefined as the tuple of clock value c
i and breadth value b
i, denoted by c
i
@
b
i. Now, the left-of-relation between any two thread segments is simply analyzed by comparing their breadth values from each epoch.Definition 2.
Given two read eventse
i and e
j to a shared memory location on two concurrent thread segments t
i and t
j, respectively, if b
i for E
(
t
i
) is less than b
j for E
(
t
j
), one says that e
i isleft of
e
j, denoted by e
i
⋞
e
j. Formally,(2)
e
i
⋞
e
j
=
T
e
i
=
T
e
j
=
R
e
a
d
∧
t
i
∥
t
j
∧
b
i
<
b
j
,where T
(
e
i
) represents the event type (read or write) of e
i. By applying the left-of-relation, we employ theleftmost event, denoted by e
l, andrightmost event, denoted by e
r, concepts to maintain only two concurrent events in R
x. We use R
l
x and R
r
x to denote the leftmost event and rightmost event, respectively, in R
x. If the current event e
i satisfies e
i
⋞
e
l
⋞
e
r, e
i is the leftmost event. This event is recorded in R
l
x instead of e
l, where the prior event e
l always satisfies the left-of-relation with e
r in R
r
x; therefore, e
l
⋞
e
r. Similarly, the current event e
i is the rightmost event and is recorded in R
r
x instead of e
r, if it satisfies e
l
⋞
e
r
⋞
e
i.We now provide a detailed description of howiFT locates three kinds of data races for concurrent events:read-write races,write-write races, andwrite-read races.Read-Write Races. Detection is possible because a write event to a shared memory location x can conflict with prior read events of x performed by any other thread. To detect read-write races, we consider two read states: (
1
) Exclusive state, where a read event of x is performed exclusively on a thread segment, and (
2
) Read Shared state, where x has read events that are shared by two or more concurrent thread segments. In the Exclusive state, because read events of x occur on the same thread, they are totally ordered, and the epoch of the last read event is recorded in R
x. Read events of x that are shared by multiple threads are unordered in a read-only manner, and each read event may consist of a data race with a later write event. Thus, if x is in the Read Shared state, two epochs of the two concurrent read events are recorded in R
x by the left-of-relation.UsingR
x, which maintains only two epochs instead of a full VC, iFT detects data races as well as FastTrack, because it locates one or two of the read-write data races.Lemma 3.
If data races exist between earlier reads and a current write eventw, iFT locates one or two of those located by FastTrack.Proof.
Two distinct shared read events towardx are kept in R
l
x and R
r
x by the left-of-relation. Since R
l
x
∥
R
r
x, we guarantee the following: (1)
IfR
l
x
→
h
b
w and R
r
x
∥
w, then iFT reports a data race between R
r
x and w, because R
l
x
⪯
w, and neither R
r
x
⊑
w nor w
⊑
R
r
x is satisfied.
(2)
IfR
l
x
∥
w and R
r
x
→
h
b
w, then iFT reports a data race between R
l
x and w, because R
r
x
⪯
w, and neither R
l
x
⊑
w nor w
⊑
R
r
x is satisfied.
(3)
IfR
l
x
∥
w and R
r
x
∥
w, then iFT reports two data races between w and both shared read events.
(4)
IfR
l
x
→
h
b
w and R
r
x
→
h
b
w, then iFT fails to report any data races.Figure2 shows three examples of read-write data races during the execution of a multithreaded program with nondeterministic interleaving of concurrent threads. In Figure 2(a), three shared read events, r
1, r
2, and r
3, happen before the two write events, w
4 and w
5. The leftmost event r
1 and the rightmost event r
3 are kept in R
l
x and R
r
x, respectively, by the left-of-relation. Thus, iFT can report a data race between r
3 and w
4, because r
1
→
h
b
w
4 and r
3
∥
w
4. When w
5 occurs on thread segment t
4 that is concurrent with the others, iFT reports two data races r
1
-
w
5, r
3
-
w
5.Figure 2
Examples of read-write data races.
(a)
(b)
(c)In Figure2(b),  t
1 and t
4 are synchronized by a lock variable l
1, and t
2 is also synchronized with t
4 by a lock variable l
2. For the execution of  Figure 2(b),  iFT records two read events r
1 and r
3 in R
l
x and R
r
x, respectively. It reports only the data race r
3
-
w
4 between R
r
x and w
4, because R
l
x
⪯
w
4 is satisfied. Therefore, r
1
→
h
b
w
4 by the synchronization between t
1 and t
4. iFT records r
2 from t
2 in R
l
x instead of r
1 if the acquiring lock l
2 is reserved, because r
1
→
h
b
r
2 by the thread interleaving t
1
→
t
4
→
t
2. Finally, iFT reports two read-write data races r
2
-
w
4, r
3
-
w
4 for the execution.In Figure2(c), there are two kinds of synchronization events, locking and a signal-wait. Because r
1
→
h
b
r
3 is satisfied by lock variable l
1, iFT records r
3 in R
l
x as the leftmost event, and r
2 is recorded in R
r
x. Thus, iFT locates no data races, because r
3
→
h
b
w
4 by the acquiring lock l
1, and r
2
→
h
b
w
4 by the signal-wait event. If a pair of wait and signal events does not occur between t
2 and t
4, iFT obviously locates the data race {
r
2
-
w
4
}, as it analyzes that the rightmost event r
2 is concurrent with w
4.Lemma 4.
If data races exist betweenR
x and a current write event, the races located by iFT are a subset of those located by FastTrack.Proof.
Suppose that the same fixed program execution order is provided to both analyses. LetI
r
a
c
e (F
r
a
c
e) be the set of races located by iFT (FastTrack), and let I
R
x
(
e
) (F
R
x
(
e
)) be the read events recorded in R
x by iFT (FastTrack). Because I
R
x
(
e
)
∈
F
R
x
(
e
) in the execution order, we guarantee the following:(1)
IfF
r
a
c
e
=
ϕ, then I
r
a
c
e
=
ϕ is satisfied because it is impossible to satisfy I
r
a
c
e
≠
ϕ.
(2)
IfF
r
a
c
e
≠
ϕ, then I
r
a
c
e
≠
ϕ is satisfied because I
r
a
c
e
=
ϕ cannot be satisfied by Lemma 3.Therefore, I
r
a
c
e
⊆
F
r
a
c
e is satisfied.For example, in  Figure2(a), the three data races r
3
-
w
4, r
1
-
w
5, r
3
-
w
5 located by iFT are a subset of the five data races r
2
-
w
4, r
3
-
w
4, r
1
-
w
5, r
2
-
w
5, r
3
-
w
5 located by FastTrack.Write-Write Races. These involve two concurrent write events to x. All write events to x are totally ordered, with the assumption that no data races have been detected on x. Thus, iFT records the epoch of the write event in W
x and locates a write-write race between W
x and a later write event to x by analyzing the epoch of W
x and the current VC of the write event, W
x
⪯
C
t.Write-Read Races. These involve a write event to x that is concurrent with a later read event of x. iFT locates such a data race by analyzing W
x
⪯
C
t.Lemma 5.
If FastTrack locates a write-write race or a write-read race during the execution of a program, iFT can locate the data race from the same fixed execution.Proof.
LetI
W
x
(
e
) (F
W
x
(
e
)) be a write event recorded in W
x by iFT (FastTrack). Then, F
r
a
c
e
=
I
r
a
c
e holds, because I
W
x
(
e
)
=
F
W
x
(
e
) in the execution order, and both analyses employ only W
x
⪯
C
t to analyze →
h
b.Algorithm1 presents the pseudocode for iFT, which consists of three algorithms:ReadCheck
(
),WriteCheck
(
), andMaintain
A
H
(
).ReadCheck
(
) andWriteCheck
(
) mainly focus on filtering events, reporting data races, and maintaining an access history A
H for a shared memory location x whenever an event e
i on thread segment t accesses x. To report data races, we use the inversion of ⪯, denoted by ⋠, to catch instances where the current event is concurrent with a prior event. InReadCheck
(
) andWriteCheck, W
x
⋠
C
t denotes that neither W
x
⪯
C
t nor C
t
⪯
W
x is satisfied.IsOrdered
(
) is used byMaintain
A
H
(
) to check the happens-before relation between the current event and prior events in A
H.Maintain
A
H
(
) manages access histories for every x and employsIsMostL
(
) andIsMostR
(
) to maintain only two concurrent events in R
x by applying the left-of-relation.Algorithm 1:The iFT algorithms.
(01)ReadCheck(x
,
t)
(02)  if E
(
t
)
=
any epoch kept in
R
x then return;
(03)  if W
x
⋠
C
t then Report a data race;
(04)  MaintainAH(R
x
,
E
(
t
));
(05) End ReadCheck
(01) WriteCheck(x
,
t)
(02)  if E
(
t
)
=
W
x then return;
(03)  if W
x
⋠
C
t or R
x
⋠
C
t then Report a data race;
(04)  MaintainAH(W
x
,
E
(
t
));
(05)  R
x
←
ϕ;
(06) End WriteCheck
(01) MaintainAH(A
H
,
e
p
o
c
h)
(02)  if A
H
=
ϕ or IsMostL(A
H
,
e
p
o
c
h) or IsMostR(A
H
,
e
p
o
c
h)
(03)   or IsOrdered(A
H
,
e
p
o
c
h) then A
H
←
e
p
o
c
h;
(04) End MaintainAHTable2 shows the changing state of an access history for detecting the data races appearing in Figure 1 using the iFT algorithm, where we assume that the breadth values are allocated as T
=
0, U
=
1, and V
=
2. In the figure, the epoch of read event r
1 on t
2, 2@0, is recorded in R
x, as the read event of x is performed exclusively. When the rightmost read r
2 occurs on u
1, x enters the Read Shared state. The epoch of r
2 (1@1) is recorded with the epoch of r
1, instead of the full VC of FastTrack in Table 1, because b
(
r
1
)
=
0 is less than b
(
r
2
)
=
1, and therefore r
1
⋞
r
2. Because r
3 is the last read event on thread T when the event occurs, the epoch of the prior leftmost event r
1 is updated to the epoch of r
3, 3@0. When w
4 occurs on u
3, the data race {
r
3
-
w
4
} is reported, as for the FastTrack algorithm. However, iFT only compares two epochs in R
x without any VC operations. iFT also reports the data race {
w
4
-
r
5
} and two data races {
w
4
-
w
6, r
5
-
w
6
}, as does the FastTrack algorithm, when r
5 and w
6 occur. Consequently, the results in Table 2 show that iFT detects apparent data races as well as FastTrack, although the new algorithm maintains only two epochs for concurrent read events in R
x.Table 2
Access history states for detecting data races using theiFT algorithm.
e
i
R
x
W
x
Races
r
1
2@0
⊥
e
r
2
2@01@1
⊥
e
r
3
3@0 1@1
⊥
e
w
4
⊥
e
3@1
r
3
-
w
4
r
5
1@2
3@1
w
4
-
r
5
w
6
⊥
e
6@0
w
4
-
w
6, r
5
-
w
6Theorem 6.
iFT efficiently and soundly locates data races if it maintains only two epochs in R
x.Proof.
TheiFT algorithm has O
(
1
) time and space overheads for detecting data races, because it removes the switching between epochs and VCs for R
x of the FastTrack algorithm by maintaining only two concurrent epochs for the Read Shared state of x. From Lemmas 3, 4, and 5, the algorithm soundly locates data races because it reports a subset including at least one of the data races located by the FastTrack algorithm.


## 5. Evaluation

We empirically evaluated the efficiency and precision ofiFT in comparison with other dynamic detection algorithms that use the happens-before analysis. The experimental results show that our technique not only soundly reports data races, but also reduces the time and space overhead of data race detection for programs with a large number of concurrent threads.


### 5.1. Implementation and Experimentation

We implemented theiFT algorithm and two other dynamic detection algorithms on top of the Pin instrumentation framework [28], which uses a JIT compiler to recompile target program binaries for dynamic instrumentation. Building a lightweight tool for monitoring memory access is easier with Pin than with other dynamic binary instrumentation frameworks, such as Valgrind [30]. The two algorithms used for comparison are Djit+ [3] (a high performance VC-based happens-before analysis algorithm) and FastTrack [6] (a state-of-the-art happens-before analysis algorithm).Figure3 depicts the architecture of the detectors. Each detector consists of an Instrumentor and a Race Detector to report data races during program execution. The Instrumentor consists of two modules: ThreadMonitor and EventMonitor. These, respectively, track thread operations and event instances for every shared memory location considering synchronization primitives. The Race Detector performs the thread identification routines to generate and manage VCs for each active thread segment, as well as the detection routines to report data races.Figure 3
Overall architecture of a data Race Detector.The thread identification routines employ the VC primitives discussed in Section2. These are commonly used to analyze the happens-before relation in the detection routines of all algorithms. A lock-free algorithm was used in the detection routines to remove the centralized bottleneck of access histories. Whenever the Instrumentor catches one of the thread operations or events, it calls either the thread identifier routines or the detection routines to add instrumentation at each interesting point of the running target binaries. Because the Instrumentor and Race Detector use only the shadow binaries of the target programs, which are generated by the JIT compiler of the Pin framework, no source code annotation is required to monitor memory access events or synchronization primitives.To supplement the correct identification of concurrent thread segments, we used a special structural table for each thread. The table consists of four important items of information, the system thread id, Pthread id, Pin thread id, and clock value. The system thread id is the thread id allocated by the operating system, and the Pthread id is allocated by Pthread functions such aspthread_create(). The Pin thread id is the logical identifier created in sequence whenever the Pin framework catches a thread start operation. Thus, we employed the Pin thread id as the breadth value b
i of an epoch (c
i
@
b
i) in the iFT algorithm. The clock value is used to form a VC of a thread segment using synchronization primitive operations.Our experimentation focused on comparing the soundness and the efficiency of on-the-fly data race detection in programs with a large number of concurrent threads. To evaluate theiFT algorithm, we compared the data races reported by each detector and measured the execution time and the memory consumed by the execution instances of a set of C/C++ benchmarks using Pthread. For this purpose, we used 12 applications from the PARSEC 2.1 benchmark suite [31]. These target different areas, including HPC, with applications such as data mining, financial analysis, and computer vision. All applications were executed with the default simulation inputs of the PARSEC benchmark suite to produce proper runtime overheads and memory consumption.Before conducting the experiments, we investigated the benchmark applications in terms of the frequency of access events and synchronization primitives. The results of this analysis with the FastTrack algorithm are given in Table 3. We usedsim-medium simulation inputs in the execution of each application. In the table, “Same Epoch” means that read/write events to a shared memory location x have been filtered out by FastTrack as they occurred after the first read/write event on the same thread segment. “Exclusive” indicates that only epochs were used to locate data races, because read/write events exclusively accessed x. “Shared” indicates the Read Shared state in which x has shared read events being performed by concurrent thread segments. “VC Scan” indicates that a current write event was compared with R
x when x entered the Read Shared state. Thus, two memory operations, Shared and VC Scan, require VC operations that require O
(
n
) time and space overheads in FastTrack.Table 3
Analysis of PARSEC benchmarks using Fa
stTrack.
Applications
# of threads
Read (78.3%)
Write (21.6%)
Same Epoch
Exclusive
Shared
Same Epoch
Exclusive
VC Scan
blackscholes
9
99.8%
0.2%
0%
99.0%
1.0%
0%
bodytrack
10
94.5%
2.6%
2.9%
87.9%
10.8%
1.3%
canneal
9
87.7%
7.4%
4.9%
69.3%
23.7%
7.0%
dedup
25
90.8%
8.7%
0.5%
70.2%
29.3%
0.5%
facesim
8
89.8%
10.1%
0.1%
94.2%
5.7%
0.1%
ferret
35
94.9%
3.7%
1.4%
75.7%
19.8%
4.5%
fluidanimate
9
84.8%
10.8%
4.4%
90.0%
9.9%
0.1%
raytrace
9
97.2%
2.7%
0.1%
99.6%
0.4%
0%
streamcluster
17
76.1%
23.3%
0.6%
84.0%
15.3%
0.7%
swaptions
9
99.1%
0.5%
0.4%
95.9%
2.2%
1.9%
vips
4
75.8%
24.2%
0%
1.3%
98.7%
0%
x264
64
97.8%
1.8%
0.4%
95.2%
4.8%
0%
Average
90.7%
8.0%
1.3%
80.2%
18.5%
1.3%From this investigation, we can see that 78.3% of all operations and events were read events and 21.6% were write events. Other operations and events accounted for less than 0.1% of the total. These results reaffirm that almost all parts of data race detection involve tracing access events to shared memory locations, because this accounts for more than 99% of operations in the benchmarks. Fortunately, the convergence of memory operations is again removed, as there is a possibility that this will affect the tracing of events for data race detection. For example, in the table, 90.7% of read events and 80.2% of write events occurred in the same epoch. VC operations are rarely needed, accounting for an average of only 1.3% of all read/write events. Thus, the switching approach in FastTrack is quite effective in improving the performance of happens-before analysis.The implementation and experimentation were carried out on a system with two 2.4 GHz Intel Xeon quad-core processors and 32 GB of memory under Linux Kernel 2.6. We installed the most recent version of the Pin framework (Version 2.12), and the applications were compiled with gcc 4.4.4 for all detectors. We used a programmed logging method to measure the execution time and memory consumption of each application. This method uses system files in theproc directory, which provides real-time information on the system, includingmeminfo,iomem, andcpuinfo. The average runtime and memory overheads of all applications were measured for ten executions under each detector. Figure 4 shows the resulting analyzed information, such as thread creation, detected data races, execution time, and memory consumption, during an execution of thex264 application using our implemented iFT detector.Figure 4
Execution result of the implementediFT detector.


### 5.2. Results and Analysis

#### 5.2.1. Precision

We acquired the reported data race results to evaluate the precision ofiFT. Three detectors were applied on the same Pin framework for fair experimentation. All applications of PARSEC benchmark were run withsim-medium simulation inputs, and two real applications were run with both of server program and several client programs. The two real applications used for the experimentation areMySQL (an open source DBMS) andCherokee (an open source web and server application). These applications were repeatedly tested until each detector had fixed all warnings. The number of data races located by the three detectors is given in Table 4.Table 4
Number of data races located on the PARSEC benchmark and real applications.
Applications
# of threads
Detected races
Djit+
Fa
stTrack
iFT
PARSEC
blackscholes
9
0
0
0
bodytrack
10
8
8
7
canneal
9
1
1
1
dedup
25
0
0
0
facesim
8
0
0
0
ferret
35
2
2
2
fluidanimate
9
1
1
1
raytrace
9
0
0
0
streamcluster
17
4
4
4
swaptions
9
0
0
0
vips
4
0
0
0
x264
64
3
3
2
Real
MySQL
78
8
8
8
Cherokee
126
7
7
7All of the detectors reported that there were no data races in six of the applications in the PARSEC benchmarks,blackscholes,dedup,facesim, raytrace,swaptions, andvips. This agrees with prior research [32], which considered an implementation of FastTrack on top of the DynamoRIO instrumentation framework. Djit+ and FastTrack reported exactly the same data races for all applications, as found in [6, 20], because these two detectors are based on identical precision. Similarly,iFT reported the same data races as FastTrack, with the exception of thebodytrack andx264 applications.All the detectors located a data race incanneal andfluidanimate, which run into user-defined synchronization functions, such asatomic
(
) andbarrier_wait
(
). They reported two data races inferret; these were caused by a shared counter variable and a shared Boolean flag for a queue in the application. The three detectors reported four data races forstreamcluster. These were caused by using the same user-defined synchronization,barrier_wait
(
), and object pointers to a shared structure without explicit synchronization. All of the detectors reported eight data races inMySQL due to object pointers to a shared structure without any proper synchronization and shared flags for thread termination. The three detectors located seven data races inCherokee. A data race inCherokee was the result of log corruption similar to a well-known bug in Apache’s logging code (Apache bug #25520).Forbodytrack, all detectors found six data races, which were caused by the initialization of objects in shared structures without synchronization and the misuse of condition variables. Djit+ and FastTrack also reported two data races involving two kinds of unprotected counter variables for a user-definedwait-notify operation, whereasiFT reported only one of the data races.iFT located two data races forx264, caused by two pointers in different functions that were referring to a shared structure and its members. The pointers allowed the shared memory locations to be concurrently accessed by read/write events from each function without any proper synchronization. The other detectors reported three data races, including two detected byiFT; the other one was caused by the same bug via a pointer to the same shared structure.Inbodytrack andx264, shared read events that are not the leftmost or rightmost events can be exempted from relevant events of the data race detection process by ouriFT algorithm. Hence,iFT reported fewer data races for these two applications, and the reported data races were a subset of those given by FastTrack. For example, in the result ofx264, a prior read access of a shared structure in a file (frame.c) was removed from R
x of an A
H, since a new read access of the same shared structure in another file (analyse.c) occurred on the leftmost thread.iFT reported only a data race between the leftmost read access and a later write access to the same shared structure in a file (encorder.c), whereas FastTrack reported two data races between these read accesses and the later write. However,iFT located the missed data race after we had fixed the previously reported data race by using a local pointer variable.From this experiment, we can conclude thatiFT is sound, because the precision of theiFT algorithm is fixed relevant to the well-established precision of FastTrack.


#### 5.2.2. Efficiency

We measured the runtime and memory consumption of the benchmarks over three detectors to evaluate the efficiency ofiFT. Figure 5 depicts the measured runtime and memory overhead results for 11 applications of PARSEC withsim-medium simulation inputs. The graph shows the average runtime and memory overheads for each of the detectors as a proportion of the original run. Becausefacesim is a representative long-running application that uses a small number of concurrent threads and naturally requires quite high runtime and memory overheads for on-the-fly data race detection, the application was excluded from the efficiency test.Figure 5
Measured runtime and memory overhead results for 11 benchmarks of PARSEC.
(a)
Average runtime overhead
(b)
Average memory overheadFrom Figure5(a), almost all of the iFT results are lower than those of the other detectors. iFT incurred an average runtime overhead of 8.5x, whereas FastTrack and Djit+ required average runtime overheads of 9.2x and 11.2x, respectively. In particular,iFT required explicitly lower runtime overheads for two applications,dedup andferret, which use more than 20 active threads during program execution. For instance,iFT incurred an average runtime overhead of 23.5x fordedup, whereas FastTrack and Djit+ incurred average runtime overheads of 27.6x and 37.3x, respectively. In the case offerret, the incurred runtime overhead ofiFT was 7.5x, while FastTrack and Djit+ incurred average runtime overheads of 10x and 16x, respectively. Several applications, such asblackscholes,canneal, andraytrace, have lower overheads than the others because of their model of parallelism (e.g., fork-join parallelism).In Figure5(b), we see that iFT incurred an average memory overhead of 4.3x, whereas FastTrack incurred an average memory overhead of 6.0x. This means that iFT reduced the average memory overhead to 58% of that of Djit+ and 72% of that of FastTrack for 11 applications. If we consider the three applications that use several ten dynamic threads, iFT incurred an average memory overhead of 1.9x, while FastTrack required an average memory overhead of 5.4x. Thus, the proposed iFT reduced the average memory overhead to 37% of that recorded by FastTrack.We measured average memory consumption for two real applications under our Pin framework. The results of the measurement appear in Figure6. For the experiments,MySQL used 78 multiple threads during 60 seconds for an execution, and 126 threads were used forCherokee. We employed four monitoring steps, Native, Pin-only, Monitoring, and Detecting, to show how many additional overheads were incurred by instrumentation work under Pin framework. Native means the original execution without our Pin framework, and Pin-only indicates the measured results that the applications were run on the Pin framework without monitoring and instrumentation work. Monitoring means that only the thread executions and memory accesses were traced under the Pin framework. Detecting means that we measured the memory consumption of the execution of the applications under the three detectors that were implemented on top of the Pin framework.Figure 6
Measured memory consumption for two real applications.In Figure6, we see that Pin-only incurred an average memory consumption of 2.2x and Monitoring incurred an average memory consumption of 2.6x.iFT incurred an average memory consumption of 2.8x, whereas FastTrack incurred an average memory consumption of 3.6x. This means that iFT reduced the average memory consumption to 62% of that of Djit+ and 76% of that of FastTrack for two applications. If we exclude Pin-only step that incurred 1,128 MB in the average case, iFT incurred an average memory consumption of 1.7x, while FastTrack required an average memory consumption of 2.3x. For the two real applications,iFT reduced the average memory consumption to 49% of FastTrack.We chose thex264 application from the PARSEC benchmark for additional comparison, because it employs a different number of concurrent threads to process the virtual pipelined stages for each input frame. In contrast, the other applications use a fixed number of threads, although they use different inputs. The comparison used all six simulation inputs provided by the PARSEC suite, because these lead to an increasing thread size in each input frame.Figure7 depicts the measured runtime and memory overhead results for thex264 application. In the experiment, iFT incurred an average runtime overhead of 6.6x, whereas the other detectors averaged more than 8x slowdown. In particular, in the executions with thesim-large input (256 threads), iFT reduces the runtime overhead to 74% of that of the other detectors. iFT performs well in reducing the memory overhead, averaging just 1.3x, whereas the memory overhead of the other detectors increased by a factor of more than 95% relative to that of iFT. Under iFT, the application ran withnative input using 1,024 concurrent threads, but the other detectors ran out of memory with thenative input because of the 32 GB limitation of our system. In this case, iFT required a runtime overhead of 11.5x and a memory overhead of 1.6x to locate two data races. It is noteworthy that the distinguished performance of iFT is caused by the elimination of the VC operations used in the FastTrack algorithm.Figure 7
Measured runtime and memory overhead results for x264 application.
(a)
Average runtime overheads
(b)
Average memory overheadsThe results in Figure7 show that iFT reduced the memory overhead by 11.4x and gave a speedup of 1.3x compared to the other dynamic detectors. The overheads of iFT were similar to those of the other algorithms for small-size inputs, asx264 uses fewer than 20 threads for these inputs. However, with the larger inputs, iFT reduced the runtime and memory overheads compared to the other detectors. For example, iFT required just 82% of the runtime and 8% of the memory overhead of FastTrack for these larger inputs. The results emphasize again that iFT is practically useful for detecting data races on-the-fly in programs with a large number of concurrent threads.The empirical results from Table4 to Figure 7 show that ouriFT algorithm is a sound and practical method for on-the-fly data race detection, because it reduces the average runtime and memory overhead to 84% and 37%, respectively, of those recorded by FastTrack.


## 5.1. Implementation and Experimentation

We implemented theiFT algorithm and two other dynamic detection algorithms on top of the Pin instrumentation framework [28], which uses a JIT compiler to recompile target program binaries for dynamic instrumentation. Building a lightweight tool for monitoring memory access is easier with Pin than with other dynamic binary instrumentation frameworks, such as Valgrind [30]. The two algorithms used for comparison are Djit+ [3] (a high performance VC-based happens-before analysis algorithm) and FastTrack [6] (a state-of-the-art happens-before analysis algorithm).Figure3 depicts the architecture of the detectors. Each detector consists of an Instrumentor and a Race Detector to report data races during program execution. The Instrumentor consists of two modules: ThreadMonitor and EventMonitor. These, respectively, track thread operations and event instances for every shared memory location considering synchronization primitives. The Race Detector performs the thread identification routines to generate and manage VCs for each active thread segment, as well as the detection routines to report data races.Figure 3
Overall architecture of a data Race Detector.The thread identification routines employ the VC primitives discussed in Section2. These are commonly used to analyze the happens-before relation in the detection routines of all algorithms. A lock-free algorithm was used in the detection routines to remove the centralized bottleneck of access histories. Whenever the Instrumentor catches one of the thread operations or events, it calls either the thread identifier routines or the detection routines to add instrumentation at each interesting point of the running target binaries. Because the Instrumentor and Race Detector use only the shadow binaries of the target programs, which are generated by the JIT compiler of the Pin framework, no source code annotation is required to monitor memory access events or synchronization primitives.To supplement the correct identification of concurrent thread segments, we used a special structural table for each thread. The table consists of four important items of information, the system thread id, Pthread id, Pin thread id, and clock value. The system thread id is the thread id allocated by the operating system, and the Pthread id is allocated by Pthread functions such aspthread_create(). The Pin thread id is the logical identifier created in sequence whenever the Pin framework catches a thread start operation. Thus, we employed the Pin thread id as the breadth value b
i of an epoch (c
i
@
b
i) in the iFT algorithm. The clock value is used to form a VC of a thread segment using synchronization primitive operations.Our experimentation focused on comparing the soundness and the efficiency of on-the-fly data race detection in programs with a large number of concurrent threads. To evaluate theiFT algorithm, we compared the data races reported by each detector and measured the execution time and the memory consumed by the execution instances of a set of C/C++ benchmarks using Pthread. For this purpose, we used 12 applications from the PARSEC 2.1 benchmark suite [31]. These target different areas, including HPC, with applications such as data mining, financial analysis, and computer vision. All applications were executed with the default simulation inputs of the PARSEC benchmark suite to produce proper runtime overheads and memory consumption.Before conducting the experiments, we investigated the benchmark applications in terms of the frequency of access events and synchronization primitives. The results of this analysis with the FastTrack algorithm are given in Table 3. We usedsim-medium simulation inputs in the execution of each application. In the table, “Same Epoch” means that read/write events to a shared memory location x have been filtered out by FastTrack as they occurred after the first read/write event on the same thread segment. “Exclusive” indicates that only epochs were used to locate data races, because read/write events exclusively accessed x. “Shared” indicates the Read Shared state in which x has shared read events being performed by concurrent thread segments. “VC Scan” indicates that a current write event was compared with R
x when x entered the Read Shared state. Thus, two memory operations, Shared and VC Scan, require VC operations that require O
(
n
) time and space overheads in FastTrack.Table 3
Analysis of PARSEC benchmarks using Fa
stTrack.
Applications
# of threads
Read (78.3%)
Write (21.6%)
Same Epoch
Exclusive
Shared
Same Epoch
Exclusive
VC Scan
blackscholes
9
99.8%
0.2%
0%
99.0%
1.0%
0%
bodytrack
10
94.5%
2.6%
2.9%
87.9%
10.8%
1.3%
canneal
9
87.7%
7.4%
4.9%
69.3%
23.7%
7.0%
dedup
25
90.8%
8.7%
0.5%
70.2%
29.3%
0.5%
facesim
8
89.8%
10.1%
0.1%
94.2%
5.7%
0.1%
ferret
35
94.9%
3.7%
1.4%
75.7%
19.8%
4.5%
fluidanimate
9
84.8%
10.8%
4.4%
90.0%
9.9%
0.1%
raytrace
9
97.2%
2.7%
0.1%
99.6%
0.4%
0%
streamcluster
17
76.1%
23.3%
0.6%
84.0%
15.3%
0.7%
swaptions
9
99.1%
0.5%
0.4%
95.9%
2.2%
1.9%
vips
4
75.8%
24.2%
0%
1.3%
98.7%
0%
x264
64
97.8%
1.8%
0.4%
95.2%
4.8%
0%
Average
90.7%
8.0%
1.3%
80.2%
18.5%
1.3%From this investigation, we can see that 78.3% of all operations and events were read events and 21.6% were write events. Other operations and events accounted for less than 0.1% of the total. These results reaffirm that almost all parts of data race detection involve tracing access events to shared memory locations, because this accounts for more than 99% of operations in the benchmarks. Fortunately, the convergence of memory operations is again removed, as there is a possibility that this will affect the tracing of events for data race detection. For example, in the table, 90.7% of read events and 80.2% of write events occurred in the same epoch. VC operations are rarely needed, accounting for an average of only 1.3% of all read/write events. Thus, the switching approach in FastTrack is quite effective in improving the performance of happens-before analysis.The implementation and experimentation were carried out on a system with two 2.4 GHz Intel Xeon quad-core processors and 32 GB of memory under Linux Kernel 2.6. We installed the most recent version of the Pin framework (Version 2.12), and the applications were compiled with gcc 4.4.4 for all detectors. We used a programmed logging method to measure the execution time and memory consumption of each application. This method uses system files in theproc directory, which provides real-time information on the system, includingmeminfo,iomem, andcpuinfo. The average runtime and memory overheads of all applications were measured for ten executions under each detector. Figure 4 shows the resulting analyzed information, such as thread creation, detected data races, execution time, and memory consumption, during an execution of thex264 application using our implemented iFT detector.Figure 4
Execution result of the implementediFT detector.


## 5.2. Results and Analysis

### 5.2.1. Precision

We acquired the reported data race results to evaluate the precision ofiFT. Three detectors were applied on the same Pin framework for fair experimentation. All applications of PARSEC benchmark were run withsim-medium simulation inputs, and two real applications were run with both of server program and several client programs. The two real applications used for the experimentation areMySQL (an open source DBMS) andCherokee (an open source web and server application). These applications were repeatedly tested until each detector had fixed all warnings. The number of data races located by the three detectors is given in Table 4.Table 4
Number of data races located on the PARSEC benchmark and real applications.
Applications
# of threads
Detected races
Djit+
Fa
stTrack
iFT
PARSEC
blackscholes
9
0
0
0
bodytrack
10
8
8
7
canneal
9
1
1
1
dedup
25
0
0
0
facesim
8
0
0
0
ferret
35
2
2
2
fluidanimate
9
1
1
1
raytrace
9
0
0
0
streamcluster
17
4
4
4
swaptions
9
0
0
0
vips
4
0
0
0
x264
64
3
3
2
Real
MySQL
78
8
8
8
Cherokee
126
7
7
7All of the detectors reported that there were no data races in six of the applications in the PARSEC benchmarks,blackscholes,dedup,facesim, raytrace,swaptions, andvips. This agrees with prior research [32], which considered an implementation of FastTrack on top of the DynamoRIO instrumentation framework. Djit+ and FastTrack reported exactly the same data races for all applications, as found in [6, 20], because these two detectors are based on identical precision. Similarly,iFT reported the same data races as FastTrack, with the exception of thebodytrack andx264 applications.All the detectors located a data race incanneal andfluidanimate, which run into user-defined synchronization functions, such asatomic
(
) andbarrier_wait
(
). They reported two data races inferret; these were caused by a shared counter variable and a shared Boolean flag for a queue in the application. The three detectors reported four data races forstreamcluster. These were caused by using the same user-defined synchronization,barrier_wait
(
), and object pointers to a shared structure without explicit synchronization. All of the detectors reported eight data races inMySQL due to object pointers to a shared structure without any proper synchronization and shared flags for thread termination. The three detectors located seven data races inCherokee. A data race inCherokee was the result of log corruption similar to a well-known bug in Apache’s logging code (Apache bug #25520).Forbodytrack, all detectors found six data races, which were caused by the initialization of objects in shared structures without synchronization and the misuse of condition variables. Djit+ and FastTrack also reported two data races involving two kinds of unprotected counter variables for a user-definedwait-notify operation, whereasiFT reported only one of the data races.iFT located two data races forx264, caused by two pointers in different functions that were referring to a shared structure and its members. The pointers allowed the shared memory locations to be concurrently accessed by read/write events from each function without any proper synchronization. The other detectors reported three data races, including two detected byiFT; the other one was caused by the same bug via a pointer to the same shared structure.Inbodytrack andx264, shared read events that are not the leftmost or rightmost events can be exempted from relevant events of the data race detection process by ouriFT algorithm. Hence,iFT reported fewer data races for these two applications, and the reported data races were a subset of those given by FastTrack. For example, in the result ofx264, a prior read access of a shared structure in a file (frame.c) was removed from R
x of an A
H, since a new read access of the same shared structure in another file (analyse.c) occurred on the leftmost thread.iFT reported only a data race between the leftmost read access and a later write access to the same shared structure in a file (encorder.c), whereas FastTrack reported two data races between these read accesses and the later write. However,iFT located the missed data race after we had fixed the previously reported data race by using a local pointer variable.From this experiment, we can conclude thatiFT is sound, because the precision of theiFT algorithm is fixed relevant to the well-established precision of FastTrack.


### 5.2.2. Efficiency

We measured the runtime and memory consumption of the benchmarks over three detectors to evaluate the efficiency ofiFT. Figure 5 depicts the measured runtime and memory overhead results for 11 applications of PARSEC withsim-medium simulation inputs. The graph shows the average runtime and memory overheads for each of the detectors as a proportion of the original run. Becausefacesim is a representative long-running application that uses a small number of concurrent threads and naturally requires quite high runtime and memory overheads for on-the-fly data race detection, the application was excluded from the efficiency test.Figure 5
Measured runtime and memory overhead results for 11 benchmarks of PARSEC.
(a)
Average runtime overhead
(b)
Average memory overheadFrom Figure5(a), almost all of the iFT results are lower than those of the other detectors. iFT incurred an average runtime overhead of 8.5x, whereas FastTrack and Djit+ required average runtime overheads of 9.2x and 11.2x, respectively. In particular,iFT required explicitly lower runtime overheads for two applications,dedup andferret, which use more than 20 active threads during program execution. For instance,iFT incurred an average runtime overhead of 23.5x fordedup, whereas FastTrack and Djit+ incurred average runtime overheads of 27.6x and 37.3x, respectively. In the case offerret, the incurred runtime overhead ofiFT was 7.5x, while FastTrack and Djit+ incurred average runtime overheads of 10x and 16x, respectively. Several applications, such asblackscholes,canneal, andraytrace, have lower overheads than the others because of their model of parallelism (e.g., fork-join parallelism).In Figure5(b), we see that iFT incurred an average memory overhead of 4.3x, whereas FastTrack incurred an average memory overhead of 6.0x. This means that iFT reduced the average memory overhead to 58% of that of Djit+ and 72% of that of FastTrack for 11 applications. If we consider the three applications that use several ten dynamic threads, iFT incurred an average memory overhead of 1.9x, while FastTrack required an average memory overhead of 5.4x. Thus, the proposed iFT reduced the average memory overhead to 37% of that recorded by FastTrack.We measured average memory consumption for two real applications under our Pin framework. The results of the measurement appear in Figure6. For the experiments,MySQL used 78 multiple threads during 60 seconds for an execution, and 126 threads were used forCherokee. We employed four monitoring steps, Native, Pin-only, Monitoring, and Detecting, to show how many additional overheads were incurred by instrumentation work under Pin framework. Native means the original execution without our Pin framework, and Pin-only indicates the measured results that the applications were run on the Pin framework without monitoring and instrumentation work. Monitoring means that only the thread executions and memory accesses were traced under the Pin framework. Detecting means that we measured the memory consumption of the execution of the applications under the three detectors that were implemented on top of the Pin framework.Figure 6
Measured memory consumption for two real applications.In Figure6, we see that Pin-only incurred an average memory consumption of 2.2x and Monitoring incurred an average memory consumption of 2.6x.iFT incurred an average memory consumption of 2.8x, whereas FastTrack incurred an average memory consumption of 3.6x. This means that iFT reduced the average memory consumption to 62% of that of Djit+ and 76% of that of FastTrack for two applications. If we exclude Pin-only step that incurred 1,128 MB in the average case, iFT incurred an average memory consumption of 1.7x, while FastTrack required an average memory consumption of 2.3x. For the two real applications,iFT reduced the average memory consumption to 49% of FastTrack.We chose thex264 application from the PARSEC benchmark for additional comparison, because it employs a different number of concurrent threads to process the virtual pipelined stages for each input frame. In contrast, the other applications use a fixed number of threads, although they use different inputs. The comparison used all six simulation inputs provided by the PARSEC suite, because these lead to an increasing thread size in each input frame.Figure7 depicts the measured runtime and memory overhead results for thex264 application. In the experiment, iFT incurred an average runtime overhead of 6.6x, whereas the other detectors averaged more than 8x slowdown. In particular, in the executions with thesim-large input (256 threads), iFT reduces the runtime overhead to 74% of that of the other detectors. iFT performs well in reducing the memory overhead, averaging just 1.3x, whereas the memory overhead of the other detectors increased by a factor of more than 95% relative to that of iFT. Under iFT, the application ran withnative input using 1,024 concurrent threads, but the other detectors ran out of memory with thenative input because of the 32 GB limitation of our system. In this case, iFT required a runtime overhead of 11.5x and a memory overhead of 1.6x to locate two data races. It is noteworthy that the distinguished performance of iFT is caused by the elimination of the VC operations used in the FastTrack algorithm.Figure 7
Measured runtime and memory overhead results for x264 application.
(a)
Average runtime overheads
(b)
Average memory overheadsThe results in Figure7 show that iFT reduced the memory overhead by 11.4x and gave a speedup of 1.3x compared to the other dynamic detectors. The overheads of iFT were similar to those of the other algorithms for small-size inputs, asx264 uses fewer than 20 threads for these inputs. However, with the larger inputs, iFT reduced the runtime and memory overheads compared to the other detectors. For example, iFT required just 82% of the runtime and 8% of the memory overhead of FastTrack for these larger inputs. The results emphasize again that iFT is practically useful for detecting data races on-the-fly in programs with a large number of concurrent threads.The empirical results from Table4 to Figure 7 show that ouriFT algorithm is a sound and practical method for on-the-fly data race detection, because it reduces the average runtime and memory overhead to 84% and 37%, respectively, of those recorded by FastTrack.


## 5.2.1. Precision

We acquired the reported data race results to evaluate the precision ofiFT. Three detectors were applied on the same Pin framework for fair experimentation. All applications of PARSEC benchmark were run withsim-medium simulation inputs, and two real applications were run with both of server program and several client programs. The two real applications used for the experimentation areMySQL (an open source DBMS) andCherokee (an open source web and server application). These applications were repeatedly tested until each detector had fixed all warnings. The number of data races located by the three detectors is given in Table 4.Table 4
Number of data races located on the PARSEC benchmark and real applications.
Applications
# of threads
Detected races
Djit+
Fa
stTrack
iFT
PARSEC
blackscholes
9
0
0
0
bodytrack
10
8
8
7
canneal
9
1
1
1
dedup
25
0
0
0
facesim
8
0
0
0
ferret
35
2
2
2
fluidanimate
9
1
1
1
raytrace
9
0
0
0
streamcluster
17
4
4
4
swaptions
9
0
0
0
vips
4
0
0
0
x264
64
3
3
2
Real
MySQL
78
8
8
8
Cherokee
126
7
7
7All of the detectors reported that there were no data races in six of the applications in the PARSEC benchmarks,blackscholes,dedup,facesim, raytrace,swaptions, andvips. This agrees with prior research [32], which considered an implementation of FastTrack on top of the DynamoRIO instrumentation framework. Djit+ and FastTrack reported exactly the same data races for all applications, as found in [6, 20], because these two detectors are based on identical precision. Similarly,iFT reported the same data races as FastTrack, with the exception of thebodytrack andx264 applications.All the detectors located a data race incanneal andfluidanimate, which run into user-defined synchronization functions, such asatomic
(
) andbarrier_wait
(
). They reported two data races inferret; these were caused by a shared counter variable and a shared Boolean flag for a queue in the application. The three detectors reported four data races forstreamcluster. These were caused by using the same user-defined synchronization,barrier_wait
(
), and object pointers to a shared structure without explicit synchronization. All of the detectors reported eight data races inMySQL due to object pointers to a shared structure without any proper synchronization and shared flags for thread termination. The three detectors located seven data races inCherokee. A data race inCherokee was the result of log corruption similar to a well-known bug in Apache’s logging code (Apache bug #25520).Forbodytrack, all detectors found six data races, which were caused by the initialization of objects in shared structures without synchronization and the misuse of condition variables. Djit+ and FastTrack also reported two data races involving two kinds of unprotected counter variables for a user-definedwait-notify operation, whereasiFT reported only one of the data races.iFT located two data races forx264, caused by two pointers in different functions that were referring to a shared structure and its members. The pointers allowed the shared memory locations to be concurrently accessed by read/write events from each function without any proper synchronization. The other detectors reported three data races, including two detected byiFT; the other one was caused by the same bug via a pointer to the same shared structure.Inbodytrack andx264, shared read events that are not the leftmost or rightmost events can be exempted from relevant events of the data race detection process by ouriFT algorithm. Hence,iFT reported fewer data races for these two applications, and the reported data races were a subset of those given by FastTrack. For example, in the result ofx264, a prior read access of a shared structure in a file (frame.c) was removed from R
x of an A
H, since a new read access of the same shared structure in another file (analyse.c) occurred on the leftmost thread.iFT reported only a data race between the leftmost read access and a later write access to the same shared structure in a file (encorder.c), whereas FastTrack reported two data races between these read accesses and the later write. However,iFT located the missed data race after we had fixed the previously reported data race by using a local pointer variable.From this experiment, we can conclude thatiFT is sound, because the precision of theiFT algorithm is fixed relevant to the well-established precision of FastTrack.


## 5.2.2. Efficiency

We measured the runtime and memory consumption of the benchmarks over three detectors to evaluate the efficiency ofiFT. Figure 5 depicts the measured runtime and memory overhead results for 11 applications of PARSEC withsim-medium simulation inputs. The graph shows the average runtime and memory overheads for each of the detectors as a proportion of the original run. Becausefacesim is a representative long-running application that uses a small number of concurrent threads and naturally requires quite high runtime and memory overheads for on-the-fly data race detection, the application was excluded from the efficiency test.Figure 5
Measured runtime and memory overhead results for 11 benchmarks of PARSEC.
(a)
Average runtime overhead
(b)
Average memory overheadFrom Figure5(a), almost all of the iFT results are lower than those of the other detectors. iFT incurred an average runtime overhead of 8.5x, whereas FastTrack and Djit+ required average runtime overheads of 9.2x and 11.2x, respectively. In particular,iFT required explicitly lower runtime overheads for two applications,dedup andferret, which use more than 20 active threads during program execution. For instance,iFT incurred an average runtime overhead of 23.5x fordedup, whereas FastTrack and Djit+ incurred average runtime overheads of 27.6x and 37.3x, respectively. In the case offerret, the incurred runtime overhead ofiFT was 7.5x, while FastTrack and Djit+ incurred average runtime overheads of 10x and 16x, respectively. Several applications, such asblackscholes,canneal, andraytrace, have lower overheads than the others because of their model of parallelism (e.g., fork-join parallelism).In Figure5(b), we see that iFT incurred an average memory overhead of 4.3x, whereas FastTrack incurred an average memory overhead of 6.0x. This means that iFT reduced the average memory overhead to 58% of that of Djit+ and 72% of that of FastTrack for 11 applications. If we consider the three applications that use several ten dynamic threads, iFT incurred an average memory overhead of 1.9x, while FastTrack required an average memory overhead of 5.4x. Thus, the proposed iFT reduced the average memory overhead to 37% of that recorded by FastTrack.We measured average memory consumption for two real applications under our Pin framework. The results of the measurement appear in Figure6. For the experiments,MySQL used 78 multiple threads during 60 seconds for an execution, and 126 threads were used forCherokee. We employed four monitoring steps, Native, Pin-only, Monitoring, and Detecting, to show how many additional overheads were incurred by instrumentation work under Pin framework. Native means the original execution without our Pin framework, and Pin-only indicates the measured results that the applications were run on the Pin framework without monitoring and instrumentation work. Monitoring means that only the thread executions and memory accesses were traced under the Pin framework. Detecting means that we measured the memory consumption of the execution of the applications under the three detectors that were implemented on top of the Pin framework.Figure 6
Measured memory consumption for two real applications.In Figure6, we see that Pin-only incurred an average memory consumption of 2.2x and Monitoring incurred an average memory consumption of 2.6x.iFT incurred an average memory consumption of 2.8x, whereas FastTrack incurred an average memory consumption of 3.6x. This means that iFT reduced the average memory consumption to 62% of that of Djit+ and 76% of that of FastTrack for two applications. If we exclude Pin-only step that incurred 1,128 MB in the average case, iFT incurred an average memory consumption of 1.7x, while FastTrack required an average memory consumption of 2.3x. For the two real applications,iFT reduced the average memory consumption to 49% of FastTrack.We chose thex264 application from the PARSEC benchmark for additional comparison, because it employs a different number of concurrent threads to process the virtual pipelined stages for each input frame. In contrast, the other applications use a fixed number of threads, although they use different inputs. The comparison used all six simulation inputs provided by the PARSEC suite, because these lead to an increasing thread size in each input frame.Figure7 depicts the measured runtime and memory overhead results for thex264 application. In the experiment, iFT incurred an average runtime overhead of 6.6x, whereas the other detectors averaged more than 8x slowdown. In particular, in the executions with thesim-large input (256 threads), iFT reduces the runtime overhead to 74% of that of the other detectors. iFT performs well in reducing the memory overhead, averaging just 1.3x, whereas the memory overhead of the other detectors increased by a factor of more than 95% relative to that of iFT. Under iFT, the application ran withnative input using 1,024 concurrent threads, but the other detectors ran out of memory with thenative input because of the 32 GB limitation of our system. In this case, iFT required a runtime overhead of 11.5x and a memory overhead of 1.6x to locate two data races. It is noteworthy that the distinguished performance of iFT is caused by the elimination of the VC operations used in the FastTrack algorithm.Figure 7
Measured runtime and memory overhead results for x264 application.
(a)
Average runtime overheads
(b)
Average memory overheadsThe results in Figure7 show that iFT reduced the memory overhead by 11.4x and gave a speedup of 1.3x compared to the other dynamic detectors. The overheads of iFT were similar to those of the other algorithms for small-size inputs, asx264 uses fewer than 20 threads for these inputs. However, with the larger inputs, iFT reduced the runtime and memory overheads compared to the other detectors. For example, iFT required just 82% of the runtime and 8% of the memory overhead of FastTrack for these larger inputs. The results emphasize again that iFT is practically useful for detecting data races on-the-fly in programs with a large number of concurrent threads.The empirical results from Table4 to Figure 7 show that ouriFT algorithm is a sound and practical method for on-the-fly data race detection, because it reduces the average runtime and memory overhead to 84% and 37%, respectively, of those recorded by FastTrack.


## 6. Related Work

Most prior dynamic techniques have focused on detecting data races more precisely or efficiently. Since FastTrack was introduced, several detectors have been designed to combine lockset analysis with happens-before analysis by leveraging the lightweight nature of epochs.AccuLock [20] was the first solution to use this combined approach, achieving comparable performance to FastTrack and limited false positives. This detector applies a new, efficient lockset algorithm to FastTrack to enforce a thread locking discipline. This uses the notion of potential data races, called ∅-races, in which any two concurrent read/write events access a shared memory location without a common lock. The detector considers the sensitivity to thread interleaving using thread locking, as it excludes the subset of happens-before relations found with lock acquirements and releases from VCs. However, AccuLock still requires O
(
n
) operations to maintain an access history and locate data races, similar to FastTrack.ThreadSanitizer [8] is another hybrid detector based on the same combination approach. This detector provides improved precision in the detection of data races by adapting the fastidious aspect of thread synchronizations and race patterns appearing in C/C++ applications. However, unlike AccuLock, it uses VCs to analyze the happens-before relation and multiple locksets for concurrent writes. Thus, the detector offers the same time and memory overhead as earlier hybrid detectors such as MultiRace [3]. Recently, a new version of ThreadSanitizer was released (but not reported officially). This included the FastTrack algorithm and epochs instead of the VCs of the old version.In our prior work [33], we presented an on-the-fly Race Detector for OpenMP programs. This detector uses a thread identifying technique to analyze the happens-before relation and a data race detection protocol that utilizes the lockset analysis. A significant improvement in efficiency was obtained because the left-of-relation was also applied to the protocol, and it is able to precisely report data races for OpenMP programs with a large number of concurrent threads. However, our prior detector may lose its soundness or efficiency when handling general threading models, like Pthread, because it only considers the structured fork-join parallel program model, such as OpenMP.


## 7. Conclusion

There is a trade-off between efficiency and precision in the detection of data races using the happens-before or lockset analysis. FastTrack is the fastest happens-before analysis algorithm to provide comparable performance to the lockset analysis. However, there is still room for improvement, as the algorithm requires some VC operations. In this paper, we presented an improved FastTrack algorithm, called iFT, that uses only the epochs in each access history by applying the left-of-relation. This algorithm is practically sound, needing only an O
(
1
) runtime and memory overhead to maintain an access history and providing similar performance to the well-established FastTrack algorithm.We implemented our algorithm as a Pin-tool on top of the Pin instrumentation framework and compared it empirically with other detection algorithms, including FastTrack. Empirical results from a set of C/C++ benchmarks showed that our iFT algorithm is a practical and sound method for on-the-fly data race detection, reducing the average runtime and memory overhead to 84% and 37%, respectively, of those required by FastTrack. This low overhead of the iFT algorithm is significant, because it can be used for on-the-fly detection based on both happens-before analysis and a hybrid technique, as presented here for an empirical comparison of efficiency. Thus, we believe that the light weight of iFT algorithm can apply to production algorithms which include fault tolerance techniques and testing tools for developing dependable software as well as safety critical software such as avionics and nuclear power systems. Future work will focus on improving the iFT algorithm via a hybrid detection technique, similar to that of AccuLock but without the false positive problem, and the enhancement of precision to handle more variant synchronization primitives, as in ThreadSanitizer.



---

*Source: 205827-2015-07-16.xml*