On linearizing parallel code
Jeanne Ferrante, Mary E. Mace · ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages (POPL) · 1985
We consider the problem of generating sequential code for programs written in a language which contains a Multiple GOTO operator, predicates and statements. This problem arises when compiling a parallel intermediate form (such as the PDG [3,4]) to run on a sequential machine; in a source-to-source FORTRAN translator when vectorization of a loop has failed; and when compiling logic designs written in a parallel design language for simulation on a sequential machine. It is easy to generate sequential code for this sort of parallel program if one allows either duplication of code or the insertion of guard variables at merge points; in fact, it is in general impossible without this addition. However, for a large class of parallel programs (such as those originally arising from sequential programs, even after some optimizations have been applied) it is possible to generate sequential code without duplication or the addition of guard variables. In this paper we present an efficient algorithm which will generate sequential code from a parallel program without duplication or additional guard variables for a large class of parallel programs.
Cited by 41 works. doi:10.1145/318593.318636 Open-access PDF
Authors
References
- The program dependence graph and its use in optimization
- Dependence graphs and compiler optimizations
- Principles of Compiler Design (Addison-Wesley series in computer science and information processing)
- A Fast and Usually Linear Algorithm for Global Flow Analysis
- Conversion of control dependence to data dependence
- IBM 3081 Processor Unit: Design Considerations and Design Process
- A program form based on data dependency in predicate regions
- On Proving the Correctness of Optimizing Transformations in a Digital Design Automation System