Amina,

I think you will have to diagram the problem situation. When situations frequently occur, there tends to be a built-in solution. This is true of most parallel programming paradigms. Dequeueing and enqueuing is significantly heavier weight code than a single threadstepping from iteration to iteration. When the work performed per iteration is small, then coding to permit rescheduling is likely counter productive. If the work is large, then there may be some advantage. In Cilk, look at the loop partitioning feature (#pragma cilk grainsize = n). The intentions being for you to control the number of execution split points. More splits == more opportunity for work stealing == more overhead in task spawn. This to say there is a trade-off between creating parallelism and performing work. Let's break appart your question 2:

when a worker X need the result of a strand Z executing into another worker Y (snip) the worker X can it help the worker Y to terminate the execution of the strand Z (snip) so that the worker X will continue its execution of strands.

To rephrase the above: X is dependent on Z, Z is dependent on Y. Your concerns are:

a) X terminating first(running to join (cilk_sync)) and Z is finished but for Y. In this case you might consider rewriting Y to contain Cilk worksharing constructs. (assuming the overhead is justified). Then hardware threads that were running X and/or Z could participate in completing Y.

b) X terminating first(running to join (cilk_sync)) and Z is NOT finished but Y spawned by Z has finished. In this case you might consider rewritingZ to contain Cilk worksharing constructs. (assuming the overhead is justified). Then hardware threads that were running X and/orY could participate in completing Z.

c) X terminating last, Z and Y spawned and terminated first. Then consider rewriting X to contain Cilk worksharing constructs (at approximate time of earlier completion of Z or Y). Note coordination of timing will vary from system to system and run to run.

Use similar stratigy for other situations of your query 2)

If you have a programming requirement to asynchronously launch and retire tasks, then you may need to look at a different parallel programming paradigm. State machines and data flow can be handled better usingsomething else.

Even with the other parallel programming paradigms you still have to trade-off granularity vs overhead.

Do you have a particular programming problem that you find difficult to impliment using Cilk?

Jim Dempsey

> can we force a worker to choice its victim (not randomly) with parameters?

No. You cannot force a worker to choose a particular victim.

- Barry

There's an errorin the sentence [bold added]:

When a worker X need a result from another worker Y, it have to wait it or it can help the worker Y to achieve the task to have quickly the result, so that the worker X can continue the execution of its task ?

Workers never wait in Cilk. If a worker reaches a sync, it does one of two things:

1. Continue execution without waiting.
2. Abandon the current computation completely (and become a thief).

It does (1) if it is the last worker to reach the sync, and (2) otherwise. Thus ifcase 2 applies to the example, worker X will start trying to steal.X will either steal work thathelps worker Y, or stealunrelated work that does not help Y, but nonetheless contributes to helping the program complete.

Brent's Lemma shows that the most careful choice of a victim from which to steal cannot improve program performance by more than 2x (on an ideal PRAM) compared to random stealing, and that's for a fairly contrived case.

TBB has no way to guide choice of victim either, though Chapter 9 of TBB Design Patternsmanual shows a way to roll your own work chooser on top of the TBB scheduler.