Asynchronous Iterative Methods for Multiprocessors
Gérard M. Baudet · Journal of the ACM · 1978
A class of asynchronous lterative methods is presented for solving a system of equations Exlstmg lteratwe methods are identified in terms of asynchronous iterations, and new schemes are introduced corresponding to a parallel implementation on a multiprocessor system with no synchronization between cooperating processes A suffloent condlnon is given to guarantee the convergence of any asynchronous iterations, and results are extended to include lteratlve methods with memory Asynchronous lteratlve methods are then evaluated from a computational point of view, and bounds are dertved for the efficiency The bounds are compared with actual measurements obtained by running various asynchronous iterations on a mulnprocessor, and the experimental results show clearly the advantage of purely, as~,nchronous lterattve methods KEY WORDS AND PHRASES asynchronous algorithms, asynchronous muhiprocessors, parallel algorithms, lteratwe methods, chaotic relaxation, analysis of algorithms CR CATE6ORIES 5 14, 5.15, 5 25 contracting operators (see, for example, [9, p. 433])In [2,6,8] the motivation of defining chaotic relaxation is to account for the parallel implementation of iterative methods on a multIprocessor system so as to reduce communication and synchronization between the cooperating processes.This reduction is obtained by not forcing the processes to follow a predetermined sequence of computations, but simply by allowing a process, when starting the evaluation of a new General permission to make fair use in teaching or research of all or part of this material is granted to lndwIdual readers and to nonprofit hbrarles acting for them provided that ACM's copyright notice is given and that reference Is made to the pubhcatlon, to its date of issue, and to the fact that reprinting privileges were granted by permission of the Association for Computing Machinery To otherwise reprint a figure, table, other substantial excerpt, or the entire work requires specific permission as does republication, or systematic or multiple reproduction