Why stealing randomly from other threads? I try to explain this myself, but please share great ideas.
If we can estimate the cost of work, then we can iterate over all queues and find the most expensive cost on top, but it incurs non trivial cost of "stealing". And the running time of each work might be hard to estimate.
kayvonf
For those interested in a more formal analysis of work stealing, I suggest you dig into the Blumofe and Leiserson paper linked as "Further Reading" for this lecture.
@bochet Choosing a random thread to steal from is important because some workloads might initially lead to highly imbalanced queues, and if the queues with the most work are checked for free threads last, then the imbalance may be worsened (this is assuming a static stealing algorithm).
l8b
This sounds similar to parts of homework 1, where we tried to distribute each row of work as randomly as possible in order to account for particularly imbalanced ones.
yes
Also seems like stealing randomly is a good fast alternative to attempting to find the optimal distribution of work across all threads and stealing the relevant work based on that distribution.
Why stealing randomly from other threads? I try to explain this myself, but please share great ideas.
If we can estimate the cost of work, then we can iterate over all queues and find the most expensive cost on top, but it incurs non trivial cost of "stealing". And the running time of each work might be hard to estimate.
For those interested in a more formal analysis of work stealing, I suggest you dig into the Blumofe and Leiserson paper linked as "Further Reading" for this lecture.
Here's a link:
Scheduling Multithreaded Computations by Work Stealing, Blumofe and Leiserson, JACM 1999
@bochet Choosing a random thread to steal from is important because some workloads might initially lead to highly imbalanced queues, and if the queues with the most work are checked for free threads last, then the imbalance may be worsened (this is assuming a static stealing algorithm).
This sounds similar to parts of homework 1, where we tried to distribute each row of work as randomly as possible in order to account for particularly imbalanced ones.
Also seems like stealing randomly is a good fast alternative to attempting to find the optimal distribution of work across all threads and stealing the relevant work based on that distribution.