How do we know that the remote work is on the top of the queue? Is that just built into the design of the function?
rbcarlso
The call to cilk_spawn adds continuations to a queue, where the local thread takes continuations from the front of the queue and the other threads steal continuations from the back of the queue. It's built into threads that use cilk work queues. Technically anything on the queue could be run remotely and anything on the queue could be run locally, but the preferred behavior is like you said, and it depends on which end threads grab work from.
regi
Doesn't this assume some sort of divide and conquer algorithm where the first few calls are "larger" pieces of work and later calls are smaller? It's possible that with a balanced work distribution, the middle bullet point doesn't apply.
EDIT: oops, this is addressed on the next slide.
kayvonf
@regi, nice observation!
sanchuah
@HLAHat, I think it just a policy choice. And, in the recursive function context, stealing the work from the top can usually get the "larger" piece of work, which can compute for a while and amortize the cost of stealing.
zhanpenf
This link "https://www.cilkplus.org/faq/20" suggests that besides random choices of victim, another idea for who to steal is to steal from a nearby core, and it is kind of making a tradeoff between exploiting locality and making progress on the critical path of the overall computation. However, the drawback for this idea is that the cores are more likely to miss stealing a large task that is on the critical path because they repeatedly steal from nearby neighbors.
How do we know that the remote work is on the top of the queue? Is that just built into the design of the function?
The call to cilk_spawn adds continuations to a queue, where the local thread takes continuations from the front of the queue and the other threads steal continuations from the back of the queue. It's built into threads that use cilk work queues. Technically anything on the queue could be run remotely and anything on the queue could be run locally, but the preferred behavior is like you said, and it depends on which end threads grab work from.
Doesn't this assume some sort of divide and conquer algorithm where the first few calls are "larger" pieces of work and later calls are smaller? It's possible that with a balanced work distribution, the middle bullet point doesn't apply.
EDIT: oops, this is addressed on the next slide.
@regi, nice observation!
@HLAHat, I think it just a policy choice. And, in the recursive function context, stealing the work from the top can usually get the "larger" piece of work, which can compute for a while and amortize the cost of stealing.
This link "https://www.cilkplus.org/faq/20" suggests that besides random choices of victim, another idea for who to steal is to steal from a nearby core, and it is kind of making a tradeoff between exploiting locality and making progress on the critical path of the overall computation. However, the drawback for this idea is that the cores are more likely to miss stealing a large task that is on the critical path because they repeatedly steal from nearby neighbors.