How Fault Detection Relates to Checkpoint Content

Broadly, there are three kinds of states in a computer system: architectural register files, memory, and I/O state. A checkpoint can comprise one or more of these states. Typically, in a computer system and particularly in a microprocessor, a register file is small and frequently written to. Memory is significantly bigger and committed to either when a store instruction executes and commits its value to memory or an I/O device transfers data to a pre-allocated portion of memory. Finally, the I/O state (e.g., disks) is usually the biggest state in a computer system and usually committed to less frequently than register files or main memory.

What constitutes a checkpoint in a system also depends on where the fault detection point is with respect to when these states are committed. This chapter describes four styles of backward error recovery depending on where the fault detection occurs. These include system where

Output and Input Commit Problems

A system with backward error recovery must also be careful about the output and input commit problems. A recovery scheme can only recover the state of a system within a certain boundary ora sphere of recovery. For example, assume that a sphere of recovery consists only of a processor chip where the fault detection occurs before memory or I/O is committed to. The checkpoint in such a recovery scheme may consist only of processor registers. On detecting an error, the processor reloads its entire state from the checkpoint and resumes execution.

The output commit problem arises if a system allows any output, which it cannot recover from, to exit the sphere of recovery. In the example just described, the processor cannot recover from memory writes it propagates to main memory or I/O operations it propagates to disks because the checkpoint it maintains does not comprehend memory or I/O state. Consequently, to avoid the output commit problem, this system cannot allow any corrupted store or I/O operation to exit the sphere of recovery until it has certified that all prior operations leading to the store or I/O operation are fault free.

Similarly, the input commit problem arises if a system restarts execution from a previous checkpoint but cannot replay inputs that had arrived from outside the sphere of recovery. During the course of normal operation in the example that was just described, a processor will receive inputs, such as load values from the memory system and external I/O interrupts. When the processor rolls back to a previous checkpoint and restarts execution, it must replay all these events since these events may not arrive again. How the backward recovery schemes solve the output and input commit problems is described in this chapter.

Granularity of Fault Detection

To only detect faults in a given domain and reduce the SDC rate, it is often sufficient to do output comparison at a coarser granularity. For example, to prevent corrupted data to exit a processor, one can compare selected instructions, such as stores, that update memory or I/O instructions, such as uncached loads and stores. Once one detects such a fault, one can halt the system and prevent any SDC from propagating to memory or disks. The same granularity of comparison may work for forward error recovery. In a triply redundant system, the component that produces the faulty store output can be identified by the output comparator, isolated, and then restarted using correct state from one of the other two components.

In contrast, the same granularity of fault detection may not work for backward error recovery. If a store output mismatch from two redundant copies is detected, it is not known which one is the faulty copy. Further, checkpoint may not be fault free since the checkpoint may consist of the architectural registers in a processor. A faulty instruction can update the architectural registers, but its effect may show up much later through a store at the output comparator. If the processor is rolled back to a previous architectural checkpoint, it cannot be guaranteed that the checkpoint itself is fault free (Figure 7.2). Hence, backward error recovery to reduce DUE necessitates fault detection at a finer granularity than what is simply needed to prevent SDC.

This chapter discusses several examples of backward error recovery schemes that will highlight different aspects of the relationship between fault detection and checkpoint creation, output and input commit problems, and granularity of fault detection.

Prediction Queue (predQ)

To force both threads to follow the same path, SRTR uses a structure called the prediction queue (predQ) to forward predicted PCs–correct or incorrect—from the leading to the trailing thread (Figure 7.9). The trailing thread uses these predicted PCs, instead of its branch predictor, to guide its instruction fetch. The leading thread must clean up predQ on a misprediction and roll back both its state and the trailing thread’s state. After instructions are fetched, they proceed to the issue queue and the AL.

Active List and Shadow Active List

The AL is a per-thread structure that holds instructions in predicted order. When an instruction is issued and removed from the issue queue, the instruction stays in its AL to allow fault checking. Because SRTR forces leading and trailing threads to follow the same path, corresponding instructions from the redundant threads occupy the same positions in their respective ALs. When the leading thread detects a misprediction, it removes wrong-path instructions from its AL and sends a signal to the trailing thread to do the same. Eventually, instructions commit from the AL in program order.

The SRTR pipeline maintains an additional structure called the SAL. The SAL entries correspond to the ones in the AL. The SAL holds pointers to the LVQ and RVQ entries.

Load Value Queue

