article

Free access

First-class synchronization barriers

Author:

Franklyn TurbakAuthors Info & Claims

ACM SIGPLAN Notices, Volume 31, Issue 6

Pages 157 - 168

https://doi.org/10.1145/232629.232645

Published: 15 June 1996 Publication History

Abstract

Our purpose is to promote a second-class mechanism --- the synchronization barrier --- to a first-class value. We introduce the synchron, a novel synchronization mechanism that enables the coordination of a dynamically varying set of concurrent threads that share access to a first-class synchronization token. We demonstrate how synchrons can be used to modularly manage resources in cases where existing techniques are either inapplicable or non-modular. In particular, synchronized lazy aggregates enable the first space-efficient aggregate data decomposition of a wide range of algorithms. We also introduce explicit-demand graph reduction, a new semantic framework that we have developed to describe concurrency and explain the meaning of a synchron rendezvous.

References

[1]

Zena Ariola and Arvind. Properties of a first-order functional language with sharing. Theoretical Computer Science, 146:69-108, 1995.

Digital Library

[2]

Shail Aditya, Arvind, and Joseph E. Stoy. Semantics of barriers in a non-strict, implicitly-parallel language. Technical Report Computation Structures Group Memo 367, MIT Laboratory for Computer Science, january 1995.

Digital Library

[3]

Zena Ariola and Matthias Felleisen. The call-byneed lambda calculus. Technical Report CIS-TR- 94-23, Department of Computer Science, University of Oregon, October 1994.

[4]

Andrew W. Appel. Compiling with Continuations. Cambridge University Press, 1992.

Digital Library

[5]

Zena Ariola. Personal communication, January 1996.

[6]

E. A. Ashcroft. Datafiow and eduction: Datadriven and demand-driven distributed computing. In J. W. deBakker, W.-P. de Roever, and G. Rozenberg, editors, Current Trends in Concurrency: Overviews and Tutorials, pages 1-50. Springer- Verlag, 1986. Lecture Notes in Computer Science, Number 224.

[7]

H.P. Barendregt et al. Toward an intermediate language based on graph rewriting, in PARLE: Parallel Architectures and Languages Europe, Volume 2, pages 159- 175. Springer-Verlag, 1987. Lecture Notes in Computer Science, Number 259.

[8]

Paul S. Barth. Atomic data structures for parallel computing. Technical Report MiT/LCS/TR- 532, MIT Laboratory for Computer Science, March 1992.

[9]

Alan Bawden. Linear Graph Reduction: Confronting the Cost of Naming. PhD thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, June 1992.

Digital Library

[10]

Richard S. Bird. Lectures on constructive functional programming. In Manfred Broy, editor, Constructive Methods in Computing Science (NA TO ASI Series, Vol. F55), pages 5-42. Springer-Verlag, 1988.

[11]

Andrew Birrel. An introduction to programming with threads. SRC Report 35, Digital Equipment Corporation, January 1989.

[12]

Eric Cooper and J. Gregory Morrisett. Adding threads to standard ML. Technical Report CMU- CS-90-186, Carnegie Mellon University Computer Science Department, December 1990.

[13]

William Clinger, Jonathan Rees, et al. Revised4 report on the algorithmic language Scheme. Lisp Pointers, 4(3), 1991.

Digital Library

[14]

E. W. Dijkstra. Co-operating sequential processes. In F. Genuys, editor, Programming Languages (NATO Advanced Study institute), pages 43-112. London: Academic Press, 1968.

[15]

John Darlington and R.M.BurstaU. A system which automatically improves programs. Acta informatica, pages 41-60, 1976.

[16]

Alessandro Forin. Futures. In Peter Lee, editor, Topics in Advanced Language Implementation, pages 219-241. MIT Press, 1991.

[17]

David Gelernter and Suresh Jagannathan. Programming Linguistics. MIT Press, 1990.

Digital Library

[18]

Andrew Gill, John Launchbury, and Simon L. Peyton Jones. A short cut to deforestation. In Functional Programming and Computer Architecture, 1993.

Digital Library

[19]

