检索结果-内蒙古大学图书馆

FT-BLAS: A fault Tolerant High Performance BLAS Implementation on x86 CPUs

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 2023年第12期34卷 3207-3223页

作者： Zhai, Yujia Giem, Elisabeth Zhao, Kai Liu, Jinyang Huang, Jiajun Wong, Bryan M. Shelton, Christian R. Chen, Zizhong Univ Calif Riverside Riverside CA 92521 USA Univ Alabama Birmingham Birmingham AL 35294 USA

Basic Linear Algebra Subprograms (BLAS) serve as a foundational library for scientific computing and machine learning. In this article, we present a new BLAS implementation, FT-BLAS, that provides performance comparable to or faster than state-of -the-art BLAS libraries, while being capable of tolerating soft errors on-the-fly. At the algorithmic level, we propose a hybrid strategy to incorporate fault-tolerant functionality. For memory-bound Level-1 and Level-2 BLAS routines, we duplicate computing instructions and re-use data at the register level to avoid memory overhead when validating the runtime correctness. Here we novelly propose to utilize mask registers on AVX512-enabled processors and SIMD registers on AVX2-enabled processors to store intermediate com-parison results. For compute-bound Level-3 BLAS routines, we fuse memory-intensive operations such as checksum encoding and verification into the GEMM assembly kernels to optimize the mem-ory footprint. We also design cache-friendly parallel algorithms for our fault-tolerant library. Through a series of architectural-aware optimizations, we manage to maintain the fault-tolerant overhead at a negligible order (<3%). Experimental results obtained on widely-used processors such as Intel Skylake, Intel Cascade Lake, and AMD Zen2 demonstrate that FT-BLAS offers high reliability and high performance - faster than Intel MKL, OpenBLAS, and BLIS by up to 3.50%, 22.14%, and 21.70%, respectively, for both serial and parallel routines spanning all three levels of BLAS we benchmarked, even under hundreds of errors injected per minute.

关键词： BLAS SIMD assembly optimization dual modular redundancy algorithm-based fault tolerance AVX-512 AVX2 OpenMP parallel algorithm

来源：评论

学校读者我要写书评

暂无评论

SYNTHESIS OF algorithm-based fault-TOLERANT SYSTEMS FOR DEPENDENCE GRAPHS

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 1993年第8期4卷 864-874页

作者： VINNAKOTA, B JHA, NK PRINCETON UNIV DEPT ELECT ENGNPRINCETONNJ 08544

algorithm-based fault tolerance (ABFT) is a scheme to improve the reliability of parallel architectures used for computation-intensive tasks. The exact implementation of an ABFT scheme is algorithm-dependent. ABFT systems have very low overhead compared to other fault tolerance schemes with similar benefits. Few results are available in the area of general synthesis of ABFT systems. A two-stage approach to the synthesis of ABFT systems is proposed. In the first stage a system-level code is chosen to encode the data used in the algorithm. In the second stage the optimal architecture to implement the scheme is chosen using dependence graphs. Dependence graphs are a graph-theoretic form of algorithm representation. We demonstrate that not all architectures are ideal for the implementation of a particular ABFT scheme. We propose new measures to characterize the fault tolerance capability of a system to better exploit the proposed synthesis method. Dependence graphs can also be used for the synthesis of ABFT schemes for non-linear problems. An example of a fault-tolerant median filter is provided to illustrate their utility for such problems.

关键词： algorithm-based fault tolerance CHECKSUM ENCODING CONCURRENT ERROR DETECTION DEPENDENCE GRAPHS fault DETECTABILITY fault LOCATABILITY SYSTEM SYNTHESIS FOR fault tolerance

来源：评论

学校读者我要写书评

暂无评论

fault TOLERANT COMPUTATION WITH THE SPARSE GRID COMBINATION TECHNIQUE

引用

SIAM JOURNAL ON SCIENTIFIC COMPUTING 2015年第3期37卷 C331-C353页

