How would something like this be efficiently implemented?
dyzz
I think Professor Kayvon stated that it has been shown that stealing work from a random queue is a good choice (correct me if im wrong). I believe it could be implemented by using shared memory or message passing constructs.
pdp
@coffee7: The other alternative is that thread 1 sits idle. So, its better it steals work and executes even if there is little overhead.
VersaceGohan
@pdp I believe @coffee7 was wondering what the most efficient way to implement work stealing. If there are N busy threads and only one of them has work in its queue, worst case it takes O(N) time to check all the busy thread queues and steal something. As @dyzz, I think stealing from a random queue should work well on average.
apr
Question regarding distributed queues in Cilk's implementation. In Cilk, idle threads choose another thread at random and steal from the double ended queue. This double ended queue only helps to prevent contention between the actual thread who owns the queue and threads that are stealing from that thread.
From a slide on the previous lecture, we also know that Cilk uses a lockless queue implementation of this double ended queue. Hence, the only reason that the distributed queue using in Cilk prevents contention is because of this lockless implementation right? If this same lockless implementation was used for a global queue, would that not prevent an idle thread from checking multiple other queues for work in case the previous queues it checked were empty?
How would something like this be efficiently implemented?
I think Professor Kayvon stated that it has been shown that stealing work from a random queue is a good choice (correct me if im wrong). I believe it could be implemented by using shared memory or message passing constructs.
@coffee7: The other alternative is that thread 1 sits idle. So, its better it steals work and executes even if there is little overhead.
@pdp I believe @coffee7 was wondering what the most efficient way to implement work stealing. If there are N busy threads and only one of them has work in its queue, worst case it takes O(N) time to check all the busy thread queues and steal something. As @dyzz, I think stealing from a random queue should work well on average.
Question regarding distributed queues in Cilk's implementation. In Cilk, idle threads choose another thread at random and steal from the double ended queue. This double ended queue only helps to prevent contention between the actual thread who owns the queue and threads that are stealing from that thread.
From a slide on the previous lecture, we also know that Cilk uses a lockless queue implementation of this double ended queue. Hence, the only reason that the distributed queue using in Cilk prevents contention is because of this lockless implementation right? If this same lockless implementation was used for a global queue, would that not prevent an idle thread from checking multiple other queues for work in case the previous queues it checked were empty?