Lei Wang
Pen-Chung Yew
ABSTRACT
Work-stealing is a key technique in many multi-threading programming languages to get good load balancing. The current work-stealing techniques have a high implementation overhead in some applications and require a large amount of memory space for data copying to assure correctness. They also cannot handle many application programs that have an unbalanced call tree or have no definitive working sets.
In this paper, we propose a new adaptive task creation strategy, called AdaptiveTC, which supports effective work-stealing schemes and also handles the above mentioned problems effectively. As shown in some experimental results, AdaptiveTC runs 2.71x faster than Cilk and 1.72x faster than Tascell for the 16-queen problem with 8 threads.
- OpenMP Application Program Interface. Version 3.0, 2008.Google Scholar
- E. Ayguade, A. Duran, J. Hoeflinger, F. Massaioli, and X. Teruel. An Experimental Evaluation of the New OpenMP Tasking Model. In the 20th International Workshop on Languages and Compilers for Parallel Computing, pages 63--77, 2007.Google Scholar
- Robert D. Blumofe and Charles E. Leiserson. Scheduling multithreaded computations by work stealing. Journal of the ACM, 46(5): 720C--748, 1999. Google ScholarDigital Library
- Robert D. Blumofe, Christopher F. Joerg, Bradley C. Kuszmaul, Charles E. Leiserson, Keith H. Randall, and Yuli Zhou. Cilk: an efficient multithreaded runtime system. In the Fifth ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP, pages 207--216, 1995. Google ScholarDigital Library
- Philippe Charles, Christian Grothoff, Vijay A. Saraswat, Christopher Donawa, Allan Kielstra, Kemal Ebcioglu, Christoph von Praun, and Vivek Sarkar. X10: an object-oriented approach to nonuniform cluster computing. In the Twentieth Annual ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications, OOPSLA, pages 519--538, 2005. Google ScholarDigital Library
- David Chase and Yossi Lev. Dynamic circular work-stealing d-eque. In the seventeenth Annual ACM Symposium on Parallelism in Algorithms and Architectures, SPAA, pages 21C--28, 2005. Google ScholarDigital Library
- Shimin Chen, Phillip B. Gibbons, Michael Kozuch, Vasileios Liaskovitis, Anastassia Ailamaki, Guy E. Blelloch, Babak Falsofi, Limor Fix, Nikos Hardavellas, Tod C. Mowry, and Chris Wilkerson. Scheduling Threads for Constructive Cache Sharing on CMPs. In the nineteenth annual ACM symposium on Parallel algorithms and architectures, SPAA, pages 105--115, 2007. Google ScholarDigital Library
- Guojing Cong, Sreedhar Kodali, Sriram Krishnamoorthy, Doug Lea, Vijay Saraswat, and Tong Wen. Solving large, irregular graph problems using adaptive work-stealing. In the 2008 37th International Conference on Parallel Processing, pages 536--545, 2008. Google ScholarDigital Library
- Alejandro Duran, Julita Corbaln, and Eduard Ayguad. Evaluation of Openmp Task Scheduling Strategies. In the 4th International Workshop on OpenMP, IWOMP, pages 100--110, 2008. Google ScholarDigital Library
- Matteo Frigo, Charles E. Leiserson, and Keith H. Randall. The implementation of the cilk-5 multithreaded language. In the ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI, pages 212C--223, 1998. Google ScholarDigital Library
- Supercomputing Technologies Group. Cilk 5.4.6 Reference Manual. Massachusetts Institute of Technology, Laboratory for Computer Science, Cambridge, Massachusetts, USA.Google Scholar
- Yi Guo, Jisheng Zhao, Vincent Cave, and Vivek Sarkar. Slaw: a scalable locality-aware adaptive work--stealing scheduler. In the 24th IEEE International Parallel and Distributed Processing Symposium, IPDPS, 2010. (To appear).Google ScholarCross Ref
- Tasuku Hiraishi, Masahiro Yasugi, Seiji Umatani, and Taiichi Yuasa. Backtracking-based Load Balancing. In the 14th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP, pages 55--64, 2009. Google ScholarDigital Library
- Hans Wolfgang Loidl, Kevin Hammond, Hans Wolfgang, and Loidl Kevin Hammond. On the Granularity of Divide-and-Conquer Parallelism. In Glasgow Workshop on Functional Programming, 1995. Google ScholarDigital Library
- Maged M. Michael, Martin T. Vechev, and Vijay A. Saraswat. Idempotent Work Stealing. In the 14th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP, pages 45--54, 2009. Google ScholarDigital Library
- Eric Mohr, David A. Kranz, and Jr Robert H. Halstead. Lazy task creation: A technique for increasing the granularity of parallel programs. IEEE Transactions on Parallel and Distributed Systems, 2(3):264C--280, 1991. Google ScholarDigital Library
Index Terms
- An adaptive task creation strategy for work-stealing scheduling
Recommendations
A work-stealing scheduler for X10's task parallelism with suspension
PPoPP '12: Proceedings of the 17th ACM SIGPLAN symposium on Principles and Practice of Parallel ProgrammingThe X10 programming language is intended to ease the programming of scalable concurrent and distributed applications. X10 augments a familiar imperative object-oriented programming model with constructs to support light-weight asynchronous tasks as well ...
An Adaptive Task Granularity Based Scheduling for Task-centric Parallelism
HPCC '14: Proceedings of the 2014 IEEE Intl Conf on High Performance Computing and Communications, 2014 IEEE 6th Intl Symp on Cyberspace Safety and Security, 2014 IEEE 11th Intl Conf on Embedded Software and Syst (HPCC,CSS,ICESS)Different from data parallel model, task parallel computing model is very important for complex analysis and data mining. Task granularity is a key factor that significantly affects the performance of task-centric parallel programs. However, current ...
Work-stealing without the baggage
OOPSLA '12: Proceedings of the ACM international conference on Object oriented programming systems languages and applicationsWork-stealing is a promising approach for effectively exploiting software parallelism on parallel hardware. A programmer who uses work-stealing explicitly identifies potential parallelism and the runtime then schedules work, keeping otherwise idle ...
Comments