Load balancing : Techniques which aim to spread
tasks among the processors in a parallel processor to avoid
some processors being idle while others have tasks queueing
for execution. Load balancing may be performed either by
heavily loaded processors (with many tasks in their queues)
sending tasks to other processors; by idle processors
requesting work from others; by some centralised task
distribution mechanism; or some combination of these. Some
systems allow tasks to be moved after they have started
executing ("{task migration") others do not. It is important
that the overhead of executing the load balancing
algorithm does not contribute significantly to the overall
processing or communications load.
Distributed scheduling algorithms may be static, dynamic or
preemptive. Static algorithms allocate processes to
processors at run time while taking no account of current
network load. Dynamic algorithms are more flexible, though
more computationally expensive, and give some consideration to
the network load before allocating the new process to a
processor. Preemptive algorithms are more expensive and
flexible still, and may migrate running processes from one
host to another if deemed beneficial. Research to date
indicates that dynamic algorithms yield significant
performance benefits, but that further (though lesser) gains
may be had through the addition of process migration
facilities.
(1995-03-13)
