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)