000203907 001__ 203907
000203907 005__ 20180913062905.0
000203907 0247_ $$2doi$$a10.1007/978-3-319-09967-5_4
000203907 022__ $$a0302-9743
000203907 020__ $$a978-3-319-09967-5
000203907 020__ $$a978-3-319-09966-8
000203907 02470 $$2ISI$$a000345593000012
000203907 037__ $$aCONF
000203907 245__ $$aNear Optimal Work-Stealing Tree Scheduler for Highly Irregular Data-Parallel Workloads
000203907 260__ $$bSpringer-Verlag Berlin$$c2014$$aBerlin
000203907 269__ $$a2014
000203907 300__ $$a32
000203907 336__ $$aConference Papers
000203907 490__ $$aLecture Notes in Computer Science
000203907 520__ $$aWe present a work-stealing algorithm for runtime scheduling of data-parallel operations in the context of shared-memory architectures on data sets with highly-irregular workloads that are not known a priori to the scheduler. This scheduler can parallelize loops and operations expressible with a parallel reduce or a parallel scan. The scheduler is based on the work-stealing tree data structure, which allows workers to decide on the work division in a lock-free, workload-driven manner and attempts to minimize the amount of communication between them. A significant effort is given to showing that the algorithm has the least possible amount of overhead. We provide an extensive experimental evaluation, comparing the advantages and shortcomings of different data-parallel schedulers in order to combine their strengths. We show specific workload distribution patterns appearing in practice for which different schedulers yield suboptimal speedup, explaining their drawbacks and demonstrating how the work-stealing tree scheduler overcomes them. We thus justify our design decisions experimentally, but also provide a theoretical background for our claims.
000203907 700__ $$0244134$$g191413$$aProkopec, Aleksandar
000203907 700__ $$0241835$$g126003$$aOdersky, Martin
000203907 7112_ $$dSEP 25-27, 2013$$cSan Jose, CA$$a26th International Workshop on Languages and Compilers for Parallel Computing (LCPC)
000203907 720_1 $$aCascaval, C$$eed.
000203907 720_1 $$aMontesinos, P$$eed.
000203907 773__ $$j8664$$tLanguages And Compilers For Parallel Computing, Lcpc 2013$$q55-86
000203907 909C0 $$xU10409$$0252187$$pLAMP
000203907 909CO $$pconf$$pIC$$ooai:infoscience.tind.io:203907
000203907 917Z8 $$x166927
000203907 937__ $$aEPFL-CONF-203907
000203907 973__ $$rREVIEWED$$sPUBLISHED$$aEPFL
000203907 980__ $$aCONF