When a thread is idle, does it constantly search randomly at other threads to see if they have anything on their work queues? Also, would synchronization overhead be a concern if/when two threads try to steal from the same thread's work queue?
poptarts
@pht I'm not entirely sure about this answer, so if someone has a better understanding please correct me.
My reasoning is that when a thread is idle, it is in its best interest to attempt to steal work from another thread. (What else would it do, anyways?)
In terms of synchronization overhead, we may be able to argue that the expected amount of synchronization is low. Say you have N threads. If thread A and thread B both become idle at the same time, the probability that they both try to steal work from the same thread C is 1/N-1 * 1/N-1, which gets lower with more threads (< 0.5% at N = 16).
bochet
We can verify that it's child first because it's always picking the first half of an interval. That's why [101, 200] ends up in a queue, and [0, 100] get further split.
muchanon
In a situation where you have more threads than cores, if we had 4 cores and 4 threads with work in their queues, is there any benefit to thread 5 trying to steal work? Would this just be wasted time and should we try to avoid stealing in this situation?
kayvonf
@muchanon. Here's a question for you. In this case, why would you want to make more threads than cores? (For simplicity, let's assume that our cores have no hardware multi-threading. Otherwise, I could ask: why would you want to make more threads than hardware execution contexts?)
cwchang
The detailed steps of the execution is like this:
Encountered cilk_spawn quicksort(0, 100). Child first, so do quicksort(0, 100) and put conti 101~200 into queue.
Encountered cilk_spawn quicksort(0, 50) in next level of recursion. Similarly, work on quicksort(0, 50) and put conti 51~100 into queue.
Work on quicksort(0, 25), put conti 26~50 into queue.
When a thread is idle, does it constantly search randomly at other threads to see if they have anything on their work queues? Also, would synchronization overhead be a concern if/when two threads try to steal from the same thread's work queue?
@pht I'm not entirely sure about this answer, so if someone has a better understanding please correct me.
My reasoning is that when a thread is idle, it is in its best interest to attempt to steal work from another thread. (What else would it do, anyways?)
In terms of synchronization overhead, we may be able to argue that the expected amount of synchronization is low. Say you have N threads. If thread A and thread B both become idle at the same time, the probability that they both try to steal work from the same thread C is 1/N-1 * 1/N-1, which gets lower with more threads (< 0.5% at N = 16).
We can verify that it's child first because it's always picking the first half of an interval. That's why [101, 200] ends up in a queue, and [0, 100] get further split.
In a situation where you have more threads than cores, if we had 4 cores and 4 threads with work in their queues, is there any benefit to thread 5 trying to steal work? Would this just be wasted time and should we try to avoid stealing in this situation?
@muchanon. Here's a question for you. In this case, why would you want to make more threads than cores? (For simplicity, let's assume that our cores have no hardware multi-threading. Otherwise, I could ask: why would you want to make more threads than hardware execution contexts?)
The detailed steps of the execution is like this:
cilk_spawn quicksort(0, 100). Child first, so doquicksort(0, 100)and putconti 101~200into queue.cilk_spawn quicksort(0, 50)in next level of recursion. Similarly, work onquicksort(0, 50)and putconti 51~100into queue.quicksort(0, 25), putconti 26~50into queue.