Q. Practical workloads for which work stealing outperforms work sharing?

classic Classic list List threaded Threaded
3 messages Options
Reply | Threaded
Open this post in threaded view
|

Q. Practical workloads for which work stealing outperforms work sharing?

Godmar Back
Hi,

what are practical workloads/example parallel implementations for which work stealing exhibits the highest performance advantages when compared to work sharing?

 - Godmar




_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Q. Practical workloads for which work stealing outperforms work sharing?

Stephane Maldini
Related/Unrelated:

Speaking of Streams (as in Reactor Streams/ Reactive Streams or even Rx Serializer) , my experience is that work stealing work greats for relatively 'low latency' merge operations where the consumer might submit some IO. In the case of Reactive Streams, its also useful to serialize requested demand upstream from N downstream threads.

If this takes too long, the stealing 'queue' might expand quickly and never give a chance for this thread to return, basically transforming your flow into a Shared workload where the first thread reaching out to the end will just dequeue further work.
If that is the case I'd envision switching back to shared workload, which often happens where IO work is related to database write for instance. I find the work steal less manageable as you might want to tune the pool.

Hope it helps the discussion, its a general concern so I thought I could give my 2c here.

On Thu, Feb 5, 2015 at 4:02 PM, Godmar Back <[hidden email]> wrote:
Hi,

what are practical workloads/example parallel implementations for which work stealing exhibits the highest performance advantages when compared to work sharing?

 - Godmar




_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest




--
Stephane Maldini | Solutions Architect, CSO EMEA | London | Pivotal


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Q. Practical workloads for which work stealing outperforms work sharing?

Godmar Back

Thanks for your reply.  I wasn't necessarily thinking of workloads where some tasks might block due to I/O - though as FJ frameworks are used for those, those are of course important. I'm thinking for now of purely CPU bound tasks.

My (admittedly somewhat naive) understanding is that work-stealing can beat work-sharing for two reasons:

a) by finding a shorter schedule overall. Here, a work-sharing scheduler would make a "wrong" assignment that later means the worker is idle and can't help. 
 
b) by working in a decentralized fashion, in a way that requires fewer - possibly contended -thread-to-thread interactions. My reading of Blumofe's paper is that that what they mean by 'thread-to-thread communication'. In this case, the performance gain would be directly related to the cost of these thread-to-thread synchronizations, and would depend on the granularity of the workload. Workloads of fine granularity, with many small tasks, would - conceivably - create high contention on the shared data structures of a work-sharing scheduler, whereas the common case synchronization overhead in the work-stealing implementation (pulling off the bottom in Blumofe's terminology) would be small as it does not require atomic operations (implemented using THE, for instance.) 

My question is what are applications in which a problem can be divided into tasks of a level of granularity such that this effect of a work-stealing scheduler is most pronounced. (After all, for coarse-grained tasks the drawback of having a shared lock (or whichever synchronization construct is used) would be less.

 - Godmar


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest