Futures in Task Graphs – Extending Taskflow with Dynamic Data Dependencies
摘要
Task-based parallel programming is a common approach to using modern multicore architectures efficiently. Hereby a programmer describes the computation as a set of tasks and their dependencies. The dependencies can be dynamic, meaning that they can only be discovered at runtime. Dynamic dependencies can be expressed with the future construct, which comes in several variants. Previous algorithmic research suggested a particularly powerful variant that allows futures to encapsulate other futures and the responsibility for filling a future to be transferred from one task to another. This powerful future type has not yet been supported by any current runtime system. This paper integrates it into the Taskflow system. We describe our changes of the programming model and user interface, sketch some implementation aspects, and evaluate the implementation with a benchmark that resembles the LU decomposition of hierarchical matrices.