Performance Optimizations for Compiler-based Error Detection

3.1
Motivation
3.1.1
Limitations of Instruction-level Error Detection
Figure 3.1 summarizes the main concept of instruction-level error detection as it is
described in Sections 2.2.2 and 2.4. The frequent checks (compare and jump instruc-
tions) break the original code into a sequence of small basic-blocks with two outgoing
edges each. In Figure 3.1, the original basic-block BB1 is split into three smaller ones:
BB1a, BB1b and BB1c (Figure 3.1.b). The performance bottleneck of this scheme is
shown up as what we call basic-block fragmentation.
This problem has two main factors:
29

30
Chapter 3. DRIFT
BB1b
BB1c
code
checking
replicated code
original code
original execution
exit edge
fragmentation
basic−block
(a)
(b)
BB1a
BB1
BB1a
(c)
BB1b
BB1c
Figure 3.1: The basic-block fragmentation of the synchronized scheme. (a) Code with-
out error detection (b) Synchronized thread-local instruction-level error detection (b)
Decoupled thread-local instruction-level error detection.
•
The new basic-blocks (BB1a, BB1b and BB1c in Figure 3.1.b) usually have a
small number of instructions. Therefore, a basic-block scheduler does not have
enough instructions to improve instruction-level parallelism (ILP).
•
The checks create new edges in the control-flow. For each check, an exit edge
is added. The new edge connects the current basic-block with the basic-block
that invokes the error handling routine. The complex control-flow due to the
checks acts as a scheduling barrier for the instruction scheduling optimization
(e.g., trace scheduling). Even with a speculative scheduler that schedules regions
of multiple basic-blocks [31][36][44][46][54][53], the control edges limit the
scheduler’s ability to hoist instructions across the basic-blocks. As a result, the
scheduler cannot extract adequate amounts of ILP. Any state-of-the-art region-
based instruction scheduler has some limitations in hoisting instructions across
basic-blocks:
– It cannot hoist instructions with side-effects over branches since this can
break the program semantics. This restricts the hoisting of system calls,
and store instructions [36, 44].

3.1. Motivation
31
STOP
YES
(a)
(b)
STOP
YES
NO
NO
EXECUTE
EXECUTE
REPLICATED
EXECUTE
REPLICATED
EXECUTE
ERROR
?
COMPARE
ERROR
?
COMPARE
Figure 3.2: The code execution of synchronized (a) and decoupled (b) error detection
schemes.
– If there is no hardware support for deferring exceptions then potentially
faulting instructions such as loads and divisions cannot be hoisted either
[45].
As a result, the scheduler generates poorly performing code with low ILP. For this
reason, basic-block fragmentation becomes a performance bottleneck for instruction-
level error detection. We will quantify this effect in Section 3.3.2.
3.1.2
Synchronized versus Decoupled Error Detection
In instruction-level error detection, the checks are synchronization points where the
execution of the code is checked for errors. For this reason, this technique is called
synchronized error detection
. In the extreme case, the checks occur after the execution
of every instruction. However, as we have already discussed, it suffices if they occur
before every non-replicated instruction (i.e., an instruction whose effect escapes the
sphere of replication). In Figure 3.2.a, it is shown that the original and the replicated
code are executed synchronously. The execution of the program is interrupted by the
checks. After confirming that the code is not affected by any error, the execution
resumes. Therefore, the execution of the synchronized error detection follows the
cycle execute-check-confirm-execute. In this way, the synchronized error detection
guarantees fail-stop capability to the program.
In thread-local instruction-level fault tolerance, the execute-check-confirm-execute

