- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Report Inappropriate Content
I am looking at TTB parallel_pipeline pattern for execution of a set of steps that have inter-dependencies (Intel Threading Challenge 2011, Problem 3... should sound familiar to some of you). The dependencies can be expressed as a Directed Acyclic Graph; however, a step never depends on later steps, only previous ones. I have two questions regarding use of TBB parallel pipelines for this problem:
1) If I have one chunk of work in the parallel portion of the pipeline wait for another chunk of work, can it deadlock? For example, suppose that the chunks of work are:
A
B (depends on A)
C
D (depends on B)
If a chunk of work is set up like:
DoWork() {
WaitForDependencies();
DoMyWork();
SignalDependents();
}
I am concerned that out-of-order execution can deadlock. For example if the parallel pipeline only has one thread, and decides to run D first, it will deadlock unless another thread is injected, or the steps are guaranteed to start in order. Perhaps there is a better construct in TBB to express this kind of situation?
2) Is it possible for a parallel filter step to return other than one output item? For example, can it return zero or three?
Thanks
John
Link Copied
6 Replies
- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Report Inappropriate Content
1) In general, you should map all dependencies to TBB constructs, otherwise
you're bound to run into deadlocks unless you use plain old threads.
Have you looked at the new graph feature?
2) Each item is taken through all stages in the order they occur in the pipeline, so no.
2) Each item is taken through all stages in the order they occur in the pipeline, so no.
- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Report Inappropriate Content
So I take it there is no "ordered parallel pipeline" or "ordered parallel queue"?
I have not seen the new graph feature. What version of TBB is it in and what's it called?Thanks
john
- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Report Inappropriate Content
I don't understand the first question?
Graph is a Community Preview Feature in recent Development Releases.
Graph is a Community Preview Feature in recent Development Releases.
- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Report Inappropriate Content
By "ordered pipeline", I mean a pipeline in which tasks are guaranteed to be dispatched in order, even if they do not complete in order, thus avoiding the deadlock issue.
- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Report Inappropriate Content
The Graph object looks cool, but unfortunately not right for this application. It looks more suitable for setting up static dependency graphs (like, say, and ETL tool) rather than fine-grained task-specific dependencies.
Thanks,
john
- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Report Inappropriate Content
"By "ordered pipeline", I mean a pipeline in which tasks are guaranteed to be dispatched in order, even if they do not complete in order, thus avoiding the deadlock issue."
Each item meets all the stages in the order of the pipeline. Each serial_in_order stage meets items in the same order as established by any previous serial_in_order stage. Otherwise anything goes. Last time I looked, each item was guided through the pipeline by a TBB task, but this is not essential. Perhaps a pipeline with only serial_in_order stages is what you need, and you accept to pay the price of reduced performance opportunities related to such a pipeline and also related to the stalls from extra dependencies outside of TBB's task dependency graph? Just be sure to avoid those deadlocks.
"The Graph object looks cool, but unfortunately not right for this application. It looks more suitable for setting up static dependency graphs (like, say, and ETL tool) rather than fine-grained task-specific dependencies."
OK, I just couldn't tell from the description. Suitable prepackaged algorithms are the appropriate choice when available, but obviously sometimes direct use of tasks is unavoidable.
Each item meets all the stages in the order of the pipeline. Each serial_in_order stage meets items in the same order as established by any previous serial_in_order stage. Otherwise anything goes. Last time I looked, each item was guided through the pipeline by a TBB task, but this is not essential. Perhaps a pipeline with only serial_in_order stages is what you need, and you accept to pay the price of reduced performance opportunities related to such a pipeline and also related to the stalls from extra dependencies outside of TBB's task dependency graph? Just be sure to avoid those deadlocks.
"The Graph object looks cool, but unfortunately not right for this application. It looks more suitable for setting up static dependency graphs (like, say, and ETL tool) rather than fine-grained task-specific dependencies."
OK, I just couldn't tell from the description. Suitable prepackaged algorithms are the appropriate choice when available, but obviously sometimes direct use of tasks is unavoidable.

Reply
Topic Options
- Subscribe to RSS Feed
- Mark Topic as New
- Mark Topic as Read
- Float this Topic for Current User
- Bookmark
- Subscribe
- Printer Friendly Page