Analysis and Optimization of Explicitly Parallel Programs

• Author(s) / Creator(s)

  • Schaeffer, Jonathan
  • Novillo, Diego
  • Unrau, Ronald

• Technical report TR98-11. Most current compiler analysis techniques are unable to cope with the semantics introduced by explicit parallel and synchronization constructs in parallel programs. In this paper we introduce new analysis and optimization techniques for compiling explicitly parallel programs that use mutual exclusion synchronization. We introduce the CSSAME form, an extension of Concurrent Static Single Assignment (CSSA) that incorporates mutual exclusion into a data flow framework for explicitly parallel programs. We show how this analysis can improve the effectiveness of constant propagation in a parallel program. We also present a modification to a sequential dead code elimination algorithm to work on explicitly parallel programs. Finally, we introduce new optimization techniques specifically targeted at explicitly parallel programs. These techniques apply optimizing transformations to a program by taking advantage of its parallel and synchronization structure. We prove the correctness of these transformations and provide algorithms that implement them. The techniques presented in this paper have been implemented by extending the SUIF compiler system. | TRID-ID TR98-11

• Date created

  1998

• Subjects / Keywords

  • CSSA
  • Concurrent Static Single Assignment
  • CSSAME form

• Type of Item

  Report

• DOI

  https://doi.org/10.7939/R3WM13X58

• License

  Attribution 3.0 International