TBB extensions

TBB's current release version lacks support for two important features that we need in several extensions built on top of Peano:

• ranges of arbitrary dimension which facilitate/prioritise vectorisation; and
• dynamic task graphs

We add both features through a "manual" tbb add-on. We also try to bring those changes into the UXL foundation standard, but it is not clear when these attempts will be successful.

Therefore, this extension is always shipped with Peano, and it is automatically built and added once you translate Peano with --with-multithreading=tbb_extension. The outcome will end up in a library called tbb_extension.a, tbb_extension_debug.a or tbb_extension_trace.a. This means that you have to add the corresponding library calls to the compiler/linker invocation. However, Peano's autotools configuration will do this for you.

Compatibility

You can also enable certain features individually. To do so, you have to compile with tbb_extension, but then you can manually (via -D flags) define

• TBB_USE_TASK_GROUP_PREVIEW to try out TBB's dynamic task group handling
• TBB_PREVIEW_BLOCKED_RANGE_ND to try out TBB's n-dimensional ranges.

Code usage

Users create an instance of dynamic_task_graph. After that, they create an arbitrary number of objects of type dynamic_task_graph_node. They have in-dependencies, i.e. each instance of dynamic_task_graph_node can have many other instances of dynamic_task_graph_node which feed into it and have to be completed before it starts to run.

Once we submit a node to the task graph through put(), it becomes itself invariant, i.e. you cannot add further in-dependencies anymore. When it is invariant, you can still copy the task node around or make it feed into other tasks. You can also forget about it. The underlying task is submitted and therefore will stay alive.

Code design

The instances of dynamic_task_graph_node form a DAG with reverse dependencies, i.e. each object holds a set of tasks it depends upon.

The put() submits the task. Internally, the submission process now builds up an object graph over instances of dynamic_task_graph_spawned_node. The spawned nodes invert the dependencies: We construct the task graph over in-dependencies. When we submit, these in-dependencies are translated into out-dependencies, i.e. each task knows now exactly which follow-up tasks to inform upon completion.

The rationale here is simple: Once a task finishes, we want to inform all follow-up tasks that this dependency is cleared. If all in-dependencies are done, the task is ready and can be released into oneTBB's scheduler. We never want to poll the tasks to see which ones are ready to go.

Implementation and memory management

Each dynamic_task_graph_node on the user side is attached a dynamic_task_graph_spawned_node once it is submitted. It is important to host these submitted task graph nodes on the heap, as they need to host a mutex. So we use a shared pointer here (as we can also copy the user-facing task descriptions).

Once we put a node into the graph, the dynamic_task_graph instance also memorises the shared pointer to the underlying dynamic_task_graph_spawned_node object. Therefore, even if the user forgets about all the user-facing instances of dynamic_task_graph_node, dynamic_task_graph will still keep the actually submitted nodes alive.

Submitted task graph might change their status quo into COMPLETE. In this case, we still hold them in the task graph until our garbage collection is kicked off and eliminates those entries to completed tasks. As we work with smart pointers, this is likley the point where the object is actually removed from the heap.

The task graph also holds a set of submitted tasks which are still alive or have completed yet not been removed. In return, some completed tasks might literally been removed from the set of tasks already. Nevertheless, users might still hold the task objects and define in-dependencies over them. These are trivially already fulfilled. In this case, we don't even insert out-dependencies in put() anymore, but we have to check if the in-tasks referred to are still among our active tasks.