The SRTR pipeline maintains the LVQ in the same way the SRT does, except it introduces a level of indirection through the SAL. The SAL maintains pointers to both LVQ and RVQ entries, thereby allowing ease of checking. Further, to facilitate the rollback of the LVQ, branches place the LVQ tail pointer in the SAL at the time they enter the AL. Because the LVQ is in (speculative) program order, the LVQ tail pointer points to the LVQ entry to which the LVQ needs to be rolled back, if the branch mispredicts. A mispredicted branch’s AL pointer locates the LVQ tail pointer in the SAL, and the LVQ is rolled back to the pointer.

Register Value Queue

The SRTR pipeline uses the RVQ to check for faults in nonmemory instructions. After the leading instruction writes its result back into its own copy of the register file, it enters the fault-check stage. In the fault-check stage, a leading thread’s instruction puts its result value in the RVQ using the pointer from the SAL. The instruction then waits in the AL to commit or squash due to faults or mispredictions. Because the fault-check stage is after write-back, the stage does not affect branch misprediction penalty or the number of bypass paths.

The trailing thread’s instructions also use the SAL to obtain their RVQ pointers and find their leading counterparts’ values. Because either the leading or trailing thread—in theory—can reach the RVQ first, the SRTR uses a full/empty bit to indicate the thread that stored its value first in an RVQ entry. When the corresponding instruction from the redundant thread reaches the fault-check stage, it is compared for mismatch with the existing entry. An RVQ entry is relinquished in queue order after the checking is done. To avoid the bandwidth pressure to compare every instruction, Vijaykumar et al. introduced a scheme called DBCE, which was discussed in Chapter 6 (see RMT Enhancements, p. 244).

Recovery in SRTR

Register values, store addresses and values, and load addresses are checked in the RVQ (store buffer) and LVQ, respectively. To facilitate the check, SRTR introduced a structure called the CV. Each entry in the CV corresponds to an entry in the AL. As instructions are placed in the AL, their CV entries are set to a not-checked-yet state. As instructions retire, they are stalled at commit until they are checked. If the check succeeds, the CV entries corresponding to the leading and trailing instructions are set to the checked-ok state. Corresponding instructions from the leading and trailing threads commit only if its CV entry and its trailing counterpart’s CV entry are in the checked-ok state.

If a check fails, the CV entries of the leading and trailing instructions are set to the failed-check state. When a failed-check entry reaches the head of the leading AL, all later instructions are squashed. The leading thread waits until the trailing thread’s corresponding entry reaches the head of the trailing AL before restarting both threads at the offending instruction. Because there is a time gap between the setting and the reading of the CV and between the committing of leading and trailing counterparts, the CV is protected by ECC to prevent faults from corrupting it in the time gap.

There are errors from which SRTR cannot recover: if a fault corrupts a register after the register value is written back (committed), then the fact that leading and trailing instructions use different physical registers allows SRTR to detect the fault on the next use of the register value. However, SRTR cannot recover from this fault. To avoid this loss of recovery, one solution is to provide ECC on the register file.

Triggers and Actions

Mechanisms to reduce exposure to radiation can be characterized in two dimensions: triggers and actions. A trigger is an event that initiates an action to reduce exposure. The goal is to avoid having instructions sit needlessly in processor structures, such as the instruction queue, for long periods of time. Hence, the trigger must be an event that indicates that queued instructions will face a long delay. Cache misses provide such a trigger. Instructions following a load that misses in the cache may not make progress while the miss is outstanding, particularly in an in-order machine. The situation is similar, though not as pronounced, for out-of-order machines in which instructions dependent on a load miss cannot make progress until the load returns data. Hence, it is fair to expect that removing instructions from the pipeline during the miss interval should not degrade performance significantly.

Once the processor incurs a cache miss, one possible action could be to remove existing instructions from the processor pipeline. These instructions can be refetched later when the cache miss returns the data. Such instruction squashing attempts to keep instructions from sitting needlessly in the pipeline for extended periods. To avoid removing instructions that could be executed before the miss completes, the pipeline should squash only those instructions that are younger than the load that missed in the cache. Fetch throttling can also be another action. Fetch throttling prevents new instructions from being added to the pipeline by stalling the front end of the machine.

This section illustrates how to reduce the AVF by squashing instructions in a pipeline (the action) based on a load miss in the processor caches (the trigger). The AVF reduction techniques are illustrated using an instruction queue–a structure that holds instructions before they are issued to the execution units in a dynamically scheduled processor pipeline.

