Q. Stealing in fully strict applications

classic Classic list List threaded Threaded
10 messages Options
Reply | Threaded
Open this post in threaded view
|

Q. Stealing in fully strict applications

Godmar Back

Hi,

may I ask two clarifying questions about the FJ design?

Q1: Is my understanding correct that FJ is designed for arbitrary DAGs where there are no restrictions on which task may join which other, as long as the resulting dependency graph is a DAG?

Q2: If a computation is "fully strict," which (I believe) means that each task is always joined by the task that created it, and if a stack-based implementation like the one in FJ is used, then is it safe to steal during calls to join() that would otherwise block? E.g. if a task being joined is already being processed by some other worker, the calling thread can steal any task from the tail end of other worker's queues? By "tail end" I mean where the oldest task was pushed that a worker spawned, assuming a FIFO order for stealing and a LIFO order for the worker's processing.

Or, does the task scheduler need to impose constraints on which tasks can be stolen even if the computation is fully strict?

Thanks.

 - Godmar


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Q. Stealing in fully strict applications

Doug Lea
On 01/27/2015 12:22 PM, Godmar Back wrote:

> Q1: Is my understanding correct that FJ is designed for arbitrary DAGs where
> there are no restrictions on which task may join which other, as long as the
> resulting dependency graph is a DAG?

Yes; it is possible to create antagonistic non-strict DAGS that run
inefficiently, but these are not very commonly programmed by accident.

>
> Q2: If a computation is "fully strict," which (I believe) means that each task
> is always joined by the task that created it, and if a stack-based
> implementation like the one in FJ is used, then is it safe to steal during calls
> to join() that would otherwise block?

At least in the case you describe and a couple of other
special cases mentioned in ForkJoinPool internal documentation.

> E.g. if a task being joined is already
> being processed by some other worker, the calling thread can steal any task from
> the tail end of other worker's queues? By "tail end" I mean where the oldest
> task was pushed that a worker spawned, assuming a FIFO order for stealing and a
> LIFO order for the worker's processing.
>
> Or, does the task scheduler need to impose constraints on which tasks can be
> stolen even if the computation is fully strict?

The only additional constraints imposed are limits to bound
the length of potential ping-pong dependency chains. This is done
to force eventual blocking in case of misuses with cyclic
dependencies, as well as to bound some internal raciness.

-Doug


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Q. Stealing in fully strict applications

Godmar Back
On Tue, Jan 27, 2015 at 3:43 PM, Doug Lea <[hidden email]> wrote:
On 01/27/2015 12:22 PM, Godmar Back wrote:

Q1: Is my understanding correct that FJ is designed for arbitrary DAGs where
there are no restrictions on which task may join which other, as long as the
resulting dependency graph is a DAG?

Yes; it is possible to create antagonistic non-strict DAGS that run
inefficiently, but these are not very commonly programmed by accident.


Q2: If a computation is "fully strict," which (I believe) means that each task
is always joined by the task that created it, and if a stack-based
implementation like the one in FJ is used, then is it safe to steal during calls
to join() that would otherwise block?

At least in the case you describe and a couple of other
special cases mentioned in ForkJoinPool internal documentation.

What exactly do you mean by ForkJoinPool internal documentation - the comments in the source code that aren't displayed in the API/HTML documentation?  
If so, which classes specifically would discuss this?  Should I look at src.zip that comes with JDK 1.8 or something newer?

 - Godmar


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Q. Stealing in fully strict applications

Doug Lea
On 01/27/2015 04:27 PM, Godmar Back wrote:

>     At least in the case you describe and a couple of other
>     special cases mentioned in ForkJoinPool internal documentation.
>
>
> What exactly do you mean by ForkJoinPool internal documentation - the comments
> in the source code that aren't displayed in the API/HTML documentation?

The base source of ForkJoinPool is at

http://gee.cs.oswego.edu/cgi-bin/viewcvs.cgi/jsr166/src/main/java/util/concurrent/ForkJoinPool.java?view=log

We don't place internal algorithm documentation in public javadocs,
because it is always subject to change, while still complying with
public APIs.

-Doug

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Q. Stealing in fully strict applications

