3 ms·

You're effectively solving the problem of small work items by making them larger. Alas, doing so in the workers introduces new failure modes. If the work item

You're effectively solving the problem of small work items by making them larger. Alas, doing so in the workers introduces new failure modes. If the work items are atomically enqueued one at a time while there are free workers, then they will also be dequeued one at a time. This can be mitigated by enqueuing work in batches. Workers also hold the lock for much longer, adding more contention on the FIFO. If you're going to do that, you're usually better off just making the work items bigger on the producer side.

dragontamer 7y ago
Yes, you're correct! This is definitely a difficult problem with many nuances. > This can be mitigated by enqueuing work in batches. > Workers also hold the lock for much longer, adding more contention on the FIFO. Fortunately, "true-FIFO" is the worst-case scenario. If you have a "Pseudo-FIFO", or "First-in USUALLY first out, but not guaranteed", you have a huge amount of flexibility with regards to avoiding contention. The "classic" pseudo-FIFO algorithm is 1x thread-local true-FIFO per thread, with work-stealing taking from the LIFO-side from remote threads. For example, Thread#1 push_back and pop_front on FIFO#1, which eventually runs out of work. Thread#1 now needs to grab work from another thread. Thread#1 chooses to worksteal from say... FIFO#23. Thread#23 is still reading from pop_front side, but Thread#1 can pop_back concurrently without any contention (as long as pop_front and pop_back operate on separate cache lines). The problem here is that Thread#1 just caused FIFO#23's data to look kinda-sorta like a stack, albeit temporarily. So you've lost the first-in-first-out guarantee. Fortunately, this isn't a major problem in many applications. (Ex: a Depth-first search becomes Depth-first when thread-local, but Breadth-first when load-balancing across cores. This is extremely good behavior in practice) > If you're going to do that, you're usually better off just making the work items bigger on the producer side. In my experience, that isn't always possible. A large number of problems are recursively defined, and splitting them up into tiny pieces is the most natural way of representing problems. Take the case of parallel tree search ("mostly" depth-first search with the pseduo-FIFO defined above). Its non-obvious what the size of any node actually is! There's basically no way to predict the size of an a work-item (and we are thus left with the workEstimate(X){ return 1; } style estimate). Other tasks (ex: Matrix Multiplication), allow for very easy tuning of work-item sizes. It all comes down to your specific application.

dragontamer 7y ago

Yes, you're correct! This is definitely a difficult problem with many nuances. > This can be mitigated by enqueuing work in batches. > Workers also hold the lock for much longer, adding more contention on the FIFO. Fortunately, "true-FIFO" is the worst-case scenario. If you have a "Pseudo-FIFO", or "First-in USUALLY first out, but not guaranteed", you have a huge amount of flexibility with regards to avoiding contention. The "classic" pseudo-FIFO algorithm is 1x thread-local true-FIFO per thread, with work-stealing taking from the LIFO-side from remote threads. For example, Thread#1 push_back and pop_front on FIFO#1, which eventually runs out of work. Thread#1 now needs to grab work from another thread. Thread#1 chooses to worksteal from say... FIFO#23. Thread#23 is still reading from pop_front side, but Thread#1 can pop_back concurrently without any contention (as long as pop_front and pop_back operate on separate cache lines). The problem here is that Thread#1 just caused FIFO#23's data to look kinda-sorta like a stack, albeit temporarily. So you've lost the first-in-first-out guarantee. Fortunately, this isn't a major problem in many applications. (Ex: a Depth-first search becomes Depth-first when thread-local, but Breadth-first when load-balancing across cores. This is extremely good behavior in practice) > If you're going to do that, you're usually better off just making the work items bigger on the producer side. In my experience, that isn't always possible. A large number of problems are recursively defined, and splitting them up into tiny pieces is the most natural way of representing problems. Take the case of parallel tree search ("mostly" depth-first search with the pseduo-FIFO defined above). Its non-obvious what the size of any node actually is! There's basically no way to predict the size of an a work-item (and we are thus left with the workEstimate(X){ return 1; } style estimate). Other tasks (ex: Matrix Multiplication), allow for very easy tuning of work-item sizes. It all comes down to your specific application.