In this case, once thread 0 pushes all the foos onto the queue, can it still pull one of the foos to work on, or will it be stuck on cilk_sync?
Khryl
I'm a little confused about this slide too. Can a thread steal work from its own work queue?
Fantasy
I think the answer is Yes. slide_044 shows that local local pushes and pops from tail of its own work queue.
Lawliet
If there is no stealing, then the execution order is the exact reverse of the stealing capable execution, correct?
kayvonf
Every worker in the system has a work queue. It's normal mode of operation is:
If it completes a piece of work, it grabs the next piece of work from it's own queue.
If it generates a new piece of work via a cilk_spawn, then it pushes the work onto its queue. In this example, it pushes the child work (the called function) onto the queue, and continues running the continuation.
We don't consider a worker thread taking work out it's own queue "stealing". I'd rather just call that "getting the next thing to do". Stealing occurs when a worker thread finishes its current piece of work, and then finds its local work queue empty. Rather than sit around and do nothing, the worker thread attempts to find another thread's work queue with work in it, and grabs (aka "steals") work from that queue.
As @Lawliet correctly points out, in this example where the spawned child work is pushed onto the local work queue, if no stealing occurs (in other words, if thread 0 does all the work), the work will be executed by thread 0 in the reverse order as it would if the cilk_spawn keyword was removed from the program.
MaxFlowMinCut
As a side note, regardless of whether we choose child stealing or continuation stealing, this code would be more efficient if implemented this way, correct:
for (int i = 0; i < N - 1; i++) {
cilk_spawn foo(i);
}
foo(N - 1);
cilk_sync();
To avoid the overhead of spawning and managing another cilk execution thread.
kayvonf
@MaxFlowMinCut: Also keep in mind that a much better way to spawn work in Cilk is to do it in parallel, not serially as it is done on this slide. Please refer to slide 47 to see the preferred way.
MaxFlowMinCut
@kayvonf Oops, yup, I meant to make that a normal function call. Thanks!
randomized
Just to clarify, here the queue essentially becomes a stack right? (Even though foo(0) was first in, thread will first execute foo(N-1) in case of no stealing).
In this case, once thread 0 pushes all the foos onto the queue, can it still pull one of the foos to work on, or will it be stuck on cilk_sync?
I'm a little confused about this slide too. Can a thread steal work from its own work queue?
I think the answer is Yes. slide_044 shows that local local pushes and pops from tail of its own work queue.
If there is no stealing, then the execution order is the exact reverse of the stealing capable execution, correct?
Every worker in the system has a work queue. It's normal mode of operation is:
cilk_spawn, then it pushes the work onto its queue. In this example, it pushes the child work (the called function) onto the queue, and continues running the continuation.We don't consider a worker thread taking work out it's own queue "stealing". I'd rather just call that "getting the next thing to do". Stealing occurs when a worker thread finishes its current piece of work, and then finds its local work queue empty. Rather than sit around and do nothing, the worker thread attempts to find another thread's work queue with work in it, and grabs (aka "steals") work from that queue.
As @Lawliet correctly points out, in this example where the spawned child work is pushed onto the local work queue, if no stealing occurs (in other words, if thread 0 does all the work), the work will be executed by thread 0 in the reverse order as it would if the
cilk_spawnkeyword was removed from the program.As a side note, regardless of whether we choose child stealing or continuation stealing, this code would be more efficient if implemented this way, correct:
To avoid the overhead of spawning and managing another cilk execution thread.
@MaxFlowMinCut: Also keep in mind that a much better way to spawn work in Cilk is to do it in parallel, not serially as it is done on this slide. Please refer to slide 47 to see the preferred way.
@kayvonf Oops, yup, I meant to make that a normal function call. Thanks!
Just to clarify, here the queue essentially becomes a stack right? (Even though foo(0) was first in, thread will first execute foo(N-1) in case of no stealing).