Accession Number:

ADA210144

Title:

Load Balancing in Multiprocessor Systems

Descriptive Note:

Technical rept.

Corporate Author:

ILLINOIS UNIV AT URBANA COORDINATED SCIENCE LAB

Personal Author(s):

• Loui, Michael C.
• Sohoni, Milind A.

Report Date:

1989-06-01

Pagination or Media Count:

12.0

Abstract:

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.

Descriptors:

• *ALGORITHMS
• *MEMORY DEVICES
• *TIME SHARING
• *DYNAMIC LOADS
• *COLLISIONS
• *MULTIPROCESSORS
• VARIATIONS
• PROCESSING
• REQUIREMENTS

Subject Categories:

• Computer Programming and Software
• Computer Hardware

Distribution Statement:

APPROVED FOR PUBLIC RELEASE