HKUST Library Institutional Repository Banner

HKUST Institutional Repository >
Computer Science and Engineering >
CSE Master Theses  >

Please use this identifier to cite or link to this item:
Title: Dynamic techniques for task scheduling on intel paragon
Authors: Lau, Ying Kit
Issue Date: 1997
Abstract: 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.
Description: Thesis (M.Phil.)--Hong Kong University of Science and Technology, 1997
x, 61 leaves : ill. ; 30 cm
HKUST Call Number: Thesis COMP 1997 Lau
Appears in Collections:CSE Master Theses

Files in This Item:

File Description SizeFormat

All items in this Repository are protected by copyright, with all rights reserved.