Efficient Lock-Free Work-stealing Iterators for Data-Parallel Collections
Aleksandar Prokopec, Dmitry Petrashko and Martin Odersky
has low work per element
collection.map(x => fun(x))
Threads steal work from each other.
No cooperation from target thread needed, lock free.
A. Prokopec and M. Odersky. Near optimal work-stealing tree scheduler for highly irregular data-parallel workloads. LCPC 2013
Even more real life:
Types of overhead
- Data access overhead,
- Scheduling overhead,
- Invocation overhead. Won't be covered here.
Data access overhead
Data consumer abstracts over data source:
- iteration scheme(eg iterate over tree as if over indexed collection),
- redundant data copying,
How severe is it?
|a + b||box(unbox(a) + unbox(a))
Lets say we have a HashMap:
Most HashMaps by nature create irregular workload.
Efficient scheduling has to be data-structure aware.
- how to iterate;
- how to steal work.
Transparent for user.
Easy to implement for developer.
See paper :-).
Or ask questions.
Eliminating abstraction penalties is necessary to realistically assess the scheduling quality.
High abstraction penalties could entirely mask scheduling penalties.