Browse Prior Art Database

Original Publication Date: 1974-Mar-31
Included in the Prior Art Database: 2007-Mar-28
Document File: 32 page(s) / 2M

Publishing Venue

Software Patent Institute

Related People

Berliner, Hans J.: AUTHOR [+2]


Asynchronous Iterative Methods for Multiprocessoro Department of Computer Science Carnegie-Mellon UniversityPittsburgh, Pennsylvania 152 13

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 6% of the total text.

Page 1 of 32

Asynchronous Iterative Methods for Multiprocessoro

Department of Computer Science Carnegie-Mellon University
Pittsburgh, Pennsylvania 152 13

November, 1976

   A class of asynchronous iterative methods is presented for solving a system of equations. Existing iterative 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 sufficient condition is given to guarantee the convergence of any asynchronous iterations, and results are extended to include iterative! methods with memory.

   Asynchronous iterative mothods are then evaluated from a computational point of view, and bounds are derived for the efficiency. The bounds are compared with actual measurements obtained by running various asynchronous iterations on a multiprocessor, and the experimental results show clearly the advantage of purely asynchronous iterative methods.

This research was partly supported by the National Science Foundation under Grant MCS 75-222-55 and the Office of Naval Research under Contract N00014-76-C-0370,
NR 044-422 and partiy by a Research Grant from the Institut de Recherche d'Informatique
et d'Automatique (IRIA), Rocquencourt, France.


[This page contains 1 picture or other non-text object]

Page 2 of 32

[This page contains 1 picture or other non-text object]

Page 3 of 32

where 2 = { J 1 j = I,

                    2,. is a sequence of non-empty subsets of , , n and 1 A i- ( (sl{j), ... , s,(j)) I j = I,

2, ... ) is a sequence of elements in IVh.

    In addition, 2 and A are subject to the following conditions: for each i = I,

... , n

(a) s&j) s j-1, j = I, 2, ...,

(b) si(j), considered as a function of j, tends to infinity as j tends to infinity,
(c) i occurs infinitely many often in the sets Jj, j 5 1, 2, ....

An asynchronous iteration corresponding to F, starting with z(0) and defined by

9 and 4 wilt be denoted by (F,x(O),2,A). a

    An asyt>chronous iteration (F,x(OI,$,A) may be thought of as corresponding to the following sequence of computations on an asynchronous multiprocessor.

    Assume we have a pool of processors avaitable. Let tj, j = 1, 2, ..., be an increasing sequence of time instants. At time tj processor P is idle and is essigned to the evaluation of the iterate dj), x(j) differs from z(j-1) by the set of components ( xi 1 i C J, ) and P starts computing these components using values of components known from previous iterates, namely the r-th component of the s,(j)-th iterate, for

r = I,

   ... , n. The choice of the components may be guided by any criterion, and, in particular, a natural criterion is to pick up the most recently available values of the components. This scheme does need any synchronization between the processes. At some time tk, later on (k r j), P will finish its computation...