Information Technology Reference
In-Depth Information
Algorithm 1.
The GPU kernel for the H-B comparison between CPU cores
X
and
Y
.SIG
X
and SIG
Y
corresponds to signature from CPU
X
and CPU
Y
.The
algorithm is explained in Section 3.2. Custom kernel synchronization function
gpu sync() and function
concurrent()
are discussed in Section 3.2.
Data
: Memory access signatures (SIG).
Result
: Flagged data race conditions.
while
(1)
do
if
isNew(
SIG
X
)
then
for
each current
SIG
Y
do
if
concurrent(
SIG
X
,SIG
Y
)&&(
SIG
X
∩
SIG
Y
=
NULL)
then
Flag data race condition;
end
end
mark SIG
X
for graduation;
end
gpu sync();
end
3.2
GPU-Side Actions
The happened-before comparisons of the signatures generated by the SG is performed
by a GPU kernel. In a nutshell, each signature from a particular CPU thread is compared
with each concurrent signature from all other CPU threads. If the intersection of the
concurrent signatures is not
NULL
, we have a potential data race condition. Figure 3(b)
shows the signature table with entries for an
n
-core CPU. Entries for processors CPU
X
and CPU
Y
are marked. Each entry in the signature table, say SIG
X
0, consists of a read
(RD
X
) signature and a write (WR
X
) signature along with the epoch start (
TS
1) and end
(
TS
2) timestamps. Since a read-after-read access is not potentially harmful, we have
to compare only three signature combinations for CPUs X and Y: RD
X
-WR
Y
,WR
X
-
RD
Y
,andWR
X
-WR
Y
. These combinations are indicated in the figure. This signature
comparison is extremely parallel and we utilize the data-parallel architecture of GPU to
perform these comparisons.
Algorithm 1 shows the GPU kernel algorithm for GUARD. The GPU threads monitor
the signature table for new incoming signatures. Once a new signature entry (SIG
X
)is
identified, the GPU thread iterates through each of the current SIG
Y
entries present
in the signature table. Potential data race is identified if the
intersection
of concurrent
signatures is not
NULL
. Timestamp information embedded in the signature is used to
test the concurrency of these signatures using the function
concurrent()
. Bitwise
AND
operation is used to efficiently calculate the intersection of the signatures. When a data
race condition is identified, information related to the race condition such as thread
and epoch numbers is written to the data race table. Once the GPU thread has iterated
through all the current SIG
Y
signatures, it marks SIG
X
for graduation and moves on to
the next SIG
X
. The signature marked for graduation can now be overwritten by CPU
X
with new signature.
