Computing Publications

Publications Home » Load Balancing using Process Migration

Load Balancing using Process Migration

Mark Nuttall

PhD Thesis
Imperial College London
August, 1997

Is process migration useful for load balancing? We present experimental results indicating that the answer to this question depends largely on the characteristics of the applied workload. Experiments with our {\em Shiva} system, which supports remote execution and process migration, show that only those CPU-bound workloads which were generated using a highly unrealistic exponential distribution for execution times show improvements for dynamic load balancing. (We use the term `dynamic' to indicate remote execution determined at and not prior to run time. The latter is known as `static' load balancing.) Using a more realistic workload distribution and adding a number of short-lived tasks significantly reduces dynamic algorithms' performance. Migration is only useful as a tool for balancing CPU-bound tasks with het erogeneous workloads. We find the migration of executing tasks to remote data to be effective for balancing I/O-bound workloads. Dynamic algorithms are of no use in this situation as they do not have prior knowledge of a task's function. We indicate the region of `workload variable space' for which this migrate-to-data approach is useful. This thesis also contains a comprehensive survey of the state of load balancing research including process migration mechanism design decisions, load balancing policy interactions, numerical indices for making and assessing the effectiveness of load balancing decisions and some important issues concerning the generation and relevance of synthetic workloads. We present a generic and flexible load balancing harness capable of supporting a wide range of experimental configurations.

Postscript of full publication (5.6 megabytes)
(need help viewing Postscript files?)
BibTEX file for the publication
Conditions for downloading publications from this site. built & maintained by Ashok Argent-Katwala.