Reducing the synchronization overhead in parallel nonsymmetric Krylov algorithms on MIMD machines

Author

Maheswaran, Muthucumaru ; Webb, Kevin J. ; Siegel, Howard Jay

Author_Institution

Sch. of Electr. & Comput. Eng., Purdue Univ., West Lafayette, IN, USA

fYear

1998

fDate

10-14 Aug 1998

Firstpage

405

Lastpage

413

Abstract

By considering electromagnetic scattering problems as examples, a study of the performance and scalability of the conjugate gradient squared (CGS) algorithm on two MIMD machines is presented. A modified CGS (MCGS) algorithm, where the synchronization overhead is effectively reduced by a factor of two, is proposed in this paper. This is achieved by changing the computation sequence in the CGS algorithm. Both experimental and theoretical analyses were performed to investigate the impact of this modification on the overall execution time

Keywords

conjugate gradient methods; parallel algorithms; performance evaluation; synchronisation; MIMD machines; conjugate gradient squared algorithm; electromagnetic scattering problems; parallel nonsymmetric Krylov algorithms; performanc; scalability; synchronization overhead; Character generation; Concurrent computing; Electromagnetic scattering; Electronic mail; Equations; Finite element methods; Frequency synchronization; Laboratories; Linear systems; Parallel processing;

fLanguage

English

Publisher

ieee

Conference_Titel

Parallel Processing, 1998. Proceedings. 1998 International Conference on

Conference_Location

Minneapolis, MN

ISSN

0190-3918

Print_ISBN

0-8186-8650-2

Type

conf

DOI

10.1109/ICPP.1998.708512

Filename

708512