Thread Scheduling for Multiprogrammed Multiprocessors.

Saved in:

Bibliographic Details
Title:	Thread Scheduling for Multiprogrammed Multiprocessors.
Authors:	Arora, N. S., Blumofe, R. D., Plaxton, C. G.
Source:	Theory of Computing Systems. 2001, Vol. 34 Issue 2, p115. 30p.
Subjects:	Multiprocessors, Multiprogramming (Electronic computers), Production scheduling, Algorithms
Abstract:	We present a user-level thread scheduler for shared-memory multiprocessors, and we analyze its performance under multiprogramming. We model multiprogramming with two scheduling levels: our scheduler runs at user-level and schedules threads onto a fixed collection of processes, while below this level, the operating system kernel schedules processes onto a fixed collection of processors. We consider the kernel to be an adversary, and our goal is to schedule threads onto processes such that we make efficient use of whatever processor resources are provided by the kernel. Our thread scheduler is a non-blocking implementation of the work-stealing algorithm. For any multithreaded computation with work T[sub 1] and critical-path length T[sub ∈] fty , and for any number P of processes, our scheduler executes the computation in expected time O(T[sub 1] /P[sub A] + T[sub ∈] fty P/P[sub A] ) , where P[sub A] is the average number of processors allocated to the computation by the kernel. This time bound is optimal to within a constant factor, and achieves linear speedup whenever P is small relative to the parallelism T[sub 1] /T[sub ∈] fty . [ABSTRACT FROM AUTHOR]
	Copyright of Theory of Computing Systems is the property of Springer Nature and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database:	Engineering Source

Description
Abstract:	We present a user-level thread scheduler for shared-memory multiprocessors, and we analyze its performance under multiprogramming. We model multiprogramming with two scheduling levels: our scheduler runs at user-level and schedules threads onto a fixed collection of processes, while below this level, the operating system kernel schedules processes onto a fixed collection of processors. We consider the kernel to be an adversary, and our goal is to schedule threads onto processes such that we make efficient use of whatever processor resources are provided by the kernel. Our thread scheduler is a non-blocking implementation of the work-stealing algorithm. For any multithreaded computation with work T[sub 1] and critical-path length T[sub ∈] fty , and for any number P of processes, our scheduler executes the computation in expected time O(T[sub 1] /P[sub A] + T[sub ∈] fty P/P[sub A] ) , where P[sub A] is the average number of processors allocated to the computation by the kernel. This time bound is optimal to within a constant factor, and achieves linear speedup whenever P is small relative to the parallelism T[sub 1] /T[sub ∈] fty . [ABSTRACT FROM AUTHOR]
ISSN:	14324350
DOI:	10.1007/s002240011004