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} } % =============================================================================== % Algorithms % =============================================================================== @article{michael2004hazard, title={Hazard pointers: Safe memory reclamation for lock-free objects}, author={Michael, Maged M}, journal={IEEE Transactions on Parallel and Distributed Systems}, volume={15}, number={6}, pages={491--504}, year={2004}, publisher={IEEE} } @inproceedings{brown2015reclaiming, title={Reclaiming memory for lock-free data structures: There has to be a better way}, author={Brown, Trevor Alexander}, booktitle={Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing}, pages={261--270}, year={2015} } % Trevor's relaxed FIFO list @inproceedings{alistarh2018relaxed, title={Relaxed schedulers can efficiently parallelize iterative algorithms}, author={Alistarh, Dan and Brown, Trevor and Kopinsky, Justin and Nadiradze, Giorgi}, booktitle={Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing}, pages={377--386}, year={2018} } % Scalable counters which only support is !0 @inproceedings{ellen2007snzi, title={SNZI: Scalable nonzero indicators}, author={Ellen, Faith and Lev, Yossi and Luchangco, Victor and Moir, Mark}, booktitle={Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing}, pages={13--22}, year={2007} } % =============================================================================== % Linux Man Pages % =============================================================================== @manual{open, key = "open", title = "open(2) Linux User's Manual", year = "2020", month = "February", } @manual{epoll, key = "epoll", title = "epoll(7) Linux User's Manual", year = "2019", month = "March", } @manual{select, key = "select", title = "select(7) Linux User's Manual", year = "2019", month = "March", } @misc{io_uring, title = {Efficient IO with io\_uring}, author = {Axboe, Jens}, year = "2019", month = "March", version = {0,4}, howpublished = {\url{https://kernel.dk/io_uring.pdf}} } @misc{libuv, key = "libuv", title = {libuv}, howpublished = {\url{https://github.com/libuv/libuv}} } % =============================================================================== % MISC % =============================================================================== @misc{nginx-design, key = "nginx", title={Inside {NGINX}: How We Designed for Performance \& Scale}, howpublished= {\href{https://www.nginx.com/blog/inside-nginx-how-we-designed-for-performance-scale} {https://\-www.nginx.com/\-blog/\-inside\--nginx\--how\--we\--designed\--for\--performance\--scale}}, } @article{schillings1996engineering, title={Be engineering insights: Benaphores}, author={Schillings, Benoit}, journal={Be Newsletters}, volume={1}, number={26}, year={1996} } @misc{wiki:thunderherd, author = "{Wikipedia contributors}", title = "Thundering herd problem --- {W}ikipedia{,} The Free Encyclopedia", year = "2020", howpublished = {\href{https://en.wikipedia.org/wiki/Thundering_herd_problem} {https://\-en.wikipedia.org/\-wiki/\-Thundering\_herd\_problem}},}, note = "[Online; accessed 14-April-2020]" } @misc{wiki:ubuntu-linux, author = "{Wikipedia contributors}", title = "Ubuntu version history : Table of versions --- {W}ikipedia{,} The Free Encyclopedia", year = "2020", howpublished = {\href{https://en.wikipedia.org/wiki/Ubuntu_version_history\#Table_of_versions} {https://\-en.wikipedia.org/\-wiki/\-Ubuntu\_version\_history\#Table\_of\_versions}}, note = "[Online; accessed 15-April-2020]" }