Self-adjusting scheduling: An on-line optimization technique for locality management and load balancing

B. Hamidzadeh, D. J. Lilja

Research output: Contribution to journalConference article

14 Scopus citations

Abstract

Techniques for scheduling parallel tasks on to the processors of a multiprocessor architecture must tradeoff three interrelated factors: 1) scheduling and synchronization costs, 2) load balancing, and 3) memory locality. Current scheduling techniques typically consider only one or two of these three factors at a time. We propose a novel Self- Adjusting Scheduling (SAS) algorithm that addresses all three factors simultaneously. This algorithm dedicates a single processor to execute an on-line branch-and-bound algorithm to search for partial schedules concurrent with the execution of tasks previously assigned to the remaining processors. This overlapped scheduling and execution, along with self-adjustment of duration of partial scheduling periods reduces scheduling and synchronization costs significantly. To satisfy the load-balancing and locality management, SAS introduces a unified cost model that accounts for both of these factors simultaneously. We compare the simulated performance of SAS with the Affinity Scheduling algorithm (AFS). The results of our experiments demonstrate that the potential loss of performance caused by dedicating a processor to scheduling is outweighed by the higher performance produced by SAS's dynamically adjusted schedules, even in systems with a small number of processors. SAS is a general on-line optimization technique that can be applied to a variety of dynamic scheduling problems.

Original languageEnglish (US)
Article number5727759
Pages (from-to)II39-II46
JournalProceedings of the International Conference on Parallel Processing
Volume2
DOIs
StatePublished - Jan 1 1994
Event23rd International Conference on Parallel Processing, ICPP 1994 - Raleigh, NC, United States
Duration: Aug 15 1994Aug 19 1994

    Fingerprint

Keywords

  • Dynamic scheduling
  • Load balancing.
  • Locality management
  • On-line optimization
  • Scheduling costs

Cite this