Please use this identifier to cite or link to this item:

Dynamic techniques for task scheduling on intel paragon

Authors Lau, Ying Kit
Issue Date 1997
Summary Efficiently scheduling parallel tasks onto the processors of a multiprocessor system is critical to achieve high performance. Given perfect information at compile time, a static scheduling strategy can produce an assignment of tasks to processors that ide-ally balances the load among the processors while minimizing the run-time scheduling overhead and the average memory referencing delay. Since perfect information is seldom available, however, dynamic scheduling strategies allow part or all of the scheduling task to be performed at run time when a large amount of useful information about tasks becomes available. In this thesis, we introduce a class of algorithms (i.e. Self-Ad-justing Dynamic Scheduling (SADS)) that undertake an on-line optimization strategy to dynamically compute partial schedules based on the loads of the other processors and the memory locality (affinity) of the tasks and the processors. The SADS algorithms dedicate a processor to perform scheduling. These techniques mask the over-head associated with the scheduling process by performing the scheduling process while the working processors are performing their previously assigned tasks. SADS algorithms explicitly control and allocate the duration of the scheduling process. These algorithms incrementally build a schedule of available tasks. Using this strategy the scheduling process can be interrupted at any time to assign a set of scheduled tasks to their corresponding processors. This thesis provides analytical and empirical analyses of the SADS family of scheduling algorithms. Our results show the strengths and weaknesses of the SADS algorithms with respect to other dynamic scheduling algorithms.
Note Thesis (M.Phil.)--Hong Kong University of Science and Technology, 1997
Language English
Format Thesis
Access View full-text via DOI
Files in this item:
File Description Size Format
th_redirect.html 339 B HTML