作者： Harding, Brendan Hegland, Markus Larson, Jay Southern, James Australian Natl Univ Inst Math Sci Acton ACT 2601 Australia Fujitsu Labs Europe Hayes UB4 8FE Middx England

This paper continues to develop a fault tolerant extension of the sparse grid combination technique recently proposed in [B. Harding and M. Hegland, ANZIAM J. Electron. Suppl., 54 (2013), pp. C394-C411]. This approach to fault tolerance is novel for two reasons: First, the combination technique adds an additional level of parallelism, and second, it provides algorithm-based fault tolerance so that solutions can still be recovered if failures occur during computation. Previous work indicates how the combination technique may be adapted for a low number of faults. In this paper we develop a generalization of the combination technique for which arbitrary collections of coarse approximations may be combined to obtain an accurate approximation. A general fault tolerant combination technique for large numbers of faults is a natural consequence of this work. Using a renewal model for the time between faults on each node of a high performance computer, we also provide bounds on the expected error for interpolation with this algorithm in the presence of faults. Numerical experiments solving the scalar advection PDE demonstrate that the algorithm is resilient to faults on a real application. It is observed that the time to solution is not significantly affected by the presence of (simulated) faults. Additionally the expected error increases with the number of faults but is relatively small even for high fault rates. A comparison with traditional checkpoint-restart methods applied to the combination technique shows that our approach is highly scalable with respect to the number of faults.

关键词： exascale computing algorithm-based fault tolerance sparse grid combination technique parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

Toward fault-tolerant parallel-in-time integration with PFASST

引用

PARALLEL COMPUTING 2017年 62卷 20-37页

作者： Speck, Robert Ruprecht, Daniel Forschungszentrum Julich Julich Supercomp Ctr D-52425 Julich Germany Univ Leeds Sch Mech Engn Woodhouse Lane Leeds LS2 9JT W Yorkshire England

We introduce and analyze different strategies for the parallel-in-time integration method PFASST to recover from hard faults and subsequent data loss. Since PFASST stores solutions at multiple time steps on different processors, information from adjacent steps can be used to recover after a processor has failed. PFASST's multi-level hierarchy allows to use the coarse level for correcting the reconstructed solution, which can help to minimize overhead. A theoretical model is devised linking overhead to the number of additional PFASST iterations required for convergence after a fault. The potential efficiency of different strategies is assessed in terms of required additional iterations for examples of diffusive and advective type. (C) 2016 Elsevier B.V. All rights reserved.

关键词： algorithm-based fault tolerance Resilience Parallel-in-time integration Gray-Scott model Boussinesq equations

来源：评论

学校读者我要写书评

暂无评论

Reliable Linear, Sesquilinear, and Bijective Operations on Integer Data Streams Via Numerical Entanglement

引用

IEEE TRANSACTIONS ON SIGNAL PROCESSING 2016年第17期64卷 4606-4617页

作者： Anam, Mohammad Ashraful Andreopoulos, Yiannis UCL Elect & Elect Engn Dept London WC1E 7JE England

A new technique is proposed for fault-tolerant linear, sesquilinear and bijective (LSB) operations onM integer data streams (M >= 3), such as: scaling, additions/subtractions, inner or outer vector products, permutations and convolutions. In the proposed method, M input integer data streams are linearly superimposed to form M numerically-entangled integer data streams that are stored in-place of the original inputs. LSB operations can then be performed directly using these entangled data streams. The results are extracted from the M entangled output streams by additions and arithmetic shifts. Any soft errors affecting one disentangled output stream are guaranteed to be detectable via a post-computation reliability check. Additionally, when utilizing a separate processor core for each stream, our approach can recover all outputs after any single fail-stop failure. Importantly, unlike algorithm-based fault tolerance (ABFT) methods, the number of operations required for the entire process is linearly related to the number of inputs and does not depend on the complexity of the performed LSB operations. We have validated our proposal in an Intel processor via several types of operations: fast Fourier transforms, convolutions, and matrix multiplication operations. Our analysis and experiments reveal that the proposed approach incurs between 0.03% to 7% reduction in processing throughput for numerous LSB operations. This overhead is 5 to 1000 times smaller than that of the equivalent ABFT method that uses a checksum stream. Thus, our proposal can be used in fault-generating processor hardware or safety-critical applications, where high reliability is required without the cost of ABFT or modular redundancy.

