There is a large body of work on the use of task graphs for various aspects of parallel systems but very little work on synthesizing task graphs for general-purpose parallel programs. The vast majority of performance models that use task graphs as inputs generally do not specify how the task graph should be constructed but assume that this has been done [3,14,19,25,27]. The various compiler-based systems that use task graphs, namely PYRROS [28], CODE [24], HENCE [24], and Jade [20] construct task graphs by assuming special information from the programmer. In particular, PYRROS, CODE and HENCE all assume that the programmer specifies the task graph explicitly (CODE and HENCE actually use a graphical programming language to do so). In Jade, the programmer specifies input and output variables used by each task and the compiler uses this information to deduce the task dependences for the program.
The PlusPYR project [12] has developed a task graph representation that has some similarities with ours (in particular, symbolic integer sets and mappings for describing task instances and communication and synchronization rules), along with compiler techniques to synthesize these task graphs. The key difference from our work is that they start with a limited class of sequential programs (annotated to identify the tasks) and use dependence analysis to compute dependences between tasks, and then derive communication and synchronization rules from these dependences. Therefore, their approach is essentially a form of simple automatic parallelization. In contrast, our goal is to generate task graphs for existing parallel programs with no special program annotations and with explicit communication. A second major difference is that they assume a simple parallel execution model in which a task receives all inputs from other tasks in parallel and sends all outputs to other tasks in parallel. In contrast, we capture much more general communication behavior in order to support realistic HPF and MPI programs.
Parashar et al. [26] construct task graphs for HPF programs compiled by the Syracuse Fortran 90D compiler, but they are limited to a very simple, loosely synchronous computational model that would not support many message-passing and HPF programs in practice. In addition, their interpretive framework for performance prediction uses functional interpretation for instantiating a dynamic task graph, which is similar to our approach for instantiating control-flow. Like the task graph model, their interpretation and performance estimation are significantly simplified (compared with ours) because of the loosely synchronous computational model. For example, they do not need to capture sophisticated communication patterns and computation partitionings, as we do using code generation from integer sets.
Dikaiakos et al. [13] developed a tool called FAST
that constructs task graphs from user-annotated parallel programs,
performs advanced task scheduling and then uses abstract simulation of
message passing to predict performance.
The PACE project [25] proposes a language and programming
environment for parallel program performance prediction. Users are required
to identify parallel subtasks and computation and communication patterns.
Finally,
Fahringer [15], Armstrong and Eigenmann [9],
Mendes and Reed [23] and many others have developed
symbolic compile-time techniques for estimating execution time,
communication volume and other metrics.
The communication and computation scaling functions available in our static
task graph are very similar to the symbolic information used by these
techniques, and could be directly extended to support their analytical
models.