A fault tolerant systolic mesh for linear system solution

Abstract

A systolic N × (N + 1) mesh to solve a system of TV 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 IN extra processors to tolerate upto 2N processor failures with very little time overhead.

Keywords:

• Linear equations
• gaussian elimination
• pairwise pivoting
• systolic array
• problem partitioning
• fault tolerance
• time redundancy
• algorithm based fault tolerance

C.R. Categories:

• B.2.3
• C.1.2
• F.1.2
• G.1.3