Options
A fault tolerant systolic mesh for linear system solution
Date Issued
01-01-1998
Author(s)
Bhuvaneswari, K.
Siva Ram Murthy, C.
Abstract
A systolic N × (N + 1) mesh to solve a system of N linear equations, using a variant of Gaussian elimination algorithm (GE), called successive GE (SGE), was presented in [2]. To ensure numerical stability, the authors have incorporated pairwise pivoting in the algorithm. However, they do not address the important issue of handling oversized problems, i.e., their design is not suitable for solving linear systems of arbitrary size. In this paper, in order to add flexibility to their design, we present two problem partitioning techniques so that problems of any size can be solved on the mesh. Further, in order to add robustness to their design, we suggest two fault tolerant schemes for handling processor failures. The first one is based on time redundancy and has 100% time overhead. It can tolerate upto 50% processor failures at no extra hardware cost. The second scheme is based on algorithm based fault tolerance and uses 2N extra processors to tolerate upto N processor failures with very little time overhead.
Volume
67