ABSTRACT
Dynamic load distribution algorithms use system state information, at least in part, to make load distribution decisions while static algorithms make no use of this information. This chapter discusses basic dynamic load distribution approaches followed by an example of global dynamic load distribution on hypercubes. The limitation of static load distribution is that it assigns tasks to processors in a once-and-for-all manner and requires a priori knowledge of program behavior. Most approaches ignore the effects of interference in a system comprised of communicating processes and the effects of the evolving process of computation. Typically, a dynamic load distribution algorithm has six policies: initiation, transfer, selection, profitability, location, and information. Dynamic load distribution algorithm must be general, adaptable, stable, scalable, fault-tolerant, and transparent to applications. Some dynamic load distribution algorithms are non-preemptive; that is, nodes can only distribute newly arrived tasks. Others are preemptive and can redistribute a running task.
