Article

Free access

The performance implications of thread management alternatives for shared-memory multiprocessors

Authors:

T. E. Anderson,

D. D. Lazowska,

H. M. LevyAuthors Info & Claims

SIGMETRICS '89: Proceedings of the 1989 ACM SIGMETRICS international conference on Measurement and modeling of computer systems

Pages 49 - 60

https://doi.org/10.1145/75108.75378

Published: 01 April 1989 Publication History

Abstract

Threads (“lightweight” processes) have become a common element of new languages and operating systems. This paper examines the performance implications of several data structure and algorithm alternatives for thread management in shared-memory multiprocessors. Both experimental measurements and analytical model projections are presented.

For applications with fine-grained parallelism, small differences in thread management are shown to have significant performance impact, often posing a tradeoff between throughput and latency. Per-processor data structures can be used to improve throughput, and in some circumstances to avoid locking, improving latency as well.

The method used by processors to queue for locks is also shown to affect performance significantly. Normal methods of critical resource waiting can substantially degrade performance with moderate numbers of waiting processors. We present an Ethernet-style backoff algorithm that largely eliminates this effect.

References

[1]

M. Acc, etta, R. Baron, W. Bolosky, D. Golub, R. Rashid, A. Tevanian, and M. Young. Mach: A New Kernel Foundation For UNIX Developmerit. Proc. Swnn~r 1986 USb:NIX Technical Conference and Exhibi. tion, June 1986, pp. 93-112.

[2]

J. Archibald and J.L. Baer. Cache Coherence Protocols: Evaluation Using a Multiprcr.essor Simulation Model. ACM Transactions on Computer Systems, vol. 4, no. 4, Nov. 1986.

Digital Library

[3]

M.J. Bach and SJ. Buroff. Multiprocessor UNIX Operating Systems. AT~T Bell Laboratories Technical journal, vol. 63, no. 8, Oct. 198,4, pp. 1733-1749.

[4]

Brian Bershad, Edward Lazowska, and Henry Levy. PRESTO: A System for Object-Oriented Parallel Programming. Software: Practice and E~erience, vol. 18, no. 8, Aug. 1988, pp. 713-732.

Digital Library

[5]

Brian Bershad, Edward Lazowska, Henry Levy, and David Wagner. An O~eM/n Environment for Building Parallel Programming Systems. Proc. SIGPLAN PPEALS 1988, pp. 1-9.

Digital Library

[6]

Kenneth W. Dritz and James M. Boyle. Beyond "Speedup": Performance Analysis of Parallel Programs. Technical Report ANL-87-7, Mathematics and Computer Science Division, Argonne National Laboratory, Feb. 1987.

[7]

Derek Eager, Edward Lazowska, and John Zahorjan. Adaptive Load Sharing in Homogeneous Distributed Systems. IEEE Transactions on Software Engineering, vol. 12, no. 5, May 1986, pp. 662-675.

Digital Library

[8]

Jan Edler, Jim Lipkis, and Edith Schonberg. Process Management for Highly Parallel UNIX Systems. UltracomputerNote #136, April 1988.

[9]

C.A.R. Hoare. Communicating Sequential Processes. Communications of the ACM, vol. 21, no. 8, Aug. 1978, pp. 666-677.

Digital Library

[10]

R. Holt. A Short Introduction to Concurrent Euclid. SIGPlANNotices, vol. 17, May 1982, pp. 60-79.

Digital Library

[11]

Eric Jul, Henry Levy, Norman Hutchinson, and Andrew Black. Fine- Grained Mobility in the Emerald System. ACM Transactions on Computer Systems, vol. 6, no. I, Feb. 1988, pp. 109-133.

Digital Library

[12]

B. Kumar and Timothy Gonsalves. Modelling and Analysis of Distributed Software Systems. Proc. 7th ACM Symposium on Operating Systems Principles, Dec. 1977, pp. 2-8.

Digital Library

[13]