32
Chapter 3. DRIFT
original code
replicated code
checking code
r2 = r1 + 100
r200 = r100 + 100
r2 = r1 + 100
BB1:
BB1a:
[r2] = 1000
r3 = [r2]
r3 = r3 + 64
cmp r2, r200
jmp
[r2] = 1000
[r3] = 2000
r3 = [r2]
r3 = [r2]
r300 = r300 + 64
r3 = r3 + 64
cmp r3, r300
jmp
BB1b:
BB1c:
[r3] = 2000
r200 = r100 + 100
r2 = r1 + 100
BB1a:
cmp r2, r200
[r2] = 1000
r3 = [r2]
r3 = [r2]
r300 = r300 + 64
r3 = r3 + 64
cmp r3, r300
jmp
jmp
BB1b:
BB1c:
[r3] = 2000
detect
detect
(a)
(b)
(c)
detect
detect
break the control−
flow semantics
Figure 3.3: The original code (a) is transformed by synchronized (b) and decoupled
(c) error detection schemes. The synchronized scheme cannot be optimized further
because the compiler should respect the program semantics. The decoupled scheme
breaks the control-flow semantics and optimizes the code.
cycle manifests itself as the basic-block fragmentation problem. The solution is to
break this cycle by decoupling the execution of the original and replicated code from
the checks (Figure 3.2.b). Decoupling reduces the impact of basic-block fragmentation
as the checks are pushed off the critical path, leading to longer stretches of instructions
to execute. This reduces the error detection overhead and boosts the performance of the
program. Such performance improvement may come at the expense of reduced fault
coverage since the program loses its fail-stop capability. However, as shown previously
(e.g., [101]), and as our experiments will demonstrate, the impact on fault-coverage is
often negligible.
3.2
DRIFT
In this thesis we propose DRIFT, an error detection scheme that addresses the short-
comings of the synchronized error detection scheme, as described earlier. DRIFT in-
troduces decoupling in instruction-level error detection by relaxing the execution of
the checks. Instead of synchronizing before every non-replicated instruction through
a check operation, DRIFT groups the checks and executes them later. In Figure 3.1.c,
it is shown that the checks are grouped together and they are pushed to the end of the
basic-block. In this way, DRIFT does not fragment the original basic-block (Figure
3.1.a) into smaller ones (Figure 3.1.b) and it enables the scheduler to do its job better.
DRIFT is based on three ideas:

3.2. DRIFT
33
i. Optimized control-flow: Modifying the control-flow of the application can en-
hance the ability of the instruction scheduler to optimize the code and reduce the
impact of basic-block fragmentation. Since instruction schedulers are not as ef-
fective across basic-blocks as within basic-blocks, larger basic-blocks are better
(higher ILP). This can be done by decoupling the execution of checks and by
executing them later together as a group. By contrasting Figure 3.1.b versus Fig-
ure 3.1.c, we observe that DRIFT generates a much more instruction-scheduler
friendly code than the synchronized scheme.
ii. It is acceptable to break the semantics of the combined original and replicated
code, as long as the semantics of the original code are respected.
The jump in-
structions due to checks force the compiler to apply conservative code motion
optimizations (Section 3.1.1) because the scheduler should respect the program se-
mantics. The compiler does not know that transient errors are exceptional events.
Thus, it does not understand that these branches are not usually taken and the pro-
gram mostly follows the error-free execution. This unawareness of normal com-
pilers to the semantics of error detection code is the main reason why the compiler
cannot automatically generate decoupled code (like the one DRIFT generates) out
of the synchronized code. Therefore the code of Figure 3.1.c cannot have been
generated by any compiler optimization. Breaking the semantics in a controlled
way is required for modifying the code in such an aggressive way. Figure 3.3
shows how our scheme breaks the control-flow semantics of the code. In synchro-
nized thread-local error detection, the errors are detected on time (Figure 3.3.b).
However, the original execution is interrupted by the checks which have negative
impact on execution time since the compiler cannot deal with the frequent check-
ing code (the compiler generates code with poor ILP, Section 3.1.1). On the other
hand, if we relax the execution of the checks (detection of the errors) by break-
ing the strict control-flow semantics, then the original execution can be decoupled
from checking code. In this way, the compiler can extract more ILP and the code
can run faster (Figure 3.3.c).
iii. DRIFT’s decoupled semantics have little to no effect on fault-coverage. As shown
in [101], modifying the semantics of the application with error detection support,
such that the checks are decoupled from the execution, has a minimal impact on
the effectiveness of error detection. This is because in the usual case, the increased
delay between the error and its detection is not great enough to let the error propa-

