Article

Free access

The impact of operating system scheduling policies and synchronization methods of performance of parallel applications

Authors:

Shigeru UrushibaraAuthors Info & Claims

SIGMETRICS '91: Proceedings of the 1991 ACM SIGMETRICS conference on Measurement and modeling of computer systems

Pages 120 - 132

https://doi.org/10.1145/107971.107985

Published: 02 April 1991 Publication History

Abstract

Shared-memory multiprocessors are frequently used as compute servers with multiple parallel applications executing at the same time. In such environments, the efficiency of a parallel application can be significantly affected by the operating system scheduling policy. In this paper, we use detailed simulation studies to evaluate the performance of several different scheduling strategies, These include regular priority scheduling, coscheduling or gang scheduling, process control with processor partitioning, handoff scheduling, and affinity-based scheduling. We also explore tradeoffs between the use of busy-waiting and blocking synchronization primitives and their interactions with the scheduling strategies. Since effective use of caches is essential to achieving high performance, a key focus is on the impact of the scheduling strategies on the caching behavior of the applications.Our results show that in situations where the number of processes exceeds the number of processors, regular priority-based scheduling in conjunction with busy-waiting synchronization primitives results in extremely poor processor utilization. In such situations, use of blocking synchronization primitives can significantly improve performance. Process control and gang scheduling strategies are shown to offer the highest performance, and their performance is relatively independent of the synchronization method used. However, for applications that have sizable working sets that fit into the cache, process control performs better than gang scheduling. For the applications considered, the performance gains due to handoff scheduling and processor affinity are shown to be small.

References

[1]

james Archibald and Jean-Loup Baer. Cache coherence protocols: Evaluation using a multiprocessor simulation model. ACM Transactions on Computer Systems, 4(4):273- 298, November 1986.

Digital Library

[2]

Forest Baskett, Tom Jermoluk, and Doug Solomon. The 4D-MP graphics superworkstation: Computing + graphics = 40 MIPS + 40 MFLOPS and i00,000 lighted polygons per second, in Proceedings of COMPCON '88, pages 468- 471, 1988.

[3]

David L. Black. Scheduling support for concurrency and parallelism in the Mach operating system. IEEE Computer, 23(5):35-43, May 1990.

Digital Library

[4]

F. J. Carrasco. A parallel maxfiow implementation. CS411 Project Report, Stanford University, March 1988.

[5]

Rohit Chandra, Anoop Gupta, and John Hennessy. COOL: A Language for Parallel Programming. Research Monographs in Parallel and Distributed Computing. The MIT Press, 1990.

[6]

Helen Davis, Stephen Goldschrnidt, and John Hennessy. Tango: A multiprocessor simulation and tracing system. Technical Report CSL-TR-90-439, Stanford University, 1990.

Digital Library

[7]

Edsger W. Dijkstra. The structure of the "THE"- multiprogramming system. Communications of the ACM, 11 (5):341-346, May 1968.

Digital Library

[8]

Thomas W. Doeppner, Jr. Threads: A system for the support of concurrent programming. Technical Report CS-87- 11, Brown University, 1987.

[9]

Jan Edler, Jim Lipkis, and Edith Schonberg. Process management for highly parallel UNIX systems. Ultracomputer Note 136, New York University, 1988.

[10]

Dror G. Feitelson and Larry Rudolph. Distributed hierarchical control for parallel processing. 1EEE Computer, 23(5):65-77, May 1990.

Digital Library

[11]

Andrew V. Goldberg and Robert E. Tarjan. A new approach to the maximum flow problem. In Proceedings of the 18th ACM Symposium on Theory of Computing, pages 136-146, 1986.

Digital Library

[12]

Dan Lenoski et al. Design of scalable shared-memory multiprocessors: The DASH approach. In Proceedings of COMPCON '90, pages 62-67, 1990.

[13]

Scott T. Leutenegger and Mary K. Vemon. The performance of multiprogrammed multiprocessor scheduling policies. In Proceedings of SIGMETRICS '90, pages 226- 236, 1990.

Digital Library

[14]

Ewing Lusk et al. Portable Programs for Parallel Processors. Holt, Rinehart and Winston, Inc., 1987.

Digital Library

[15]

Shikharesh Majumdar, Derek L. Eager, and Richard B. Bunt. Scheduling in multiprogrammed parallel systems. In Proceedings of SIGMETRICS ' 88, pages 104-113, 1988.

Digital Library

[16]

