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.