docs/ExamplesNondeterministicControlFlow.html
| | Taskflow: A General-purpose Task-parallel Programming System |
Loading...
Searching...
No Matches
Nondeterministic Control Flow
We demonstrate how Taskflow models nondeterministic control flow using conditional tasking — a powerful pattern for stochastic search, probabilistic simulation, and optimization algorithms whose execution path is determined only at runtime.
Consider a fair binary coin. We toss it repeatedly until we observe five consecutive heads. The probability of obtaining five heads in a row is 1/25 = 1/32:
The expected number of tosses required to reach five consecutive heads is therefore 32. Our goal is to model this stochastic process as a Taskflow task graph and verify that the observed average over many trials matches the theoretical expectation.
We create five condition tasks, each returning a random binary value. A return value of 0 (heads) advances execution to the next coin-flip task; a return value of 1 (tails) sends execution back to the first coin-flip task to restart. This structure expresses nondeterministic control flow directly as a task graph — no explicit loop variables, mutexes, or synchronisation needed:
#include <taskflow/taskflow.hpp>
int main() {
tf::Taskflow taskflow;
tf::Executor executor;
const size_t rounds = 10000;
size_t tosses = 0;
size_t total_tosses = 0;
// reset the toss counter at the start of each trial
tf::Task init = taskflow.emplace(& { tosses = 0; })
.name("init");
// each condition task returns 0 (heads) or 1 (tails)
tf::Task B = taskflow.emplace(& { ++tosses; return std::rand() % 2; })
.name("flip-coin-1");
tf::Task C = taskflow.emplace(& { return std::rand() % 2; })
.name("flip-coin-2");
tf::Task D = taskflow.emplace(& { return std::rand() % 2; })
.name("flip-coin-3");
tf::Task E = taskflow.emplace(& { return std::rand() % 2; })
.name("flip-coin-4");
tf::Task F = taskflow.emplace(& { return std::rand() % 2; })
.name("flip-coin-5");
// accumulate the toss count when five consecutive heads are achieved
tf::Task stop = taskflow.emplace(& { total_tosses += tosses; })
.name("stop");
init.precede(B);
// 0 (heads) → advance to next flip; 1 (tails) → restart from B
B.precede(C, B);
C.precede(D, B);
D.precede(E, B);
E.precede(F, B);
F.precede(stop, B);
// run 10,000 independent trials
executor.run_n(taskflow, rounds).wait();
double average_tosses = static_cast<double>(total_tosses) / rounds;
assert(std::fabs(average_tosses - 32.0) < 1.0);
std::cout << "average tosses to five consecutive heads: "
<< average_tosses << '\n';
return 0;
}
class to create an executor
Definition executor.hpp:62
tf::Future< void > run_n(Taskflow &taskflow, size_t N)
runs a taskflow for N times
Task emplace(C &&callable)
creates a static task
Definition flow_builder.hpp:1571
class to create a task handle over a taskflow node
Definition task.hpp:569
Task & precede(Ts &&... tasks)
adds precedence links from this to other tasks
Definition task.hpp:1258
class to create a taskflow object
Definition taskflow.hpp:64
After 10,000 trials, the observed average converges to approximately 32, matching the theoretical expectation. The corresponding task graph is shown below:
Although individual executions are non-deterministic, the task graph's control flow expands to a tree of tasks according to Taskflow's scheduling rule for conditional tasking (see Conditional Tasking). Each path from the root to stop represents one successful run of five consecutive heads, and no two live paths can race — the conditional edges ensure that only one execution path is active at any time.
The same pattern extends naturally to higher-arity conditions. With a ternary coin (three equally likely outcomes), two outcomes advance execution and one restarts. The expected number of tosses to observe five identical consecutive results is 35 = 243:
tf::Task B = taskflow.emplace(& { ++tosses; return std::rand() % 3; })
.name("flip-coin-1");
tf::Task C = taskflow.emplace(& { return std::rand() % 3; })
.name("flip-coin-2");
tf::Task D = taskflow.emplace(& { return std::rand() % 3; })
.name("flip-coin-3");
tf::Task E = taskflow.emplace(& { return std::rand() % 3; })
.name("flip-coin-4");
tf::Task F = taskflow.emplace(& { return std::rand() % 3; })
.name("flip-coin-5");
// outcomes 0 and 1 advance; outcome 2 restarts
B.precede(C, B, B);
C.precede(D, B, B);
D.precede(E, B, B);
E.precede(F, B, B);
F.precede(stop, B, B);
executor.run_n(taskflow, rounds).wait();
double average_tosses = static_cast<double>(total_tosses) / rounds;
assert(std::fabs(average_tosses - 243.0) < 1.0);
This pattern scales to probabilistic conditions of any arity, making conditional tasking a natural fit for Monte Carlo simulation, stochastic search, Markov chain sampling, and any algorithm whose control flow depends on outcomes known only at runtime.