Analyzing Impact on Performance

Traditionally, the terms MTBF and MTTF have been used to reason about error rates in processors and systems (see Metrics, p. 9, Chapter 1). Although MTTF provides a metric for error rates, it does not allow one to reason about the trade-off between error rates and the performance of a processor. Weaver et al. [23] introduced the concept of MITF as one approach to reason about this trade-off. MITF tells us how many instructions a processor will commit, on average, between two errors. MITF is related to MTTF as follows:

As with SDC and DUE MTTFs, one has corresponding SDC and DUE MITFs. Hence, for example, a processor running at 2 GHz with an average IPC of 2 and DUE MTTF of 10 years would have a DUE MITF of 1.3 × 10¹⁸ instructions.

A higher MITF implies a greater amount of work done between errors. Assuming that, within certain bounds, increasing MITF is desirable, then one can use MITF to reason about the trade-off between performance and reliability. Since MITF = 1/(raw error rate × AVF), one has

Thus, at a fixed frequency and raw error rate, MITF is proportional to the ratio of IPC to AVF. More specifically, SDC MITF is proportional to IPC/(SDC AVF), and DUE MITF is proportional to IPC/(DUE AVF). It can be argued that mechanisms that reduce both the AVF and the IPC, such as the one proposed in the previous section, may be worthwhile only if they increase the MITF, that is, if they increase the IPC-to-AVF ratio by reducing AVF relative to the base case to a greater degree than reducing IPC.

Although one can use MITF to reason about performance versus AVF for incremental changes, one needs to be cautious not to misuse it. For example, it could be argued that doubling processor performance while reducing the MTTF by 50% is a reasonable trade-off as the MITF would remain constant. However, this explanation may be inadequate for customers who see their equipment fail twice as often.

Benefits of Pipeline Squash for an Instruction Queue

Table 7.1 shows how the average IPC and average AVFs change when all instructions in the instruction queue are squashed after a load miss in the L1 and the L0 caches [23]. The simulated machine configuration is the same as used in ACE Analysis Using the Point-of-Strike Fault Model, p. 106, Chapter 3. The L0 cache is the smallest data cache closest to the processor pipeline. The L1 cache is larger than L0 but is accessed only on an L0 miss. The SDC arises when the instruction queue is not protected, whereas the DUE arises if the instruction queue is protected with parity.

In this machine, when instructions are squashed on load misses in the L1 cache, the IPC decreases only by 1.7% (from 1.21 to 1.19) for a reduction in SDC and DUE AVFs by 26% (from 29% to 22%) and 18% (from 29% to 1.09%), respectively. However, when instructions are squashed on L0 misses, the IPC decreases by 10% for a reduction in SDC and DUE AVFs of only 35% and 23%, respectively. Squashing based on L0 misses provides a greater reduction in AVF for a correspondingly higher reduction in performance. Nevertheless, squashing on L1 misses appears more profitable because the SDC MITF (proportional to IPC/SDC AVF) and DUE MITF (proportional to IPC/DUE AVF) go up 37% and 15%, respectively.

Gomaa and Vijaykumar [8] studied squashing instructions on an L1 miss for an out-of-order processor. They found that the SDC AVF of the instruction queue of their simulated machine decreases by 21%, which is close to what Weaver et al. [23] reported for an in-order pipeline, shown in Table 7.1. However, Gomaa et al. [9] found that the IPC decreases by 3.5%, which is almost two times higher than that reported by Weaver et al. [23]. This is probably because an out-of-order pipeline can more effectively hide some of the cache miss latency by continuing to issue instructions following the load that missed in the cache. Squashing these instructions that could be issued out of order in the shadow of the load miss would degrade performance. In contrast, an in-order pipeline may not be able to issue instructions in the shadow of a load miss. Therefore, squashing such instructions would not cause significant performance degradation.

Basic Idea

Fault screening is a mechanism that classifies program, architectural, or microarchitectural state into fault free state and faulty state. This is much like screening cancerous cells as benign or malignant. Because fault screening is much like diagnosing diseases from a patient’s symptoms, the mechanism has also been referred to as symptomatic fault detection.

Fault screeners differ from a traditional fault detection mechanism, such as a parity code, in three ways. First, typically traditional fault detectors can precisely detect faults a detector is designed to catch (e.g., single-bit faults). In contrast, fault screeners can only probabilistically identify whether a given state is faulty or fault free at a given point of time.

