next up previous
Next: The Static Task Graph: Up: The Application Representation in Previous: The Application Representation in


Definitions of Key Terms

Task:
A unit of work in a parallel program that is executed by a single thread, and such that any precedence relationship between a pair of tasks only arises at task boundaries.

Thread:
A logical or actual entity that executes tasks of a program. In a multi-threaded system, threads will be actual operating-system entities scheduled onto processes. In a single-threaded application, threads may not actually exist but we use the term ``thread'' for uniformity (i.e., we assume there is one thread per process).

Process:
An operating system entity that ``executes'' the threads of a program. Also the entity that is scheduled onto processors.

Static Task Graph or STG:
(For a given program) A hierarchical graph in which each vertex is either a task node, a control-flow node (loop or branch), or a call node representing a subgraph for a called procedure. A task node captures either computation or communication. Each task node in the graph represents a set of parallel tasks (since the degree of parallelism may be unknown until execution time). Each edge represents a precedence between a pair of nodes, which may be enforced either by control-flow or synchronization.

Dynamic Task Graph or DTG:
(For a program and a particular input) A directed acyclic graph in which each vertex represents a task and each edge represents a precedence between a pair of tasks. A task can begin execution only after all its predecessor tasks, if any, complete execution.

Task Scheduling:
The allocation of dynamic tasks to threads. The task scheduling strategy is implicitly or explicitly specified by the parallel program, even though the actual resulting schedules may be dynamic, i.e., data-dependent and/or timing-dependent. Examples of task scheduling strategies include static, block partitioning of loop iterations (as in Sweep3D) or dynamic scheduling techniques such as guided self-scheduling or explicit task queues.

Condensed Dynamic Task Graph:
(For a program, a particular input, and a particular allocation of tasks to threads) A directed acyclic graph in which each vertex denotes a collection of tasks executed by a single thread, and each edge denotes a precedence between a pair of vertices (i.e. all the tasks in the vertex at the head of the edge must complete before any task in the vertex at the tail can begin execution).

A condensed static task graph can be defined analogously, where a sequence of task nodes can be collapsed if they do not include any communication and if every task node is instantiated into an identical set of dynamic task instances at run-time.

This representation may be important because capturing all the fine-grain parallelism in the program (e.g., all individual loop iterations) as individual tasks might be too expensive for very large problems. The condensed graph essentially collapses all the tasks executed by a thread between synchronization points into a single condensed task. Note that this graph therefore depends on the specific allocation of tasks to threads. The tradeoffs in using the condensed dynamic task graph are described below.


next up previous
Next: The Static Task Graph: Up: The Application Representation in Previous: The Application Representation in
Rizos Sakellariou 2000-09-15