34
Chapter 3. DRIFT
r3=r2+100
r20=r10+16
[r20]=r3
r4=r2+200
r3=r4+r5
r30=r10+32
[r30]=r3
r3=r2+100
r20=r10+16
[r20]=r3
r4=r2+200
r3=r4+r5
[r30]=r3
r30=r10+32
original code
original execution
0
1
2
3
BB1
BB1
before scheduling
Code without Error Detection
after scheduling
Figure 3.4: The code before and after instruction scheduling for the original code without
error detection.
gate to the output (Figure 3.3.c). Moreover, it has been shown in [25][41][93] that
a significant number of errors such as ISA-defined exceptions can be detected by
the operating system. This is a fundamental feature of DRIFT, which guarantees
its high fault-coverage despite the modified semantics that allow better perfor-
mance.
3.2.1
DRIFT Motivating Example
The following example presents the original code in Figure 3.4 and the transformation
of the code after the insertion of the error detection code from SWIFT and DRIFT
(Figures 3.5 and 3.6 respectively). Each figure shows the code before instruction
scheduling (left) and the scheduling table (right) of a hypothetical 4-issue machine
which supports predication. The outcome of compare instructions is kept in predicate
registers.
The following observations can be made:
•
The overhead of the replicated code is less significant than the jump instructions.
In Figure 3.4, it is shown how the original code is scheduled. The dependences
between the instructions do not allow the compiler to fully benefit from the avail-
able hardware parallelism in the architecture. The empty slots are filled with
the replicated and checking code as it is shown in Figure 3.5. In this way, the
overhead of redundant code is partially hidden. Applications with low ILP can
efficiently hide the error detection overhead in processors with even moderate
amounts of parallelism.
•
Basic-Block Fragmentation:
The checks act as fragmentation points for the

3.2. DRIFT
35
BB2
BB3
0
4
1
2
3
5
6
7
BB1
BB2
BB3
BB4
BB5
r3’=r2’+100
r3=r2+100
r20’=r10’+16
r20=r10+16
cmp p1,p0=r3,r3’
(p1) jmp
cmp p2,p0=r20,r20’
(p2) jmp
[r20]=r3
r4’=r2’+200
r4=r2+200
r3’=r4’+r5’
r3=r4+r5
r30’=r10’+32
r30=r10+32
cmp p3,p0=r30,r30’
(p3) jmp
cmp p4,p0=r3,r3’
(p4) jmp
[r30]=r3
(p3) jmp
r3=r4+r5
cmp p3,p0=r30,r30’
[r20]=r3
r30’=r10’+32
r30=r10+32
(p2) jmp
r3’=r4’+r5’
(p1) jmp
cmp p1,p0=r3,r3’
cmp p2,p0=r20,r20’
r3’=r2’+100
r3=r2+100
r20’=r10’+16
r4=r2+200
r4’=r2’+200
r20=r10+16
cmp p4,p0=r3,r3’
(p4) jmp
[r30]=r3
8
BB5
BB4
before scheduling after scheduling
SWIFT − Synchronized Error Detection
original code
replicated code
checking code
exit edge
intra−block transfer
error−free execution
BB1
Figure 3.5: The code before and after instruction scheduling for the synchronized
scheme (SWIFT).

