Algorithmic approaches to low overhead fault detection for sparse linear algebra
Algorithmic approaches to low overhead fault detection for sparse linear algebra
复制标题
稀疏线性代数低开销故障检测的算法方法
DOI：
10.1109/dsn.2012.6263938
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
G. Bronevetsky
中科院分区：
文献类型：
--
作者：
Joseph Sloan;Rakesh Kumar;G. Bronevetsky
高性能计算系统的尺寸和复杂性不断增加，使得单个电路产生错误结果的可能性越来越大，特别是在低能耗模式下运行时。基于算法的容错（ABFT）[20]的先前技术已经被提出用于检测密集线性操作中的错误，但是在稀疏问题的上下文中具有高开销。在本文中，我们提出了一套算法技术，最大限度地减少稀疏问题的故障检测的开销。这些技术基于两种见解。首先，许多稀疏问题都是结构良好的（例如对角、带状对角、块对角），这允许采样技术产生用于故障检测的检查的良好近似。这些近似检查对于许多稀疏线性代数应用是可接受的。其次，许多线性应用程序有足够的重用，可以使用预处理技术使这些应用程序更适合低成本的算法检查。所提出的技术，以产生高达2倍的性能开销减少传统的ABFT检查的频谱稀疏的问题。使用常见的线性求解器的案例研究进一步说明了所提出的算法技术的好处。
The increasing size and complexity of High-Performance Computing systems is making it increasingly likely that individual circuits will produce erroneous results, especially when operated in a low energy mode. Previous techniques for Algorithm - Based Fault Tolerance (ABFT) [20] have been proposed for detecting errors in dense linear operations, but have high overhead in the context of sparse problems. In this paper, we propose a set of algorithmic techniques that minimize the overhead of fault detection for sparse problems. The techniques are based on two insights. First, many sparse problems are well structured (e.g. diagonal, banded diagonal, block diagonal), which allows for sampling techniques to produce good approximations of the checks used for fault detection. These approximate checks may be acceptable for many sparse linear algebra applications. Second, many linear applications have enough reuse that pre-conditioning techniques can be used to make these applications more amenable to low-cost algorithmic checks. The proposed techniques are shown to yield up to 2× reductions in performance overhead over traditional ABFT checks for a spectrum of sparse problems. A case study using common linear solvers further illustrates the benefits of the proposed algorithmic techniques.