Selected Topics in Large Scale Discrete Optimization


DYNAMIC LOAD BALANCING ON HETEROGENEOUS NETWORKS

Ewald Speckenmeyer

Institute for Informatics
University of Köln
Köln, Germany

Thursday, June 10, 1999

4 - 5 PM

DIMACS Center, CoRE Building, Room 431, Rutgers University

For a slide show click here!

Back to TUTORIALS main page



This talk presents a dynamic load balancing algorithm for a network of heterogeneous computers. Our approach is based on a fast distributed precomputation step calculating the necessary load movements. When dealing with slow network connections or incomplete load information often a perfect balanced load is not necessary, therefore the allowed degree of inbalance is adjustable.

A detailed average case analysis is carried out concerning the total load transfer and the number of transfer rounds. Its performance is empirically demonstrated solving the satisfiability problem on a heterogeneous network of workstations.