软件实现的软差错检测和恢复技术

饶盛原

摘要：软差错被认为是现代微处理器可靠性所面临的最主要的挑战，由于软件实现的软差错检测和恢复技术不需要额外的物理资源并能适用于现在已存在的处理器，因此受到了众多科研人员的关注。该文按照不同的实现层级对现有的一些经典技术方案进行了收集，简要介绍其原理与实验效果，并在文末对不同层级技术的优缺点进行了比较分析。

关键词： 软差错； 软件容错； 检测和恢复

中图分类号：TP3 文献标识码：A 文章编号：1009-3044（2019）04-0080-04

1概述

随着芯片密度的不断增加，现代微处理器更容易受到各种干扰而产生软差错，虽然没有造成硬件的永久性故障，但是软差错的发生很有可能会影响到程序的正常运行。针对软差错的检测和恢复研究已开展了很多年，也产生了很多可用的技术，这些技术按照实现方式可以分为硬件实现的和软件实现的两类。由于硬件实现的技术需要对硬件的设计进行修改或增加特殊的检测和恢复设备，需要较高的实现成本。而软件实现的方式不需要额外设备，并且能较好地支持现有处理器等优点，吸引了众多学者对其进行研究。

本文主要对近20年来经典的软件实现的软差错检测和恢复技术进行了总结，并按照不同的实现层级，分为指令级、源代码级、线程级和进程级等几大类

2 指令级冗余实现的软差错检测和恢复

经过数十年的研究，众多学者提出了多项通过指令冗余实现的软差错检测和恢复技术，其中Stanford大学CRC（Center for Reliable Computing）中心于2002年提出的针对软差错造成的数据流错误的EDDI（Error Detection by Duplicated Instructions）[1]方法和针对软差错造成的控制流错误的CFCSS（Control Flow Checking by Software Signatures） [2]方法是其中的典型代表；在此之后Princeton大学的Reis G A等人结合EDDI和CFCSS方法提出了同时具有检测数据流错误和控制流错误的SWIFT（Software Implemented Fault Tolerance） [3]方法；为了能够对检测到的软差错进行恢复，Reis G A等人又在SWIFT的基础上实现了SWIFT-R[4]方法。最近两年，Didehban M等人针对SWIFT和SWIFT-R中存在的一些缺陷进行优化，分别实现了nZDC[5]方法和NEMESIS[6]方法。这些方法的发展过程如图1所示，下面将对这些方法进行介绍。

2.1 EDDI

EDDI是在程序编译时对程序的指令进行复制，将原程序的每条指令（Master Instruction， MI）都复制成一个副本指令（Shadow Instruction， SI）加入原程序当中，然后在存储和分支指令之前加入比较指令（Comparison Instruction， CI），用以比较MI和SI的执行结果，如果执行结果不一致即表示检测到程序数据流错误。一段经EDDI处理的加法指令示例如图2所示。

通过注入单粒子翻转故障，将未经过EDDI方法处理过的原程序和经过EDDI方法处理后的程序进行了比较，发现经过EDDI方法处理后的程序，将程序的平均出错率由20%降到了1.5%。同时EDDI也使得处理后的程序由于程序类型的不同，执行时间增加了13%～105.9%，程序的大小增加了44%～113%。

2.2 CFCSS

CFCSS是在程序编译时，根据每一个基本块中除最后一条指令外，块内顺序执行指令这一原则，将程序划分为多个基本块，为每一个基本块生成一个唯一的数字标签S（Signature），并且在每个基本块的开始的地方加入两条特殊指令。其中一条指令负责根据刚刚执行完的基本块和下一个要执行的基本块的S生成新的动态标签G，并由一个名为GSR（General Signature Register）的寄存器进行保存，另一条指令负责将G与当前基本块的S进行比较，如果不一致则表示检测到程序控制流的错误。

CFCSS是一种比较高效的检测方法，只需要在原程序中插入较少的检测指令就可以检测到软差错引起的控制流错误。但是CFCSS方法的主要缺陷在于不能检测出基本块内部发生的控制流错误，同时由于動态标签G的生成算法在生成过程中可能会导致G与错误基本块的S一致，从而发生检测混淆和检测出错的现象，这也是CFCSS算法的一个缺点（针对这一缺点，一些学者提出了ICFCSS等方法对其进行改进）。故障注入实验的结果表明：在未经过CFCSS方法处理的程序中，33.7%的分支故障会导致程序出错，经过CFCSS方法处理后的程序则只有3.1%的分支故障会导致程序出错。同时CFCSS也使得处理后的程序由于程序类型的不同，执行时间增加了16%～69%，程序大小增加了26%～64%。

