tbb::dynamic_task_graph Class Reference

Very simple dynamic task graph interface. More...

#include <dynamic_task_graph.h>

Collaboration diagram for tbb::dynamic_task_graph:

Public Member Functions
	dynamic_task_graph (::oneapi::tbb::task_group &arena)
	Construct task graph over arena.
void	put (dynamic_task_graph_node &node)
	Put a new node into the task graph.
void	wait (dynamic_task_graph_node node)
	Wait for one specific node.
void	wait (const std::set< dynamic_task_graph_node > &node)
	Wait for set of nodes.
void	wait_for_all ()
	Wait for all tasks to finish.
std::size_t	size () const
	Number of tasks in graph.

Private Types
using	SpawnedTaskMutex = ::oneapi::tbb::spin_rw_mutex
	I originally used.
using	SpawnedTasksContainer = std::set< std::shared_ptr< dynamic_task_graph_spawned_node > >
	See documentation of dynamic_task_graph_spawned_node for a discussion why we have to use smart pointers here.

Private Member Functions
void	clean_up_completed_tasks ()
	Remove all completed task.

Private Attributes
::oneapi::tbb::task_group &	_task_group
SpawnedTaskMutex	_spawned_task_mutex
SpawnedTasksContainer	_spawned_tasks
	Spawned tasks known to system.

Friends
class	dynamic_task_graph_spawned_node

Detailed Description

Very simple dynamic task graph interface.

Each task graph is tied to an arena and maintains a set of graphs nodes aka tasks with dependencies between them. Immediately after tasks become ready, the task graph spawns them into the arena.

Implementation

The task graph holds a big hash map mapping individual task numbers of type dynamic_task_graph_node_number onto dynamic_task_graph_node which in turn hold the actual task graph. The entries are added to the list when we construct a node. They are removed after the ask has terminated.

Author

Tobias Weinzierl

Definition at line 138 of file dynamic_task_graph.h.

Member Typedef Documentation

SpawnedTaskMutex

using tbb::dynamic_task_graph::SpawnedTaskMutex = ::oneapi::tbb::spin_rw_mutex

private

I originally used.

using SpawnedTaskMutex = ::oneapi::tbb::spin_mutex;

but it is absolutely crucial that the lock for the spawned tasks does not become a bottleneck.

Definition at line 294 of file dynamic_task_graph.h.

SpawnedTasksContainer

using tbb::dynamic_task_graph::SpawnedTasksContainer = std::set< std::shared_ptr<dynamic_task_graph_spawned_node> >

private

See documentation of dynamic_task_graph_spawned_node for a discussion why we have to use smart pointers here.

Just to reiterate the core message why we need this: A user creates an instance of a task, i.e. dynamic_task_graph_node. Once submitted, this node holds a (smart) pointer to a task, and then is allowed to throw the node away. So we have to safe the submitted task!

Definition at line 307 of file dynamic_task_graph.h.

Constructor & Destructor Documentation

dynamic_task_graph()

tbb::dynamic_task_graph::dynamic_task_graph

(

::oneapi::tbb::task_group &

arena

)

Construct task graph over arena.

Parameters

arena

Arena to be used once the task becomes ready. It is the user's responsibility to ensure that the arena is valid.

Member Function Documentation

clean_up_completed_tasks()

void tbb::dynamic_task_graph::clean_up_completed_tasks ( )

private

Remove all completed task.

Almost a garbage collection over the tasks that are complete. This makes follow up traversals of the _spawned_tasks container faster. The routine is a helper for the waits.

put()

void tbb::dynamic_task_graph::put

(

dynamic_task_graph_node &

node

)

Put a new node into the task graph.

The ownership of the node is passed over to the task graph. You don't have to delete it yourself. This is different to oneAPI's flow graph, where we can work with references, as we rely on the fact that nodes stay alive until we call wait_for_all. Here, everything is dynamic and the task might or might not be executed immediately or be referenced later on.

Once you have submitted a node, it becomes read-only, i.e. you cannot add any further in-dependencies to it. But you can still copy it or you can even delete the object. The ownership of the underlying "real" task now resides within the dynamic_task_graph object.

Internally, the put will create a second object of the type dynamic_task_graph_spawned_node, and then it will translate all dependencies into links between instances of dynamic_task_graph_spawned_node. However, the directions here are inverted: Users model their task dependencies as in-dependencies. When they submit tasks, the relations are translated into out-dependencies, i.e. each task knows which tasks are follow-up tasks and need to be notified once we are ready. We translate in-dependencies into a forward-flow model.

