article

Free access

Optimizing parallel programs with explicit synchronization

Authors:

Arvind Krishnamurthy,

Katherine YelickAuthors Info & Claims

ACM SIGPLAN Notices, Volume 30, Issue 6

Pages 196 - 204

https://doi.org/10.1145/223428.207142

Published: 01 June 1995 Publication History

Abstract

We present compiler analyses and optimizations for explicitly parallel programs that communicate through a shared address space. Any type of code motion on explicitly parallel programs requires a new kind of analysis to ensure that operations reordered on one processor cannot be observed by another. The analysis, based on work by Shasha and Snir, checks for cycles among interfering accesses. We improve the accuracy of their analysis by using additional information from post-wait synchronization, barriers, and locks.

We demonstrate the use of this analysis by optimizing remote access on distributed memory machines. The optimizations include message pipelining, to allow multiple outstanding remote memory operations, conversion of two-way to one-way communication, and elimination of communication through data re-use. The performance improvements are as high as 20-35% for programs running on a CM-5 multiprocessor using the Split-C language as a global address layer.

References

[1]

S.V. Adve and M. D. Hill. Weak Ordering-A New Definition. In I 7th International Symposium on Computer Architecture, April 1990.

Digital Library

[2]

P~. Arpaci, D. Culler, A. Krishnamurthy, S. Steinberg, and K. Yelick. Empirical Evaluation of the CRAY-T3D: A Compiler Perspective. In Internatzonat Symposium on Computer Architect~tre, June 1995.

Digital Library

[3]

H. Berryman, J. Saltz, and J. Scroggs. Execution Time Support for Adaptive Scientific Algorithms on Distributed Memory Multiprocessors. Concurrenty: Practice and Experience, June 1991.

Digital Library

[4]

D. Callahan and J. Subhlok. Static Analysis of Low-level Synchronization. In A CM SIGPLAN and SIGOPS Workshop on Parallel and Distributed Debugging, May 1988.

Digital Library

[5]

W. W. Carlson and J. M. Draper. Distributed Data Access in AC. In A CM Symposzum on Pr~nc,ples and Practice of Parallel Programming, July 1995.

Digital Library

[6]

D.E. Culler, A. Dusseau, S. C. Goldstein, A. Krishnamurthy, S. Lumetta, T. yon Eicken, and K. Yelick. Parallel Programming in Split-C. In Supercomp~t~ng '93, Portland, Oregon, November 1993.

Digital Library

[7]

K. Gharachorloo, D. Lenoski, J. Laudon, A. Gupta, and J. Hennessy. Memory Consistency and Event Ordering in Scalable Shared-Memory Multiprocessors. In 17th International Symposzum on Computer Architecture, 1990.

Digital Library

[8]

D. Grunwald and H. Srinivasan. Data flow equations for Explicitly Parallel Programs. In A UM Symposium on Principles and Practices of Parallel Programming, June 1993.

Digital Library

[9]

S. Hiranandani, K. Kennedy. and C.-W. Tseng. Compiler 0ptimziations for Fortran D on MIMD Distributed-Memory Machines. In Proceedings of the 199t International Conference on Supercomputing, 1991.

Digital Library

[10]

T. Ig. Jeremiassen and S. J. Eggers. Reducing False Sharing on Shared Memory Multiprocessors through Compile Time Data Transformations. In A CM Symposium on Principles and Practice of Parallel Programming, July 1995.

Digital Library

[11]

A. Krishnamurthy and K. Yelick. Optimizing Parallel SPMD Programs. In Languages and Compilers for Parallel Computing, 1994.

Digital Library

[12]

L. Lamport. How to Make a Multiprocessor Computer that Correctly Executes Multiprocess Programs. IEEE Transactions on Computers, C-28(9), September 1979.

[13]

D. Lenoski, J. Laudon, K. Gharachorloo, A. Gupta, and J. Hennessy. The Directory-Based Cache Coherence Protocol for the DASH Multiprocessor. In 17th International Symposium on Computer Architecture, May 1990.

Digital Library

[14]

N. K. Madsen. Divergence Preserving Discrete Surface Integral Methods for Maxwell's Curl Equations Using Non- Orthogonal Unstructured Grids. Technical Report 92.04, RIACS, February 1992.

[15]

S. Midkiff and D. Padua. Issues in the Optimization of Parallel Programs. In International Conference on Parallel Processing- Vol II, 1990.

[16]

S. P. Midkiff, D. Padua, and R. G. Cytron. Compiling Programs with User Parallelism. In Languages and Compilers for Parallel Computing, 1990.

Digital Library

[17]

A. Rogers and K. Pingali. Compiling for distributed memory architectures. IEEE Transactions on Parallel and Distributed Systems, March 1994.

Digital Library

[18]

D. Shasha and M. Snir. Efficient and Correct Execution of Parallel Programs that Share Memory. ACM Transactions on Programming Languages and Systems, 10(2), April 1988.

Digital Library

[19]

J.P. Singh, W. D. Weber, and A. Gupta. SPLASH: Stanford parallel applications for shared memory. Computer Architecture News, March 1992.

Digital Library

[20]

The SPARC Architecture Manual: Version 8. Spare International, Inc., 1992.

Digital Library

[21]

T. yon Eicken, D. E. Culler, S. C. Goldstein, and K. E. Schauser. Active Messages: a Mechanism for Integrated Communication and Computation. In International Symposium on Computer Architecture, May 1992.

Digital Library

Cited By

