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]"
}