Second, often a fault detection mechanism is assumed to be fail-stop—that is, on detecting a fault, the detection mechanism works with the processor or OS to halt further progress of a program to avoid any SDC. The probabilistic nature of fault screeners makes it difficult for fault screeners to be fail-stop.

Third, a fault screener can identify propagated faults, whereas often a fault detection mechanism cannot do the same. For example, if a fault occurs in an unprotected structure and then propagates to a parity-protected structure, the parity code cannot detect the fault. This is because the parity is computed on the already faulty bits. A fault screener screens faults based on program behavior and does not rely on computing a code based on incoming values. Hence, fault screeners are adept at identifying faults that propagate from structure to structure.

A fault screener identifies faulty state by detecting departure of program state from expected or established behavior. Racunas et al. [16] refer to such a departure as a perturbation. A perturbation may be natural, resulting from variations in program input or current phase of the application. A perturbation may also be induced by a fault. One can consider a static instruction in an algorithm that generates a result value between 0 and 16 the first thousand times it is executed. Its execution history suggests that the next value it generates will also be within this range. If the next instance of the instruction instead generates a value of 50, this value is a deviation from the established behavior and can be considered a perturbation. The new value of 50 could be a natural perturbation resulting from the program having moved to process a new set of data or it could be an induced perturbation resulting from a fault.

Interestingly, perturbations induced by a fault resulting from a neutron or an alpha particle strike far exceed the natural perturbation in a program. For example, a strike to a higher order bit of an instruction address is highly likely to crash a program, causing an induced perturbation. In the absence of software bugs, such extreme situations are unlikely during the normal execution of a program. The next subsection illustrates this phenomenon.

Natural versus Induced Perturbations

To illustrate how induced perturbations may far exceed natural perturbations, Racunas et al. [16] used departure from a static instruction’s established result value space as an operational definition of a perturbation. Astatic instruction is an instruction that appears in a program binary at a fixed address when loaded into program memory but can have numerous dynamic instances as it is executed throughout a program. For example, incrementing the loop counter in a program loop can be a static instruction, but when it is executed multiple times for each iteration of the loop, it becomes a dynamic instantiation of the instruction. A static instruction’s result value space is the set of values generated by the dynamic instances of that static instruction. Racunas et al. [16] classify this value space into three classes. The first class consists of static instructions each of whose working set of results is fewer than 256 unique values 99.9% of the time. For a static instruction falling into this class, a perturbation is defined as any new result that cannot be found in this array of 256 recently generated unique values.

The second class consists of static instructions whose result values have an identifiable stride between consecutive instances of the instruction 99.9% of the time. Racunas et al. [16] maintain an array of 256 most recent unique strides for each static instruction. Each stride is computed by subtracting the most recent result value generated by the instruction from its current result value. For static instructions falling into this class, a perturbation is defined as any new result that produces a stride that cannot be found in the array of 256 unique strides.

The third class consists of any static instruction not falling into either of the first two classes. For these instructions, the first result value they generate is recorded. Each time a new result value is generated, it is compared to this first result, and any bits in the new result that differ from the first result are identified. A bitmask is maintained that represents the set of all bits that have never changed from the first result value through the entire course of program execution. For this class of static instructions, a perturbation is defined as any new result value that differs from the first result value in a bit location that has previously been invariant. After each perturbation occurs, the bitmask is changed to mark the new bit as a variant. Hence, a static instruction with a 32-bit result can be responsible for a maximum of 32 perturbations in the course of the entire benchmark run. The method of detecting invariant bits in this class is similar to the method of software bug detection proposed by Hangal and Lam [11].

Figure 7.10 compares natural and induced perturbations caught by the fault screening mechanism described. For this graph, Racunas et al. [16] ran each benchmark 10 000 times. On each program run, they picked a random segment of dynamic execution 64 instructions in length. The black bar in the graph represents the number of the 10 000 segments that contain a natural perturbation during the normal run of the benchmark. For example, for SQL, it can be seen that 386 of these 10 000 random segments contain a natural perturbation. Next, they ran the benchmark again, with injecting a fault into the program just before each of the same random segments of execution. The gray bar represents the number of these segments that contain a perturbation after the fault is injected. The graph shows that the number of instances of program perturbations increases more than 30-fold on average in the presence of a fault. This is the fundamental phenomenon that underlies fault screening.

