Basic parfor-loop support in DaphneDSL

[pdamme]

Motivation: So far, DAPHNE only supports data-level parallelism by executing the same operations on different chunks of the input data. This is implemented in DAPHNE’s vectorized engine. However, task-level parallelism would be a viable alternative in certain cases. For instance, if the iterations of a for-loop do not depend on each other, they could be executed in parallel.

Task: This project is to introduce basic support for parfor-loops in DAPHNE. DaphneDSL should offer a parfor-statement (which could optionally accept additional parameters for the task-level parallelism). The DAPHNE compiler should analyze these parfor-loops to detect if there are dependencies between the iterations, and potentially to compile/optimize the code for different iterations individually. Finally, the DAPHNE runtime should be able to execute multiple different iterations of the loop in parallel. Implementation in C++.

Hints:

• See the paper “Matthias Boehm, Shirish Tatikonda, Berthold Reinwald, Prithviraj Sen, Yuanyuan Tian, Douglas Burdick, Shivakumar Vaithyanathan: Hybrid Parallelization Strategies for Large-Scale Machine Learning in SystemML. Proc. VLDB Endow. 7(7): 553-564 (2014)” for more details on parfor-loops.

[philipportner]

In case one wants to also look into this for generated code, the SCF dialect has scf.parallel.