Demand-Driven Execution of Static Directed Acyclic Graphs Using Task Parallelism

The dataflow model allows natural expression of parallelism in an application. Applications expressed in the dataflow model can be executed either using the data-driven or the demand-driven schemes. Although both these schemes have their utility in different scenarios, the realization of the demand-driven scheme is not adequately supported in the existing solutions for task parallelism. In this paper, we examine some of the requirements placed by the demand-driven execution scheme on task parallelism. We present PFunc, a new library-based solution for task parallelism that fully supports the demand-driven execution scheme. We compare the runtimes and peak memory consumption of an unsymmetric sparse LU factorization emulation parallelized using both the data- and demand-driven execution schemes. This comparison shows that the demand-driven model provides benefits that necessitate its full support in task parallelism.