Software-Based Techniques

Following the state-of-the-art review, the next step is to implement fault tolerance techniques. We will start by explaining in detail and implementing two known software-based techniques, called Variables and Inverted Branches (AZAMBUJA 2010b), which will later be used as a complement to hybrid fault tolerance techniques. These techniques have been proposed in the past years and achieved high fault detection rates at low performance degradation levels and therefore are useful not only as an introduction to software-based fault tolerance techniques, but also to be combined with hardware-based and hybrid techniques. Then, three novel hybrid techniques will be proposed and implemented, based on both software and hardware replication characteristics. The three hybrid techniques will be divided into their software and hardware sides and described in detail, concerning both operation description and implementation. 

Fault tolerance techniques aiming to detect transient effects can be mainly divided in three broad categories (1) software-based techniques, (2) hardware-based techniques and (3) l brid techniques. Fault tolerance techniques can be applied at different levels of implementation, starting from the software level down to the architecture description level, the logical and transistor level, until the layout level. In this book, we will focus on hybrid techniques applied at software level. 

The result from the use of hybrid techniques is high efficiency, since they can provide a high level of confiability while minimizing the introduced overhead. They also offer low development time (from the software-based techniques) and small performance degradation (from the hardware-based techniques). As drawbacks, they requite the application source code (in order to transform it), which is not always available, and require changes, at least, in the system s architecture. 

Software-based techniques to detect control flow errors differ from data flow because of one main reason, which is control flow techniques can be optimized. Data flow techniques always have to replicate data (registers, variables or memory positions) and compare it, while control flow techniques can analyze the code, comprehend it and optimize the replication and comparison. Most control flow techniques perform an analysis on the program s execution flow, divide the program irrto Basic Blocks (BB) and parse the program flow as a graph between different nodes (BBs). A BB is defined as a sequence of consecutive instmctions that are always executed sequentially, meaning that the control flow always enters a BB in the first instmctions and leaves at the end of it. 

In order to improve CEDA, Vemu (2007) proposed ACCE and ACCE with Duplication (ACCED). They use the same detection capabilities from CEDA, but improve it by allowing error correction. Despite being unable to mitigate all control flow errors, ACCE imposes low laterrcy for error correction with performance overhead of about 20%. The otdy issue that remains is that neither ACCE nor ar r software-based technique is able to detect intra-node control flow errors, or in other words, faults causing control flow errors inside the same BB. 

As stated in the previous Chapters, software-based techniques are unable to detect all faults affecting the control flow, while hardware-based techniques cannot protect processors without at least doubling its area. On the other hand, combined into hybrid techniques, they can not only present increase their detection rates, but also be optimized into achieving a better tradeoff between area overhead and performance degradation, and fault detection. 

In the following sections, we will present the HPCT tool to automatically transform program codes into hardened ones, two known software-based techniques, called Variables and Inverted Branches, and three novel hybrid techniques to detect transient faults in embedded processors, named PODER, OCFCM, and HETA, combined with the previous known software-based techniques. 

The PODER technique is the first novel hybrid technique presented in this book. It was initially based in the CCA technique and its two-element queue to keep track of the changes in the program s control flow, called BID and CFID. The technique aims at detecting a few types of control flow errors, such as (1) incorrect jumps to the beginning of a BB, (2) incorrect jumps inside the same BB, (3) incorrect jumps to unused memory addresses, and (4) control flow loops. It is important to mention that PODER cannot detect errors in branch instructions, where a path should have been taken, but was not taken, and vice versa. In order to do so, it must be combined with the Inverted Branches software-based technique, described previously in Sect. 4.3. 

An incorrect jump to the same BB is an issue that cannot be solved purely by software-based techniques. The main problem is that the granularity required for that is at instmction level, while jumps to different BB require BB granularity. In order to detect errors inside the same BB, software-based technique would have to duplicate every instmction, which would lead to huge performance losses. From the related software-based techniques, none could detect such kind of error. 

