I'm a TBB newbie, but am familiar with concurrent programming etc... I've looked over the docs and read a few threads in the forum, so I am aware that I'm not the first to ask questions about DAGs.
I'm looking to use TBB to evaluate a complex directed graph of operations. I've seen a few suggestions on how to do this (eg: the white/grey/black edge colouring) which look reasonable, but involve quite a bit of book keeping to implement. I was wondering if there is anything equivalent to a task level mutex/lock which would simplify the implementation, and if not, is it a reasonable feature request?
For my purposes, we have a graph of operations. How I see it is that a TTB task is generated for each node in our graph, computes whatever it needs to do and shoves the result back into the graph node. So if we have a simple graph, where node A depends on nodes B and C, this would be fairly straight forward. We recurse up backwards through the dependency chain from A, first generating task for A, which generates tasks for B and C and waits for them (or rather a continuation task does). Tasks B and C do what they need to do then task A runs. All happy and easy enough with TBB.
However if we have another node D, which both B and C depend on it gets complex. We have a diamond dependency, so B and C's tasks will attempt to generate a task for D. Boo, what do we do here? We could...
- compute D twice and waste a thread and associated resources,
- block one thread and wait for D to be computed and waste a thread,
- implement the edge colouring idea to traverse through D, which would be quite complex to implement the glue for.
My suggestion is that there be TBB task level mutexes and locks, with them it would be comparatively trivial to implement this traversal. When a task gets to D it locks such a mutex, checks to see if the value is there, if not, it generates the task for D, waits for it to complete, then unlocks the mutex. So the first tasks computes D, the second one stops. However, being a task level lock, instead of blocking the entire thread, it blocks the calling task. The thread running that task suspends it at the point of the lock, goes away and attempts to do other work, every so often checking to see if the lock has now been gained and then resumes the task at that point. So if there were any parallel tasks needed to produce D, our blocked thread 'teleports' around the block and continue to do useful work on other tasks.
I can't imagine you could implement such a thing client side at all, as it needs to play with the TBB scheduler. Without peering into the source, I can't see this as being to hard to implement (always optimistic me), with a fairly simple lock class a few tweaks to the task queues. Admittedly this is effectively voluntary preemption, which goes against the design philosophy of TBB. If that is out of the question, something similar could be done with a 'lock continuation' task. Either way, the key point is not to have the entire thread waiting on a mutex, but only to have a task wait.
Anyone else see this at all a practical idea, or see some better way of implementing this in TBB?