https://github.com/jtb20 created https://github.com/llvm/llvm-project/pull/216324
This patch contains the bulk of the new runtime support for taskgraph record/replay. Relative to previously-posted versions, this version substantially reworks irreducible graph handling, and also reimplements exec descriptor-based host replay. Key points are as follows. The task/taskdata structures and the dependencies between them are duplicated whilst recording a taskgraph, keeping the existing runtime dependency handling unaffected by the taskgraph implementation -- e.g. during runtime execution, it is valid for output dependencies to be dropped as soon as the producing task completes. This separation is intended to eliminate race conditions when tasks which complete unpredictably might or might not be marked as having a subsequent task depend on them. The dependencies between tasks in a taskgraph are processed by static analysis: the high-level process is akin to turning data dependencies between tasks into control-flow dependencies. This is done by building a set of successors and predecessors for each recorded task, then decomposing the resulting DAG into parallel and sequential regions. In the (presumed relatively unlikely, in real-world code) case that the graph is irreducible, an algorithm is used to find the subgraph that cannot be reduced, and make it an irreducible region (with children that may be nodes, parallel or sequential regions, or even other irreducible regions). For irreducible regions in the output graph, the immediate children *retain* their "intra" predecessor and successor lists. Deps pointing in or out of the irreducible region, or those for other region types (parallel, sequential, etc.) are dropped. The algorithm to find and collapse irreducible regions works as follows. Firstly, the graph is decomposed into single-entry, single-exit (SESE) regions, using calculated dominator and postdominator edges. SESE regions may be nested -- the top-level graph forms a SESE region itself, from the entry point to the exit point, and there may also be subgraphs which form SESE regions. SESE regions thus form a tree, rooted at the outermost level of the graph. The leaves of that tree are taken and collapsed into irreducible regions in our output graph. We already know such leaf regions cannot be reduced by parallel-sequential decomposition, because the SESE-region finding code runs after the point where that previous phase can do no further work. The output of this process is a set of nested kmp_taskgraph_region structures -- parallel, sequential or irreducible (each with some number of children), or nodes representing a single task. The two phases -- parallel/sequential decomposition and irreducible-region handling -- alternate until we obtain a single, top-level region. This nested structure is then used for both host-based taskgraph replay and (TBD) offload-based taskgraph replay. It is hoped that the high-level semantics will be useful when mapping to e.g. other graph APIs. Already for host-based execution, reductions only work with parallel regions: much of the complexity here is to allow that to work reliably, particularly where reduction results obtained at some point in the replay of a taskgraph might be used within that *same* taskgraph replay instance. Replaying a taskgraph processed into this nested region tree on the CPU involves another set of linked structures, of type kmp_taskgraph_exec_descr. These form a kind of trace of a traversal over the kmp_taskgraph_region structure, so that a pointer to a kmp_taskgraph_exec_descr is somewhat equivalent to a "program counter". The bulk of the processing here is done by __kmp_build_exec_descrs_1: we create descr structures for task nodes, for wait nodes, and for parallel regions. Each descr has a pointer to the originating region, an in-degree, and a successor list. Host-based replay is then quite straightforward: __kmp_taskgraph_exec_descr_start looks for reduction metadata on parallel regions, or invokes recorded tasks for task-node regions. Recorded taskgraphs are located directly by using a handle passed in from the user's compiled program, rather than using a linked list or hashtable to find taskgraph records to replay keyed by an index: the compiler generates a static pointer per-lexical taskgraph construct (instantiation in the case of templated code), and the address of that is passed to the runtimeto be written back with the address of the processed taskgraph data. _______________________________________________ llvm-branch-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-branch-commits