36
Chapter 3. DRIFT
cmp p2,p0=r20,r20’
[r20]=r3
r4’=r2’+200
r4=r2+200
r3’=r4’+r5’
r3=r4+r5
r30’=r10’+32
r30=r10+32
cmp p3,p0=r30,r30’
cmp p4,p0=r3,r3’
[r30]=r3
(p1) jmp
(p2) jmp
(p3) jmp
(p4) jmp
[r20]=r3
r3’=r4’+r5’
r3=r4+r5
r30’=r10’+32
r30=r10+32
cmp p3,p0=r30,r30’
cmp p4,p0=r3,r3’
[r30]=r3
(p1) jmp
(p2) jmp
(p3) jmp
0
1
2
7
BB1
r3’=r2’+100
r3=r2+100
r20’=r10’+16
r20=r10+16
cmp p1,p0=r3,r3’
cmp p1,p0=r3,r3’
cmp p2,p0=r20,r20’
r3’=r2’+100
r3=r2+100
r20’=r10’+16
r4=r2+200
r4’=r2’+200
r20=r10+16
(p4) jmp
BB4
before scheduling after scheduling
BB2
BB3
BB4
3
4
BB1
BB2
5
6
BB3
DRIFT − Decoupled Error Detection (4 checks are grouped)
original code
replicated code
checking code
error−free execution
exit edge
Figure 3.6: The code before and after instruction scheduling for the DRIFT scheme. In
this example four checks are clustered together.

3.2. DRIFT
37
control-flow graph and they split the code into numerous basic-blocks. For
example, the original code of Figure 3.4 is a single basic-block, but the error
detection code of Figure 3.5 spans over 5 basic-blocks (BB1-BB5).
The key difference between the synchronized scheme (Figure 3.5) and the DRIFT
scheme (Figure 3.6) is the amount of fragmentation of the basic-blocks. The syn-
chronized case is the most fragmented one, as checks are regularly injected into
the code (see Figure 3.5 left). On the other hand, DRIFT groups together multi-
ple checks. In the example of Figure 3.6, it groups 4 checks together which are
placed at the end of the basic-block.
•
Performance and Schedule:
The impact of basic-block fragmentation is shown
at the left in Figures 3.5 and 3.6. In the synchronized case, the checks fragment
the code (see Figure 3.5 left) and the instructions are isolated in small basic-
blocks. DRIFT clusters the checks at the end of the basic-block. In this way, all
the instructions remain in the original basic-block (see Figure 3.6 left).
An intra-block scheduler schedules the instructions of each basic-block. Then,
an inter-block scheduler hoists as many instructions as possible across the basic-
blocks in order to improve the ILP. The inter-block transfers are marked with
green. The synchronized scheme is fragmented as jump instructions introduce
edges into the control-flow. These edges prohibit aggressive code hoisting in
several cases. For example, “[r20]=r3” of BB3 cannot be hoisted into BB2 or
BB1 as it has side-effects (writes to memory) and the compiler cannot guarantee
that this instruction will be executed (the execution might follow another control
path). For this reason, the compiler will break the program semantics if it hoists
the store instruction in another basic-block. For the same reason, “r[30]=r3” of
BB5 cannot be hoisted either. These factors prohibit the scheduler from taking
advantage of the available ILP. The produced schedule is full of NOP instruc-
tions.
Removing the code motion restrictions of the synchronized scheme, the schedule
improves considerably. For example, in Figure 3.6, all instructions are within a
single basic-block (BB1) which makes it straight-forward for any scheduler to
parallelize. In this way, DRIFT produces scheduler-friendly code which can be
more easily optimized. As it is shown in Figure 3.6, the scheduler exploits all
the available ILP and it produces a compact schedule.

