A Parallel Adaptive Gauss-Jordan Algorithm |
| |
Authors: | Melab N Talbi E-G Petiton S |
| |
Affiliation: | (1) Laboratoire d'Informatique du Littoral, Université du Littoral, BP 719, 3, rue Louis David, 62228 Calais Cedex, France;(2) Laboratoire d'Informatique Fondamentale de Lille (LIFL-CNRS URA 369), Université des Sciences et Technologies de Lille, 59655 Villeneuve d'Ascq cedex, France;(3) Laboratoire d'Informatique Fondamentale de Lille (LIFL-CNRS URA 369), Université des Sciences et Technologies de Lille, 59655 Villeneuve d'Ascq cedex, France |
| |
Abstract: | This paper presents a parallel adaptive version of the block-based Gauss-Jordan algorithm, utilized to invert large matrices. This version includes a characterization of the workload and a mechanism of its folding/unfolding. Furthermore, this paper proposes a work scheduling strategy and an application-oriented solution for the fault tolerance problem. The application is implemented and experimented with MARS1 in dedicated and non-dedicated environments. The results show that an absolute efficiency of 92% is possible on a cluster of DEC/ALPHA processors interconnected by a Gigaswitch network and an absolute efficiency of 67% can be obtained on an Ethernet network of SUN-Sparc 4 workstations. Moreover, the algorithm is tested on a meta-system including both the two parks of machines. Finally, an out-of-core solution for the algorithm is proposed. This solution allows a gain of 66% of data input operations and reduces the central memory space required for storing the data space of the algorithm by a factor q, where q is the dimension of the matrix to be inverted in terms of data blocks. |
| |
Keywords: | Gauss-Jordan algorithm adaptive parallelism network of workstations (NOW) meta-systems scheduling fault tolerance out-of-core |
本文献已被 SpringerLink 等数据库收录! |
|