Topology Aware Task Mapping
- PDF / 2,410,009 Bytes
- 82 Pages / 565.087 x 755.008 pts Page_size
- 77 Downloads / 194 Views
Synonyms DAG scheduling; Workflow scheduling
Definition Task Graph Scheduling is the activity that consists in mapping a task graph onto a target platform. The task graph represents the application: Nodes denote computational tasks, and edges model precedence constraints between tasks. For each task, an assignment (choose the processor that will execute the task) and a schedule (decide when to start the execution) are determined. The goal is to obtain an efficient execution of the application, which translates into optimizing some objective function, most usually the total execution time.
Discussion Introduction Task Graph Scheduling is the activity that consists in mapping a task graph onto a target platform. The task graph is given as input to the scheduler. Hence, scheduling algorithms are completely independent of models and methods used to derive task graphs. However, it is insightful to start with a discussion on how these task graphs are constructed. Consider an application that is decomposed into a set of computational entities, called tasks. These tasks are linked by precedence constraints. For instance, if some task T produces some data that is used (read) by another tasks T ′ , then the execution of T ′ cannot start before the completion of T. It is therefore natural to represent the application as a task graph: The task graph is a DAG (Directed Acyclic Graph), whose nodes are the
tasks and whose edges are the precedence constraints between tasks. The decomposition of the application into tasks is given to the scheduler as input. Note that the task graph may be directly provided by the user, but it can also be determined by some parallelizing compiler from the application program. Consider the following algorithm to solve the linear system Ax = b, where A is an n × n nonsingular lower triangular matrix and b is a vector with n components: for i = to n do Task Ti,i : xi ← bi /ai,i for j = i + to N do Task Ti,j : bj ← bj − aj,i × xi end end For a given value of i, ⩽ i ⩽ n, each task Ti,∗ represents some computations executed during the ith iteration of the external loop. The computation of xi is performed first (task Ti,i ). Then, each component bj of vector b such that j > i is updated (task Ti,j ). In the original sequential program, there is a total precedence order between tasks. Write T , Bj has exactly one predecessor.
●
For each j > , the predecessor Bi of Bj is also on the list, where i < j.
Hence, treegions represent trees of basic blocks in the control flow graph. Since treegions do not contain any side entrances, each path through a treegion yields a superblock. Like superblock compilers, treegion compilers employ tail duplication and other regionenlarging techniques. More recent work by Zhou and Conte [, ] shows that treegions can be made quite effective without significant code growth.
Nonlinear Regions Nonlinear region approaches include percolation scheduling [] and DAG-based scheduling []. Trace scheduling- [] extends treegions by removing the restriction on side entra
Data Loading...
