𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Effects of Asynchronism on the Convergence Rate of Iterative Algorithms

✍ Scribed by Aydin Üresin; Michel Dubois

Publisher
Elsevier Science
Year
1996
Tongue
English
Weight
392 KB
Volume
34
Category
Article
ISSN
0743-7315

No coin nor oath required. For personal study only.

✦ Synopsis

In multiprocessor systems, iterative algorithms can be implemented synchronously or asynchronously. Unfortunately, few guidelines exist to make a choice. In this paper, we compare the execution times of an asynchronous iterative algorithm and of its synchronous counterpart. Synchronization overhead and communication times are neglected in order to focus on the effect of asynchronism on the convergence rate. Under some assumptions, we derive an analytical model. In this model, Q tasks with identical and independently distributed execution time distributions execute on P processors. We show the effects of execution time fluctuations, of the number of processors and tasks, of the scheduling policy and of the amount of coupling among iterate components. The models show that the asynchronous iteration may be up to twice as slow as the synchronous one. This worst case is achieved when the processing time fluctuations are very small, and the coupling among components is strong.

📜 SIMILAR VOLUMES

Techniques for bounding the convergence
Techniques for bounding the convergence rate of genetic algorithms
✍ Yuri Rabinovich; Avi Wigderson 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 308 KB 👁 2 views

The main purpose of the present paper is the study of computational aspects, ## Ž . and primarily the convergence rate, of genetic algorithms GAs . Despite the fact that such algorithms are widely used in practice, little is known so far about their theoretical properties, and in particular about

On the Rate of Multivariate Poisson Conv
On the Rate of Multivariate Poisson Convergence
✍ Bero Roos 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 141 KB

The distribution of the sum of independent nonidentically distributed Bernoulli random vectors in R k is approximated by a multivariate Poisson distribution. By using a multivariate adaption of Kerstan's (1964, Z. Wahrsch. verw. Gebiete 2, 173 179) method, we prove a conjecture of Barbour (1988, J.

Rate of Convergence of the Discrete Póly
Rate of Convergence of the Discrete Pólya-1 Algorithm
✍ A.G. Egger; G.D. Taylor 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 389 KB

The rate of convergence of the discrete Polya-1 algorithm is studied. Examples are given to show that the rates derived are sharp. (c) 1993 Academic Press, Inc