In the greedy policy, what bookkeeping is needed when a processor steals? Since we don't need to know what thread initiated work (since we implement sync by continuing work on the last thread), what else is there to keep track of?
This comment was marked helpful 0 times.
bwasti
I am pretty sure the bookkeeping refers to popping the work from the double ended queue.
This comment was marked helpful 0 times.
kayvonf
One of the overheads is the reference counting of completed children that needs to occur after a steal. If a processor completes its current task, then looks at the bottom of the dequeue and sees there's no more work because of a steal, then the processor needs to make sure the caller frame (managed elsewhere at this point) gets notification that this child task has completed. I'm not sure about Cilk Plus specifically, but the research versions of Cilk lazily created these structures only when work was actually stolen.
This comment was marked helpful 0 times.
elemental03
Just wanted to note that threads steal from random cores, not nearby ones.
The reason why is explained in this faq on the main site for Cilk. They also answer some other interesting queries one might have such as why they use a dequeue rather than a FIFO queue :
In the greedy policy, what bookkeeping is needed when a processor steals? Since we don't need to know what thread initiated work (since we implement sync by continuing work on the last thread), what else is there to keep track of?
This comment was marked helpful 0 times.
I am pretty sure the bookkeeping refers to popping the work from the double ended queue.
This comment was marked helpful 0 times.
One of the overheads is the reference counting of completed children that needs to occur after a steal. If a processor completes its current task, then looks at the bottom of the dequeue and sees there's no more work because of a steal, then the processor needs to make sure the caller frame (managed elsewhere at this point) gets notification that this child task has completed. I'm not sure about Cilk Plus specifically, but the research versions of Cilk lazily created these structures only when work was actually stolen.
This comment was marked helpful 0 times.
Just wanted to note that threads steal from random cores, not nearby ones.
The reason why is explained in this faq on the main site for Cilk. They also answer some other interesting queries one might have such as why they use a dequeue rather than a FIFO queue :
Cilk FAQ
This comment was marked helpful 0 times.