Pipeline order guarantees?

[john_e_lilley]

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

[RafSchietekat]

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.

[john_e_lilley]

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

[RafSchietekat]

I don't understand the first question?

Graph is a Community Preview Feature in recent Development Releases.

[john_e_lilley]

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.

[john_e_lilley]

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

[RafSchietekat]

"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.