错误流模型:硬件故障的软件传播建模与分析

无论是可靠性工程还是软件可靠性中的可靠性模型,都难以描述硬件故障在程序中的传播问题.首先建立了计算数据流模型,并以无穷存储机器的指令集为例,说明可以为任意程序建立计算数据流图.在计算数据流模型的基础上,进一步建立了错误流模型.把计算过程中的错误分成物理错误和传播错误两种,通过分析这两种错误的本质和传播规律,给出了6条有关错误传播的规则和2条独立定律.根据这些规则和定律,能够计算出在程序运行过程中,任意时刻在任意位置上出现错误的概率.最后以一个简单的无穷存储机器程序为例,简要地展示了错误流模型描述硬件故障在程序中传播的能力.

高效的部分冗余容错编译：复制错误流关键子图

传统的容错编译通常复制所有的计算并且使用完全冗余的存储单元来保证容错.这种完全冗余在存储空间和性能上的开销都是相当大的.在错误流分析的基础上提出错误流图的关键子图的概念以及通过关键结点和关键路径生成关键子图的方法,并设计了通过复制错误流关键子图实现部分冗余的算法.在保证有效容错能力的同时,部分冗余明显减小了经过容错编译的程序在存储空间和性能上的开销.实验显示,与复制全部错误流图的完全冗余相比,在结点覆盖率降低6.25%的情况下,部分冗余算法最多能够减少寄存器的使用数量6.25%,减少功耗超过17%,减少执行时间接近26%,同时提高性能超过22%.

高性能低功耗的容错编译技术:错误流压缩算法

在许多关键应用中,计算机的高性能、低功耗和高可靠性是必须同时满足的要求.传统的软件容错技术频繁使用和比较分支指令检测错误,带来了巨大的性能和功耗的开销.提出了基于计算数据流模型的错误流模型,并设计了错误流压缩算法.在错误流压缩算法中,利用附加计算压缩了错误流的直径,显著减少了分支指令的数量,而总指令数不变.针对StreamIT提供的快速傅立叶变换测试程序,采用Wattch对错误流压缩算法进行模拟测试.实验结果表明,当循环参数n=225时,与传统的EDDI算法相比,使用错误流压缩算法可减少分支指令24%以上,IPC提高超过12%,同时,功耗减少了将近5%.给出的推算表明在该实验中,如果内层循环体的存储指令数量为8,分支指令的减少可以达到43%以上.