38
Chapter 3. DRIFT
original code
replicated code
checking code
r2 = r1 + 100
r3 = r3 + 64
[r3] = r2
r4 = r2 + 100
r5 = r4 + 100
r6 = r3 + 64
[r6] = r5
r200 = r100 + 100
r2 = r1 + 100
r300 = r300 + 64
r3 = r3 + 64
cmp r6, r600
jmp
[r6] = r5
r4 = r2 + 100
r400 = r200 + 100
[r3] = r2
cmp r2, r200
cmp r3, r300
r500 = r400 + 100
r5 = r4 + 100
r600 = r300 + 64
r6 = r3 + 64
cmp r5, r500
jmp
jmp
jmp
jmp
r200 = r100 + 100
r2 = r1 + 100
cmp r3, r300
[r3] = r2
r400 = r200 + 100
r4 = r2 + 100
r300 = r300 + 64
r3 = r3 + 64
cmp r2, r200
jmp
r500 = r400 + 100
r5 = r4 + 100
r600 = r300 + 64
r6 = r3 + 64
cmp r5, r500
jmp
cmp r6, r600
jmp
[r6] = r5
r200 = r100 + 100
r2 = r1 + 100
r300 = r300 + 64
r3 = r3 + 64
cmp r2, r200
cmp r3, r300
[r3] = r2
r400 = r200 + 100
r4 = r2 + 100
r500 = r400 + 100
r5 = r4 + 100
r600 = r300 + 64
r6 = r3 + 64
cmp r5, r500
cmp r6, r600
[r6] = r5
jmp
jmp
jmp
jmp
BB1:
BB1b:
BB1d:
BB1a:
BB1b:
BB1d:
BB1c:
BB1a:
BB1c:
BB1e:
BB1e:
BB1a:
BB1b:
BB1d:
BB1c:
(a)
(b)
(c)
(d)
Figure 3.7: In this example, decouple factor 3 (c) and 4 (d) have similar impact on the
original code (a). In this way, the decoupled scheme prevents basic-block fragmen-
tation and creates large basic-blocks. On the contrary, the synchronized scheme (b)
fragments the code and creates small basic-blocks with few instructions.
3.2.2
Decouple Factor
To better study the impact of decoupling on performance, we introduce the concept
of decouple factor. This metric describes the number of checks that are clustered
together. As explained in Section 3.1, DRIFT relaxes the execution of the checks by
grouping them together. Each group of checks contains up to N number of checks. We
refer to this as decoupling N checks or setting the decouple factor to N. Therefore, the
decouple factor is a knob that controls the number of checks that are executed together
in a group. As the decouple factor increases, more checks are grouped together, and
the effect of basic-block fragmentation is reduced.
Figure 3.7 shows how decouple factor works. In Figure 3.7.c, the decouple fac-
tor is three. Thus, three checks are clustered together. Similar to synchronized error
detection (Figure 3.7.b), the checks split the basic-block in five smaller basic-blocks.
But, in Figure 3.7.c, the original basic-block has more instructions. In this example,
decouple factor three and four (Figures 3.7.c and 3.7.d) have similar impact on basic-
block fragmentation. Both configurations keep the majority (or all) the instructions in
the original basic-block. Moreover, in this example, a decouple factor of two produces

3.2. DRIFT
39
almost the same code as the synchronized error detection technique. In general, the
synchronized error detection is represented by a decouple factor of one.
Increasing the decouple factor has three side-effects:
i. For small values of the decouple factor, the program has similar (though slightly
better) behavior to the synchronized error detection and suffers from basic-block
fragmentation. As the decouple factor increases, more checks are clustered to-
gether giving the scheduler the freedom to schedule the instructions more effi-
ciently and improve the ILP.
ii. Performance is not always improved as the decouple factor increases. On the
contrary, there is a chance to degrade performance due to hardware congestion.
For large values of the decouple factor, many checks are executed later in the code.
Therefore, the distance between the definition and the use of a value increases as
the decouple factor increases. For large values of the decouple factor, more values
are kept in the register file for a longer period of time. This might lead to predicate
register pressure which can cause performance degradation if it results in register
spilling. Another factor that increases the probability of hardware congestion is
the large number of consecutive compare instructions. In this case, there might not
be enough units to deal with them in a timely manner. As a result, the compare
instructions might stall until a unit is available.
iii. According to the value of the decouple factor, the checks might not be emitted
before the non-replicated instructions. In Figure 3.7.d, the checks are emitted
after all the instructions of the basic-block. Thus, if the check executes much
later (large values of decouple factor), we slightly increase the risk of allowing
erroneous data to propagate to memory and corrupt the output of the program.
As a result, it is not easy to predict which value of the decouple factor is the best.
There is a trade-off between the number of checks that are decoupled, the hardware
capacity and the fault-coverage. We explore the effect of the decouple factor on both
performance and reliability in Section 3.3.