Midkiff S(2012)Automatic Parallelization: An Overview of Fundamental Compiler TechniquesSynthesis Lectures on Computer Architecture10.2200/S00340ED1V01Y201201CAC0197:1(1-169)Online publication date: 28-Jan-2012
https://doi.org/10.2200/S00340ED1V01Y201201CAC019
Lin CNagarajan VGupta R(2011)Efficient Sequential Consistency Using Conditional FencesInternational Journal of Parallel Programming10.1007/s10766-011-0176-340:1(84-117)Online publication date: 28-Jun-2011
https://doi.org/10.1007/s10766-011-0176-3
Cadavid Rengifo HGómez Perdomo J(2009)Web text corpus extraction system for linguistic tasksIngeniería e Investigación10.15446/ing.investig.v29n3.1518329:3(54-60)Online publication date: 1-Sep-2009
https://doi.org/10.15446/ing.investig.v29n3.15183
Show More Cited By

Index Terms

Optimizing parallel programs with explicit synchronization
1. Computing methodologies
  1. Parallel computing methodologies
    1. Parallel programming languages
2. Software and its engineering
  1. Software notations and tools
    1. Compilers
      1. Source code generation
    2. General programming languages
      1. Language types
        Concurrent programming languages
        Distributed programming languages
        Parallel programming languages

Recommendations

Optimizing parallel programs with explicit synchronization
PLDI '95: Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation

We present compiler analyses and optimizations for explicitly parallel programs that communicate through a shared address space. Any type of code motion on explicitly parallel programs requires a new kind of analysis to ensure that operations reordered ...
Optimizing explicitly parallel programs
Compiling data-parallel programs for clusters of SMPs: Research Articles
Compilers for Parallel Computers

Clusters of shared-memory multiprocessors (SMPs) have become the most promising parallel computing platforms for scientific computing. However, SMP clusters significantly increase the complexity of user application development when using the low-level ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGPLAN Notices

ACM SIGPLAN Notices Volume 30, Issue 6

June 1995

327 pages

ISSN:0362-1340

EISSN:1558-1160

DOI:10.1145/223428

Editors:
Brent T. Hailpern
IBM T. J. Watson Research Center, Yorktown Heoghts, NY
,
Richard L. Wexelblat
IRS IS:AO, Washington, DC

Issue’s Table of Contents

PLDI '95: Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation
June 1995
335 pages
ISBN:0897916972
DOI:10.1145/207110
Chairman:
David W. Wall
Digital—Western Research Laboratory

Copyright © 1995 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: 01 June 1995

Published in SIGPLAN Volume 30, Issue 6

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

49
Total Citations
View Citations
524
Total Downloads

Downloads (Last 12 months)75
Downloads (Last 6 weeks)24

Reflects downloads up to 24 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Midkiff S(2012)Automatic Parallelization: An Overview of Fundamental Compiler TechniquesSynthesis Lectures on Computer Architecture10.2200/S00340ED1V01Y201201CAC0197:1(1-169)Online publication date: 28-Jan-2012
https://doi.org/10.2200/S00340ED1V01Y201201CAC019
Lin CNagarajan VGupta R(2011)Efficient Sequential Consistency Using Conditional FencesInternational Journal of Parallel Programming10.1007/s10766-011-0176-340:1(84-117)Online publication date: 28-Jun-2011
https://doi.org/10.1007/s10766-011-0176-3
Cadavid Rengifo HGómez Perdomo J(2009)Web text corpus extraction system for linguistic tasksIngeniería e Investigación10.15446/ing.investig.v29n3.1518329:3(54-60)Online publication date: 1-Sep-2009
https://doi.org/10.15446/ing.investig.v29n3.15183
Knoop JSteffen B(1999)Code motion for explicitly parallel programsACM SIGPLAN Notices10.1145/329366.30110634:8(13-24)Online publication date: 1-May-1999
https://dl.acm.org/doi/10.1145/329366.301106
Knoop JSteffen BSnir MChien A(1999)Code motion for explicitly parallel programsProceedings of the seventh ACM SIGPLAN symposium on Principles and practice of parallel programming10.1145/301104.301106(13-24)Online publication date: 1-May-1999
https://dl.acm.org/doi/10.1145/301104.301106
Zhu YHendren L(1999)Communication Optimizations for Parallel C ProgramsJournal of Parallel and Distributed Computing10.1006/jpdc.1999.155458:2(301-332)Online publication date: 1-Aug-1999
https://dl.acm.org/doi/10.1006/jpdc.1999.1554
Nanri TSato HShimasaki M(1997)Using cache optimizing compiler for managing software cache on distributed shared memory systemProceedings of the High-Performance Computing on the Information Superhighway, HPC-Asia '9710.5555/523549.822914Online publication date: 28-Apr-1997
https://dl.acm.org/doi/10.5555/523549.822914
Nanri TSato HShimasaki M(1997)Using cache optimizing compiler for managing software cache on distributed shared memory systemProceedings High Performance Computing on the Information Superhighway. HPC Asia '9710.1109/HPC.1997.592166(312-318)Online publication date: 1997
https://doi.org/10.1109/HPC.1997.592166
Soden RPalen L(2018)Informating CrisisProceedings of the ACM on Human-Computer Interaction10.1145/32744312:CSCW(1-22)Online publication date: 1-Nov-2018
https://dl.acm.org/doi/10.1145/3274431
Soden RLord A(2018)Mapping Silences, Reconfiguring LossProceedings of the ACM on Human-Computer Interaction10.1145/32744302:CSCW(1-21)Online publication date: 1-Nov-2018
https://dl.acm.org/doi/10.1145/3274430
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 Issue’s Table of Contents