Safe self-scheduling: A parallel loop scheduling scheme for shared-memory multiprocessors
MetadataShow full item record
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.
The article of record as published may be found at https://doi.org/10.1007/BF02577870
RightsThis 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.
Showing items related by title, author, creator and subject.
Ronen, David (Monterey, California. Naval Postgraduate School, 1987-04); NPS55-87-003Truck routing and scheduling problems are differentiated from other vehicle routing and scheduling problems and a classification scheme for the former ones is outlined. Many characteristics of practical truck routing and ...
Uziel, Amir (Monterey, California. Naval Postgraduate School, 1998., 1998-06-01);This work addresses issues related to the design and performance of a wireless integrated services network with emphasis on a tactical framework. We propose an asynchronous transfer mode (ATM)-like protocol architecture ...
Luqi; Berzins, V. (Naval Postgraduate School, 1988); NPS 52-88-035Prototype System Description Language (PSDL) is a high level real-time language with special features for hard real-time system specification and design. It can be used to firm up requirements through execution of its ...