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

B. Hamidzadeh, D. J. Lilja

Research output: Contribution to journalConference articlepeer-review

19 Scopus citations


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
StatePublished - 1994
Externally publishedYes
Event23rd International Conference on Parallel Processing, ICPP 1994 - Raleigh, NC, United States
Duration: Aug 15 1994Aug 19 1994


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


Dive into the research topics of 'Self-adjusting scheduling: An on-line optimization technique for locality management and load balancing'. Together they form a unique fingerprint.

Cite this