Dynamic task scheduling using online optimization

TitleDynamic task scheduling using online optimization
Publication TypeJournal Article
Year of Publication2000
AuthorsHamidzadeh, B., L. Y. Kit, and D. J. Lilja
JournalParallel and Distributed Systems, IEEE Transactions on
Pagination1151 - 1163
Date Publishednov.
Keywordscomputational complexity, database application, distributed memory systems, dynamic task scheduling, Intel Paragon distributed memory multiprocessor, memory locality, multiprocessor system, online optimization, partial schedules, performance evaluation, processor load balance, processor scheduling, resource allocation, scheduling overhead, self-adjusting dynamic scheduling, task-to-processor assignments

Algorithms for scheduling independent tasks on to the processors of a multiprocessor system must trade-off processor load balance, memory locality, and scheduling overhead. Most existing algorithms, however, do not adequately balance these conflicting factors. This paper introduces the self-adjusting dynamic scheduling (SADS) class of algorithms that use a unified cost model to explicitly account for these factors at runtime. A dedicated processor 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 SADS algorithm, called DBSADS, controls the scheduling overhead by giving higher priority to partial schedules with more task-to-processor assignments. These algorithms are compared to two distributed scheduling algorithms within a database application on an Intel Paragon distributed memory multiprocessor system.


a place of mind, The University of British Columbia

Electrical and Computer Engineering
2332 Main Mall
Vancouver, BC Canada V6T 1Z4
Tel +1.604.822.2872
Fax +1.604.822.5949

Emergency Procedures | Accessibility | Contact UBC | © Copyright 2021 The University of British Columbia