As may be obvious by now, fault screeners are often incapable of distinguishing between natural and induced perturbations. Consequently, the use of such screeners most likely will require an accompanying recovery mechanism to avoid crashing a program in the presence of natural perturbations. Fault screeners are also incapable of catching faults that do not cause program perturbations, unless the fault coincides with an unrelated natural perturbation.

Research in Fault Screeners

Wang and Patel [22] and Racunas et al. [16] have studied several fault screeners and have shown that their screening accuracy may vary between 30% and 75%, as shown in Figure 7.11. Different fault screeners use different history and microarchitecture state to screen faults. For example, the ext-history screener tracks the history of past values seen by a static instruction, the dyn-range tracks the dynamic range of values seen by a static instruction, invar tries to identify bits that are invariant and seen by a static instruction, tlb screens faults based on tlb misses, and bloom uses a bloom filter [5] to screen for errors.

Much research remains in the design and use of fault screeners to make them practical and useful in commodity microprocessors. Wang and Patel [22] studied other screeners, such as cache misses. However, screener design needs refinement and will remain an area of active research. The use of such screeners also needs further investigation. Wang and Patel [22] describe a design called RESTORE, which recovers a processor pipeline from an earlier checkpoint once it screens an error. Racunas et al. [16] propose recovering the pipeline state by flushing the pipeline and restarting it on screening an error.

Also, researchers are yet to evaluate the SER reduction from fault screening. Prior investigation has only evaluated the accuracy of fault screeners using fault injection into committed instruction state. This needs to be translated into an SER for bits in a chip. The difficulty is that the ACE analysis described in Chapter 3 cannot be used directly to evaluate the SER from fault screeners. This is because ACE analysis tries to abstract the SER from a single fault free execution. In contrast, fault screeners are only activated in the presence of a faulty symptom. Hence, without fault injection, it may be difficult to model the SER of a chip using a fault screener.

Structure of the History Buffer

The history buffer consists of a table with a number of entries. Each entry contains information pertinent to a retired instruction, such as the instruction pointer, the old destination register value, and the physical register to which the destination architecture register was mapped. The instruction pointer can be either the program counter or an implementation-dependent instruction number. The old destination value records the value of the register before this instruction rewrote it with its destination register value. Finally, the register mapping is also needed to identify the physical register that was updated. The number of entries in the history buffer is dependent on the implementation and must be chosen carefully to avoid stalls in the pipeline. The history buffer mechanism can work with many fault detection mechanisms, such as Lockstepping and SRT, which detect faults after register values have been committed.

Adding Entries to the History Buffer

When an instruction retires, but before it writes its destination register to the register file, an entry is created in the history buffer, and the entry’s contents are updated with the instruction pointer, old register value, and register map. Reading the old register value may require an additional read port in the register file. An additional read port may increase the size of the register file and/or increase its access time. Nevertheless, there are known techniques to avoid this performance loss (e.g., by replicating the register file). In effect, by updating the history buffer when an instruction retires, an incremental checkpoint of the processor state is created.

Freeing up Entries in the History Buffer

When a retired instruction passes its fault detection point, the corresponding entry in the history buffer is freed up. This is because the checkpoint corresponding to an instruction that has been certified to be fault free is no longer needed.

Recovery Using the History Buffer

If the fault detection mechanism detects a fault in a retired instruction, then the recovery mechanism kicks in. The following are the steps involved in recovering a processor that uses SRT as its fault detection mechanism:

Fingerprint Mechanism

A fingerprint provides a concise view of the past and present program states. It contains a summary of the outputs of any new register values created by each executing instruction, the new memory values (for stores), and the effective addresses (for both loads and stores). By capturing all updates to architectural state, a fingerprint can ensure that it can help create a fault free checkpoint. It should be noted that this implementation of fingerprinting allows not only register values to be committed to the register file but also memory values to be committed to the processor caches. Nevertheless, the caches are not allowed to write back their modified data to main memory till the fault check has been done.

For fault detection with RMT processors, the fingerprint implementation must monitor only committed register values. However, for fault detection with Lockstepped processors, the fingerprint implementation can monitor both speculative and committed updates to the physical register file since both Lockstepped processors are cycle synchronized.

To create the fingerprint, Smolens et al. [19] propose hashing the generated values into a cyclic code. There are two key requirements for the code. First, the code must have a low probability of undetected faults. Second, the code should be small for both easy computation and low bandwidth comparison. For a p-bit CRC code, the probability of an undetected error is at most 2^−p. Smolens et al. [19] used a 16-bit (p = 16) CRC code for their evaluation. A 16-bit CRC code has a 0.000015 probability that an error will go undetected. The reader is referred to Cyclic Redundancy Check, p. 178, Chapter 5, for a discussion on CRC codes.

