tarch::multicore::native Namespace Reference

Functions
void	spawnAndWaitAsTaskLoop (const std::vector< tarch::multicore::Task * > &tasks)
	Map onto native tasking.
void	spawnTask (Task *task, const std::set< TaskNumber > &inDependencies, const TaskNumber &taskNumber)
	Spawn a new task into the tasking backend.
void	waitForTasks (const std::set< TaskNumber > &inDependencies)
	Wait for other task.
void	waitForAllTasks ()
	Slightly different than the umbrella version in the general namespace.

Function Documentation

spawnAndWaitAsTaskLoop()

void tarch::multicore::native::spawnAndWaitAsTaskLoop

(

const std::vector< tarch::multicore::Task * > &

tasks

)

Map onto native tasking.

Run over the tasks and issue native tasks. If the tasks spawn, in return, further subtasks, these will either end up in a thread-local queue or will be mapped onto native tasks. The behaviour here depends on decisions within tarch::multicore::spawnTask() guided by the orchestration. If the subtasks enqueue tasks into the thread-local queue, they will remain there. This routine does not touch the thread-local queue.

The responsibility for the pointers in tasks is handed over to the runtime of choice, i.e. you don't have to delete them.

OpenMP mapping of a task loop onto a task loop

In OpenMP 6 and newer, we should use transparent tasks, as we want to expose task dependencies which do not stem from siblings. If OpenMP 6 is not supported, then we should disable the corresponding syntax.

NVIDIA

NVIDIA's nvc++ does not support taskloops. We have contacted their R&D and they confirmed that they only implement a subset of OpenMP, and the taskloop is not on the list of features that they want to support.

Implementation and bugs

See discussion in the context of the other taskloop: It is important to label tasks as shared even though I think copying should be fine as a copy degenerates to a shallow copy.

You are not allowed to call this routine for an empty task set. The empty task set means that the taskloop construct becomes nop. The subsequent taskwait hence synchronises on one logical level above within the task hierarchy, which is not what we want.

Parameters

tasks

Set of tasks. Is guaranteed to be non-empty.

spawnTask()

void tarch::multicore::native::spawnTask	(	Task *	task,
		const std::set< TaskNumber > &	inDependencies,
		const TaskNumber &	taskNumber
	)

Spawn a new task into the tasking backend.

This routine is invoked by tarch::multicore::spawnTask(). The invoking method is not a sole forwarding. It takes care of the categorisation of ready tasks into pending tasks, and it also handles all the fusion for GPUs. Therefore, if it delegates calls to this class, we really can directly map the task 1:1 onto the native task system used.

Serial code

This is a trivial case in a serial run: As we have already completed all incoming tasks (we work serially and all incoming tasks have to be done by this time), we can simply process the task and return. As a direct consequence, all dependencies of future tasks are always fulfilled.

C++ variant

1. We first check if a task with this number is among the submitted tasks. This is possible if a previous algorithm phase has submitted a task with this number which was a sink, but noone ever waited for it. This should usually not happen and is a sign of bad code design. We issue a warning, free all locks and wait for the previous task with the same number to terminate.
2. Next, we spawn the actual task via a std::async call. The core task code consists of three parts:
   • We first run through all the dependencies and ensure they all are fulfilled. waitForTasks() realises check.
   • Execute the task object.
   • Free its memory.
3. We store the shared_future returned by the task. If the task number equals NoOutDependencies, we know that noone will ever be able to wait for this task. In this case, we skip the storing.

OpenMP

OpenMP models dependencies through addresses. While it does not use the data to which these addresses point to, it is important that the addresses are valid, i.e. the system owns these memory locations. I use an internal array to administer the byte array which I use for dependencies. So the first thing is that we try to expand the memory region so we can accommodate the dependencies. Therefore, we call tarch::multicore::omp::internal::reserveDependencyTrackingMemory() first.

Next we increment numberOfPendingTasks, so noone else assumes that no tasks are pending. While we continue, we further block the memory region with a read semaphore, so noone reallocates it.

OpenMP now has iterators in taskwait and dependency statements. Yet, the set of in-dependencies is not iterable. So we create a vector into which we paste the task numbers. This also contains the outgoing task number, i.e. if there had been a task with that number before, we basically impose an inout dependency and ensure this one terminates first.

We also use iterators to administer the out dependencies. This "set" is either empty or has exactly one entry.

Finally, we distinguish OpenMP 5 and OpenMP 6 realisations. Please consult the documentations of tarch::multicore::omp::internal::spawnTaskWithOpenMP6() and tarch::multicore::omp::internal::spawnTaskWithOpenMP5() for details.

Realisation pitfalls

I originally had

#pragma omp atomic
numberOfSpawnedTasks++;

outside of the if/else cascade. However, that means that the subsequent canServeDependencyEntry() calls will not increase the memory used. They assume that the task were already out. Therefore, it is important to increment this counter as late as possible.

Task dependencies

OpenMP now supports iterators and accessors over arrays. I tried

