Thread Scheduling for Multiprogrammed Multiprocessors.
Saved in:
| 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 |
| FullText | Links: – Type: pdflink Text: Availability: 0 |
|---|---|
| Header | DbId: egs DbLabel: Engineering Source An: 5349542 AccessLevel: 6 PubType: Academic Journal PubTypeId: academicJournal PreciseRelevancyScore: 0 |
| IllustrationInfo | |
| Items | – Name: Title Label: Title Group: Ti Data: Thread Scheduling for Multiprogrammed Multiprocessors. – Name: Author Label: Authors Group: Au Data: <searchLink fieldCode="AR" term="%22Arora%2C+N%2E+S%2E%22">Arora, N. S.</searchLink><br /><searchLink fieldCode="AR" term="%22Blumofe%2C+R%2E+D%2E%22">Blumofe, R. D.</searchLink><br /><searchLink fieldCode="AR" term="%22Plaxton%2C+C%2E+G%2E%22">Plaxton, C. G.</searchLink> – Name: TitleSource Label: Source Group: Src Data: <searchLink fieldCode="JN" term="%22Theory+of+Computing+Systems%22">Theory of Computing Systems</searchLink>. 2001, Vol. 34 Issue 2, p115. 30p. – Name: Subject Label: Subjects Group: Su Data: <searchLink fieldCode="DE" term="%22Multiprocessors%22">Multiprocessors</searchLink><br /><searchLink fieldCode="DE" term="%22Multiprogramming+%28Electronic+computers%29%22">Multiprogramming (Electronic computers)</searchLink><br /><searchLink fieldCode="DE" term="%22Production+scheduling%22">Production scheduling</searchLink><br /><searchLink fieldCode="DE" term="%22Algorithms%22">Algorithms</searchLink> – Name: Abstract Label: Abstract Group: Ab Data: 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] – Name: AbstractSuppliedCopyright Label: Group: Ab Data: <i>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.</i> (Copyright applies to all Abstracts.) |
| PLink | https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=5349542 |
| RecordInfo | BibRecord: BibEntity: Identifiers: – Type: doi Value: 10.1007/s002240011004 Languages: – Code: eng Text: English PhysicalDescription: Pagination: PageCount: 30 StartPage: 115 Subjects: – SubjectFull: Multiprocessors Type: general – SubjectFull: Multiprogramming (Electronic computers) Type: general – SubjectFull: Production scheduling Type: general – SubjectFull: Algorithms Type: general Titles: – TitleFull: Thread Scheduling for Multiprogrammed Multiprocessors. Type: main BibRelationships: HasContributorRelationships: – PersonEntity: Name: NameFull: Arora, N. S. – PersonEntity: Name: NameFull: Blumofe, R. D. – PersonEntity: Name: NameFull: Plaxton, C. G. IsPartOfRelationships: – BibEntity: Dates: – D: 01 M: 02 Text: 2001 Type: published Y: 2001 Identifiers: – Type: issn-print Value: 14324350 Numbering: – Type: volume Value: 34 – Type: issue Value: 2 Titles: – TitleFull: Theory of Computing Systems Type: main |
| ResultId | 1 |
