Load Balancing in Multiprocessor Systems
ILLINOIS UNIV AT URBANA COORDINATED SCIENCE LAB
Pagination or Media Count:
We present an algorithm for dynamic load balancing in a multiprocessor system that minimizes the number of accesses to the shared memory. The algorithm assumes no information, probabilistic or otherwise, regarding task arrivals or processing requirements. For k processors to process n tasks, the algorithm incurs Ok log k log n potential memory collisions in the worst case. The algorithm itself is a simple variation of the strategy of visiting the longest queue. The key idea is to delay reporting task arrivals and completions, where the delay is a function of dynamic loading conditions.
- Computer Programming and Software
- Computer Hardware