DependencyTrackingDataType* outDependencyPointer = dependencyTrackingBaseAddress + taskNumber;
[...]
#pragma omp task [...] depend(out: *outDependencyPointer) untied

but that didn't work. So it seems that OpenMP struggles with the dereferencing. However, it seems that

#pragma omp task [...] depend(out: dependencyTrackingBaseAddress[taskNumber]) untied

does work.

TBB

With TBB, we maintain two versions: one for a new (preview) TBB version where dynamic task graph construction is supported, and one for an older version, where such a feature is not yet available, and we need our own TBB extension.

In the one version, we create a task handle via a defer() call. In the other version, we create an instance of dynamic_task_graph_node. If the task has no outgoing dependencies, we don't have to register it in some way, i.e. to memorise, as noone will be able to refer to it later anyway. However, we have to add an additional incoming dependency in case that such a task has existed before.

Next, we add the user-defined incoming dependencies to this task.

Finally, we either move the handle into the global task group, making it a proper task (new TBB version), or we put it into our own task graph object which then translates it into a proper task.

No multithreading

We just execute this task. We know that tasks may not have anti-dependencies. That is, we know that any incoming task has been spawned before. By induction, it therefore has already completed. We also don't have any competition, as there are no competing tasks. So we actually can ignore all the parameters and just execute the task.

waitForAllTasks()

void tarch::multicore::native::waitForAllTasks

(

)

Slightly different than the umbrella version in the general namespace.

See comments there. This version only waits for tasks which have been submitted with a valid task number.

Serial code

This routine degenerates to nop, as no task can be pending. spawnTask() always executed the task straightaway.

C++

There are different ways how to implement this wait: The most straight-forward implementation takes all the keys and the invokes waitForTasks() for all keys. We do not implement this pattern, as it would mean that we potentially copy quite a lot of keys. Instead, we iteratively wait for one task after another to finish. This implies that we give the runtime system a lot of freedom in which order and how parallel to tidy up all tasks.

OpenMP

In OpenMP, we do a generic taskwait, but then we use the opportunity as well to grow the memory used for dependency tracking by calling reserveDependencyTrackingMemory(). We still need the generic taskwait first, as there's no guarantee that reserveDependencyTrackingMemory() will actually expand the memory and wait for all other tasks.

waitForTasks()

void tarch::multicore::native::waitForTasks

(

const std::set< TaskNumber > &

inDependencies

)

Wait for other task.

Serial code

Degenerates to nop here, as all incoming tasks are completed. We just have to ensure that the task we are waiting for is not(!) registered, i.e. has actually been submitted.

C++ code

waitForTasks() is quite tricky, as we have to avoid any deadlocks here. We therefore use a quite defensive programming.

1. We lock the set of spawned tasks. If a dependency task is in there and is valid, we memorise it in a pointer checkFuture and release the lock.
2. Should we have found a dependency, we call the C++ wait. From hereon, the core task is complete, but there's still an entry in the global lookup table of spawned tasks. At this point, we might actually have finished a lot of tasks recursively.
3. We briefly lock the data structure again and check if the task is bookmarked in there and is already complete. In this case, we remove the entry. We kind of run an on-the-fly immediate garbage collection to slim down our map of spawned tasks.

OpenMP

As we model task dependencies over pointers on a huge memory region, we first of all issue a read lock over this memory region. After all, we don't want to code to free this memory region while we work on it.

After that, we move those task dependencies that we can map onto OpenMP dependencies (there might be some numbers which are so high that they have never been used so far and hence cannot be served by our memory region) into an std::vector. It has to be a vector, as OpenMP's iterators want to access the iterator with a [...] accessor.

If this set (list) of task dependencies is not empty, we issue an OpenMP taskwait. See remarks below on flaws with some OpenMP versions (which we currently do not accommodate). I think this part would not require an if, as it degenerates if the set of dependencies is empty, but then I am afraid that it might degenerate into a taskwait, which is not what we want.

Finally, we check which OpenMP version we support. If the version is OpenMP 5 or lower, then task dependencies cannot be transparent. That is, task dependencies in OpenMP work only between siblings. We however have task dependencies between tasks that are not spawned by the same parent task. Therefore, we have to manually ensure that all tasks have terminated. We do so by polling hasTaskFinishedInOpenMP5(). This routine's documentation provides further information on the underlying mechanisms.

OpenMP flaws

Joachim Jenke has flagged that there are some OpenMP versions that

#pragma omp taskwait depend(iterator(j=0:iterableExistingInDepencencies.size()), in: dependencyTrackingBaseAddress[iterableExistingInDepencencies[j]])

might fail with some (older) OpenMP versions. A workaround is the construct through an empty task:

#pragma omp task depend(iterator(j=0:iterableExistingInDepencencies.size()), in: dependencyTrackingBaseAddress[iterableExistingInDepencencies[j]]) if (0)
{}

Here, we model a task which is actually never spawned as task due to if statement that evaluates to false. However, the in-dependencies will be resolved nevertheless.

There is an issue that can arise if every thread is waiting on a different task, similar to in spawnTaskWithOpenMP5(...). See this function for more details.