一种基于还原程序的硬件故障检测方法

摘要

本发明公开了一种基于还原程序的硬件故障检测方法，目的是加大源程序和冗余程序运行时的时空差异性，克服数据溢出等问题，提高瞬时故障和永久性故障的故障检测率。技术方案是遍历源程序，对源程序进行预处理后，找出源程序中的原子数据，构造原子数据表和数据指令关联表；接着将源程序划分为若干可还原程序块，构造可还原程序块表和控制流图，并为每个可还原程序块构造运算关系图；然后为每个可还原程序块找出最优还原路径；最后在每个可还原程序块中插入容错指令，将插入容错指令后的源程序编译为目标代码。采用本发明可以检测出瞬时故障和永久性故障，提高故障检测率，克服数据溢出问题，且节省存储资源。

主权项

一种基于还原程序的硬件故障检测方法，其特征在于包括以下步骤：第一步，遍历源程序，对源程序进行预处理，方法是：1.1判断源程序中是否存在源、目的操作数相同的指令，即格式为R＝R OP R1的指令，OP表示一个可还原运算指令对应的操作码，R和R1均为寄存器，如果存在则执行第1.2步，否则转第1.3步；1.2用中间数据保存指令R2＝R+0，R＝R2 OP R1替换源、目的操作数相同的指令R＝R 0P R1，R2为新分配的寄存器；1.3判断源程序是否存在定点除法指令，如果存在则执行第1.4步，否则转第1.5步；1.4在定点除法指令前插入求余指令，利用求余指令rem＝R1％R2保存除法操作的余数；1.5判断源程序是否存在数据传送指令，即格式为R1＝R2的指令，如果存在则执行第1.6步，否则转第二步；1.6用加法指令R1＝R2+0替换数据传送指令R1＝R2；第二步，找出源程序中的原子数据，构造原子数据表和数据指令关联表，方法是找出源程序中作为寄存器型操作数和立即操作数的原子数据；原子数据是指由寄存器、存储器等存储单元记录、在指令中不可再分的数据，数据指令关联表存放每条可还原运算指令及其操作的原子数据信息，包括指令编号及作为源、目的操作数的原子数据编号；这一步包括以下步骤：2.1寻找源程序中的原子数据，构造原子数据表，方法如下：2.1.1将源程序中不同的立即操作数确定为不同的原子数据，为不同的原子数据分配不同的原子数据编号，并将每个原子数据的以下信息存入原子数据表：原子数据编号，驻留寄存器，驻留状态；其中，驻留寄存器信息设置为空，驻留状态设置为驻留中；2.1.2对源程序中目的操作数为寄存器类型的指令，将指令向目的操作数寄存器中写入的数据确定为原子数据，为不同的原子数据分配不同的原子数据编号，并将每个原子数据的以下信息存入原子数据表：原子数据编号，驻留寄存器，驻留状态；其中，一个原予数据a的驻留寄存器即为指令写入a的寄存器，每个原子数据驻留状态信息设置为未驻留； 2.2构造数据指令关联表，具体方法如下：2.2.1对于任意一条可还原运算指令I，将指令向目的操作数寄存器写入的原子数据确定为I的目的操作数对应的原子数据；2.2.2若指令I的一个源操作数B是立即操作数，则将立即操作数对应的原子数据确定为B对应的原子数据；2.2.3若指令I的一个源操作数C是寄存器操作数，则从当前指令向前寻找最近向该寄存器中写入数据的指令，将找到的这条指令写入的原子数据确定为C对应的原子数据；2.2.4判断是否已找出所有可还原运算指令的目的操作数和源操作数对应的原子数据，如果是则将可还原运算指令的指令编号、目的操作数对应的原子数据编号、源操作数对应的原子数据编号存放到数据指令关联表，执行第三步，否则转第2.2.1步；第三步，将源程序划分为若干可还原程序块，构造可还原程序块表和控制流图；可还原程序块是顺序执行的可还原运算指令的极大集合，控制流只能从可还原程序块的入口和出口进出，并且可还原程序块内除最后一条指令外都必须是可还原运算指令；可还原程序块表则专门存放每个可还原程序块的信息，包括可还原程序块的块编号、入口和出口地址；控制流图是以可还原程序块为结点，以可还原程序块之间的控制流关系为边的图；插入到每个可还原程序块内的还原运算指令序列定义为对应的还原程序块；这一步包含如下步骤：3.1确定各个可还原程序块的入口指令；3.2对每个入口指令，确定其对应的出口指令；3.3每个入口指令和其对应的出口指令之间的程序块为一个可还原程序块，为每个可还原程序块分配一个块编号，并将块编号和入口、出口地址存入可还原程序块表；3.4构造程序的控制流图，方法是：分析每个可还原程序块的出口指令，如果是转移指令，则存在当前可还原程序块到转移目标所在的可还原程序块之间的控制流关系；如果不是转移指令，则存在当前可还原程序块到下一条指令所在的可还原程序块之间的控制流关系；将可还原程序块作为结点，如果一个结点到另一个结点有控制流关系，则产生前一个结点到后一个结点的一条有向边；第四步，为每个可还原程序块构造运算关系图，运算关系图以单层二叉树为基本构件，反映可还原程序块内原子数据之间的运算关系；单层二叉树是只含一个父结点和其 子结点的二叉树，即高度为2的二叉树；一个可还原程序块的运算关系图的构造方法是：4.1对可还原程序块内的每条可还原运算指令，查找数据指令关联表，得出其源、目的操作数对应的原子数据编号，分别为每条可还原运算指令构造一棵单层二叉树，父结点代表目的操作数信息元组，包括目的操作数对应的原子数据编号，当前指令编号，子结点代表源操作数信息元组包括源操作数对应的原子数据编号，当前指令编号；4.2结合数据指令关联表，查找可还原程序块内所有具有如下关系的可还原运算指令对：一条指令I1的源操作数B对应的原子数据编号和另一条指令I2的目的操作数对应的原子数据编号相同；对每个这样的指令对，将指令I2的二叉树作为一个结点替代指令I1的二叉树中源操作数B对应的子结点，这样，I1和I2的二叉树合并得到一个子图；4.3结合数据指令关联表，查找可还原程序块内所有具有如下关系的可还原运算指令对：一条指令I1的源操作数B对应的原子数据编号和另一条指令I2的某个源操作数对应的原子数据编号相同；对每个这样的指令对，在对应的两个二叉树中，将B对应的子结点作为两个二叉树的公共子结点，同时删除I2对应的二叉树中原子数据编号和B相同的子结点，这样，I1和I2的二叉树合并成为一个子图；4.2和4.3所得的子图和其它单层二叉树一起构成可还原程序块的运算关系图；第五步，为每个可还原程序块找出最优还原路径即包含还原运算指令最多的还原路径，步骤如下：5.1找出当前可还原程序块使用的寄存器：在可还原程序块表中查找当前块的入口和出口，确定当前可还原程序块中包含的指令，然后在数据指令关联表中查找出当前可还原程序块中包含的指令关联的所有原子数据，最后在原子数据表中找出这些原子数据驻留的寄存器，找出的寄存器即称为当前可还原程序块使用的寄存器；5.2找出所有初态数据：对每一个当前可还原程序块使用的寄存器R，查找可还原程序块内第一个使用寄存器R的指令，将该指令中R对应的原子数据定义为当前可还原程序块的初态数据，利用数据指令关联表找出所有初态数据；5.3找出所有终态数据：对每一个当前可还原程序块使用的寄存器R，查找可还原程序块内最后一个使用寄存器R的指令，将该指令中R对应的原子数据定义为当前可还原程序块的终态数据，利用数据指令关联表找出所有终态数据；5.4更新原子数据表：在原子数据表中，将所有终态数据对应的寄存器驻留状态设置为驻留中，将除立即操作数外的所有非终态数据的驻留状态设置为未驻留；5.5按以下步骤找出当前可还原程序块的局部最优还原路径并存入还原路径信息表； 一个可还原程序块的多个还原路径构成集合S，局部最优还原路径是S的某个子集的最优还原路径，可还原程序块的最优还原路径是所有局部最优还原路径中最优的；5.5.1检索当前可还原程序块的运算关系图，从尚未产生还原运算指令的单层二叉树中找出当前所有满足下述特征的单层二叉树作为备选的单层二叉树：设一个单层二叉树的父结点和子结点分别为A、B、C，对应的操作是A＝B OP C，A结点对应的原子数据的寄存器驻留状态为驻留中，且B、C中至少有一个结点对应的原子数据的寄存器驻留状态为驻留中；5.5.2从备选的单层二叉树中选择符合条件的树A′＝B′OP C，并为选择出的树产生还原运算指令B′＝A′ROP C′，将产生的所有还原运算指令按产生的顺序加入临时还原指令表L，并将原子数据表中还原运算指令的目的操作数B′对应的原子数据驻留状态更新为驻留中，将B′对应寄存器中其它原子数据的驻留状态更新为未驻留；5.5.3判断是否运算关系图中所有单层二叉树都有对应的还原运算指令，如果是则执行第5.5.4步，否则转到第5.5.1步；5.5.4找出局部最优还原路径并存入还原路径信息表：对L中的还原运算指令序列，在其包含的所有可能的错误传播路径A→B→D…M中找出最长的错误传播路径，将最长的错误传播路径对应的还原运算指令序列作为局部最优还原路径存入还原路径信息表；5.6判断是否已找出所有局部最优还原路径，如果是则执行第5.7步，否则转第5.5步；5.7找出最优还原路径：比较得出还原路径信息表中最长的还原运算指令序列，即得当前可还原程序块的最优还原路径；第六步，在每个可还原程序块中插入容错指令，过程如下：6.1构造初态数据备份指令：找到第五步中找出的最优还原路径的最后一个错误传播点，该错误传播点即为需要备份的初态数据，分配缓冲区并产生存储指令备份需要备份的初态数据；6.2构造终态数据备份指令：找出在最优还原路径中被重写的终态数据，基于控制流图，利用编译技术中的活跃变量分析方法，找出被重写的终态数据中在当前可还原程序块内最后两条指令之间的位置活跃的数据，产生存储指令在缓冲区备份这些活跃的且被重写的终态数据；一个数据a在位置t处活跃是指位置t后存在指令使用数据a； 6.3构造实现如下功能的检查点指令：如果当前可还原程序块执行的是定点运算，比较备份的初态数据和还原的初态数据是否相等，如果相等则执行后面的指令，否则报告错误并跳出程序；如果当前可还原程序块执行的是浮点运算，则设定误差允许范围，并比较备份的初态数据和还原的初态数据之间的差别是否小于误差允许范围，如果是则执行后面的指令，否则报告错误并跳出程序；6.4构造数据恢复指令：利用读指令实现从缓冲区中恢复第6.2步备份的数据；6.5在可还原程序块中按下列顺序依次插入容错指令：初态数据备份指令→可还原运算指令序列→终态数据备份指令→最优还原路径→检查点指令→数据恢复指令→可还原程序块最后一条指令；第七步，将插入容错指令后的源程序编译为目标代码，在目标平台上运行此代码，实现执行程序功能和检测平台故障。