Robert Halstead. Multilisp: A language for concurrent symbolic computation. A CM Transactions on Programming Languages and Systems, pages 501- 528, October 1985.

Digital Library

[20]

C.A.R. Hoare. Monitors: An operating system structuring concept. Communications of the A CM, 17(10):549-557, 1974.

Digital Library

[21]

C.A.R. Hoare. Communicating Sequential Processes. Prentice-Hall, 1985.

Digital Library

[22]

R. J. M. Hughes. Parallel functional languages use less space. Technical report, Oxford University Programming Research Group, 1984.

[23]

R. J. M. Hughes. Why functional programming matters. In David Turner, editor, Research Topics in Functional Programming, pages 17-42. Addison Wesley, 1990.

[24]

James S. Miller. MultiScheme: A parallel processing system based on MIT Scheme. Technical Report MIT/LCS/TR-402, MIT Laboratory for Computer Science, September 1987.

[25]

Robin Milner. Communication and Concurrency. Prentice-Hall, 1989.

Digital Library

[26]

K eshav Pingali and Arvind. Efficient demanddriven evaluation (I). A CM Transactions on Programming Languages and Systems, 7(2):311-333, April 1985.

Digital Library

[27]

Keshav Pingali and Arvind. Efficient demanddriven evaluation (II). A CM Transactions on Programming Languages and Systems, 8(1):109-139, January 1986.

Digital Library

[28]

James L. Peterson. Petri nets. A CM Computing Surveys, 9(3):223-250, 1977.

Digital Library

[29]

Simon L. Peyton Jones. The Implementation of Functional Programming Languages. Prentice-Hall, 1987.

Digital Library

[30]

Gordon D. Plotkin. A structural approach to operational semantics. Technical Report DAIMI FN-19, Aarhus University Computer Science Department, September 1981.

[31]

J. H. Reppy. CML: A higher-order concurrent language. In Proceed~ng~ of the SlCPLAN '91 Conference on Programming Language Design and Implementation., pages 293-305, 1991.

Digital Library

[32]

D. A. Turner. A new implementation for applicatire languages. Software - Practice and Experience, 9:31-49, 1979.

[33]

Franldyn Turbak. Slivers: Computational Modularity via Synchronized Lazy Aggregates. PhD thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, February 1994. Accessible from http://www-swiss, ai .mit. edu/~lyn/slivers.html Also to appear as MIT Artificial Intelligence Laboratory AI-TR- 1466.

Digital Library

[34]

Philip WadIer. Listlessness is better than laziness: Lazy evaluation and garbage collection at compiletime. In A CM Symposium On Lisp and Functional Programming, pages 45-52, 1984.

Digital Library

[35]

Philip Wadler. Deforestation: Transforming programs to eliminate trees. In 2nd European Symposium on Programming, pages 344-358, 1988. Lecture Notes in Computer Science, Number 300.

Digital Library

[36]

Richard C. Waters. Series. In Guy L. Steele Jr., editor, Common Lisp: The Language, pages 923- 955. Digital Press, 1990.

[37]

Richard C. Waters. Automatic transformation of series expressions into loops. A CM Transactions on Programming Languages and Systems, 13(1):52-98, January 1991.

Digital Library

[38]

Paul R. Wilson. Uniprocessor garbage collection techniques. A CM Computing Surveys (to appear).

Cited By

Cogumbreiro THu RMartins FYoshida N(2018)Dynamic Deadlock Verification for General Barrier SynchronisationACM Transactions on Programming Languages and Systems10.1145/322906041:1(1-38)Online publication date: 11-Dec-2018
https://doi.org/10.1145/3229060
Cogumbreiro THu RMartins FYoshida N(2018)Dynamic Deadlock Verification for General Barrier SynchronisationACM Transactions on Programming Languages and Systems10.1145/322906041:1(1-38)Online publication date: 11-Dec-2018
https://dl.acm.org/doi/10.1145/3229060
Cogumbreiro THu RMartins FYoshida N(2015)Dynamic deadlock verification for general barrier synchronisationACM SIGPLAN Notices10.1145/2858788.268851950:8(150-160)Online publication date: 24-Jan-2015
https://dl.acm.org/doi/10.1145/2858788.2688519
Show More Cited By

