Orchestrating interactions among parallel computations
Susan L. Graham, Steven E. Lucco, Oliver J. Sharp · ACM SIGPLAN Notices · 1993
Many parallel programs contain multiple sub-computations, each with distinct communication and load balancing requirements. The traditional approach to compiling such programs is to impose a processor synchronization barrier between sub-computations, optimizing each as a separate entity. This paper develops a methodology for managing the interactions among sub-computations, avoiding strict synchronization where concurrent or pipelined relationships are possible. Our approach to compiling parallel programs has two components: symbolic data access analysis and adaptive runtime support. We summarize the data access behavior of sub-computations (such as loop nests) and split them to expose concurrency and pipelining opportunities. The split transformation has been incorporated into an extended FORTRAN compiler, which outputs a FORTRAN 77 program augmented with calls to library routines written in C and a coarse-grained dataflow graph summarizing the exposed parallelism. The compiler encodes symbolic information, including loop bounds and communication requirements, for an adaptive runtime system, which uses runtime information to improve the scheduling efficiency of irregular sub-computations. The runtime system incorporates algorithms that allocate processing resources to concurrently executing sub-computations and choose communication granularity. We have demonstrated that these dynamic techniques substantially improve performance on a range of production applications including climate modeling and x-ray tomography, expecially when large numbers of processors are available.
Cited by 2 works. doi:10.1145/173262.155100
Authors
References
- Dependence graphs and compiler optimizations
- Efficiently computing static single assignment form and the control dependence graph
- Software pipelining: an effective scheduling technique for VLIW machines
- Guided Self-Scheduling: A Practical Scheduling Scheme for Parallel Supercomputers
- Automatic loop interchange
- Allocating Independent Subtasks on Parallel Processors
- Compiler optimizations for Fortran D on MIMD distributed-memory machines
- Proceedings 2000 International Conference on Computer Design
- Partitioning parallel programs for macro-dataflow
- Proceedings 2004 International Conference on Parallel Processing ICPP 2004