Task graphs and their equivalents have proved to be a valuable abstraction for representing the execution of parallel programs in a number of different applications. Perhaps the most widespread use of task graphs has been for performance modeling of parallel programs, including quantitative analytical models [3,19,25,26,27], theoretical and abstract analytical models [14], and program simulation [5,13]. A second important use of task graphs is in parallel programming systems. Parallel programming environments such as PYRROS [28], CODE [24], HENCE [24], and Jade [20] have used task graphs at three different levels: as a programming notation for expressing parallelism, as an internal representation in the compiler for computation partitioning and communication generation, and as a runtime representation for scheduling and execution of parallel programs. Although the task graphs used in these systems differ in representation and semantics (e.g., whether task graph edges capture purely precedence constraints or also dataflow requirements), there are close similarities. Perhaps most importantly, they all capture the parallel structure of a program separately from the sequential computations, by breaking down the program into computational ``tasks'', precedence relations between tasks, and (in some cases) explicit communication or synchronization operations between tasks.
If task graph representations could be constructed automatically, via compiler support, for common parallel programming standards such as Message-Passing Interface (MPI), High Performance Fortran (HPF), and OpenMP, the techniques and systems described above would become available to a much wider range of programs than they are currently. Within the context of the POEMS project [4], we have developed a task graph based application representation that is used to support modeling of the end-to-end performance characteristics of a large-scale parallel application on a large parallel system, using a combination of analytical, simulation and hybrid models, and models at multiple levels of resolution for individual components. This paper describes how parallelizing compiler technology can be used to automate the process of constructing this task graph representation for HPF programs compiled to MPI (and, in the near future, for existing MPI programs directly). In particular, this paper makes the following contributions:
In addition to the above techniques, which to our knowledge are new, the compiler also uses standard techniques to compute symbolic scaling functions for task computation times and message communication volumes.
The techniques described above have been implemented in the Rice dHPF compiler system, which compiles HPF programs to MPI for message-passing systems using aggressive techniques for computation partitioning and communication optimization [1,6,22]. This implementation was recently used in a joint project with the parallel simulation group at UCLA to improve the scalability of simulation of message passing programs [5]. In that work, we showed how compiler information captured in the task graph can be used to reduce the memory and time requirements for simulating message-passing programs in detail. In the context of the present paper, these results illustrate the potential importance of automatically constructing task graphs for widely used programming standards.
The next section briefly describes the key features of our static and dynamic task graph representations. Section 3 is the major technical section, which presents the compiler techniques described above to construct the task graph representations. Section 4 provides some results about the structure of the compiler-generated task graphs for simple programs and illustrates how task graphs have been used to improve the scalability of simulation, as mentioned above. We conclude with a brief overview of related work (Section 5) and a discussion of future plans (Section 6).