Jeffrey D. McDonald and Donald Baganoff. Vectorization of a particle simulation method for hypersonic rarifled flow. In A/AA Thermodynamics, Plasmadynamics and Lasers Conference, June 1988.

[17]

John K. Ousterhout. Scheduling techniques for concurrent systems. In 3rd International Conference on Distributed Computing Systems, pages 22-30, 1982.

[18]

Edward Rothberg and Anoop Gupta. Techniques for improving the performance of sparse matrix factorization on multiprocessor workstations. In Proceedings of Supercomputing "90, November 1990.

Digital Library

[19]

Kenneth C. Sevcik. Characterizations of parallelism in applications and their use in scheduling. In Proceedings of SIGMETRICS '89, pages 171-180, 1989.

Digital Library

[20]

Mark S. Squillante and Edward D. Lazowska. Using processor-cache affinity in shared-memory multiprocessor scheduling. Technical Report 89-06-01, Department of Computer Science, University of Washington, June 1989.

[21]

Charles P. Thacker, Lawrence C. Stewart, and Edwin H. Satterthwaite, Jr. Firefly: A multiprocessor workstation. 1EEE Transactions on Computers, 37(8):909-920, August 1988.

Digital Library

[22]

Dominique Thiebaut and Harold S. Stone. Footprints in the cache. ACM Transactions on Computer Systems, 5(4):305- 329, November I987.

Digital Library

[23]

Andrew Tucker and Anoop Gupta. Process control and scheduling issues for multiprogrammed shared-memory multiprocessors. In Proceedings of the 12th ACM Symposium on Operating Systems Principles, pages 159-166, 1989.

Digital Library

[24]

john Zahorjan, Edward D. Lazowska, and Derek L. Eager. Spinning versus blocking in parallel systems with uncertainty. In Proceedings of the International Seminar on Performance of Distributed and Parallel Systems, pages 455-472, December 1988.

[25]

John Zahorjan, Edward D. Lazowska, and Derek L. Eager. The effect of scheduling discipline on spin overhead in shared memory parallel systems. Technical Report 89-07- 03, Department of Computer Science, University of Washington, July 1989.

[26]

John Zahorjan and Cathy McCann. Processor scheduling m shared memory multiprocessors. In Proceedings of S1G- METRICS ' 90, pages 214-225, 1990.

Digital Library

Cited By

Mururu GNi KGavrilovska APande SEgger BLee D(2023)PinIt: Influencing OS Scheduling via Compiler-Induced AffinitiesProceedings of the 24th ACM SIGPLAN/SIGBED International Conference on Languages, Compilers, and Tools for Embedded Systems10.1145/3589610.3596279(87-98)Online publication date: 13-Jun-2023
https://dl.acm.org/doi/10.1145/3589610.3596279
Andreoli RCucinotta T(2023)Inducing Huge Tail Latency on a MongoDB deployment2023 IEEE International Conference on Cloud Engineering (IC2E)10.1109/IC2E59103.2023.00020(107-112)Online publication date: 25-Sep-2023
https://doi.org/10.1109/IC2E59103.2023.00020
Zhou DFang VXie TPan WKesavan RLin TPatel N(2018)Empirical Evaluation and Enhancement of Enterprise Storage System Request SchedulingACM Transactions on Storage10.1145/319374114:2(1-27)Online publication date: 27-Apr-2018
https://dl.acm.org/doi/10.1145/3193741
Show More Cited By

Index Terms

The impact of operating system scheduling policies and synchronization methods of performance of parallel applications
1. Software and its engineering
  1. Software creation and management
    1. Software development process management
      1. Software development methods
  2. Software organization and properties
    1. Contextual software domains
      1. Operating systems
        Process management
        Multiprocessing / multiprogramming / multitasking
        Scheduling

Recommendations

The impact of operating system scheduling policies and synchronization methods of performance of parallel applications

Shared-memory multiprocessors are frequently used as compute servers with multiple parallel applications executing at the same time. In such environments, the efficiency of a parallel application can be significantly affected by the operating system ...
Combining performance and priority for scheduling resizable parallel applications

We illustrate and evaluate the potential impact of dynamic resizability on parallel job scheduling. Our ReSHAPE framework includes a job scheduler that supports dynamic resizing of malleable parallel applications. We propose and evaluate new scheduling ...
Parallel job scheduling algorithms

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGMETRICS '91: Proceedings of the 1991 ACM SIGMETRICS conference on Measurement and modeling of computer systems

April 1991

228 pages

ISBN:0897913922

DOI:10.1145/107971