Index Terms

First-class synchronization barriers
1. Software and its engineering
  1. Software notations and tools
    1. Compilers
    2. Formal language definitions
2. Theory of computation

Recommendations

First-class synchronization barriers
ICFP '96: Proceedings of the first ACM SIGPLAN international conference on Functional programming

Our purpose is to promote a second-class mechanism --- the synchronization barrier --- to a first-class value. We introduce the synchron, a novel synchronization mechanism that enables the coordination of a dynamically varying set of concurrent threads ...
Partial aborts for transactions via first-class continuations
ICFP 2015: Proceedings of the 20th ACM SIGPLAN International Conference on Functional Programming

Software transactional memory (STM) has proven to be a useful abstraction for developing concurrent applications, where programmers denote transactions with an atomic construct that delimits a collection of reads and writes to shared mutable ...
Partial aborts for transactions via first-class continuations
ICFP '15

Software transactional memory (STM) has proven to be a useful abstraction for developing concurrent applications, where programmers denote transactions with an atomic construct that delimits a collection of reads and writes to shared mutable ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGPLAN Notices

ACM SIGPLAN Notices Volume 31, Issue 6

June 15, 1996

273 pages

ISSN:0362-1340

EISSN:1558-1160

DOI:10.1145/232629

Chairmen:
Robert Harper
Carnegie Mellon Univ., Pittsburgh, PA
,
Richard L. Wexelblat

Issue’s Table of Contents

ICFP '96: Proceedings of the first ACM SIGPLAN international conference on Functional programming
June 1996
273 pages
ISBN:0897917707
DOI:10.1145/232627
Chairman:
Robert Harper
Carnegie Mellon Univ., Pittsburgh, PA
,
Editor:
Richard L. Wexelblat

Copyright © 1996 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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 15 June 1996

Published in SIGPLAN Volume 31, Issue 6

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
439
Total Downloads

Downloads (Last 12 months)87
Downloads (Last 6 weeks)12

Reflects downloads up to 09 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Cogumbreiro THu RMartins FYoshida N(2018)Dynamic Deadlock Verification for General Barrier SynchronisationACM Transactions on Programming Languages and Systems10.1145/322906041:1(1-38)Online publication date: 11-Dec-2018
https://doi.org/10.1145/3229060
Cogumbreiro THu RMartins FYoshida N(2018)Dynamic Deadlock Verification for General Barrier SynchronisationACM Transactions on Programming Languages and Systems10.1145/322906041:1(1-38)Online publication date: 11-Dec-2018
https://dl.acm.org/doi/10.1145/3229060
Cogumbreiro THu RMartins FYoshida N(2015)Dynamic deadlock verification for general barrier synchronisationACM SIGPLAN Notices10.1145/2858788.268851950:8(150-160)Online publication date: 24-Jan-2015
https://dl.acm.org/doi/10.1145/2858788.2688519
Cogumbreiro THu RMartins FYoshida NCohen AGrove D(2015)Dynamic deadlock verification for general barrier synchronisationProceedings of the 20th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming10.1145/2688500.2688519(150-160)Online publication date: 24-Jan-2015
https://dl.acm.org/doi/10.1145/2688500.2688519
Donnelly KFluet M(2008)Transactional events1Journal of Functional Programming10.1017/S095679680800691618:5-6(649-706)Online publication date: 1-Sep-2008
https://dl.acm.org/doi/10.1017/S0956796808006916
Donnelly KFluet M(2006)Transactional eventsACM SIGPLAN Notices10.1145/1160074.115982141:9(124-135)Online publication date: 16-Sep-2006
https://dl.acm.org/doi/10.1145/1160074.1159821
Donnelly KFluet MReppy JLawall J(2006)Transactional eventsProceedings of the eleventh ACM SIGPLAN international conference on Functional programming10.1145/1159803.1159821(124-135)Online publication date: 17-Sep-2006
https://dl.acm.org/doi/10.1145/1159803.1159821

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 Issue’s Table of Contents