Evaluation Methodology

To evaluate chip-external fault detection using fingerprinting for full-state comparison, Smolens et al. [19] simulated the execution of all 26 SPEC CPU 2000 benchmarks using SimpleScalar sim-cache [6] and two commercial workloads—TPC-C and SPECWeb—using Virtutech Simics. The simulated processor executed one IPC at a clock frequency of 1 GHz. The only microarchitecture parameter relevant to this evaluation was the level 2 (L2) cache configuration. The simulated processor has an inclusive 1-megabyte four-way set-associative cache with 64-byte lines.

The benchmarks used for evaluation can be classified into three categories: SPEC integer, SPEC floating point, and commercial workloads. Using the prescribed procedure from SimPoint [14], the authors simulated up to eight predetermined 100 million instruction regions from each SPEC benchmark’s complete execution trace. Using Simics, the authors ran two commercial workloads on Solaris 8: a TPC-C-like online transaction processing (OLTP) workload with IBM DB2 and a SPECWeb. The 100-client OLTP workload consisted of a 40-warehouse database striped across five raw disks and one dedicated log disk. The SPECWeb workload serviced 100 connections with Apache 2.0. The authors warmed both commercial workloads until the CPU utilization reached 100% and the transaction rate reached steady state. Once warmed, the commercial workloads executed for 500 million instructions.

Bandwidth Required for Full-State Comparison Using Lockstepped Processors

Smolens et al. [19] evaluated fault detection mechanisms based on their state-comparison bandwidth demand between mirrored processors. The bandwidth required for off-chip comparison is calculated as the sum of the address and databus traffic from off-chip memory requests. The average chip-external bandwidths generated by the three simulated application classes—SPEC CPU 2000 integer (SPEC CINT), SPEC CPU 2000 floating-point (SPEC CFP), and commercial—were

Whether Lockstepped or RMT systems can handle these full-state comparison bandwidths will depend on the exact system configuration.

Full-state comparison without fingerprinting uses the entire register file contents and all cache lines modified since the last checkpoint. The number of updated cache lines, however, grows slowly as the checkpoint interval is increased because of spatial locality. Assuming that the full-state comparison bandwidth amortizes over the entire checkpoint interval, the required bandwidth decreases as the checkpoint interval increases. In Figure 7.12, the average bandwidth requirement decreases sharply as the checkpoint interval increases. However, for the range of intervals compatible with I/O interarrival times of commercial workloads (hundred to thousands of instructions), the required bandwidth remains above several hundred megabytes per second.

Fingerprinting provides a compressed view of the architectural state changes and significantly reduces this bandwidth pressure. Instead of comparing every instruction result, fingerprinting compares only two bytes per checkpoint interval. The bandwidth overhead for fingerprint comparison is thus orders of magnitude less than full-state comparison. Assuming a 1000-instruction checkpoint interval on a 1000-MIPS processor, fingerprinting consumes just 2 megabytes per second.

 Load values, since memory contents may be modified external to the sphere of replication by other processors or I/O devices

 Asynchronous interrupts

 Timing-dependent operations, such as ones that read on-chip cycle counters.

Fault Detection, Checkpointing, and Logging

As discussed earlier (RMT within a Single-Processor Core, p. 227, Chapter 6), an SRT processor’s performance advantage over Lockstepping comes from doing the fault detection in the larger SRT-Memory sphere. Nevertheless, when checkpoints are created, it may also be necessary to check them for faults. That is, all new register values from the two redundant threads must be compared for mismatch. In the absence of a mismatch, they can be sent to the ECC-protected checkpoint storage. Because the checkpoint includes the state of the architectural register file, fault detection during checkpoint creation is similar to the checking required for the smaller SRT-Register’s sphere used in SRTR. However, the logging mechanism may avoid the performance problems suffered by SRTR due to limited slack. The log of external events, such as loads and asynchronous interrupts, ensures that the internal state of the machine at the point of a detected fault can be reproduced starting from the last checkpoint. This capability decouples the fault detection in SRT-Memory (used to verify data sent out externally) from the fault detection in SRT-Register (used to validate checkpoints).

