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

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, .