✦ LIBER ✦

Parallel randomized load balancing

✍ Scribed by Micah Adler; Soumen Chakrabarti; Michael Mitzenmacher; Lars Rasmussen

Publisher: John Wiley and Sons
Year: 1998
Tongue: English
Weight: 313 KB
Volume: 13
Category: Article
ISSN: 1042-9832
DOI: 10.1002/(sici)1098-2418(199809)13:2<159::aid-rsa3>3.0.co;2-q

No coin nor oath required. For personal study only.

✦ Synopsis

It is well known that after placing n balls independently and uniformly at

Ž

. random into n bins, the fullest bin holds ⌰ log nrlog log n balls with high probability. More recently, Azar et al. analyzed the following process: randomly choose d bins for each ball, and then place the balls, one by one, into the least full bin from its d choices. Azar et al. They show that after all n balls have been placed, the fullest bin contains only Ž . log log nrlog dq ⌰ 1 balls with high probability. We explore extensions of this result to parallel and distributed settings. Our results focus on the tradeoff between the amount of

📜 SIMILAR VOLUMES

Parallel Load Balancing for Problems wit

Parallel Load Balancing for Problems with Good Bisectors

✍ Stefan Bischof; Ralf Ebner; Thomas Erlebach 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 264 KB

Parallel load balancing is studied for problems with certain bisection properties. A class of problems has :-bisectors if every problem p of weight w( p) in the class can be subdivided into two subproblems whose weight (load) is at least an :-fraction of the original problem. A problem p is to be sp

Parallel thinning algorithms on multicom

Parallel thinning algorithms on multicomputers: experimental study on load balancing

✍ Montoya, M. G. ;Gil, C. ;Garcia, I. 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 156 KB

An Adaptive Load Balancing Method for Pa

An Adaptive Load Balancing Method for Parallel Molecular Dynamics Simulations

✍ Yuefan Deng; Ronald F. Peierls; Carlos Rivera 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 222 KB

We describe an adaptive method for achieving load balance in parallel computations simulating phenomena which are distributed over a spatially extended region, but are local in nature. We have tested the method on standard short-ranged parallel molecular dynamics calculations. The performance gain w

Parallel program analysis on workstation

Parallel program analysis on workstation clusters: Memory utilisation and load balancing

✍ Togneri, Roberto 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 159 KB

Using a workstation cluster for parallel program development requires consideration of various factors to optimise the mapping of the algorithm to the characteristics of the environment. In this paper we present a new analysis and verification of well-known ideas in parallel programming research of

Parallel CFD fire modelling on office PC

Parallel CFD fire modelling on office PCs with dynamic load balancing

✍ A. J. Grandison; E. R. Galea; M. K. Patel; J. Ewer 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 108 KB

## Abstract Parallel processing techniques have been used in the past to provide high performance computing resources for activities such as Computational Fluid Dynamics. This is normally achieved using specialized hardware and software, the expense of which would be difficult to justify for many f

Adaptive Load Balance Techniques in Para

Adaptive Load Balance Techniques in Parallel Rarefied Gas Simulations

✍ S. Antonov; F.-J. Pfreundt; J. Struckmeier 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 451 KB

The paper presents some adaptive load balance techniques for the simulation of rarefied gas flows on parallel computers. It is shown that a static load balance is insufficient to obtain a scalable parallel efficiency. Hence, two adaptive techniques are investigated which are based on simple algorith