This decoupling has two effects. First, checkpoint validation is not in the critical path of the program execution and thus can be done at leisure and in the background. Second, the log-based method does not have to create checkpoints corresponding to every output point. Rather, checkpoints can be created at any desired frequency. As discussed above, decreases in checkpoint frequency come at the cost of increased log storage and increased recovery latency.

Handling Faults in Nonrecovery Mode

In such a design, during normal execution (i.e., in a nonrecovery mode), an output mismatch for data exiting the SRT-Memory sphere (e.g., in a store address or in a value) indicates the presence of a fault. Then, both the leading- and the trailing-thread contexts are flushed because one cannot tell the thread that contains the fault. Both thread contexts are reloaded from the latest complete checkpoint. Then execution is resumed in recovery mode in which both the threads are driven by the saved event log.

This recovery mode is indistinguishable from the normal operation for the trailing thread but is distinct for the leading thread. Thus, for example, leading thread loads will be satisfied from the log rather than from the data cache, as in a normal operation. These recovery operations continue until all outputs generated since the checkpoint have been regenerated. This point is detected by maintaining a counter that tracks the number of outputs generated since the previous checkpoint, decrementing this counter for each regenerated output and exiting recovery mode when the counter reaches zero. The regenerated outputs, such as stores, are discarded because they have already been exposed outside the SRT-Memory.

Handling Faults during Checkpoint Creation

Checkpoint creation may occur either continuously in the background or at periodic intervals. Register values from both threads are compared for mismatch. In the absence of any mismatch, the outputs are committed to the external checkpoint storage. However, on a mismatch, both threads are flushed and restored to the previous complete checkpoint. Then the same procedure is followed as outlined earlier. It should be noted that external checkpoint storage must be capable of storing a full valid checkpoint until a subsequent checkpoint can be fully validated, potentially requiring twice the capacity of the architectural register file.

Handling Faults during Recovery Mode

Faults could occur during the recovery procedure itself. To detect these faults, one can run both the leading and trailing threads and compare both threads’ outputs that leave the SRT-Memory sphere. A detected fault during recovery mode could imply the presence of a permanent fault, when one could flag this to the OS to let it decide future action. Alternatively, if system designers believe that transient faults could be likely in such a situation, then they could simply restart both the redundant threads from the last checkpoint and run them off the saved event log.

Logging Loads Using the LVQ

As discussed earlier, the log required for recovery is a simple extension of the input replication mechanism already needed by an SRT processor to provide fault detection. Hence, one can leverage the input replication mechanisms, which recreate nondeterministic events from the leading thread in the trailing thread, to handle these same events for recovery. RMT replicates load values from the leading to the trailing thread using an LVQ. The LVQ is a queue of load values as seen by the leading thread. Loads from the trailing thread obtain their values from the LVQ instead of the data cache.

Extending the LVQ for recovery consists of maintaining LVQ entries after the trailing thread has consumed them until a checkpoint is completed. If checkpoints are frequent, entries may be kept in the same physical LVQ structure used for input replication. Otherwise, a larger log may be required, when LVQ entries may be copied from the primary LVQ to a separate recovery-only LVQ structure. Because the performance of recovery may not be critical, the recovery LVQ may be larger, slower, and farther from the core than the replication LVQ. Even if a single physical structure is used, it is useful to logically distinguish replication LVQ entries (which have not been consumed by the trailing thread) from recovery LVQ entries (which have been consumed by the trailing thread but are not yet incorporated in the latest checkpoint).

Logging Asynchronous Interrupts

Asynchronous interrupts are replicated in an SRT processor by logging the point in the dynamic instruction stream at which the interrupt is taken in the leading thread and by generating the interrupt at the same point in the trailing thread, or by forcing the thread copies to synchronize to the same execution point and delivering the interrupt simultaneously. In the former scenario, asynchronous interrupts could be logged and replayed in the same manner as loads. The mechanism for generating interrupts from the log can leverage the logic used to generate interrupts in the trailing thread in a normal operation. In the latter scenario, interrupts are not stored and transferred between threads, so there is no mechanism to leverage. In this case, a more direct approach would be to force a check point after the threads synchronize, eliminating the need to log interrupt events. Other nondeterministic events should be addressed on a case-by-case basis, though this framework of leveraging the replication mechanism for logging (or forcing checkpoints) should apply in general.

Distributed Parity

