Why is the order of execution mentioned in both this and the previous slides? Do we care about the order of execution? I thought the work spawned by cilk_spawn is independent and could be executed in any order. Any particular benefit of having the same execution order as for program with spawn removed?
vrkrishn
Think about a typical prototype for a divide and conquer algorithm:
fun divide_and_conquer(0,n);
fun merge(p,q);
Where the divide and conquer function has multiple sub calls to divide and conquer followed by one call to merge.
Say you were trying to run this code on one machine, then it becomes clear what order of execution means. Say we reach the line:
p = divide_and_conquer(0,n/2) // child
In the child-first order of execution, your computer will save the register states at the time of the call and then immediate run the called divide_and_conquer child process.
In the continuation-first order of execution, the computer makes a note that it has to run divide_and_conquer(0,n/2) but does not immediately execute. Instead, it puts the note onto some queue and continues to the next line; it once again puts divide_and_conquer(n/2,n) onto some queue.
Finally, it reaches the merge function call and sees that it needs the output of the child steps to continue so it executes the queued child processes
vrkrishn
Essentially, the continuation order of execution follows the philosophy of: Don't go into a recursive call until the every recursive call that is made is known.
The child order of execution follows the philosophy of: Execute a recursive call as soon as it is made
amaliujia
@afa4. The order talking here is in the context when forbidding child stealing. So when allow stealing, order cannot predict.
subliminal
Does Cilk always use run-child-first? Or are there situations where it uses run-continuation-first scheduling as well?
Why is the order of execution mentioned in both this and the previous slides? Do we care about the order of execution? I thought the work spawned by cilk_spawn is independent and could be executed in any order. Any particular benefit of having the same execution order as for program with spawn removed?
Think about a typical prototype for a divide and conquer algorithm:
fun divide_and_conquer(0,n);
fun merge(p,q);
Where the divide and conquer function has multiple sub calls to divide and conquer followed by one call to merge.
Say you were trying to run this code on one machine, then it becomes clear what order of execution means. Say we reach the line:
In the child-first order of execution, your computer will save the register states at the time of the call and then immediate run the called divide_and_conquer child process.
In the continuation-first order of execution, the computer makes a note that it has to run divide_and_conquer(0,n/2) but does not immediately execute. Instead, it puts the note onto some queue and continues to the next line; it once again puts divide_and_conquer(n/2,n) onto some queue.
Finally, it reaches the merge function call and sees that it needs the output of the child steps to continue so it executes the queued child processes
Essentially, the continuation order of execution follows the philosophy of: Don't go into a recursive call until the every recursive call that is made is known.
The child order of execution follows the philosophy of: Execute a recursive call as soon as it is made
@afa4. The order talking here is in the context when forbidding child stealing. So when allow stealing, order cannot predict.
Does Cilk always use run-child-first? Or are there situations where it uses run-continuation-first scheduling as well?