The dynamic task graph provides a detailed description of the parallel structure of a program for a particular program input, which can be used for abstract or detailed performance modeling [5]. The DTG is acyclic and in particular, no control-flow nodes (loops or branches) are included in the graph. Except for a few pathological examples, the DTG is independent of the task scheduling. In particular, different task scheduling strategies can lead to different execution behavior and therefore different performance for the same DTG. This ability of the DTG to capture the intrinsic parallel structure of the program separate from the task scheduling can be powerful for comparing alternative scheduling strategies, particularly for shared memory programs that often use sophisticated dynamic and semi-static task scheduling strategies [5].
The dynamic task graph can be thought of as being instantiated from the static task graph for a particular program input by instantiating the parallel instances of the tasks, unrolling all the loops, and resolving all dynamic branch instances. The DTG thus obtained describes the actual tasks executed at runtime, the precedences between them, and the precise communication operations executed. The symbolic scaling functions in the static task graph can be evaluated to provide cost estimates for the tasks, once the computation time per loop iteration is predicted analytically or measured. The challenges in computing the dynamic task graph and in ensuring efficient handling of large problem sizes are discussed below.