Scheduling Multithreaded Computations by Work Stealing % =============================================================================== % Work stealing examples % =============================================================================== % Cilk [4], @article{frigo1998implementation, title={The implementation of the Cilk-5 multithreaded language}, author={Frigo, Matteo and Leiserson, Charles E and Randall, Keith H}, journal={ACM Sigplan Notices}, volume={33}, number={5}, pages={212--223}, year={1998}, publisher={ACM} } % Cilk-NOW @inproceedings{blumofe1997adaptive, title={Adaptive and reliable parallel computing on networks of workstations}, author={Blumofe, Robert D and Lisiecki, Philip A and others}, booktitle={USENIX 1997 Annual Technical Conference on UNIX and Advanced Computing Systems}, pages={133--147}, year={1997} } % Intel Threading Building Blocks (TBB) @article{intelTBB, title={Intel R Threading Building Blocks Documentation. Sept. 2013}, author={Intel, R}, journal={URL: https://www.threadingbuildingblocks.org/docs/help/index.htm} } % Java's Fork-join Framework @inproceedings{lea2000java, title={A Java fork/join framework}, author={Lea, Doug}, booktitle={Proceedings of the ACM 2000 conference on Java Grande}, pages={36--43}, year={2000}, organization={ACM} } % Microsoft Task Parallel Library @article{leijen2009design, title={The design of a task parallel library}, author={Leijen, Daan and Schulte, Wolfram and Burckhardt, Sebastian}, journal={Acm Sigplan Notices}, volume={44}, number={10}, pages={227--242}, year={2009}, publisher={ACM} } % StackThreads/MP @book{taura1999stackthreads, title={Stackthreads/mp: integrating futures into calling standards}, author={Taura, Kenjiro and Tabata, Kunio and Yonezawa, Akinori}, volume={34}, number={8}, year={1999}, publisher={ACM} } @article{feldmann1993game, title={Game tree search on massively parallel systems}, author={Feldmann, Rainer and Mysliwietz, P and Monien, B}, journal={Advances in Computer Chess}, volume={7}, year={1993}, publisher={Citeseer} } @article{finkel1987dib, title={DIB—a distributed implementation of backtracking}, author={Finkel, Raphael and Manber, Udi}, journal={ACM Transactions on Programming Languages and Systems (TOPLAS)}, volume={9}, number={2}, pages={235--256}, year={1987}, publisher={ACM} } @phdthesis{halbherr1994mimd, title={MIMD-style parallel programming based on continuation-passing threads}, author={Halbherr, Michael Roland Sven}, year={1994}, school={ETH Zurich} } @phdthesis{kuszmaul1994synchronized, title={Synchronized MIMD computing}, author={Kuszmaul, Bradley Clair}, year={1994}, school={Massachusetts Institute of Technology} } @article{mohr1991lazy, title={Lazy task creation: A technique for increasing the granularity of parallel programs}, author={Mohr, Eric and Kranz, David A and Halstead, Robert H}, journal={IEEE transactions on Parallel and Distributed Systems}, volume={2}, number={3}, pages={264--280}, year={1991}, publisher={IEEE} } @article{vandevoorde1988workcrews, title={WorkCrews: An abstraction for controlling parallelism}, author={Vandevoorde, Mark T and Roberts, Eric S}, journal={International Journal of Parallel Programming}, volume={17}, number={4}, pages={347--366}, year={1988}, publisher={Springer} } % =============================================================================== % Work stealing examples % =============================================================================== %---------- % discussion about best case and worst case for full computation % cited by 1720 @article{blumofe1999scheduling, title={Scheduling multithreaded computations by work stealing}, author={Blumofe, Robert D and Leiserson, Charles E}, journal={Journal of the ACM (JACM)}, volume={46}, number={5}, pages={720--748}, year={1999}, publisher={ACM} } %---------- % executing process trees in parallel % mostly used with lazy evaluation and dependency graphs % cited by 267 % cited by blumofe1999scheduling as first 'work-stealing idea' @inproceedings{burton1981executing, title={Executing functional programs on a virtual tree of processors}, author={Burton, F Warren and Sleep, M Ronan}, booktitle={Proceedings of the 1981 conference on Functional programming languages and computer architecture}, pages={187--194}, year={1981}, organization={ACM} } %---------- % work-stealing used for multilisp. % "unfair scheduling policy" % cited by 285 % cited by blumofe1999scheduling as first 'work-stealing idea' implementation @inproceedings{halstead1984implementation, title={Implementation of Multilisp: Lisp on a multiprocessor}, author={Halstead Jr, Robert H}, booktitle={Proceedings of the 1984 ACM Symposium on LISP and functional programming}, pages={9--17}, year={1984}, organization={ACM} } % =============================================================================== % HPC schedulers with bounds % =============================================================================== %---------- % discussion about bounds % cited by blumofe1999scheduling % mentionned as not practical % CAN'T find it @article{burton1996guaranteeing, title={Guaranteeing good memory bounds for parallel programs}, author={Burton, F Warren}, journal={IEEE Transactions on software engineering}, number={10}, pages={762--773}, year={1996}, publisher={IEEE} } %---------- % discussion about bounds % cited by blumofe1999scheduling % mentionned as not practical % - from abstract % talks about implicit concurrency % does not work online or for something other than HPC @inproceedings{blelloch1995provably, title={Provably efficient scheduling for languages with fine-grained parallelism}, author={Blelloch, Guy E and Gibbons, Phillip B and Matias, Yossi}, booktitle={Proceedings of the seventh annual ACM symposium on Parallel algorithms and architectures}, pages={1--12}, year={1995}, organization={ACM} } %---------- % discussion about bounds % cited by blumofe1999scheduling % mentionned as not practical % - from abstract % talks about bound on total time and space % no concept of fairness or latency among tasks @inproceedings{blelloch1997space, title={Space-efficient scheduling of parallelism with synchronization variables}, author={Blelloch, Guy E and Gibbons, Phillip B and Matias, Yossi and Narlikar, Girija J}, booktitle={Proceedings of the ninth annual ACM symposium on Parallel algorithms and architectures}, pages={12--23}, year={1997}, organization={ACM} }