面向硬件故障的软件容错 ——模型，算法和实验

论文摘要

空间计算机是空间信息处理的基础平台,具有重大的战略意义。在空间环境中,硬件瞬时故障给空间计算机带来的可靠性问题非常突出。使用抗辐照器件可以提高空间计算机的可靠性,但是抗辐照器件性能非常低,价格非常高,功耗也很高,不适合用来建造用于科学计算目的的高性能的空间计算机。COTS器件性能很高,价格和功耗都很低,在COTS器件上面通过软件技术容忍硬件瞬时故障,可以提供高可靠、高性能、低成本和低功耗的空间计算机的解决方案。但是软件对于硬件瞬时故障传播的影响如何,软件容忍硬件瞬时故障的能力到底如何,这种能力对于系统有什么样的影响,都还没有模型能够描述。软件冗余在容忍硬件故障的同时,也带来了很大的开销,如何减小这种开销的影响,也是需要解决的问题。本文先建立了计算数据流模型,并在计算数据流模型的基础上建立了错误流模型。通过区分两种不同类型的错误,以及引入的6条错误传播规则和2条错误独立定律,我们计算出了错误流模型中任意数据在任意时刻产生错误的概率。在此基础上,我们根据容错概念的本质含义,概率化的定义了程序的容错能力。并分析了程序的容错能力对软件实现的双冗余容错系统的容错能力和性能的影响。以程序的容错能力为优化目标,我们提出了通过基于错误流分析的等价变换提高程序的容错能力的概念和方法。其中,我们还在错误流分析的基础上,提出了两种容错算法的优化方法,明显增加了性能并降低了功耗。本文的主要创新如下,1.通过引入原子数据和计算关系的概念,建立了计算数据流模型,描述了存储单元之间由于计算而形成的时空联系。通过引入原子数据的错误概率函数和计算关系的错误传播概率函数,在计算数据流模型上建立了错误流模型,概率化的描述了计算关系传播硬件错误的特性,计算出了任意存储单元在任意时刻发生错误的概率。最终建立了错误流分析的理论框架。2.基于错误流分析提出程序容错能力的概念,给出了程序容错能力的计算方法,提出容忍错误是程序内在属性的观点。并以程序的容错能力为优化目标,提出了一种不进行任何显式的冗余,而仅通过基于错误流分析的等价变换就能提高程序容错能力的方法。并且应用错误流分析,描述了构建双冗余容错系统的方法,分析了提高单个软件副本的容错能力会给双冗余容错系统带来的影响。3.提出对于程序容错能力具有关键影响的错误流关键子图的概念,基于错误流分析分别给出了由关键结点和关键路径生成错误流关键子图的方法。并且提出一种仅复制错误流关键子图的部分冗余容错算法,和EDDI算法相比,部分冗余容错算法在损失很小的错误覆盖率的情况下,能够提高IPC性能10%,减少执行时间15%,减小能量消耗10%。4.通过分析EDDI算法由于插入的分支指令而造成的性能和功耗损失,提出了一种通过附加计算减少分支指令数量的错误流压缩算法,和EDDI算法相比,错误流压缩算法在增加很小的错误延迟的情况下,能够提高性能12%,减少执行时间10%,减小能量消耗5%。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 研究背景
• 1.1.1 高性能的空间计算机
• 1.1.2 空间应用对空间计算机的制约因素
• 1.1.3 基于COTS器件的空间计算机
• 1.1.4 面向硬件故障的软件容错技术
• 1.2 研究内容
• 1.2.1 程序对硬件错误传播的影响
• 1.2.2 程序的容错能力和性能之间的矛盾
• 1.2.3 单个软件副本的容错能力对系统的影响
• 1.3 研究方法
• 1.3.1 错误流分析
• 1.3.2 系统运行时分析
• 1.4 本文的主要贡献和创新
• 1.5 论文的结构
• 第二章 错误流模型
• 2.1 错误流模型
• 2.1.1 计算数据流模型
• 2.1.2 计算数据流图的建立
• 2.1.3 错误流模型和错误流图
• 2.1.4 URM程序示例
• 2.2 错误流分析
• 2.2.1 错误的分类
• 2.2.2 错误传播的规则和定律
• 2.2.3 错误概率的计算
• 2.2.4 URM程序示例
• 2.3 程序的容错能力
• 2.3.1 错误流图的出口
• 2.3.2 程序的容错能力
• 2.4 错误流关键子图
• 2.4.1 从关键结点生成关键子图
• 2.4.2 从关键路径生成关键子图
• 2.4.3 关键子图的复制
• 2.4.4 关键结点和关键路径的选取
• 2.5 小结
• 第三章 优化程序的性能和容错能力
• 3.1 提高完全冗余的性能并降低功耗
• 3.1.1 分支指令对性能和功耗的危害
• 3.1.2 EDDI算法
• 3.1.3 错误流压缩算法
• 3.2 通过部分冗余进一步减小开销
• 3.2.1 部分冗余算法
• 3.3 无冗余容错编译
• 3.3.1 基于错误流分析的等价变换
• 3.4 小结
• 第四章 双冗余容错系统的错误流分析
• 4.1 双冗余容错系统
• 4.2 双冗余容错系统分析
• 4.2.1 双冗余容错系统的容错能力分析
• 4.2.2 双冗余容错系统的性能分析
• 4.3 小结
• 第五章 未来的工作和展望
• 结束语
• 致谢
• 参考文献
• 作者在学期间取得的学术成果
• 附录A 实验环境配置