关键词： Linear operations sum-of-products algorithm-based fault tolerance silent data corruption core failures numerical entanglement

来源：评论

学校读者我要写书评

暂无评论

Design and analysis of two highly scalable sparse grid combination algorithms

引用

JOURNAL OF COMPUTATIONAL SCIENCE 2016年第Part3期17卷 547-561页

作者： Strazdins, Peter E. Ali, Md. Mohsin Harding, Brendan Australian Natl Univ Res Sch Comp Sci Canberra ACT 0200 Australia Australian Natl Univ Inst Math Sci Canberra ACT 0200 Australia

Many large scale scientific simulations involve the time evolution of systems modelled as Partial Differential Equations (PDEs). The sparse grid combination technique (SGCT) is a cost-effective method for solve time-evolving PDEs, especially for higher-dimensional problems. It consists of evolving PDE over a set of grids of differing resolution in each dimension, and then combining the results to approximate the solution of the PDE on a grid of high resolution in all dimensions. It can also be extended to support algorithmic-based fault-tolerance, which is also important for computations at this scale. In this paper, we present two new parallel algorithms for the SGCT that supports the full distributed memory parallelization over the dimensions of the component grids, as well as across the grids as well. The direct algorithm is so called because it directly implements a SGCT combination formula. We give details of the design and implementation of a 'partial' sparse grid data structure, which is needed for its efficient implementation. The second algorithm converts each component grid into their hierarchical surpluses, and then uses the direct algorithm on each of the hierarchical surpluses. The conversion to/from the hierarchical surpluses is also an important algorithm in its own right. It requires a technique called sub-griding in order to correctly deal with the combination of very small surpluses. An analysis of both indicates the direct algorithm minimizes the number of messages, whereas the hierarchical surplus minimizes memory consumption and offers a reduction in bandwidth by a factor of 1-2(-d), where d is the dimensionality of the SGCT. However, this is offset by its incomplete parallelism (70-80%) and a factor of 2(d) load imbalance in practical scenarios. Our analysis also indicates both are suitable in a bandwidth limited regime and that the direct algorithm is scalable with respect to d. Experimental results including the strong and weak scalability of

关键词： High performance computing Parallel computing PDE solvers Sparse grid combination technique algorithm-based fault tolerance

来源：评论

学校读者我要写书评

暂无评论

A mesh check-sum ABFT scheme for stream ciphers

引用

INTERNATIONAL JOURNAL OF COMMUNICATION NETWORKS AND DISTRIBUTED SYSTEMS 2009年第4期3卷 285-300页

作者： Zhang, Chang N. Liu, Xiao Wei Univ Regina TRLabs Dept Comp Sci Regina SK S4S 0A2 Canada

To enhance the security and reliability of the widely-used stream ciphers, a novel mesh check-sum ABFT scheme for stream ciphers is developed. By utilising the ready-made arithmetic unit in stream ciphers, single and multiple errors can be detected and corrected in a cheap way. To meet different requirements in practical applications, 4-D mesh check-sum ABFT scheme is proposed which can be applied to RC4 or other stream ciphers. The 2-D mesh check-sum ABFT scheme is able to detect and correct single error with high efficiency. The 4-D mesh check-sum ABFT scheme is capable of correcting up to three errors located randomly in an N-element matrix with acceptable computation and bandwidth overhead. The workload can be remarkably reduced when most communications are error-free. Our scheme also provides one-to-one mapping between index and check-sum, so that error can be located and recovered by easier logic and simpler operation.

