A new algorithm based on Givens rotations for solving linearequations on fault-tolerant mesh-connected processors |
| |
Authors: | Murthy KNB Bhuvaneswari K Ram Murthy CS |
| |
Affiliation: | Dept. of Electr. & Electron. Eng., Malnad Coll. of Eng., Hassan; |
| |
Abstract: | In this paper, we propose a new I/O overhead free Givens rotations based parallel algorithm for solving a system of linear equations. The algorithm uses a new technique called two-sided elimination and requires an N×(N+1) mesh-connected processor array to solve N linear equations in (5N-log N-4) time steps. The array is well suited for VLSI implementation as identical processors with simple and regular interconnection pattern are required. We also describe a fault-tolerant scheme based on an algorithm based fault tolerance (ABFT) approach. This scheme has small hardware and time overhead and can tolerate up to N processor failures |
| |
Keywords: | |
|