2.3 SWIFT

EDDI与CFCSS结合能够检测到软差错导致的数据流错误和控制流错误，SWIFT将EDDI和CFCSS进行了整合，并对这两种方法进行了优化。其中最主要的改进在于SWIFT认为存储器已经通过ECC或奇偶校验码等机制进行了保护，从而不考虑内存发生故障的情况。因此，SWIFT将从内存读取出的数据复制一份，然后与EDDI一样插入副本指令进行冗余计算，再在存储指令之前将所存数据进行一致性的检测。和EDDI相比，SWIFT只使用了一半的内存，访问内存的操作也减少了一般，因此对性能有了很大的提升。针对控制流的错误，SWIFT采用的方法与CFCSS类似，不同之处在于SWIFT使用了一个专门的寄存器“sigoff”来保存在生成G过程中产生的中间值。但是SWIFT同样没有解决无法检测出基本块内部的控制流错误这一缺点。

通过注入单粒子翻转故障，将通过SWIFT方法处理后的程序和经过EDDI+ECC+CFE方法处理后的程序进行了比较，发现经过SWIFT方法处理后的程序能够检测到70%的故障，同时程序大小平均比采用EDDI+ECC+CFE方法的程序小15%，执行时间也比采用EDDI+ECC+CFE的程序少51%。

2.4 SWIFT-R

SWIFT方法只具有软差错的检测能力，而SWIFT-R在SWIFT的基础上使其具备了恢复能力。SWIFT-R将指令的冗余变成了三份，然后对三个版本指令的执行结果进行比较，出现两份或以上一致的结果则判断为正确的结果，然后对错误副本的指令执行结果进行恢复。

通过注入单粒子翻转故障，发现SWIFT-R方法能够减少89.4%的故障，同时将程序的执行时间增加了99%。

3 源代码级冗余实现的软差错检测和恢复

由于源代码级冗余实现软差错检测和恢复会产生过多冗余代码，并且使得性能损失严重，通过此方法实现的软差错检测和恢复的研究并不多。典型性的方法有意大利都灵理工大学的A Benso等人于2000年提出的RECOO[8]、M Rebaudengo等人于2001年提出的ThOR[7]以及Stanford大学CRC实验室于2002提出的ED4I[9]。这些方法的发展过程如图4所示，下面将对这些方法进行介绍。

3.1 ThOR

ThOR在源程序预编译时复制源程序中每一条语句，然后加入将计算结果进行比较的语句，用于判断是否出现错误。ThOR的基本转换规则如下：1.对每一个变量都进行复制；2.每一个对于变量的读、写等操作同样需要在副本上进行；3.在对变量进行读、写之后需要将其与副本进行比较来检测它的正确性。此外，原程序中的函数调用参数和返回值也要进行冗余备份。

通过注入单粒子翻转故障，发现经过ThOR方法处理的程序，能够检测到64.4%的数据流错误。与未经过ThOR方法处理的程序相比，程序的执行时间平均延长了3.62倍，程序的大小平均增加了3.89倍。

3.2 RECOO

RECOO是一个针对C和C++程序的编译工具，其目标是检测发生在内存、寄存器等存储部件中的数据错误。该工具的基本思想是通过复制变量来实现错误的检测：变量每次被赋予新值的时候均会产生其副本变量，然后在对每一个变量进行读操作的时候或者该变量不再使用时，将变量与其副本进行比较。在对变量进行复制的时候，可以考虑根据考虑变量的存在时间和对其他变量对其的依赖性计算其可靠性权重，然后可以根据可靠性权重决定是否对该变量进行复制，以减少程序的大小和缩短程序执行的时间。

故障注入实验的结果表明：当使用RECOO复制程序中30%的变量时，能减少68%的FSVs（Fail-Silent Violations），复制70%的变量时，能减少89%的FSVs。同时，复制30%变量时，程序的执行时间增加6%，程序的大小增加18%；复制所有变量时，程序的执行时间增加16%，程序的大小增加37%。

