Basic compiler algorithms for parallel programs

Jaejin Lee, David A Padua, Samuel P. Midkiff

Research output: Contribution to conferencePaper

Abstract

Traditional compiler techniques developed for sequential programs do not guarantee the correctness (sequential consistency) of compiler transformations when applied to parallel programs. This is because traditional compilers for sequential programs do not account for the updates to a shared variable by different threads. We present a concurrent static single assignment (CSSA) form for parallel programs containing cobegin/coend and parallel do constructs and post/wait synchronization primitives. Based on the CSSA form, we present copy propagation and dead code elimination techniques. Also, a global value numbering technique that detects equivalent variables in parallel programs is presented. By using global value numbering and the CSSA form, we extend classical common subexpression elimination, redundant load/store elimination, and loop invariant detection to parallel programs without violating sequential consistency. These optimization techniques are the most commonly used techniques for sequential programs. By extending these techniques to parallel programs, we can guarantee the correctness of the optimized program and maintain single processor performance in a multiprocessor environment.

Original languageEnglish (US)
Pages1-12
Number of pages12
StatePublished - Jan 1 1999
EventProceedings of the 1999 7th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP) aspart of the Federated Computing Research Conference(FCRC'99) - Atlanta, GA, USA
Duration: May 4 1999May 6 1999

Conference

ConferenceProceedings of the 1999 7th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP) aspart of the Federated Computing Research Conference(FCRC'99)
CityAtlanta, GA, USA
Period5/4/995/6/99

Fingerprint

Synchronization

ASJC Scopus subject areas

  • Software

Cite this

Lee, J., Padua, D. A., & Midkiff, S. P. (1999). Basic compiler algorithms for parallel programs. 1-12. Paper presented at Proceedings of the 1999 7th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP) aspart of the Federated Computing Research Conference(FCRC'99), Atlanta, GA, USA, .

Basic compiler algorithms for parallel programs. / Lee, Jaejin; Padua, David A; Midkiff, Samuel P.

1999. 1-12 Paper presented at Proceedings of the 1999 7th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP) aspart of the Federated Computing Research Conference(FCRC'99), Atlanta, GA, USA, .

Research output: Contribution to conferencePaper

Lee, J, Padua, DA & Midkiff, SP 1999, 'Basic compiler algorithms for parallel programs', Paper presented at Proceedings of the 1999 7th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP) aspart of the Federated Computing Research Conference(FCRC'99), Atlanta, GA, USA, 5/4/99 - 5/6/99 pp. 1-12.
Lee J, Padua DA, Midkiff SP. Basic compiler algorithms for parallel programs. 1999. Paper presented at Proceedings of the 1999 7th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP) aspart of the Federated Computing Research Conference(FCRC'99), Atlanta, GA, USA, .
Lee, Jaejin ; Padua, David A ; Midkiff, Samuel P. / Basic compiler algorithms for parallel programs. Paper presented at Proceedings of the 1999 7th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP) aspart of the Federated Computing Research Conference(FCRC'99), Atlanta, GA, USA, .12 p.
@conference{a7cb92e1f5b9416da819c37d9e466aa6,
title = "Basic compiler algorithms for parallel programs",
abstract = "Traditional compiler techniques developed for sequential programs do not guarantee the correctness (sequential consistency) of compiler transformations when applied to parallel programs. This is because traditional compilers for sequential programs do not account for the updates to a shared variable by different threads. We present a concurrent static single assignment (CSSA) form for parallel programs containing cobegin/coend and parallel do constructs and post/wait synchronization primitives. Based on the CSSA form, we present copy propagation and dead code elimination techniques. Also, a global value numbering technique that detects equivalent variables in parallel programs is presented. By using global value numbering and the CSSA form, we extend classical common subexpression elimination, redundant load/store elimination, and loop invariant detection to parallel programs without violating sequential consistency. These optimization techniques are the most commonly used techniques for sequential programs. By extending these techniques to parallel programs, we can guarantee the correctness of the optimized program and maintain single processor performance in a multiprocessor environment.",
author = "Jaejin Lee and Padua, {David A} and Midkiff, {Samuel P.}",
year = "1999",
month = "1",
day = "1",
language = "English (US)",
pages = "1--12",
note = "Proceedings of the 1999 7th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP) aspart of the Federated Computing Research Conference(FCRC'99) ; Conference date: 04-05-1999 Through 06-05-1999",

}

TY - CONF

T1 - Basic compiler algorithms for parallel programs

AU - Lee, Jaejin

AU - Padua, David A

AU - Midkiff, Samuel P.

PY - 1999/1/1

Y1 - 1999/1/1

N2 - Traditional compiler techniques developed for sequential programs do not guarantee the correctness (sequential consistency) of compiler transformations when applied to parallel programs. This is because traditional compilers for sequential programs do not account for the updates to a shared variable by different threads. We present a concurrent static single assignment (CSSA) form for parallel programs containing cobegin/coend and parallel do constructs and post/wait synchronization primitives. Based on the CSSA form, we present copy propagation and dead code elimination techniques. Also, a global value numbering technique that detects equivalent variables in parallel programs is presented. By using global value numbering and the CSSA form, we extend classical common subexpression elimination, redundant load/store elimination, and loop invariant detection to parallel programs without violating sequential consistency. These optimization techniques are the most commonly used techniques for sequential programs. By extending these techniques to parallel programs, we can guarantee the correctness of the optimized program and maintain single processor performance in a multiprocessor environment.

AB - Traditional compiler techniques developed for sequential programs do not guarantee the correctness (sequential consistency) of compiler transformations when applied to parallel programs. This is because traditional compilers for sequential programs do not account for the updates to a shared variable by different threads. We present a concurrent static single assignment (CSSA) form for parallel programs containing cobegin/coend and parallel do constructs and post/wait synchronization primitives. Based on the CSSA form, we present copy propagation and dead code elimination techniques. Also, a global value numbering technique that detects equivalent variables in parallel programs is presented. By using global value numbering and the CSSA form, we extend classical common subexpression elimination, redundant load/store elimination, and loop invariant detection to parallel programs without violating sequential consistency. These optimization techniques are the most commonly used techniques for sequential programs. By extending these techniques to parallel programs, we can guarantee the correctness of the optimized program and maintain single processor performance in a multiprocessor environment.

UR - http://www.scopus.com/inward/record.url?scp=0032691545&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0032691545&partnerID=8YFLogxK

M3 - Paper

AN - SCOPUS:0032691545

SP - 1

EP - 12

ER -