B.W. Lampson and D.D. Redell. Experiences with Processes and Monitors in Mesa. Communications of the ACM, vol. 23, no. 2, Feb. 1980, pp. 104-i17.

Digital Library

[14]

Edward Lazowska, John Zahorjan, O. Scott Graham, and Kenneth Sevcik. Quantitative System Performance. Prentice-Hall, 1984.

Digital Library

[15]

Tom Lover and Shreekant Thakkar. The Symmetry Multiprocessor System. Proc. 1988 International Conference on Parallel Processing, pp. 303-310.

[16]

Robert Metcalfe and David Boggs. Ethernet: Distributed Packet Switching for Local Computer Networks. Communications of the ACM, vol. 19, no. 7, July 1976, pp. 395-404.

Digital Library

[17]

D.A. Mundie and D.A. Fisher. Parallel Processing in Ada. IEEE Computer, Aug. 1985, pp. 20-25.

Digital Library

[18]

Lionel Ni and Ching-Fern Wu. Design Trade-offs for Process Scheduling in Tightly Coupled Multiprocessor Systems. Proc. 1985 International Conference on Parallel Processing, pp. 63-70.

[19]

Michael Scott, Thomas LeBlanc, and Brian Marsh. Design Rationale for Psyche, a General Purpose Multiprocessor Operating System. Proc. 1988 International Conference on Parallel Processing, August, 1988.

[20]

. Sequent compmer Systems, Inc. Symmetry Technical Summary.

[21]

Charles Thacker, Lawrence Stewart, and Edward Satterthwaite Jr. Firefly: A Multiprocessor Workstation. IEEE Transactions on Computers, vol. 37, no. 8, Aug. 1988, pp. 909-920.

Digital Library

[22]

Mark Vandevoorde and Eric Roberts. WorkCrews: An Abstraction for Controlling Parallelism. Digital Equipment Corporation Systems Research Center, 1988.

[23]

David Wagner, Edward l.,a~wska, and Brian Bershad. Techniques for Efficient Shared-Menmry Parallel Simulation. Proc. Performance '89 / ACM SIGMETRICS 1989.

[24]

John Zahorjan, Edward Lazowska, and Derek Eager. Spinning Versus Blocking in Parallel Systems with Uncertainty. Proc. International Seminar on the Performance of Distributed and Parallel Systems, North Holland, De~ 1988.

Cited By

Gyen APataki N(2021)Comprehension of Thread Scheduling for the C++ Programming Language2021 International Conference on Data and Software Engineering (ICoDSE)10.1109/ICoDSE53690.2021.9648489(1-6)Online publication date: 3-Nov-2021
https://doi.org/10.1109/ICoDSE53690.2021.9648489
Abellán JFernández JAcacio M(2015)Efficient Hardware-Supported Synchronization Mechanisms for ManycoresHandbook on Data Centers10.1007/978-1-4939-2092-1_26(753-803)Online publication date: 17-Mar-2015
https://doi.org/10.1007/978-1-4939-2092-1_26
Abellán JFernández JAcacio M(2013)Design of an efficient communication infrastructure for highly contended locks in many-core CMPsJournal of Parallel and Distributed Computing10.1016/j.jpdc.2012.06.01073:7(972-985)Online publication date: Jul-2013
https://doi.org/10.1016/j.jpdc.2012.06.010
Show More Cited By

Index Terms

Recommendations

The Performance Implications of Thread Management Alternatives for Shared-Memory Multiprocessors

An examination is made of the performance implications of several data structure and algorithm alternatives for thread management in shared-memory multiprocessors. Both experimental measurements and analytical model projections are presented. For ...
The performance implications of thread management alternatives for shared-memory multiprocessors

Threads (“lightweight” processes) have become a common element of new languages and operating systems. This paper examines the performance implications of several data structure and algorithm alternatives for thread management in shared-memory ...
Speculative Locks for Concurrent Execution of Critical Sections in Shared-Memory Multiprocessors

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGMETRICS '89: Proceedings of the 1989 ACM SIGMETRICS international conference on Measurement and modeling of computer systems

