Partitioned Matrix Arithmetic with High Reliability

具高可靠度之分割矩陣演算法

張莉莉(Lily Chang) ； 陳良基(Liang-Gee Chen)

《國防管理學報》 9卷2期 (1988/06) Pp. 63-70

https://doi.org/10.29496/JNDM.198806.0005

摘要

此篇文章提出一具高可靠度之分割矩陣演算法，這種新的演算法則極適用於超大型積體電路（VLSI）陣列處理器之架構。在實際應用上，快速且正確的解決大量之科技性計算或統計分析是極其必要的，因為VLSI製造技術的進步，即時處理大量資料已成為可行。但因受限於IC上處理器數量的限制，較大矩陣仍需先經分割才能被適切的處理。此外，除了快速處理資料外我們亦希望經過這些冗長運算後，解答是正確無誤的，為了解決這些問題，本文提出一有效率且具高可靠度的演算法來處理須經分割的大型矩陣運算。因為，一般矩陣運算不外乎加法、乘法、LU分解及反矩陣合成，所以我們（1）先說這四種運算設計出四個特殊IC模組，使每一模組具有容錯的功能，亦即均能檢查出計算後的錯誤並更正錯誤。（2）證明對任一大矩陣的四基本運算均可經分割後由上述四個基本模組處理而得高可靠度的結果。

並列摘要

In this paper, a new class of partitioned matrix algorithms has been developed for possible VLSI implementation of large-scale matrix solvers with high reliability. Fast and large matrix solvers are higherly demanded in signal/image processing and in many real-time and scientific applications. Matrix partitioning and concurrent computation are needed to fit these requirements. In addition to achieving high performance, high reliability is also imnortant to ensure that the results of long computation are valid. This paper proposes a system-level method for concurrent computations on VLSI array processors, called algorithm-based fault tolerance. The technique firstly encodes matrix at a high level Then efficient algorithms are designed to operate on encoded data and produce decoded outputs, Algorithm-based fault tolerance schemes can detect and correct errors when matrix operations are performed using multiple processor systems. This paper shows only a few functional types of VLSI arithmetic chips are needed for submatrix faun-tolerant computations after partitioning. This approach is not restricted by problem sizes and thus can be applied to solve arbitrarily large linear systems of equations in an iterative fashion. The following four fault-tolerant computations are shown systematically partitionable into fault-tolerant submatrix operations, which are feasible for direct VLSI implementation: L-U decomposition of a dense matrix; inversion of a triangular matrix; multiplication and addition of two compatible matrices.