Martin Buchholz-3
In reply to this post by Godmar Back

On Tue, Jan 27, 2015 at 1:27 PM, Godmar Back <[hidden email]> wrote:
On Tue, Jan 27, 2015 at 3:43 PM, Doug Lea <[hidden email]> wrote:
On 01/27/2015 12:22 PM, Godmar Back wrote:

Q1: Is my understanding correct that FJ is designed for arbitrary DAGs where
there are no restrictions on which task may join which other, as long as the
resulting dependency graph is a DAG?

Yes; it is possible to create antagonistic non-strict DAGS that run
inefficiently, but these are not very commonly programmed by accident.


Q2: If a computation is "fully strict," which (I believe) means that each task
is always joined by the task that created it, and if a stack-based
implementation like the one in FJ is used, then is it safe to steal during calls
to join() that would otherwise block?

At least in the case you describe and a couple of other
special cases mentioned in ForkJoinPool internal documentation.

What exactly do you mean by ForkJoinPool internal documentation - the comments in the source code that aren't displayed in the API/HTML documentation?  
If so, which classes specifically would discuss this?  Should I look at src.zip that comes with JDK 1.8 or something newer?

 - Godmar


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest



_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Q. Stealing in fully strict applications

Godmar Back

I'm having trouble locating the discussion of the fully-strict case in the comments of ForkJoinPool.java.

My doubts are, specifically - "helping" is described as a more "conservative" form of leapfrogging. I read "conservative" as that it might not decide to steal/help whereas fully fledged leap-frogging implementation would. 