3.3 ED4I

ED4I利用了数据多样性来检测程序错误。其通过将程序中的变量和常量同时乘以一个相同的多样性因子k，使其转换为具有相同功能的不同程序，由另一个同时运行的程序比较他们的结果或是在程序执行结束时比较两个版本的程序输出结果之间是否相差k倍。k的取值对ED4I的效果产生很大的影响，实验证明当k取-2 时取得了较为理想的效果。

4 线程级冗余实现的软差错检测和恢复

随着多核平台的迅猛发展，出现了一些多核平台下基于软件或硬件实现的软差错检测和恢复方法，软件实现的方法中具有典型性的有Intel公司于2007年提出的SRMT（Software-based Redundant Multi-Threading） [10]和Princeton大学的Yun Zhang等人于2012年提出的DAFT（Decoupled Acyclic Fault Tolerance） [11]。这些方法的发展过程如图7所示，下面将对这些方法进行介绍。

4.1 SRMT

SRMT是在编译的过程中为程序生成一个主线程（leading thread）和一个伴随线程（trailing thread），两个线程执行的计算操作相同。同时，主线程除了执行原有的计算操作之外，还需要与伴随线程进行通信；而伴随线程除了重复执行主线程的计算操作之外，还需要在某些恰当的位置将两个线程的执行结果进行比较。对于访问共享内存和执行I/O操作的系统调用等不可重复的计算全部都有主线程完成，但是这种操作执行之前需要获知伴随线程的比较结果，从而保证此时线程状态的正确性。经SRMT处理后的程序执行过程如图8所示。

通过注入单粒子翻转故障，发现SRMT对于基准程序集SPEC2000中的整型和浮点程序的故障覆盖率为99.98%和99.6%，具有非常高的覆蓋率。但是由于主线程和伴随线程需要大量的通信，使用多核处理器的硬件通信队列将使得程序执行的时间增加19%，使用软件实现的通信队列将使得程序执行的时间增加186%。

4.2 DAFT

DAFT的基本思路与SRMT相同，但是DAFT中采用了许多消除线程间进行同步检查的操作，如采用特殊的异常处理机制区分异常和软差错、对IO的内存映射地址着重保护等方法减少主线程的等待，使主线程能够顺畅运行，从而降低了程序运行时间。

通过注入单粒子翻转故障，发现经DAFT处理后的程序在SPEC2000和SPEC2006进行实验时，运行时间平均增加了38%，程序大小平均变为原来的2.4倍，同时还有99.93%的故障覆盖率。

5 进程级冗余实现的软差错检测和恢复

在多核平台下，还可以在进程级实现软差错的检测和恢复。A Shye等人于2009年提出的方法PLR[12]就是一种典型的进程级冗余实现的软差错检测和恢复方法。PLR的整体结构如图9所示。PLR方法在程序被执行前创建一个监控（Monitor）进程，然后把应用进程复制n次（n为2时进行故障检测，n等于3时可以进行故障的检测和修复），其中一个为主进程（Master Process），其他为从属进程（Slave Processes）。在实际运行过程中，只有主线程能够通过syscall emulation层执行真正的系统调用，从属进程执行仿真的系统调用。syscall emulation层还实现错误检测和恢复，所有的系统调用参数都需要进行比较以确保正确，系统调用的返回结果要被复制给每一个从属进程。在将进程进行复制之后，原进程就成了一个名义进程（Figurehead Process），它不执行实际的程序，只是在等待冗余进程执行结束，或者是在monitor的帮助下将收到的外部信号广播给冗余的进程。

针对软差错的检测，PLR是通过以下三种方式：1）在syscall emulation层，通过比较输出结果，将会检测到软差错导致的不正确的输出。2）通过Watchdog超时检测控制流出错误，如软差错导致的控制流错误，调用了错误的系统调用，在syscall emulation层中，通过与其他进程进行比较便能发现出现错误；或是软差错导致其中一个进程进入死循环等进程挂起情况。在下一个系统调用期间，除了挂起进程之外的所有進程都将结果传送至syscall emulation层中，最终会导致超时。3）软差错导致非法指令、总线错误等故障导致的程序失效，这些程序失效产生的外部信号将会由名义进程进行检测。故障注入实验的结果表明，PLR的软差错检测和恢复能力都能达到硬件容错技术的水平，对于四路的对称多处理器（SMP），PLR只导致程序运行的时间增加了16.9%。

