Building asynchronous `future` callback chain from compile-time dependency graph (DAG)
<p>I have a compile-time <a href="https://en.wikipedia.org/wiki/Directed_acyclic_graph" rel="noreferrer">directed acyclic graph</a> of asynchronous tasks. The DAG shows the dependencies between the tasks: by analyzing it, it's possible to understand what tasks can run in parallel <em>(in separate threads)</em> and what tasks need to wait for other tasks to finish before they can begin <em>(dependencies</em>).</p>

<p>I want to generate a callback chain from the DAG, using <code>boost::future</code> and the <code>.then(...)</code>, <code>when_all(...)</code> continuation helper functions. The result of this generation will be a function that, when called, will start the callback chain and execute the tasks as described by the DAG, running as many tasks as possible in parallel.</p>

<p>I'm having trouble, however, finding a general algorithm that can work for all cases.</p>

<p>I made a few drawings to make the problem easier to understand. This is a legend that will show you what the symbols in the drawings mean:</p>

<p><a href="https://i.stack.imgur.com/h7gU1.png" rel="noreferrer"><img src="https://i.stack.imgur.com/h7gU1.png" alt="Legend: how to read the images."></a></p>

<p>Let's begin with a simple, linear DAG:</p>

<p><a href="https://i.stack.imgur.com/jmB2P.png" rel="noreferrer"><img src="https://i.stack.imgur.com/jmB2P.png" alt="Example 0: linear DAG."></a></p>

<p>This dependency graph consists of three tasks <em>(<code>A</code>, <code>B</code>, and <code>C</code>)</em>. <code>C</code> depends on <code>B</code>. <code>B</code> depends on <code>A</code>. There is no possibility of parallelism here - the generation algorithm would build something similar to this:</p>

<pre><code>boost::future&lt;void&gt; A, B, C, end;

A.then([]
    {
        B.then([]
            {
                C.get();
                end.get();
            });
    });
</code></pre>

