Load Balancing in Multiprocessor Systems

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 O(k 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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jun 01, 1989
Accession Number
ADA210144

Entities

People

  • Michael C. Loui
  • Milind A. Sohoni

Organizations

  • University of Illinois Urbana–Champaign

Tags

Communities of Interest

  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Algorithms
  • Availability
  • Classification
  • Collisions
  • Computational Science
  • Computations
  • Contracts
  • Engineering
  • Illinois
  • Mathematical Analysis
  • Military Research
  • Multiprocessors
  • Notation
  • Parallel Computing
  • Scheduling (Production)
  • Security
  • Steady State

Fields of Study

  • Computer science

Readers

  • Computer Networking
  • Computer Science/Computer Engineering/Data Science/Digital Signal Processing.