000186071 001__ 186071
000186071 005__ 20190316235626.0
000186071 037__ $$aREP_WORK
000186071 245__ $$aAchieving Efficient Work-Stealing for Data-Parallel Collections
000186071 269__ $$a2013
000186071 260__ $$c2013
000186071 300__ $$a12
000186071 336__ $$aReports
000186071 520__ $$aIn modern programming high-level data-structures are an important foundation for most applications. With the rise of the multi-core era, there is a growing trend of supporting data-parallel collection operations in general purpose programming languages and platforms. To facilitate object-oriented reuse these operations are highly parametric, incurring abstraction performance penalties. Furthermore, data-parallel operations must scale when used in problems with irregular workloads. Work-stealing is a proven load-balancing technique when it comes to irregular workloads, but general purpose work-stealing also suffers from abstraction penalties. In this paper we present a generic design of a data-parallel collections framework based on work-stealing for shared-memory architectures. We show how abstraction penalties can be overcome through callsite specialization of data-parallel operations instances. Moreover, we show how to make work-stealing fine-grained and efficient when specialized for particular data-structures. We experimentally validate the performance of different data-structures and data-parallel operations, achieving up to 60X better performance with abstraction penalties eliminated and 3X higher speedups by specializing work-stealing compared to existing approaches.
000186071 6531_ $$adata parallelism
000186071 6531_ $$aconc-lists
000186071 6531_ $$awork-stealing collections
000186071 6531_ $$acallsite specialization
000186071 6531_ $$aparallel hash-tables
000186071 6531_ $$aparallel arrays
000186071 6531_ $$aabstraction penalty
000186071 6531_ $$aworkload-driven
000186071 6531_ $$aload balancing
000186071 6531_ $$adomain-specific work-stealing
000186071 700__ $$0244134$$g191413$$aProkopec, Aleksandar
000186071 700__ $$0241835$$g126003$$aOdersky, Martin
000186071 8564_ $$uhttps://infoscience.epfl.ch/record/186071/files/workstealing-collections.pdf$$zn/a$$s333048$$yn/a
000186071 909C0 $$xU10409$$0252187$$pLAMP
000186071 909CO $$qGLOBAL_SET$$pIC$$ooai:infoscience.tind.io:186071$$preport
000186071 917Z8 $$x191413
000186071 917Z8 $$x191413
000186071 917Z8 $$x191413
000186071 937__ $$aEPFL-REPORT-186071
000186071 973__ $$aEPFL
000186071 980__ $$aREPORT