<p><em>(Note that all code samples are not 100% valid - I'm ignoring move semantics, forwarding and lambda captures.)</em></p>

<p>There are many approaches to solve this linear DAG: either by starting from the end or the beginning, it's trivial to build a correct callback chain.</p>

<p>Things start to get more complicated when <a href="https://en.wikipedia.org/wiki/Fork%E2%80%93join_model" rel="noreferrer">forks and joins</a> are introduced.</p>

<p>Here's a DAG with a fork/join:</p>

<p><a href="https://i.stack.imgur.com/S5o4g.png" rel="noreferrer"><img src="https://i.stack.imgur.com/S5o4g.png" alt="Example 1: DAG with a fork/join."></a></p>

<p>It's difficult to think of a callback chain that matches this DAG. If I try to work backwards, starting from the end, my reasoning is as follows:</p>

<ul>
<li><code>end</code> depends on <code>B</code> and <code>D</code>. <em>(join)</em>

<ul>
<li><code>D</code> depends on <code>C</code>.</li>
<li><code>B</code> and <code>C</code> depend on <code>A</code>. <em>(fork)</em></li>
</ul></li>
</ul>

<p>A possible chain looks something like this:</p>

<pre><code>boost::future&lt;void&gt; A, B, C, D, end;

A.then([]
    {
        boost::when_all(B, C.then([]
                               {
                                   D.get();
                               }))
            .then([]
                {
                    end.get();
                });
    });
</code></pre>

<p>I found it difficult to write this chain by hand, and I'm also doubtful about its correctness. I could not think of a general way to implement an algorithm that could generate this - additional difficulties are also present due to the fact that <code>when_all</code> needs its arguments to be moved into it. </p>

<p>Let's see one last, even more complex, example:</p>

<p><a href="https://i.stack.imgur.com/rMxYl.png" rel="noreferrer"><img src="https://i.stack.imgur.com/rMxYl.png" alt="Example 2: complex DAG."></a></p>

<p>Here we want to exploit parallelism as much as possible. Consider task <code>E</code>: <code>E</code> can be run in parallel with any of <code>[B, C, D]</code>.</p>

<p>This is a possible callback chain:</p>

<pre><code>boost::future&lt;void&gt; A, B, C, D, E, F, end;

A.then([]
    {
        boost::when_all(boost::when_all(B, C).then([]
                            {
                                D.get();
                            }),
            E)
            .then([]
                {
                    F.then([]
                        {
                            end.get();
                        });
                });
    });
</code></pre>

<p>I've tried to come up with a general algorithm in several ways:</p>

<ul>
<li><p>Starting from the beginning of the DAG, trying to build up the chain using <code>.then(...)</code> continuations. This doesn't work with joins, as the target join task would is repeated multiple times.</p></li>
<li><p>Starting from the end of the DAG, trying to generate the chain using <code>when_all(...)</code> continuations. This fails with forks, as the node that creates the fork is repeated multiple times.</p></li>
</ul>

<p>Obviously the "breadth-first traversal" approach doesn't work well here. From the code samples that I have hand-written, it seems that the algorithm needs to be aware of forks and joins, and needs to be able to correctly mix <code>.then(...)</code> and <code>when_all(...)</code> continuations.</p>

<p>Here are my final questions:</p>

<ul>
<li><p><strong>Is it always possible to generate a <code>future</code>-based callback chain from a DAG of task dependencies, where every task appears only once in the callback chain?</strong></p></li>
<li><p><strong>If so, how can a general algorithm that, given a task dependency DAG builds a callback chain, be implemented?</strong></p></li>
</ul>

<hr>

<p>EDIT 1: </p>

<p><a href="http://vittorioromeo.info/Misc/dag_task_idea.pdf" rel="noreferrer">Here's an additional approach</a> I'm trying to explore.</p>

<p>The idea is to generate a <code>([dependencies...] -&gt; [dependents...])</code> map data structure from the DAG, and to generate the callback chain from that map.</p>

<p>If <code>len(dependencies...) &gt; 1</code>, then <code>value</code> is a <em>join</em> node.</p>

<p>If <code>len(dependents...) &gt; 1</code>, then <code>key</code> is a <em>fork</em> node.</p>

<p>All the key-value pairs in the map can be expressed as <code>when_all(keys...).then(values...)</code> continuations.</p>

<p>The difficult part is figuring out the correct order in which to "expand" <em>(think about something similar to a parser)</em> the nodes and how to connect the fork/join continuations together.</p>

<p>Consider the following map, generated by image <a href="https://i.stack.imgur.com/rMxYl.png" rel="noreferrer">4</a>.</p>

<pre><code>depenendencies  |  dependents
----------------|-------------
[F]             :  [end]
[D, E]          :  [F]
[B, C]          :  [D]
[A]             :  [E, C, B]
[begin]         :  [A]
</code></pre>

<p>By applying some sort of parser-like reductions/passes, we can get a "clean" callback chain:</p>

<pre><code>// First pass:
// Convert everything to `when_all(...).then(...)` notation
when_all(F).then(end)
when_all(D, E).then(F)
when_all(B, C).then(D)
when_all(A).then(E, C, B)
when_all(begin).then(A)

// Second pass:
// Solve linear (trivial) transformations
when_all(D, E).then(
    when_all(F).then(end)
)
when_all(B, C).then(D)
when_all(
    when_all(begin).then(A)
).then(E, C, B)

// Third pass:
// Solve fork/join transformations
when_all(
    when_all(begin).then(A)
).then(
    when_all(
        E, 
        when_all(B, C).then(D)
    ).then(
        when_all(F).then(end)
    )   
)
</code></pre>

<p>The third pass is the most important one, but also the one that looks really difficult to design an algorithm for.</p>

<p>Notice how <code>[B, C]</code> have to be found inside the <code>[E, C, B]</code> list, and how, in the <code>[D, E]</code> dependency list, <code>D</code> must be interpreted as the result of <code>when_all(B, C).then(D)</code> and chained together with <code>E</code> in <code>when_all(E, when_all(B, C).then(D))</code>.</p>

<p>Maybe the entire problem can be simplified as:</p>

<p><strong>Given a map consisting of <code>[dependencies...] -&gt; [dependents...]</code> key value pairs, how could an algorithm that transforms those pairs to a <code>when_all(...)</code>/<code>.then(...)</code> continuation chain be implemented?</strong></p>

<p>EDIT 2:</p>

<p>Here's some <a href="http://pastebin.com/wRJpUr4b" rel="noreferrer">pseudocode</a> I came up with for the approach described above. It seems to work for the DAG I tried, but I need to spend more time on it and "mentally" test it with other, trickier, DAG configurations.</p>