6 软件实现的软差错检测和恢复技术比较

根据对软件实现的软差错检测和恢复技术的介绍，我们分别从能处理的错误类型、针对软差错的检测和恢复能力，还有其对性能的影响等方面对上述方法进行比较。

指令级冗余实现的软差错检测和恢复技术大多都具有较强的检错能力，并且这种方法的性能开销相对适中。由于这类方法进行的是指令级的冗余，因此该方法能够对软错误进行精确定位，进而以细粒度的方式来进行软错误恢复。这些优点也是此类方法被广泛研究的原因。

源代码冗余实现的软差错检测和恢复技术的检错能力较为一般。同时，由于这类方法进行冗余的粒度较大，因此性能开销也比较大，并且不能精确定位软差错的发生，不过该方法是在源代码级别上进行的冗余，因此其实现也相对较为容易。

线程级冗余实现的软差错检测和恢复技术的故障覆盖率较高，但是这种方法需要多核处理器的支持，因此只能应用与多核平台。此外由于这类方法中主线程和伴随线程需要频繁进行通信，因此对系统的性能有较大的影响。同时，由于这类方法是在线程级别进行软差错的检验，因此在考虑对此类方法的添加软差错恢复能力的时候，只能通过粗粒度的方法进行错误恢复。

进程级冗余实现的软差错检测和恢复技术的故障覆盖率也比较高，但是这种方法同样只能应用与多核平台。同时，这类方法针对软差错的恢复，也只能在进程级别进行恢复。

参考文献：

[1] Oh N， Shirvani P P， Mccluskey E J. Error detection by duplicated instructions in super-scalar processors[J]. IEEE Transactions on Reliability， 2002， 51（1）：63-75.

[2] Oh N， Shirvani P P， Mccluskey E J. Control-flow checking by software signatures[J]. IEEE Transactions on Reliability， 2002， 51（1）：111-122.

[3] Reis G A， Chang J， Vachharajani N， et al. SWIFT： software implemented fault tolerance[C]// International Symposium on Code Generation and Optimization. IEEE， 2005.

[4] Chang J， Reis G A， August D I. Automatic Instruction-Level Software-Only Recovery[J]. IEEE Micro， 2007， 27（1）：83-92.

[5] Didehban M， Shrivastava A. nZDC： a compiler technique for near zero silent data corruption[C]// Design Automation Conference. IEEE， 2016.

[6] Didehban M， Shrivastava A， Lokam S R D. NEMESIS： A software approach for computing in presence of soft errors[C]// 2017 IEEE/ACM International Conference on Computer-Aided Design （ICCAD）. ACM， 2017.

[7] Rebaudengo M， Reorda M S， Torchiano M， et al. A source-to-source compiler for generating dependable software[C]// IEEE International Workshop on Source Code Analysis & Manipulation. IEEE， 2001.

[8] Benso A， Chiusano S， Prinetto P， et al. A C/C++ Source-to-Source compiler for dependable applications[C]// International Conference on Dependable Systems & Networks. IEEE， 2000.

[9] Oh N， Mitra S， Mccluskey E J. ED4I： Error detection by diverse data and duplicated instructions[J]. IEEE Transactions on Computers， 2002， 51（2）：180-199.

[10] Wang C， Kim H S， Wu Y， et al. Compiler-Managed Software-based Redundant Multi-Threading for Transient Fault Detection[C]// International Symposium on Code Generation & Optimization. IEEE Computer Society， 2007.

[11] Zhang Y， Lee J W， Johnson N P， et al. DAFT： Decoupled Acyclic Fault Tolerance[C]// International Conference on Parallel Architectures & Compilation Techniques. IEEE， 2010.

[12] Shye A， Blomstedt J， Moseley T， et al. PLR： A Software Approach to Transient Fault Tolerance for Multicore Architectures[J]. IEEE Transactions on Dependable and Secure Computing， 2009， 6（2）：135-148.

【通联编辑：梁书】