Safe self-scheduling: A parallel loop scheduling scheme for shared-memory multiprocessors
Loading...
Authors
Liu, J.
Saletore, V.A.
Lewis, T.G.
Subjects
Advisors
Date of Issue
1994-12-01
Date
Publisher
Language
Abstract
In this paper we present Safe Self-Scheduling (SSS), a new scheduling scheme that schedules parallel loops with variable length iteration execution times not known at compile time. The scheme assumes a shared memory space. SSS combines static scheduling with dynamic scheduling and draws favorable advantages from each. First, it reduces the dynamic scheduling overhead by statistically scheduling a major portion of loop iterations. Second, the workload is balanced with simple and efficient self-scheduling scheme by applying a new measure, the smallest critical chore size. Experimental results comparing SSS with other scheduling schemes indicate that SSS surpasses other scheduling schemes. In the experiment on Gauss-Jordan, an application that is suitable for static scheduling schemes, SSS is the only self-scheduling scheme that outperforms the static scheduling scheme. This indicates that SSS achieves a balanced workload with a very small amount of overhead.
Type
Article
Description
The article of record as published may be found at https://doi.org/10.1007/BF02577870
Series/Report No
Department
Organization
Identifiers
NPS Report Number
Sponsors
USDOE
Funder
Format
Citation
Journal Name: International Journal of Parallel Programming; Journal Volume: 22; Journal Issue: 6; Other Information: PBD: Dec 1994
Distribution Statement
Rights
This publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.