关键词： stream cipher algorithm-based fault tolerance error detection error correction RC4 parity check sum arithmetic unit matrix computation exclusive or

来源：评论

学校读者我要写书评

暂无评论

"Short-Dot": Computing Large Linear Transforms Distributedly Using Coded Short Dot Products

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2019年第10期65卷 6171-6193页

作者： Dutta, Sanghamitra Cadambe, Viveck Grover, Pulkit Carnegie Mellon Univ Dept Elect & Comp Engn Pittsburgh PA 15213 USA Penn State Univ Dept Elect Engn University Pk PA 16802 USA

We consider the problem of computing a matrix-vector product Ax using a set of P parallel or distributed processing nodes prone to "straggling," i.e., unpredictable delays. Every processing node can access only a fraction (s/N) of the N-length vector x, and all processing nodes compute an equal number of dot products. We propose a novel error correcting code-that we call " Short-Dot"-that introduces redundant, shorter dot products such that only a subset of the nodes' outputs are sufficient to compute Ax. To address the problem of straggling in computing matrix-vector products, prior work uses replication or erasure coding to encode parts of the matrix A, but the length of the dot products computed at each processing node is still N. The key novelty in our work is that instead of computing the long dot products as required in the original matrix-vector product, we construct a larger number of redundant and short dot products that only require a fraction of x to be accessed during the computation. Short-Dot is thus useful in a communication-constrained scenario as it allows for only a fraction of x to be accessed by each processing node. Further, we show that in the particular regime where the number of available processing nodes is greater than the total number of dot products, Short-Dot has lower expected computation time under straggling under an exponential model compared to existing strategies, e.g. replication, in a scaling sense. We also derive fundamental limits on the trade-off between the length of the dot products and the recovery threshold, i.e., the required number of processing nodes, showing that Short-Dot is near-optimal.

关键词： algorithm-based fault tolerance coded computing matrix sparsification stragglers

来源：评论

学校读者我要写书评

暂无评论

Correcting DFT Codes with Modified Berlekamp-Massey algorithm and Syndrome Extension

Correcting DFT Codes with Modified Berlekamp-Massey Algorith...

引用

17th IEEE Pacific Rim International Symposium on Dependable Computing (PRDC)

作者： Redinbo, Robert Univ Calif Davis ECE Dept Davis CA 95616 USA

Real number block codes derived from the discrete Fourier transform (DFT) are corrected by coupling a very modified Berlekamp-Massey algorithm with a syndrome extension process. Enhanced extension recursions based on ... 详细信息

ISBN: (纸本)9780769545905

关键词： algorithm-based fault tolerance Discrete Fourier Transform Codes Berlekamp-Massey algorithm Kalman Estimation Syndrome Extensions

来源：评论

学校读者我要写书评

暂无评论

Physics-based Checksums for Silent-Error Detection in PDE Solvers 25th

Physics-Based Checksums for Silent-Error Detection in PDE So...

引用

25th International Conference on Parallel and Distributed Computing (Euro-Par)

作者： Salloum, Maher Mayo, Jackson R. Armstrong, Robert C. Sandia Natl Labs POB 969 Livermore CA 94551 USA

ISBN: (纸本)9783030483401;9783030483395

We discuss techniques for efficient local detection of silent data corruption in parallel scientific computations, leveraging physical quantities such as momentum and energy that may be conserved by discretized PDEs. The conserved quantities are analogous to "algorithm-based fault tolerance" checksums for linear algebra but, due to their physical foundation, are applicable to both linear and nonlinear equations and have efficient local updates based on fluxes between subdomains. These physics-based checksums enable precise intermittent detection of errors and recovery by rollback to a checkpoint, with very low overhead when errors are rare. We present applications to both explicit hyperbolic and iterative elliptic (unstructured finite-element) solvers with injected memory bit flips.

关键词： Silent errors Partial differential equations Linear algebra algorithm-based fault tolerance Checkpoint/restart

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：