Efficient Work Stealing for Portability of Nested Parallelism and Composability of Multithreaded Program
Adnan Adnan, Zainuddin Zahir, Wardi Wardi · Hasanuddin University Repository · 2013
We present performance evaluations of parallel-for loop with work stealing technique. The parallel-for by work stealing transforms the parallel-loop into a form of binary tree by making use of method of divide-and-conquer. Iterations are distributed in the leaves proce- dures of the binary tree, and the parallel executions are performed by stealing subtrees from the bottom of the tree. The work stealing and divide-and-conquer are used to address the portability prob- lem in nested parallelism and composability. By work stealing and divide-and-conquer techniques, fine-grained parallel-for can be im- plemented without contributing large work overhead. Low work overhead is important as the number of processor could be less than expected. Low overhead and fine-grained of work stealing sched- uler makes highly parallel processor cores are able to scale the per- formance. In addition, the approach used in this work makes effi- cient nested parallelism is possible. Because of a low overhead, we show that the work stealing and divide-and-conquer deliver good scalability in nested parallel Sparse LU factorization.