I didn't go to the lecture and I'm a little confused about the execution order difference specified in here... So in this slide, the execution order is different because with spawning, thread 0 will execute foo(N-1) first and foo(0) the last(because of the work queue) and the original order should be foo(0) - foo(N-1)?
grose
So, there's a few different orders mentioned in this slide. First, there is the order that the cilk_spawn's occur, which is foo(0) first, and foo(N-1) last. Then, there is the order they will be removed from the queue.
I think you may be confused by the drawing of the queue, but assuming it's a standard FIFO queue, it appears that the "front" of the queue, i.e. the work that will be done first, is at the top, which might be confusing since it's the further end from Thread 0.
However, it doesn't really matter what order the foo's get executed in, since the interface of cilk_spawn doesn't specify an order, it simply says "these pieces of work are independent, and may be executed in any order, but they must be completed by cilk_sync".
xwenwenwen
Thank you so much! That clarifies a lot :))
uncreative
It seems that one of the dangers of this approach, is that in the beginning of program execution we are likely to execute a bunch of threads which only spawn work (assuming we have several cilk_spawn calls at the start of each function). This could lead to a very high memory footprint.
MediumPepsi
@uncreative I agree with you. But one benefit of this is that we have enough parallelism if we have many cores.
HCN
"these pieces of work are independent, and may be executed in any order, but they must be completed by cilk_sync" really clarifies a lot for me.
I didn't go to the lecture and I'm a little confused about the execution order difference specified in here... So in this slide, the execution order is different because with spawning, thread 0 will execute foo(N-1) first and foo(0) the last(because of the work queue) and the original order should be foo(0) - foo(N-1)?
So, there's a few different orders mentioned in this slide. First, there is the order that the cilk_spawn's occur, which is foo(0) first, and foo(N-1) last. Then, there is the order they will be removed from the queue.
I think you may be confused by the drawing of the queue, but assuming it's a standard FIFO queue, it appears that the "front" of the queue, i.e. the work that will be done first, is at the top, which might be confusing since it's the further end from Thread 0.
However, it doesn't really matter what order the foo's get executed in, since the interface of cilk_spawn doesn't specify an order, it simply says "these pieces of work are independent, and may be executed in any order, but they must be completed by cilk_sync".
Thank you so much! That clarifies a lot :))
It seems that one of the dangers of this approach, is that in the beginning of program execution we are likely to execute a bunch of threads which only spawn work (assuming we have several cilk_spawn calls at the start of each function). This could lead to a very high memory footprint.
@uncreative I agree with you. But one benefit of this is that we have enough parallelism if we have many cores.
"these pieces of work are independent, and may be executed in any order, but they must be completed by cilk_sync" really clarifies a lot for me.