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