April 1989

242 pages

ISBN:0897913159

DOI:10.1145/75108

Chairman:
Domenico Ferrari
Univ. of California, Berkeley

ACM SIGMETRICS Performance Evaluation Review Volume 17, Issue 1
May 1989
209 pages
ISSN:0163-5999
DOI:10.1145/75372
Editor:
Blaine D. Gaither
Gould Inc., San Diego, CA
Issue’s Table of Contents

Copyright © 1989 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: 01 April 1989

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

SIGMETRICS89

Sponsor:

SIGMETRICS

SIGMETRICS89: Performance 89 Intl Conference on Measurement & Modeling of Computer Systems

May 23 - 26, 1989

California, Oakland, USA

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

24
Total Citations
View Citations
1,234
Total Downloads

Downloads (Last 12 months)166
Downloads (Last 6 weeks)19

Reflects downloads up to 01 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Gyen APataki N(2021)Comprehension of Thread Scheduling for the C++ Programming Language2021 International Conference on Data and Software Engineering (ICoDSE)10.1109/ICoDSE53690.2021.9648489(1-6)Online publication date: 3-Nov-2021
https://doi.org/10.1109/ICoDSE53690.2021.9648489
Abellán JFernández JAcacio M(2015)Efficient Hardware-Supported Synchronization Mechanisms for ManycoresHandbook on Data Centers10.1007/978-1-4939-2092-1_26(753-803)Online publication date: 17-Mar-2015
https://doi.org/10.1007/978-1-4939-2092-1_26
Abellán JFernández JAcacio M(2013)Design of an efficient communication infrastructure for highly contended locks in many-core CMPsJournal of Parallel and Distributed Computing10.1016/j.jpdc.2012.06.01073:7(972-985)Online publication date: Jul-2013
https://doi.org/10.1016/j.jpdc.2012.06.010
Nicolau AKejariwal A(2011)How Many Threads to Spawn during Program Multithreading?Languages and Compilers for Parallel Computing10.1007/978-3-642-19595-2_12(166-183)Online publication date: 2011
https://doi.org/10.1007/978-3-642-19595-2_12
Nicolau AKejariwal A(2010)How many threads to spawn during program multithreading?Proceedings of the 23rd international conference on Languages and compilers for parallel computing10.5555/1964536.1964548(166-183)Online publication date: 7-Oct-2010
https://dl.acm.org/doi/10.5555/1964536.1964548
Matthews CCoady YAppavoo JProbst C(2006)Portability eventsProceedings of the 3rd workshop on Programming languages and operating systems: linguistic support for modern operating systems10.1145/1215995.1216006(11-es)Online publication date: 22-Oct-2006
https://dl.acm.org/doi/10.1145/1215995.1216006
Stoess JUhlig V(2006)Flexible, Low-overhead Event Logging to Support Resource SchedulingProceedings of the 12th International Conference on Parallel and Distributed Systems - Volume 210.1109/ICPADS.2006.50(115-120)Online publication date: 12-Jul-2006
https://dl.acm.org/doi/10.1109/ICPADS.2006.50
Weissman B(1998)Performance counters and state sharing annotationsACM SIGOPS Operating Systems Review10.1145/384265.29103532:5(127-138)Online publication date: 1-Oct-1998
https://dl.acm.org/doi/10.1145/384265.291035
Weissman BBhandarkar DAgarwal A(1998)Performance counters and state sharing annotationsProceedings of the eighth international conference on Architectural support for programming languages and operating systems10.1145/291069.291035(127-138)Online publication date: 1-Oct-1998
https://dl.acm.org/doi/10.1145/291069.291035
Weissman B(1998)Performance counters and state sharing annotationsACM SIGPLAN Notices10.1145/291006.29103533:11(127-138)Online publication date: 1-Oct-1998
https://dl.acm.org/doi/10.1145/291006.291035
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

Media

Figures

Other

Tables

View Table of Contents