A New and Faster Gaussian Elimination Based Fault Tolerant Systolic Linear System Solver
✍ Scribed by K. Bhuvaneswari; K.N. Balasubramanya Murthy; C. Siva Ram Murthy
- Publisher
- Elsevier Science
- Year
- 1997
- Tongue
- English
- Weight
- 241 KB
- Volume
- 44
- Category
- Article
- ISSN
- 0743-7315
No coin nor oath required. For personal study only.
✦ Synopsis
This paper presents a new systolic algorithm for the complete solution of a system of N linear equations in (N 2 /2 + O(N)) time steps using 2N processing elements (PEs). It is based on a variant of the Gaussian elimination (GE) algorithm called the successive GE and is faster than any existing GE based algorithm using O(N ) PEs. We also suggest two fault tolerant schemes that tolerate up to N PE failures. The first scheme is a time redundancy based approach with no hardware overhead and 100% time overhead. This scheme can tolerate up to N PE failures. The second scheme is based on algorithm based fault tolerance (ABFT) and uses N extra PEs to tolerate up to N -1 PE failures with very little time overhead. The number of errors that can be detected/corrected in both schemes is more than that in any existing fault tolerant systolic array.