As everything is dynamic here, it could be that we refer with an in-dependency to a task that's already completed. It might even have been removed completely from the set of spawned tasks. In this case, we can safely ignore these in-dependency. We do not even have to increment the dependency counter.

Implementation

1. Create a new spawned task. This is a shared pointer.
2. Loop over all in-dependencies. For each one for which we find an entry in the graph, first of all lock it. If it has already terminated, unlock the semaphore and delete it. This is kind of an on-the-fly garbage collection. Otherwise, the task obviously has not yet finished, so we increase the number of our in-dependencies to mark the new task has to complete before we start ourselves, and we add ourselves to the other task's out dependencies.
3. Insert task into set of pending tasks.
4. Release semaphore on new task, so all other tasks which feed into this one can inform it about their termination from now on.
5. Reduce the task's in-counter by one. The constructor of dynamic_task_graph_spawned_node always increments this counter artificially by one to avoid that it is released too soon.

We always have to increment the task dependency counter before we actually insert the new task, as the predecessor migth literally just now be about to finish and hence immediately unlock our own task while we still construct its input dependencies. By incrementing first, we are on the safe side that our task will not gallop ahead.

size()

std::size_t tbb::dynamic_task_graph::size

(

)

const

Number of tasks in graph.

This includes all running and pending tasks.

Referenced by tarch.plotter.api.input.Patch.Patch::__repr__().

Here is the caller graph for this function:

wait() [1/2]

void tbb::dynamic_task_graph::wait

(

const std::set< dynamic_task_graph_node > &

node

)

Wait for set of nodes.

wait() [2/2]

void tbb::dynamic_task_graph::wait

(

dynamic_task_graph_node

node

)

Wait for one specific node.

Realisation

Very simplistic implementation: We know that the task has been submitted, so its spawned task's pointer should be in the repo. If it is not there (anymore), it has finished. It also could still be in there yet have the state complete. So we run into a while loop over the repo. As long as the task is still bookmarked there, we yield.

I originally had a wait in there on the underlying task graph:

if (isTaskStillInQueue()) {
  _task_group.wait();
  clean_up_completed_tasks();
}

This cannot work if we study the TBB documentation (https://oneapi-spec.uxlfoundation.org/specifications/oneapi/v1.3-rev-1/elements/onetbb/source/task_scheduler/task_group/task_group_cls): wait() returns if and only if all tasks in the group have completed (or we cancelled them). So we should use a taskyield() indeed.

Parameters

node	Task to wait for. This task has to be submitted. Otherwise, we trigger an assertion.

See also

wait_for_all()

wait_for_all()

void tbb::dynamic_task_graph::wait_for_all

(

)

Wait for all tasks to finish.

This is a brute force method which has to be used with care. It strongly synchronises, and it is not clear if it can deadlock if multiple threads invoke it at the same time.

The implementation is close to trivial:

• We hand over the task responsibility to the task group, so the task group can process some of its ready tasks.
• We remove all of those tasks which are now flagged as ready.
• We jump back to the start (iteration) if there are still pending tasks in the queue.

It seems that wait() on a task group returns immediately if there are no further tasks pending in there. This is very reasonable yet might mean that there are still tasks being processed at this point. They might in return not have released any successor tasks, i.e. there might still be some tasks in the queue that are marked as submitted and have not yet been released as their in dependency counter has not been decreased yet. Therefore, we have to loop.

Friends And Related Symbol Documentation

dynamic_task_graph_spawned_node

friend class dynamic_task_graph_spawned_node

friend

Definition at line 140 of file dynamic_task_graph.h.

Field Documentation

_spawned_task_mutex

SpawnedTaskMutex tbb::dynamic_task_graph::_spawned_task_mutex

private

Definition at line 295 of file dynamic_task_graph.h.

_spawned_tasks

SpawnedTasksContainer tbb::dynamic_task_graph::_spawned_tasks

private

Spawned tasks known to system.

Definition at line 312 of file dynamic_task_graph.h.

_task_group

::oneapi::tbb::task_group& tbb::dynamic_task_graph::_task_group

private

Definition at line 282 of file dynamic_task_graph.h.

---

The documentation for this class was generated from the following file:

• src/tbb/dynamic_task_graph.h