000189237 001__ 189237
000189237 005__ 20190316235717.0
000189237 037__ $$aREP_WORK
000189237 245__ $$aOn a Near Optimal Work-Stealing Tree Data-Parallel Scheduler for Highly Irregular Workloads
000189237 269__ $$a2013
000189237 260__ $$c2013
000189237 300__ $$a30
000189237 336__ $$aReports
000189237 520__ $$aWe present a work-stealing algorithm for runtime scheduling of dataparallel 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, workloaddriven 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.
000189237 6531_ $$awork-stealing tree
000189237 6531_ $$adata-parallelism
000189237 6531_ $$awork-stealing
000189237 6531_ $$ascheduling
000189237 6531_ $$alock-free
000189237 700__ $$0244134$$g191413$$aProkopec, Aleksandar
000189237 700__ $$aOdersky, Martin$$g126003$$0241835
000189237 8564_ $$uhttps://infoscience.epfl.ch/record/189237/files/scheduler2.pdf$$zPreprint$$s487307$$yPreprint
000189237 909C0 $$xU10409$$0252187$$pLAMP
000189237 909CO $$qGLOBAL_SET$$pIC$$ooai:infoscience.tind.io:189237$$preport
000189237 917Z8 $$x191413
000189237 937__ $$aEPFL-REPORT-189237
000189237 973__ $$aEPFL
000189237 980__ $$aREPORT