Dynamic task scheduling using online optimization

Algorithms for scheduling independent tasks on to the processors of a multi processor system must trade-off processor load balance, memory locality, an d scheduling overhead. Most existing algorithms, however, do not adequately balance these conflicting factors. This paper introduces the Self-Adjustin g Dynamic Scheduling (SADS) class of algorithms that use a unified cost mod el to explicitly account for these factors at runtime. A dedicated processo r performs scheduling in phases by maintaining a tree of partial schedules and incrementally assigning tasks to the least-cost schedule. A scheduling phase terminates whenever any processor becomes idle, at which time partial schedules are distributed to the processors. An extension of the basic SAD S algorithm, called DBSADS, controls the scheduling overhead by giving high er priority to partial schedules with more task-to-processor assignments. T hese algorithms are compared to two distributed scheduling algorithms withi n a database application on an Intel Paragon distributed-memory multiproces sor system.