Chairman:
Tom W. Keller
IBM Corp, Austin, TX

ACM SIGMETRICS Performance Evaluation Review Volume 19, Issue 1
May 1991
223 pages
ISSN:0163-5999
DOI:10.1145/107972
Editor:
Tom W. Keller
IBM Corp., Austin, TX
Issue’s Table of Contents

Copyright © 1991 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGMETRICS: ACM Special Interest Group on Measurement and Evaluation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 02 April 1991

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

SIGMETRICS91

Sponsor:

SIGMETRICS

SIGMETRICS91: ACM SIGMETRICS Conference on Measurement & Modeling of Computer Systems

May 21 - 24, 1991

California, San Diego, USA

Acceptance Rates

Overall Acceptance Rate 459 of 2,691 submissions, 17%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

160
Total Citations
View Citations
1,994
Total Downloads

Downloads (Last 12 months)239
Downloads (Last 6 weeks)29

Reflects downloads up to 02 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Mururu GNi KGavrilovska APande SEgger BLee D(2023)PinIt: Influencing OS Scheduling via Compiler-Induced AffinitiesProceedings of the 24th ACM SIGPLAN/SIGBED International Conference on Languages, Compilers, and Tools for Embedded Systems10.1145/3589610.3596279(87-98)Online publication date: 13-Jun-2023
https://dl.acm.org/doi/10.1145/3589610.3596279
Andreoli RCucinotta T(2023)Inducing Huge Tail Latency on a MongoDB deployment2023 IEEE International Conference on Cloud Engineering (IC2E)10.1109/IC2E59103.2023.00020(107-112)Online publication date: 25-Sep-2023
https://doi.org/10.1109/IC2E59103.2023.00020
Zhou DFang VXie TPan WKesavan RLin TPatel N(2018)Empirical Evaluation and Enhancement of Enterprise Storage System Request SchedulingACM Transactions on Storage10.1145/319374114:2(1-27)Online publication date: 27-Apr-2018
https://dl.acm.org/doi/10.1145/3193741
Teabe BTchana AHagimont DCadar CPietzuch PKeeton KRodrigues R(2016)Application-specific quantum for multi-core platform schedulerProceedings of the Eleventh European Conference on Computer Systems10.1145/2901318.2901340(1-14)Online publication date: 18-Apr-2016
https://dl.acm.org/doi/10.1145/2901318.2901340
Cui YWang YChen YShi Y(2015)Requester-Based Spin Lock: A Scalable and Energy Efficient Locking Scheme on Multicore SystemsIEEE Transactions on Computers10.1109/TC.2013.19664:1(166-179)Online publication date: Jan-2015
https://doi.org/10.1109/TC.2013.196
Pusukuri KGupta RBhuyan LAmaral JTorrellas J(2014)ShufflingProceedings of the 23rd international conference on Parallel architectures and compilation10.1145/2628071.2628074(289-300)Online publication date: 24-Aug-2014
https://dl.acm.org/doi/10.1145/2628071.2628074
Raghavan AEmurian LShao LPapaefthymiou MPipe KWenisch TMartin M(2013)Computational sprinting on a hardware/software testbedACM SIGPLAN Notices10.1145/2499368.245113548:4(155-166)Online publication date: 16-Mar-2013
https://dl.acm.org/doi/10.1145/2499368.2451135
Raghavan AEmurian LShao LPapaefthymiou MPipe KWenisch TMartin M(2013)Computational sprinting on a hardware/software testbedACM SIGARCH Computer Architecture News10.1145/2490301.245113541:1(155-166)Online publication date: 16-Mar-2013
https://dl.acm.org/doi/10.1145/2490301.2451135
Meehean JArpaci-Dusseau AArpaci-Dusseau RLivny MFranke HHeinecke APalem KUpfal E(2013)Uncovering CPU load balancing policies with harmonyProceedings of the ACM International Conference on Computing Frontiers10.1145/2482767.2482784(1-10)Online publication date: 14-May-2013
https://dl.acm.org/doi/10.1145/2482767.2482784
Raghavan AEmurian LShao LPapaefthymiou MPipe KWenisch TMartin MSarkar VBodik R(2013)Computational sprinting on a hardware/software testbedProceedings of the eighteenth international conference on Architectural support for programming languages and operating systems10.1145/2451116.2451135(155-166)Online publication date: 16-Mar-2013
https://dl.acm.org/doi/10.1145/2451116.2451135
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Figures

Tables

Media

View Table of Conten