𝔖 Bobbio Scriptorium
✦   LIBER   ✦

An improved diffusion algorithm for dynamic load balancing

✍ Scribed by Y.F. Hu; R.J. Blake

Publisher
Elsevier Science
Year
1999
Tongue
English
Weight
231 KB
Volume
25
Category
Article
ISSN
0167-8191

No coin nor oath required. For personal study only.

✦ Synopsis

Diusion type algorithms [1,3,11] are some of the most popular algorithms for scheduling in dynamic load balancing. It is known however that this type of algorithm can suer from slow convergence. In this paper the performance of the diusion type algorithms is improved, while retaining the nearest neighbour communication requirement, through the use of Chebyshev polynomials. It is also proved that both the diusion algorithm and the improved diusion algorithm have an optimal property in terms of the amount of load migrated. Numerical results are given comparing the algorithm with the diusion algorithm as well as a fast algorithm that requires global communication.

πŸ“œ SIMILAR VOLUMES

An optimal migration algorithm for dynam
An optimal migration algorithm for dynamic load balancing
✍ HU, Y. F.; BLAKE, R. J.; EMERSON, D. R. πŸ“‚ Article πŸ“… 1998 πŸ› John Wiley and Sons 🌐 English βš– 207 KB πŸ‘ 2 views

The problem of redistributing the work load on parallel computers is considered. An optimal redistribution algorithm, which minimises the Euclidean norm of the migrating load, is derived. The relationship between this algorithm and some existing algorithms is discussed and the convergence of the new

Accelerated diffusion algorithms for dyn
Accelerated diffusion algorithms for dynamic load balancing
✍ Gregory Karagiorgos; Nikolaos M. Missirlis πŸ“‚ Article πŸ“… 2002 πŸ› Elsevier Science 🌐 English βš– 87 KB

In this paper we consider the application of accelerated techniques in order to increase the rate of convergence of the diffusive iterative load balancing algorithms. In particular, we compare the application of Semi-Iterative, Second Degree and Variable Extrapolation techniques on the basic diffusi

V_THR: An Adaptive Load Balancing Algori
V_THR: An Adaptive Load Balancing Algorithm
✍ Pallab Dasgupta; A.K. Majumder; P. Bhattacharya πŸ“‚ Article πŸ“… 1997 πŸ› Elsevier Science 🌐 English βš– 173 KB

This paper presents a new adaptive algorithm for dynamic load balancing on a shared BUS architecture. We present results obtained from simulation studies and queuing analysis, which reflect the relation between the BUS contention and the efficiency of load balancing. The proposed algorithm uses a sc