A multi-grained distributed implementation of the parallel Block Conjugate Gradient algorithm

The Block Conjugate Gradient algorithm (Block-CG) was developed to solve sparse linear systems of equations that have multiple right-hand sides. We have adapted it for use in heterogeneous, geographically distributed, parallel architectures. Once the main operations of the Block-CG (Tasks) have been collected into smaller groups (subjobs), each subjob is matched by the middleware MJMS (MPI Jobs Management System) with a suitable resource selected among those which are available. Moreover, within each subjob, concurrency is introduced at two different levels and with two different granularities: the coarse-grained parallelism to perform independent tasks and the fine-grained parallelism within the execution of a task. We refer to this algorithm as to multi-grained distributed implementation of the parallel Block-CG. We compare the performance of a parallel implementation with the one of the distributed implementation running on a variety of Grid computing environments. The middleware MJMS-developed by some of the authors and built on top of Globus Toolkit and Condor-G-was used for co-allocation, synchronization, scheduling and resource selection. Copyright (C) 2010 John Wiley & Sons, Ltd.