In order to detect such errors, PODER uses the communication between software-based techniques and hardware-based techniques. It does so by calculating a second signature for each BB, called XOR, during compilation time (by the software-based techniques), and during runtime (by the hardware module). The XOR value equals to the result of the operation exclusive OR (XOR) between all the instmctions from the BB. 

Tables 4.3 and 4.4 show the original and modified program s execution time, code size, and data size for the matrix multiplication and bubble sort algorithms, respectively. They present results for the original unhardened program, as well as the version hardened with PODER and hardened with PODER combined with the Inverted Branches and Variables software-based techniques (Combined Techniques).

OCFCM itself is defined as a non-intrasive hardware module and therefore corrld be considered a pure hardware-based technique. Irrstead, OCFCM alone cannot achieve its main objective, which is detecting control flow errors. To do so, it has to be complemented by the Inverted Branches software-based technique (described in Sect. 4.3) and configured by the apphcation running in the processor. Because of these characteristics, it is considered as a hybrid farrlt tolerant technique, even if not as tightly coupled with the software-side as PODER. 

Software-based program code transformation it is rrsed to corrligirre the OCF-CMs and perform small transfomratiorrs in the program code, if necessary. Also, other software-based techniques are rrsed to complemerrt OCFCM s detection capabilities. 

The innovation of this approach relies on the use reconfigurability and software-based techniques to use different application-specific non-intrasive hardware mod-... 

The software-based side on OCFCM is responsible for choosing which module will be active (when using a set of OCFCM) and performing the transformation on the software that implements the Inverted Branches software-based technique. It also has to guarantee that the program code does not use jumps with dynamic destina-... 

Hybrid Error-detection Technique using Assertions (HETA) is the third and final hybrid technique presented in this book. It was initially based in the CEDA software-based technique and its abiUty to efiSciently detect control flow errors between different BBs, and PODER and its ability to detect control flow errors inside the same BB. HETA is aimed at both FPGAs and ASICs, since it implements a non-intrasive hardware module combined with transformation rules on the program code. 

It is important to note that HETA, like PODER and OCFCM, cannot detect incorrect but legal jumps (according to the program graph). In order to do that, the Inverted Branches software-based technique, described in Sect. 4.3 is required. Also, HETA may present aliasing, when the program code has many BBs. With big apphcations, some signatures may start to repeat themselves and an error may not be detected by the technique. 

Like PODER and OCFCM, HETA can also detect control flow loops (4). In order to detect this kind of error, a watchdog timer is implemented. The counter is reset every time the software-based technique side enters a BB, by performing a Reset XOR instruction. When the counter overflows, an error is flagged. By doing so, the hardware module can detect a control flow loop that causes the execution flow to be stuck at a single instruction. 

Such results show that software-based techniques combined with HETA can be used in harsh environments and allow designers to reach fast fault diagnosis and correction. When comparing to hardware-based techniques, such as Xilinx Triple Modular Redundancy (XTMR) with scmbbing, that require modifications to the microprocessor s hardware, we can notice an area reduction higher than 66% and still acceptable fault coverage of 96.9%. On the other hand, the hardened application takes 1.48 times the original time to execute and 6.5 % more area to implement the OCFCM hardware module. 

In order to perform the experiments presented in this Chapter, we implemented the miniMIPS hardened with the novel hybrid HETA technique and the software-based techniques Variables and Inverted Branches on both flash-based and SRAM-based FPGAs. We visited three facilities, used two types of energetio particles, and performed tests for SEE and TID. In the following, each radiation experiment and its results are diseussed in detail. 

Detected faults errors detected by the software-based technique and HETA s hardware module that did not affect the matrix multiplication result ... 

CHIELLE, E. AZAMBUJA, J. BARTH, R. ALMEIDA, E KASTENSMIDT, E. Evaluating Selective Redundancy in Data-flow Software-based Techniques. IEEE Transactions On Nuclear Science, Los Alamitos, USA IEEE Computer Society, 2013. 

---