Report Number: CS-TR-94-1514
Institution: Stanford University, Department of Computer Science
Title: Load Balancing Using Time Series Analysis for Soft Real Time
Systems with Statistically Periodic Loads
Author: Hailperin, Max
Date: May 1994
Abstract: This thesis provides design and analysis of techniques for
global load balancing on ensemble architectures running
soft-real-time object-oriented applications with
statistically periodic loads. It focuses on estimating the
instantaneous average load over all the processing elements.
The major contribution is the use of explicit stochastic
process models for both the loading and the averaging itself.
These models are exploited via statistical time-series
analysis and Bayesian inference to provide improved average
load estimates, and thus to facilitate global load balancing.
This thesis explains the distributed algorithms used and
provides some optimality results. It also describes the
algorithms' implementation and gives performance results from
simulation. These results show that our techniques allow more
accurate estimation of the global system loading, resulting
in fewer object migrations than local methods. Our method is
shown to provide superior performance, relative not only to
static load-balancing schemes but also to many adaptive
load-balancing methods. Results from a preliminary analysis
of another system and from simulation with a synthetic load
provide some evidence of more general applicability.