Looking at leap frogging, and the leap frog depth rule (Section 3.1) in particular, I cannot tell whether the leap frog depth rule is necessary for fully strict computations also or only in the general DAG case. Earlier in the leap frogging paper (Section 2.4) the authors seem to assume a fully-strict computation, and imply that the leap frog depth rule is required. (I don't know when this term was coined, historically, it may be after the leap frogging paper was published.)  This would mean that even for fully-strict computations worker threads couldn't steal willy-nilly when attempting to help. But I'm quite frankly confused about this.

Of course, this mailing list is about FJ, not my troubles reading old papers; but I would still like to understand better how FJ implements constraints on its task scheduling and how those depend on the structure of the underlying computational DAG.
Also, are there any unit tests that attempt to present adverse DAGs to the FJ framework?

 - Godmar 

On Tue, Jan 27, 2015 at 6:08 PM, Martin Buchholz <[hidden email]> wrote:

On Tue, Jan 27, 2015 at 1:27 PM, Godmar Back <[hidden email]> wrote:
On Tue, Jan 27, 2015 at 3:43 PM, Doug Lea <[hidden email]> wrote:
On 01/27/2015 12:22 PM, Godmar Back wrote:

Q1: Is my understanding correct that FJ is designed for arbitrary DAGs where
there are no restrictions on which task may join which other, as long as the
resulting dependency graph is a DAG?

Yes; it is possible to create antagonistic non-strict DAGS that run
inefficiently, but these are not very commonly programmed by accident.


Q2: If a computation is "fully strict," which (I believe) means that each task
is always joined by the task that created it, and if a stack-based
implementation like the one in FJ is used, then is it safe to steal during calls
to join() that would otherwise block?

At least in the case you describe and a couple of other
special cases mentioned in ForkJoinPool internal documentation.

What exactly do you mean by ForkJoinPool internal documentation - the comments in the source code that aren't displayed in the API/HTML documentation?  
If so, which classes specifically would discuss this?  Should I look at src.zip that comes with JDK 1.8 or something newer?

 - Godmar


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest




_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Q. Stealing in fully strict applications

Doug Lea
On 01/27/2015 06:29 PM, Godmar Back wrote:

> My doubts are, specifically - "helping" is described as a more "conservative"
>  form of leapfrogging. I read "conservative" as that it might not decide to
> steal/help whereas fully fledged leap-frogging implementation would.

Yes. The original formulations of leap-frogging and some other
work-stealing techniques allowed indefinite spinning
in cases including when the stealer will eventually produce tasks
that can be helped but hasn't. FJ gives up after a while and
blocks/compensates.

(Aside: We also provide a purely continuation-based
form of ForkJoinTask, CountedCompleter, that people can use to
avoid dependent blocking, at the price of having to think in
terms of CPS transforms. We also use this internally in cases where
we don't trust tasks to not indefinitely block. It's unfortunate
that this API is so user-hostile that we didn't even include it
initially.)

> Earlier in the leap frogging paper (Section 2.4) the authors seem to assume a
> fully-strict computation, and imply that the leap frog depth rule is
> required. (I don't know when this term was coined, historically, it may be
> after the leap frogging paper was published.)

Yes, it was.

> This would mean that even for fully-strict computations worker threads
> couldn't steal willy-nilly when attempting to help. But I'm quite frankly
> confused about this.

There are only a few scenarios that must be avoided, that
don't differ much in strict vs non-strict cases. You cannot
create a dependency cycle that could cause
(A waitsFor B) and (B waitsFor A). In some pure trees, this can't happen
anyway under the usual steal rules (so the very first non-JDK versions
of FJ, supporting only these case did not even need to track/check).

>  Also, are there any unit tests that attempt to present
> adverse DAGs to the FJ framework?
>

A few are in the tck tests (although not highlighted as such). Others
aren't integrated yet into any repository. One of these days...

-Doug

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Q. Stealing in fully strict applications

thurstonn
Doug Lea wrote
On 01/27/2015 06:29 PM, Godmar Back wrote:

> My doubts are, specifically - "helping" is described as a more "conservative"
>  form of leapfrogging. I read "conservative" as that it might not decide to
> steal/help whereas fully fledged leap-frogging implementation would.

Yes. The original formulations of leap-frogging and some other
work-stealing techniques allowed indefinite spinning
in cases including when the stealer will eventually produce tasks
that can be helped but hasn't. FJ gives up after a while and
blocks/compensates.
But my understanding of your response to an earlier question I posed regarding the max stack height of a FJWT was:
msh + (msh - 1) + . . . + 1, where msh := max sequential stack height, which is more aggressive (less conservative) than leapfrogging, where msh's are == (P2 in the leapfrogging paper)
Reply | Threaded
Open this post in threaded view
|

Re: Q. Stealing in fully strict applications

Doug Lea
On 01/29/2015 08:03 AM, thurstonn wrote:

> But my understanding of your response to an earlier question I  posed
> <http://jsr166-concurrency.10961.n7.nabble.com/FJ-stack-bounds-td11552.html>
> regarding the max stack height of a FJWT was:
> msh + (msh - 1) + . . . + 1, where msh := max sequential stack height, which
> is more aggressive (less conservative) than leapfrogging, where msh's are ==
> (P2 in the leapfrogging paper)

When FJ uses leap-frogging, it has the same msh bound. It
also handles a few additional cases that amount to
stealing a sibling in a local deque, at the cost of
more stack frames but fewer threads. Almost none of these
cases are good programming practice, but are not illegal.
For example, the infamously bad out-of-order-join case:
   a.fork(); b.fork(); a.join(); b.join();

-Doug



_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Q. Stealing in fully strict applications

thurstonn
Doug Lea wrote
On 01/29/2015 08:03 AM, thurstonn wrote:

> But my understanding of your response to an earlier question I  posed
> <http://jsr166-concurrency.10961.n7.nabble.com/FJ-stack-bounds-td11552.html>
> regarding the max stack height of a FJWT was:
> msh + (msh - 1) + . . . + 1, where msh := max sequential stack height, which
> is more aggressive (less conservative) than leapfrogging, where msh's are ==
> (P2 in the leapfrogging paper)

When FJ uses leap-frogging, it has the same msh bound. It
also handles a few additional cases that amount to
stealing a sibling in a local deque, at the cost of
more stack frames but fewer threads. Almost none of these
cases are good programming practice, but are not illegal.
For example, the infamously bad out-of-order-join case:
   a.fork(); b.fork(); a.join(); b.join();

-Doug
So is the following accurate:

If all fj worker threads join tasks in the **opposite** order in which it forks them, the worst-case maximum stack height == maximum stack height of a sequential execution?