ReVive implements distributed parity to both detect faults and recover from errors in its distributed memory, which serves both as the main memory and as a part of the checkpoint. The scheme is similar to what is used in RAID (Redundant Array of Inexpensive Disks) systems. As Figure 7.15 shows, in ReVive, memory is organized as parity groups, where a memory block in one node contains the parity bits corresponding to the data bits for the other nodes. Thus, a parity bit P in the memory block holding parity can be computed as P = A XOR B XOR C, where A, B, and C are the corresponding data bits in each of the other memories.

When a memory write occurs in a specific memory block, the corresponding controller sends the XOR of the original parity bits and the newly created parity bits for the memory block that was just written to the memory that holds its parity bits. Assume the new parity bit is C′. Then the controller holding C sends an update U = C XOR C′ to the controller with the parity bit. The reader can easily verify that the controller with the parity bits can compute the new parity bit simply as P′ = P XOR U. Using this distributed parity scheme, ReVive can completely recover from single-bit transient faults in its memory system and from the complete loss of a node’s entire memory.

Logging Writes

ReVive must keep track of the first write to any memory block since the last checkpoint was created. When it detects a write, it copies the old value into a log and writes the new value to memory. Then, on detecting a fault, it can simply use the log to reset the values of all blocks to recreate the checkpoint and restart execution.

Typically, cache-coherent, shared-memory multiprocessors implement a single-writer invalidation protocol, which allows multiple readable copies of a memory block, but only one node can write the block at any time. To write a block, a node must have the only copy of the block and must be its exclusive owner. Before a block transitions from readable to exclusive, the corresponding node must request an exclusive write access to this block. This makes it easy for a memory controller to detect a node’s intention to write a memory block. At that point, the memory controller can save the old value of the memory block in the log.

To only log the first write to block after a checkpoint, ReVive augments its blocks with an additional bit—called the log bit–beyond what may be needed by the coherence protocol. The log bit tracks first writes to a block after a checkpoint. If the log bit is set, then ReVive will not copy the block’s old value to the log when a write request comes. The log bits are reset when a checkpoint is created.

Global Checkpoint Creation

To create the global checkpoint, ReVive follows a simple two-phase protocol. First, all processors and nodes synchronize and flush all their caches to write all modified data back to memory. Then the processors synchronize again to ensure that all processors have completed writing all their data back to memory. All the log bits are also cleared at this time. The checkpoint is now established, and all processors can resume execution. Because an error may occur during the creation of a checkpoint, ReVive does not discard the old log till all processors complete the two-phase protocol.

Creating Consistent Checkpoints

In SafetyNet, all nodes periodically take local checkpoints at a globally synchronous logical time. The local checkpoint is a combination of the processor’s architectural state and a log of first memory writes since the last checkpoint was initiated. To ensure that the local checkpoints reflect a consistent system state, SafetyNet exploits the key insight that, in retrospect, a coherence transaction appears logically atomic once the entire coherence transaction has completed. A transaction’s point of atomicity can be established when the previous owner of the requested block processes the request. For example, in Figure 7.16, the point of atomicity could be T1. Node 0 sends a request to the previous owner (Node 1). Node 1 establishes the point of atomicity at T1 and forwards its last checkpoint number (checkpoint #2) to Node 0 as its checkpoint number for the point of atomicity. Node 0, the requestor, does not learn the location of the atomicity point until it receives the response that completes the transaction. To ensure that the system never recovers to the “middle” of a transaction, the requestor does not advance the recovery point until all its outstanding transactions complete successfully. After completion, the transaction appears atomic.

Advancing the Global Recovery Point

At any point of time, SafetyNet maintains a combination of local checkpoints that constitute a consistent global state, which is referred to as the global recovery point. As each node creates local checkpoints, one must advance the global recovery point, so that each node can free up the storage for its prior local checkpoints. Further, any I/O operation can be performed only after a global recovery point is established.

For a checkpoint interval to be fault free, no fault detector in the system should signal an error and every transfer of ownership in that interval must complete successfully. This ensures that the data were transferred fault free to the requestor. Once every component has independently declared that it has received fault free data in response to all its requests in the interval before the checkpoint, the global recovery point can be advanced. At this point, all transactions prior to this checkpoint have had their points of atomicity determined. Then the state for the prior recovery point can be deallocated lazily. One can establish this global recovery point in the background to avoid slowing down the main computation.

The latency to establish the global recovery point depends on the fault detection latency. Some faults that manifest themselves as corrupted messages can be caught immediately through CRC codes, which are often used to protect network messages. Other faults, such as dropped messages, may have to rely on timeout latency that can be many traversals of the interconnect.