next up previous
Next: Tree Ordering Up: Parallel Search Approaches Previous: Task Distribution

   
Load Balancing

When a problem is broken into disjoint subtasks the workload will likely vary among processors. Because one processor may run out of work before others, load balancing is used to activate the idle processor. The first phase of load balancing involves selecting a processor from which to request work. One example is the nearest neighbor approach [22]; alternative approaches include selecting random processors or allowing a master processor to keep track of processor loads and send the ID of a heavily loaded processor to one that is idle. During the second phase of load balancing, the donating processor decides which work, if any, to give. A search algorithm typically stores nodes which have not been fully expanded on an Open list. When giving work to another processor, nodes can be given from the head of the list (deep in the tree), the tail (near the root), or from a sampling of all levels [19].

A number of approaches have been introduced for reducing processor idle time using a load balancing operation. Using the quality equalizing strategy [22], processors anticipate idle time by sending out a work request when their load is almost empty, so that they can continue processing remaining nodes while waiting for a response. Alternative approaches are not receiver based, but allow an overly-loaded processor to initiate a load balance operation [16,28] or allow all processors to periodically shift work to keep the average load within acceptable bounds [2,32].


next up previous
Next: Tree Ordering Up: Parallel Search Approaches Previous: Task Distribution