Article

Free access

Barrier inference

Authors:

Alexander Aiken,

David GayAuthors Info & Claims

POPL '98: Proceedings of the 25th ACM SIGPLAN-SIGACT symposium on Principles of programming languages

Pages 342 - 354

https://doi.org/10.1145/268946.268974

Published: 21 January 1998 Publication History

Abstract

Many parallel programs are written in SPMD style i.e. by running the same sequential program on all processes. SPMD programs include synchronization, but it is easy to write incorrect synchronization patterns. We propose a system that verifies a program's synchronization pattern. We also propose language features to make the synchronization pattern more explicit and easily checked. We have implemented a prototype of our system for Split-C and successfully verified the synchronization structure of realistic programs.

References

[1]

J. Auslander, M. Philipose, C. Chambers, S. J. Eggers, and B. N. Bershad. Fast, Effective Dynamic Compilation. In Proceedings of the A CM SIGPLAN '96 Con- }erence on Programming Language Design and Implementation, pages 149-159, Philadelphia, Pennsylvania, May 1996.

Digital Library

[2]

D. (3allahan, K. Kennedy, and J. Subhlok. Analysis of Event Synchronization in a Parallel Programming Tool. In Proceedings of the Second A CM SIGPLAN Symposium on Principles and Practice of Parallel Programming, pages 21-30, Seattle WA, March 1990.

Digital Library

[3]

D. (3allahan and J. Subhlok. Static Analysis of Low- Level Synchronization. In Proceedings of the A CM SIGPLAN and SIGOPS Workshop on Parallel and Distributed Debugging, pages 100-111, Madison, WI USA, {1} 1989. A(3M Press, New York, NY, USA. Published as SIGPLAN Notices, volume 24, number

Digital Library

[4]

Gray Research Incorporated. The URA Y T3D Hardware Reference Manual, 1993.

[5]

D. E. (3uller, A. Dusseau, S. (3. Goldstein, A. Krishnamurthy, S. Lumetta, T. yon Eicken, and K. Yelick. Introduction to Sptit-U. University of California, Berkeley, 1993.

[6]

D. Gay. Barrier Inference. Technical Report U(3B//GSD-97-965, EECS Computer Science Division, University of California, Berkeley, July 1997.

Digital Library

[7]

D. Gifford, P. Jouvelot, J. Lucassen, and M. Sheldon. FX-87 REFERENCE MANUAL. Technical Report MIT-LCS//MIT/L(3S/TR-407, Massachusetts Institute of Technology, Laboratory for Computer Science, September 1987'.

[8]

J. Gosling, B. Joy, and G. Steele. The Java Language Specification. The Java Series. Addison-Wesley, Readhag, MA, USA, June 1996.

Digital Library

[9]

D. P. Helmbold and (3. E. McDowell. Computing Reachable States of Parallel Programs. Proceedings of the A CM/ONR Workshop on Parallel and Dis-. tributed Debugging, published in A CM SIGPLAN Notices, 26(12):76--84, December 1991.

Digital Library

[10]

T. 3eremiassen and S. Eggers. Computing Per-Process Summary Side-Effect Information. In Proceedings of the 5th International Workshop on Languages and Compilers for Parallel Computing, number 757 in Lecture Notes in Computer Science, pages 175-191, New Haven, (3onnecticut, August 3-5, 1992. Springer- Verlag.

Digital Library

[11]

T. E. Jeremiassen and S. 3. Eggers. Static Analysis of Barrier Synchronization in Explicitly Parallel Systems. In Proceedings of the IFIP WG 10.3 Working Conference on Parallel Architectures and Compilation Techniques, PACT '94, pages 171-180, Montreal, Quebec, August 24-26, 1994. North-Holland Publishing Co.

Digital Library

[12]

N. D. Jones, (3. K. Gomard, and P. Sestoff. Partial Evaluation and Automatic Program Generation. Prentice-Hall, 1993.

Digital Library

[13]

A. Krishnamurthy, D. E. Culler, A. Dusseau, S. G. Goldstein, S. Lumetta, T. yon Eicken, and K. Yelick. Parallel Programming in Split-G. In Proceedings of the Supercomputing "93 Conference, pages 262-273, Portland, OR, November 1993. IEEE Computer Society Press.

Digital Library

[14]

A. Krishnamur~hy and K. Yelick. Optimizing Parallel Programs with Explicit Synchronization. In ACM SIGPLAN '95 Conference on Programming Language Design and Implementation, pages 196--204, New York, NY, USA, June 1995. ACM Press.

Digital Library

[15]

W. Landi and B. G. Ryder. A Safe Approximate A1- goriLhm for Iaterprocedural Poinier Aliasing. In A GM SIGPLAN '9~ Conyerence on Programming Language Design and Implementation, pages 235-248, June 1992.

Digital Library

[16]

D. H. Lawrie, T. Layman, D. Baer, and J. :M. Randal. Glypnir- A Programming Language for Illiac IV. Communications of the A CM, 18(3):157-164, March 1975.

Digital Library

[17]

C. E. Leiserson, Z. S. Abuhamdeh, D. C. Douglas, C. R. Feynman, M. N. Ganmukhi, 5. V. Hill, W. D. Hillls, B. C. Kuszmaul, M. A. SL Pierre, D. S. Wells, M. C. Wong, S. Yang, and R. Zak. The Network Architecture of the CM-5. In Symposium on Parallel and Distributed Algorithms "9,9, June 1992.

Digital Library

[18]

S. P. Masficola and B. G. Ryder. Non-concurrency Analysis. In Fourth A CM SIGPLAN Symposium on Princip}es and Practice of Parallel Programming, pages 129-138, New York, NY, USA, July 1993. AGM Press.

Digital Library

[19]

C. E. McDowell. A Practical Algorithm for Static Analysis of Parallel Programs. Journal of Parallel and Distributed Gompu~ing, 6(3):515-536, {6} 1989.

Digital Library

[20]

Message Passing Interface Forum. Document for a standard message-passing interface. Technical Report UT-CS-93-214, University of Tennessee, Knoxville, 1993.

Digital Library

[21]

M. A. Nichols, H. J. Siegel, and H. G. Dietz. Data Management and Control-Flow Aspects of an SIMD/SPMD Parallel Language/Compiler. IEEE Transactions on Parallel and Distributed Systems, 4(2):222-234, February 1993.

Digital Library

[22]

R. N. Taylor. A General-Purpose Algorithm for Analyzing Concurrent Programs. Communications of the ACM, 26(5):362-376, May 1983.

Digital Library

[23]

Thinking Machines Corporation. G* Programming Guide, 1993.

[24]

L. Wang. ELP User's Manual Parallel Processing Laboratory, School of Electrical and Computer Engineering, Purdue UniversiLy, March 1996.

[25]

S. Cameron Woo, M. Ohaxa, E. Torrie, J. Pal Shin~h, and A. Gupta. The SPLASH-2 Programs: Characterization and Methodological Considerations. In Proceedings of the 22rid Annual International Symposium on Computer Architecture, pages 24-36, Santa Margherita Ligure, I~aly, June 22-24, 1995. ACM SIGARCH and IEEE Computer Society TCGA.

Digital Library

[26]

M. Young and R. N. Taylor. Combining Static Concurrency Analysis 'wi~h Symbolic Execution. In Proceedings Workshop on Software Testing, pages 10-18, 1986.

Cited By

Burak SIvanov IDomke JMüller M(2024)SPMD IR: Unifying SPMD and Multi-value IR Showcased for Static Verification of CollectivesRecent Advances in the Message Passing Interface10.1007/978-3-031-73370-3_1(3-20)Online publication date: 25-Sep-2024
https://doi.org/10.1007/978-3-031-73370-3_1
Moses WIvanov IDomke JEndo TDoerfert JZinenko ODehnavi MKulkarni MKrishnamoorthy S(2023)High-Performance GPU-to-CPU Transpilation and Optimization via High-Level Parallel ConstructsProceedings of the 28th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming10.1145/3572848.3577475(119-134)Online publication date: 25-Feb-2023
https://dl.acm.org/doi/10.1145/3572848.3577475
Rosemann JMoll SHack S(2021)An abstract interpretation for SPMD divergence on reducible control flow graphsProceedings of the ACM on Programming Languages10.1145/34343125:POPL(1-31)Online publication date: 4-Jan-2021
https://dl.acm.org/doi/10.1145/3434312
Show More Cited By

Index Terms

Recommendations

Barrier Inference
Distributed Hardwired Barrier Synchronization for Scalable Multiprocessor Clusters

Conventional multiprocessors mostly use centralized, memory-based barriers to synchronize concurrent processes created in multiple processors. These centralized barriers often become the bottleneck or hot spots in the shared memory. In this paper, we ...
Lightweight barrier-based parallelization support for non-cache-coherent MPSoC platforms
CASES '07: Proceedings of the 2007 international conference on Compilers, architecture, and synthesis for embedded systems

Many MPSoC applications are loop-intensive and amenable to automatic parallelization with suitable compiler support. One of the key components of any compiler-parallelized code is barrier instructions which are used to perform global synchronization ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

POPL '98: Proceedings of the 25th ACM SIGPLAN-SIGACT symposium on Principles of programming languages

January 1998

403 pages

ISBN:0897919793

DOI:10.1145/268946

Chairmen:
David B. MacQueen
Bell Labs
,
Luca Cardelli
Digital Equipment Corp.

Copyright © 1998 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

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 21 January 1998

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

POPL98

Sponsor:

POPL98: Symposium on Principles of Programming Languages

January 19 - 21, 1998

California, San Diego, USA

Acceptance Rates

POPL '98 Paper Acceptance Rate 32 of 175 submissions, 18%;

Overall Acceptance Rate 824 of 4,130 submissions, 20%

Upcoming Conference

POPL '25

Sponsor:
sigplan

The 52nd Annual ACM SIGPLAN Symposium on Principles of Programming Languages

January 19 - 25, 2025

Denver , CO , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

88
Total Citations
View Citations
249
Total Downloads

Downloads (Last 12 months)106
Downloads (Last 6 weeks)15

Reflects downloads up to 17 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Burak SIvanov IDomke JMüller M(2024)SPMD IR: Unifying SPMD and Multi-value IR Showcased for Static Verification of CollectivesRecent Advances in the Message Passing Interface10.1007/978-3-031-73370-3_1(3-20)Online publication date: 25-Sep-2024
https://doi.org/10.1007/978-3-031-73370-3_1
Moses WIvanov IDomke JEndo TDoerfert JZinenko ODehnavi MKulkarni MKrishnamoorthy S(2023)High-Performance GPU-to-CPU Transpilation and Optimization via High-Level Parallel ConstructsProceedings of the 28th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming10.1145/3572848.3577475(119-134)Online publication date: 25-Feb-2023
https://dl.acm.org/doi/10.1145/3572848.3577475
Rosemann JMoll SHack S(2021)An abstract interpretation for SPMD divergence on reducible control flow graphsProceedings of the ACM on Programming Languages10.1145/34343125:POPL(1-31)Online publication date: 4-Jan-2021
https://dl.acm.org/doi/10.1145/3434312
Dabrowski F(2021)On Single-Valuedness in Textually Aligned SPMD ProgramsInternational Journal of Parallel Programming10.1007/s10766-021-00710-5Online publication date: 4-May-2021
https://doi.org/10.1007/s10766-021-00710-5
Jakobsson ADabrowski FBousdira WHung CPapadopoulos G(2019)Safe usage of registers in BSPlibProceedings of the 34th ACM/SIGAPP Symposium on Applied Computing10.1145/3297280.3297421(1400-1407)Online publication date: 8-Apr-2019
https://dl.acm.org/doi/10.1145/3297280.3297421
Bousdira W(2019)Transforming non textually aligned SPMD programs into textually aligned SPMD programs by using rewriting rules2019 International Conference on High Performance Computing & Simulation (HPCS)10.1109/HPCS48598.2019.9188223(982-989)Online publication date: Jul-2019
https://doi.org/10.1109/HPCS48598.2019.9188223
Huchant PSaillard EBarthou DCarribault P(2019)Multi-valued Expression Analysis for Collective CheckingEuro-Par 2019: Parallel Processing10.1007/978-3-030-29400-7_3(29-43)Online publication date: 26-Aug-2019
https://dl.acm.org/doi/10.1007/978-3-030-29400-7_3
Wilcox JFlanagan CFreund S(2018)VerifiedFTACM SIGPLAN Notices10.1145/3200691.317851453:1(354-367)Online publication date: 10-Feb-2018
https://dl.acm.org/doi/10.1145/3200691.3178514
Wilcox JFlanagan CFreund SKrall AGross T(2018)VerifiedFTProceedings of the 23rd ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming10.1145/3178487.3178514(354-367)Online publication date: 10-Feb-2018
https://dl.acm.org/doi/10.1145/3178487.3178514
Dabrowski FHaddad HWainwright RChbeir R(2018)Textual alignment in SPMD programsProceedings of the 33rd Annual ACM Symposium on Applied Computing10.1145/3167132.3167254(1046-1053)Online publication date: 9-Apr-2018
https://dl.acm.org/doi/10.1145/3167132.3167254
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