% -------------------------------------------------- % Cforall @misc{cfa:frontpage, howpublished = {\href{https://cforall.uwaterloo.ca}{https://\-cforall.uwaterloo.ca}} } @article{cfa:typesystem, author = {Aaron Moss and Robert Schluntz and Peter A. Buhr}, title = {{\CFA} : Adding modern programming language features to {C}}, journal = {Softw. Pract. Exp.}, volume = {48}, number = {12}, pages = {2111--2146}, year = {2018}, url = {https://doi.org/10.1002/spe.2624}, doi = {10.1002/spe.2624}, timestamp = {Thu, 09 Apr 2020 17:14:14 +0200}, biburl = {https://dblp.org/rec/journals/spe/MossSB18.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} } % -------------------------------------------------- % old survey mostly about job scheduling % talks about the literature mostly centering on upfront/static scheduling with task graphs as inputs % already mentions multi-core @article{DBLP:journals/csur/Gonzalez77, author = {Mario J. Gonzalez Jr.}, title = {Deterministic Processor Scheduling}, journal = {{ACM} Comput. Surv.}, volume = {9}, number = {3}, pages = {173--204}, year = {1977}, url = {https://doi.org/10.1145/356698.356700}, doi = {10.1145/356698.356700}, timestamp = {Tue, 06 Nov 2018 12:50:48 +0100}, biburl = {https://dblp.org/rec/journals/csur/Gonzalez77.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} } % very short survey, highlights more interseting surveys as : % Casavant and Kuhl [1988], Chapin [1993], Shirazi et al. [1995], and Singhal and Shivaratri [1994] % still seems to mention static or partially static scheduling as a dominating trend @article{DBLP:journals/csur/Chapin96, author = {Steve J. Chapin}, title = {Distributed and Multiprocessor Scheduling}, journal = {{ACM} Comput. Surv.}, volume = {28}, number = {1}, pages = {233--235}, year = {1996}, url = {https://doi.org/10.1145/234313.234410}, doi = {10.1145/234313.234410}, timestamp = {Tue, 06 Nov 2018 12:50:49 +0100}, biburl = {https://dblp.org/rec/journals/csur/Chapin96.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} } % more comprehensive survey that discusses many algorithms % still exclusively static scheduling @article{DBLP:journals/csur/KwokA99, author = {Yu{-}Kwong Kwok and Ishfaq Ahmad}, title = {Static scheduling algorithms for allocating directed task graphs to multiprocessors}, journal = {{ACM} Comput. Surv.}, volume = {31}, number = {4}, pages = {406--471}, year = {1999}, url = {https://doi.org/10.1145/344588.344618}, doi = {10.1145/344588.344618}, timestamp = {Fri, 30 Nov 2018 12:48:46 +0100}, biburl = {https://dblp.org/rec/journals/csur/KwokA99.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} } % recent survey on kernel-thread scheduling % specifically focusing on schedulers that try to optimize to % reduce contention or reduce cache conflicts or improve some other ressource sharing metric @article{DBLP:journals/csur/ZhuravlevSBFP12, author = {Sergey Zhuravlev and Juan Carlos Saez and Sergey Blagodurov and Alexandra Fedorova and Manuel Prieto}, title = {Survey of scheduling techniques for addressing shared resources in multicore processors}, journal = {{ACM} Comput. Surv.}, volume = {45}, number = {1}, pages = {4:1--4:28}, year = {2012}, url = {https://doi.org/10.1145/2379776.2379780}, doi = {10.1145/2379776.2379780}, timestamp = {Tue, 06 Nov 2018 12:50:49 +0100}, biburl = {https://dblp.org/rec/journals/csur/ZhuravlevSBFP12.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} } % great survey on work-stealing % highlights many of the recent work both theoretical and not @article{DBLP:journals/ijpp/YangH18, author = {Jixiang Yang and Qingbi He}, title = {Scheduling Parallel Computations by Work Stealing: {A} Survey}, journal = {Int. J. Parallel Program.}, volume = {46}, number = {2}, pages = {173--197}, year = {2018}, url = {https://doi.org/10.1007/s10766-016-0484-8}, doi = {10.1007/s10766-016-0484-8}, timestamp = {Wed, 01 Apr 2020 08:50:06 +0200}, biburl = {https://dblp.org/rec/journals/ijpp/YangH18.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} } % -------------------------------------------------- % introduction of work stealing @inproceedings{DBLP:conf/fpca/BurtonS81, author = {F. Warren Burton and M. Ronan Sleep}, editor = {Arvind and Jack B. Dennis}, title = {Executing functional programs on a virtual tree of processors}, booktitle = {Proceedings of the 1981 conference on Functional programming languages and computer architecture, {FPCA} 1981, Wentworth, New Hampshire, USA, October 1981}, pages = {187--194}, publisher = {{ACM}}, year = {1981}, url = {https://doi.org/10.1145/800223.806778}, doi = {10.1145/800223.806778}, timestamp = {Tue, 06 Nov 2018 11:07:48 +0100}, biburl = {https://dblp.org/rec/conf/fpca/BurtonS81.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} } % introduction of randomized work stealing @inproceedings{DBLP:conf/focs/Blumofe94, author = {Robert D. Blumofe}, title = {Scheduling Multithreaded Computations by Work Stealing}, booktitle = {35th Annual Symposium on Foundations of Computer Science, Santa Fe, New Mexico, USA, 20-22 November 1994}, pages = {356--368}, publisher = {{IEEE} Computer Society}, year = {1994}, url = {https://doi.org/10.1109/SFCS.1994.365680}, doi = {10.1109/SFCS.1994.365680}, timestamp = {Wed, 16 Oct 2019 14:14:54 +0200}, biburl = {https://dblp.org/rec/conf/focs/Blumofe94.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} } % migration cost @inproceedings{DBLP:conf/sigmetrics/SquillanteN91, author = {Mark S. Squillante and Randolph D. Nelson}, editor = {Tom W. Keller}, title = {Analysis of Task Migration in Shared-Memory Multiprocessor Scheduling}, booktitle = {Proceedings of the 1991 {ACM} {SIGMETRICS} conference on Measurement and modeling of computer systems, San Diego, California, USA, May 21-24, 1991}, pages = {143--155}, publisher = {{ACM}}, year = {1991}, url = {https://doi.org/10.1145/107971.107987}, doi = {10.1145/107971.107987}, timestamp = {Sat, 07 Sep 2019 11:59:22 +0200}, biburl = {https://dblp.org/rec/conf/sigmetrics/SquillanteN91.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} } @article{DBLP:journals/pe/EagerLZ86, author = {Derek L. Eager and Edward D. Lazowska and John Zahorjan}, title = {A Comparison of Receiver-Initiated and Sender-Initiated Adaptive Load Sharing}, journal = {Perform. Evaluation}, volume = {6}, number = {1}, pages = {53--68}, year = {1986}, url = {https://doi.org/10.1016/0166-5316(86)90008-8}, doi = {10.1016/0166-5316(86)90008-8}, timestamp = {Sat, 22 Feb 2020 19:26:16 +0100}, biburl = {https://dblp.org/rec/journals/pe/EagerLZ86.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} } % affinity for work-stealing @article{DBLP:journals/tpds/SquillanteL93, author = {Mark S. Squillante and Edward D. Lazowska}, title = {Using Processor-Cache Affinity Information in Shared-Memory Multiprocessor Scheduling}, journal = {{IEEE} Trans. Parallel Distributed Syst.}, volume = {4}, number = {2}, pages = {131--143}, year = {1993}, url = {https://doi.org/10.1109/71.207589}, doi = {10.1109/71.207589}, timestamp = {Fri, 02 Oct 2020 14:40:30 +0200}, biburl = {https://dblp.org/rec/journals/tpds/SquillanteL93.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} } systems with affinity scheduling @inproceedings{squillante2001threshold, title={Threshold-based priority policies for parallel-server systems with affinity scheduling}, author={Squillante, Mark S and Xia, Cathy H and Yao, David D and Zhang, Li}, booktitle={Proceedings of the 2001 American Control Conference.(Cat. No. 01CH37148)}, volume={4}, pages={2992--2999}, year={2001}, organization={IEEE} } @article{DBLP:journals/mst/AcarBB02, author = {Umut A. Acar and Guy E. Blelloch and Robert D. Blumofe}, title = {The Data Locality of Work Stealing}, journal = {Theory Comput. Syst.}, volume = {35}, number = {3}, pages = {321--347}, year = {2002}, url = {https://doi.org/10.1007/s00224-002-1057-3}, doi = {10.1007/s00224-002-1057-3}, timestamp = {Sun, 28 May 2017 13:18:25 +0200}, biburl = {https://dblp.org/rec/journals/mst/AcarBB02.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} } @article{DBLP:journals/tcs/NarangS11, author = {Ankur Narang and Rudrapatna K. Shyamasundar}, title = {Performance driven distributed scheduling of parallel hybrid computations}, journal = {Theor. Comput. Sci.}, volume = {412}, number = {32}, pages = {4212--4225}, year = {2011}, url = {https://doi.org/10.1016/j.tcs.2010.11.044}, doi = {10.1016/j.tcs.2010.11.044}, timestamp = {Sun, 28 May 2017 13:20:06 +0200}, biburl = {https://dblp.org/rec/journals/tcs/NarangS11.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} } Optimization via reflection on work stealing in TBB @inproceedings{DBLP:conf/ipps/RobisonVK08, author = {Arch Robison and Michael Voss and Alexey Kukanov}, title = {Optimization via Reflection on Work Stealing in {TBB}}, booktitle = {22nd {IEEE} International Symposium on Parallel and Distributed Processing, {IPDPS} 2008, Miami, Florida USA, April 14-18, 2008}, pages = {1--8}, publisher = {{IEEE}}, year = {2008}, url = {https://doi.org/10.1109/IPDPS.2008.4536188}, doi = {10.1109/IPDPS.2008.4536188}, timestamp = {Wed, 16 Oct 2019 14:14:51 +0200}, biburl = {https://dblp.org/rec/conf/ipps/RobisonVK08.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} } @article{DBLP:journals/ipl/SuksompongLS16, author = {Warut Suksompong and Charles E. Leiserson and Tao B. Schardl}, title = {On the efficiency of localized work stealing}, journal = {Inf. Process. Lett.}, volume = {116}, number = {2}, pages = {100--106}, year = {2016}, url = {https://doi.org/10.1016/j.ipl.2015.10.002}, doi = {10.1016/j.ipl.2015.10.002}, timestamp = {Fri, 26 May 2017 22:54:40 +0200}, biburl = {https://dblp.org/rec/journals/ipl/SuksompongLS16.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} } %theory @article{DBLP:journals/jpdc/MirchandaneyTS90, author = {Ravi Mirchandaney and Donald F. Towsley and John A. Stankovic}, title = {Adaptive Load Sharing in Heterogeneous Distributed Systems}, journal = {J. Parallel Distributed Comput.}, volume = {9}, number = {4}, pages = {331--346}, year = {1990}, url = {https://doi.org/10.1016/0743-7315(90)90118-9}, doi = {10.1016/0743-7315(90)90118-9}, timestamp = {Sat, 22 Feb 2020 19:36:31 +0100}, biburl = {https://dblp.org/rec/journals/jpdc/MirchandaneyTS90.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} } @article{DBLP:journals/mst/BenderR02, author = {Michael A. Bender and Michael O. Rabin}, title = {Online Scheduling of Parallel Programs on Heterogeneous Systems with Applications to Cilk}, journal = {Theory Comput. Syst.}, volume = {35}, number = {3}, pages = {289--304}, year = {2002}, url = {https://doi.org/10.1007/s00224-002-1055-5}, doi = {10.1007/s00224-002-1055-5}, timestamp = {Sun, 28 May 2017 13:18:24 +0200}, biburl = {https://dblp.org/rec/journals/mst/BenderR02.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} } @inproceedings{DBLP:conf/sigmetrics/GastG10, author = {Nicolas Gast and Bruno Gaujal}, editor = {Vishal Misra and Paul Barford and Mark S. Squillante}, title = {A mean field model of work stealing in large-scale systems}, booktitle = {{SIGMETRICS} 2010, Proceedings of the 2010 {ACM} {SIGMETRICS} International Conference on Measurement and Modeling of Computer Systems, New York, New York, USA, 14-18 June 2010}, pages = {13--24}, publisher = {{ACM}}, year = {2010}, url = {https://doi.org/10.1145/1811039.1811042}, doi = {10.1145/1811039.1811042}, timestamp = {Tue, 06 Nov 2018 11:07:18 +0100}, biburl = {https://dblp.org/rec/conf/sigmetrics/GastG10.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} } @article{DBLP:journals/jacm/BlellochGM99, author = {Guy E. Blelloch and Phillip B. Gibbons and Yossi Matias}, title = {Provably Efficient Scheduling for Languages with Fine-Grained Parallelism}, journal = {J. {ACM}}, volume = {46}, number = {2}, pages = {281--321}, year = {1999}, url = {https://doi.org/10.1145/301970.301974}, doi = {10.1145/301970.301974}, timestamp = {Tue, 06 Nov 2018 12:51:45 +0100}, biburl = {https://dblp.org/rec/journals/jacm/BlellochGM99.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} } @article{DBLP:journals/siamcomp/BerenbrinkFG03, author = {Petra Berenbrink and Tom Friedetzky and Leslie Ann Goldberg}, title = {The Natural Work-Stealing Algorithm is Stable}, journal = {{SIAM} J. Comput.}, volume = {32}, number = {5}, pages = {1260--1279}, year = {2003}, url = {https://doi.org/10.1137/S0097539701399551}, doi = {10.1137/S0097539701399551}, timestamp = {Sat, 27 May 2017 14:22:58 +0200}, biburl = {https://dblp.org/rec/journals/siamcomp/BerenbrinkFG03.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} } @article{DBLP:journals/mst/AroraBP01, author = {Nimar S. Arora and Robert D. Blumofe and C. Greg Plaxton}, title = {Thread Scheduling for Multiprogrammed Multiprocessors}, journal = {Theory Comput. Syst.}, volume = {34}, number = {2}, pages = {115--144}, year = {2001}, url = {https://doi.org/10.1007/s00224-001-0004-z}, doi = {10.1007/s00224-001-0004-z}, timestamp = {Sun, 28 May 2017 13:18:24 +0200}, biburl = {https://dblp.org/rec/journals/mst/AroraBP01.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} } @article{DBLP:journals/anor/TchiboukdjianGT13, author = {Marc Tchiboukdjian and Nicolas Gast and Denis Trystram}, title = {Decentralized list scheduling}, journal = {Ann. Oper. Res.}, volume = {207}, number = {1}, pages = {237--259}, year = {2013}, url = {https://doi.org/10.1007/s10479-012-1149-7}, doi = {10.1007/s10479-012-1149-7}, timestamp = {Thu, 13 Aug 2020 12:41:25 +0200}, biburl = {https://dblp.org/rec/journals/anor/TchiboukdjianGT13.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} } @inproceedings{DBLP:conf/isaac/TchiboukdjianGTRB10, author = {Marc Tchiboukdjian and Nicolas Gast and Denis Trystram and Jean{-}Louis Roch and Julien Bernard}, editor = {Otfried Cheong and Kyung{-}Yong Chwa and Kunsoo Park}, title = {A Tighter Analysis of Work Stealing}, booktitle = {Algorithms and Computation - 21st International Symposium, {ISAAC} 2010, Jeju Island, Korea, December 15-17, 2010, Proceedings, Part {II}}, series = {Lecture Notes in Computer Science}, volume = {6507}, pages = {291--302}, publisher = {Springer}, year = {2010}, url = {https://doi.org/10.1007/978-3-642-17514-5\_25}, doi = {10.1007/978-3-642-17514-5\_25}, timestamp = {Fri, 13 Dec 2019 13:08:09 +0100}, biburl = {https://dblp.org/rec/conf/isaac/TchiboukdjianGTRB10.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} } @inproceedings{DBLP:conf/ppopp/AgrawalLS10, author = {Kunal Agrawal and Charles E. Leiserson and Jim Sukha}, editor = {R. Govindarajan and David A. Padua and Mary W. Hall}, title = {Helper locks for fork-join parallel programming}, booktitle = {Proceedings of the 15th {ACM} {SIGPLAN} Symposium on Principles and Practice of Parallel Programming, {PPOPP} 2010, Bangalore, India, January 9-14, 2010}, pages = {245--256}, publisher = {{ACM}}, year = {2010}, url = {https://doi.org/10.1145/1693453.1693487}, doi = {10.1145/1693453.1693487}, timestamp = {Tue, 06 Nov 2018 16:57:27 +0100}, biburl = {https://dblp.org/rec/conf/ppopp/AgrawalLS10.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} } @inproceedings{DBLP:conf/spaa/AgrawalFLSSU14, author = {Kunal Agrawal and Jeremy T. Fineman and Kefu Lu and Brendan Sheridan and Jim Sukha and Robert Utterback}, editor = {Guy E. Blelloch and Peter Sanders}, title = {Provably good scheduling for parallel programs that use data structures through implicit batching}, booktitle = {26th {ACM} Symposium on Parallelism in Algorithms and Architectures, {SPAA} '14, Prague, Czech Republic - June 23 - 25, 2014}, pages = {84--95}, publisher = {{ACM}}, year = {2014}, url = {https://doi.org/10.1145/2612669.2612688}, doi = {10.1145/2612669.2612688}, timestamp = {Wed, 21 Nov 2018 11:18:43 +0100}, biburl = {https://dblp.org/rec/conf/spaa/AgrawalFLSSU14.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} } @inproceedings{DBLP:conf/ipps/ColeR13, author = {Richard Cole and Vijaya Ramachandran}, title = {Analysis of Randomized Work Stealing with False Sharing}, booktitle = {27th {IEEE} International Symposium on Parallel and Distributed Processing, {IPDPS} 2013, Cambridge, MA, USA, May 20-24, 2013}, pages = {985--998}, publisher = {{IEEE} Computer Society}, year = {2013}, url = {https://doi.org/10.1109/IPDPS.2013.86}, doi = {10.1109/IPDPS.2013.86}, timestamp = {Wed, 16 Oct 2019 14:14:51 +0200}, biburl = {https://dblp.org/rec/conf/ipps/ColeR13.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} } @inproceedings{Albers12, author = {Susanne Albers and Antonios Antoniadis}, title = {Race to Idle: New Algorithms for Speed Scaling with a Sleep State}, booktitle = {Proceedings of the 2012 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)}, doi = {10.1137/1.9781611973099.100}, URL = {https://epubs.siam.org/doi/abs/10.1137/1.9781611973099.100}, eprint = {https://epubs.siam.org/doi/pdf/10.1137/1.9781611973099.100}, year = 2012, month = jan, pages = {1266-1285}, } @inproceedings{atikoglu2012workload, title={Workload analysis of a large-scale key-value store}, author={Atikoglu, Berk and Xu, Yuehai and Frachtenberg, Eitan and Jiang, Song and Paleczny, Mike}, booktitle={Proceedings of the 12th ACM SIGMETRICS/PERFORMANCE joint international conference on Measurement and Modeling of Computer Systems}, pages={53--64}, year={2012} } @article{schillings1996engineering, title={Be engineering insights: Benaphores}, author={Schillings, Benoit}, journal={Be Newsletters}, volume={1}, number={26}, year={1996} } % 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} } @article{zhuravlev2012survey, title={Survey of energy-cognizant scheduling techniques}, author={Zhuravlev, Sergey and Saez, Juan Carlos and Blagodurov, Sergey and Fedorova, Alexandra and Prieto, Manuel}, journal={IEEE Transactions on Parallel and Distributed Systems}, volume={24}, number={7}, pages={1447--1464}, year={2012}, publisher={IEEE} } @article{vikranth2013topology, title={Topology aware task stealing for on-chip NUMA multi-core processors}, author={Vikranth, BRWACRR and Wankar, Rajeev and Rao, C Raghavendra}, journal={Procedia Computer Science}, volume={18}, pages={379--388}, year={2013}, publisher={Elsevier} } @inproceedings{min2011hierarchical, title={Hierarchical work stealing on manycore clusters}, author={Min, Seung-Jai and Iancu, Costin and Yelick, Katherine}, booktitle={Fifth Conference on Partitioned Global Address Space Programming Models (PGAS11)}, volume={625}, year={2011}, organization={Citeseer} } @article{ribic2014energy, title={Energy-efficient work-stealing language runtimes}, author={Ribic, Haris and Liu, Yu David}, journal={ACM SIGARCH Computer Architecture News}, volume={42}, number={1}, pages={513--528}, year={2014}, publisher={ACM New York, NY, USA} } @inproceedings{torng2016asymmetry, title={Asymmetry-aware work-stealing runtimes}, author={Torng, Christopher and Wang, Moyang and Batten, Christopher}, booktitle={2016 ACM/IEEE 43rd Annual International Symposium on Computer Architecture (ISCA)}, pages={40--52}, year={2016}, organization={IEEE} } % -------------------------------------------------- % ULE FreeBSD scheduler @inproceedings{DBLP:conf/bsdcon/Roberson03, author = {Jeff Roberson}, editor = {Gregory Neil Shapiro}, title = {{ULE:} {A} Modern Scheduler for FreeBSD}, booktitle = {Proceedings of BSDCon 2003, San Mateo, California, USA, September 8-12, 2003}, pages = {17--28}, publisher = {{USENIX}}, year = {2003}, url = {http://www.usenix.org/publications/library/proceedings/bsdcon03/tech/roberson.html}, timestamp = {Wed, 04 Jul 2018 13:06:34 +0200}, biburl = {https://dblp.org/rec/conf/bsdcon/Roberson03.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} } % -------------------------------------------------- % Martin's LibFibre @article{DBLP:journals/pomacs/KarstenB20, author = {Martin Karsten and Saman Barghi}, title = {User-level Threading: Have Your Cake and Eat It Too}, journal = {Proc. {ACM} Meas. Anal. Comput. Syst.}, volume = {4}, number = {1}, pages = {17:1--17:30}, year = {2020}, url = {https://doi.org/10.1145/3379483}, doi = {10.1145/3379483}, timestamp = {Thu, 09 Jul 2020 22:58:54 +0200}, biburl = {https://dblp.org/rec/journals/pomacs/KarstenB20.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} } % -------------------------------------------------- % Linux CFS @inproceedings{DBLP:conf/eurosys/LoziLFGQF16, author = {Jean{-}Pierre Lozi and Baptiste Lepers and Justin R. Funston and Fabien Gaud and Vivien Qu{\'{e}}ma and Alexandra Fedorova}, editor = {Cristian Cadar and Peter R. Pietzuch and Kimberly Keeton and Rodrigo Rodrigues}, title = {The Linux scheduler: a decade of wasted cores}, booktitle = {Proceedings of the Eleventh European Conference on Computer Systems, EuroSys 2016, London, United Kingdom, April 18-21, 2016}, pages = {1:1--1:16}, publisher = {{ACM}}, year = {2016}, url = {https://doi.org/10.1145/2901318.2901326}, doi = {10.1145/2901318.2901326}, timestamp = {Tue, 06 Nov 2018 16:58:31 +0100}, biburl = {https://dblp.org/rec/conf/eurosys/LoziLFGQF16.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} } @misc{MAN:linux/cfs, title = {{CFS} Scheduler - The Linux Kernel documentation}, howpublished = {\href{https://www.kernel.org/doc/html/latest/scheduler/sched-design-CFS.html}{https://\-www.kernel.org/\-doc/\-html/\-latest/\-scheduler/\-sched-design-CFS.html}} } @misc{MAN:linux/cfs2, title = {{CFS}: Completely fair process scheduling in Linux}, author = {Marty Kalin}, year = {2019}, month = {February}, howpublished = {\href{https://opensource.com/article/19/2/fair-scheduling-linux}{https://\-opensource.com/\-article/\-19/2\-/\-fair-scheduling-linux}} } @article{MAN:linux/cfs/pelt, title={Per-entity load tracking}, author={Corbet, Jonathan}, journal={LWN article, available at: {\href{https://lwn.net/Articles/531853}{https://\-lwn.net/\-Articles/\-531853}}}, year={2013} } @misc{MAN:linux/cfs/balancing, title={Reworking {CFS} load balancing}, journal={LWN article}, year={2019}, howpublished = {\href{https://lwn.net/Articles/793427}{https://\-lwn.net/\-Articles/\-793427}}, } @manual{MAN:linux/sched, title = {SCHED(7) - Linux Programmer's Manual}, url = {https://man7.org/linux/man-pages/man7/sched.7.html}, year = {2019}, month = {august} } @manual{MAN:bsd/kqueue, title = {KQUEUE(2) - FreeBSD System Calls Manual}, url = {https://www.freebsd.org/cgi/man.cgi?query=kqueue}, year = {2020}, month = {may} } % Apple's MAC OS X @manual{MAN:apple/scheduler, title = {Mach Scheduling and Thread Interfaces - Kernel Programming Guide}, organization = {Apple Inc.}, note = {\href{https://developer.apple.com/library/archive/documentation/Darwin/Conceptual/KernelProgramming/scheduler/scheduler.html}{https://\-developer.apple.com/\-library/archive/\-documentation/\-Darwin/\-Conceptual/\-KernelProgramming/\-scheduler/\-scheduler.html}} } @book{MAN:inteldev, key = {Intel 64 and IA-32 Architectures Software Developer’s Manual}, title = {Intel® 64 and IA-32 Architectures Software Developer’s Manual}, publisher = {Intel{\textregistered}}, year = {2016}, volume = {3B: System Programming Guide, Part 2}, url = {\href{https://www.intel.com/content/www/us/en/architecture-and-technology/64-ia-32-architectures-software-developer-vol-3b-part-2-manual.html}{https://\-www.intel.com/\-content/\-www/\-us/\-en/\-architecture\--and\--technology/\-64\--ia\--32\--architectures\--software\--developer\--vol\--3b\--part\--2\--manual\-.html}}, } @misc{MemcachedThreading, author = {Oracle}, title = {MySQL 5.6 Reference Manual Including MySQL NDB Cluster 7.3-7.4 Reference Guide}, howpublished = {\href{https://docs.oracle.com/cd/E17952_01/mysql-5.6-en/ha-memcached-using-threads.html}{https://docs.oracle.com/\-cd/E17952\_01/\-mysql-5.6-en/\-ha-memcached-using-threads.html}}, note = "[Online; accessed 5-August-2022]" } Windows's Scheduler @inbook{MAN:windows/scheduler, author = {Kate Chase and Mark E. Russinovich}, title = {Windows Internals}, chapter = {Processes, Threads, and Jobs in the Windows Operating System}, edition = {5th Edition}, publisher = {Microsoft Press}, year = {2009}, month = {June}, series = {Developer Reference}, howpublished = {\href{https://www.microsoftpressstore.com/articles/article.aspx?p=2233328&seqNum=7#:~:text=Overview\%20of\%20Windows\%20Scheduling,a\%20phenomenon\%20called\%20processor\%20affinity}{https://\-www.microsoftpressstore.com/\-articles/\-article.aspx?p=2233328&seqNum=7#:~:text=Overview\%20of\%20Windows\%20Scheduling,a\%20phenomenon\%20called\%20processor\%20affinity}} } @misc{GITHUB:go, title = {GitHub - The Go Programming Language}, author = {The Go Programming Language}, howpublished = {\href{https://github.com/golang/go}{https://\-github.com/\-golang/\-go}}, version = {Change-Id: If07f40b1d73b8f276ee28ffb8b7214175e56c24d} } @inproceedings{YTUBE:go, author = {Dmitry Vyukov}, title = {Go scheduler: Implementing language with lightweight concurrency}, year = {2019}, booktitle = {Hydra}, howpublished = {\href{https://www.youtube.com/watch?v=-K11rY57K7k&ab_channel=Hydra}{https://\-www.youtube.com/\-watch?v=-K11rY57K7k&ab_channel=Hydra}} } @inproceedings{:erlang, author = {Kenneth Lundin, Ericsson AB}, title = {Inside the Erlang VM}, year = {2008}, booktitle = {Erlang User Conference}, howpublished = {\href{http://www.erlang.se/euc/08/euc_smp.pdf}{http://\-www.erlang.se/\-euc/\-08/\-euc_smp.pdf}} } @manual{MAN:tbb/scheduler, title = {Scheduling Algorithm - Intel{\textregistered} Threading Building Blocks Developer Reference}, organization = {Intel{\textregistered}}, howpublished = {\href{https://www.threadingbuildingblocks.org/docs/help/reference/task_scheduler/scheduling_algorithm.html}{https://\-www.threadingbuildingblocks.org/\-docs/\-help/\-reference/\-task\_scheduler/\-scheduling\_algorithm.html}} } @manual{MAN:quasar, title = {Quasar Core - Quasar User Manual}, organization = {Parallel Universe}, howpublished = {\href{https://docs.paralleluniverse.co/quasar}{https://\-docs.paralleluniverse.co/\-quasar}} } @misc{MAN:project-loom, howpublished = {\href{https://www.baeldung.com/openjdk-project-loom}{https://\-www.baeldung.com/\-openjdk-project-loom}} } @misc{MAN:kotlin, howpublished = {\href{https://kotlinlang.org/docs/multiplatform-mobile-concurrency-and-coroutines.html}{https://\-kotlinlang.org\-/docs\-/multiplatform\--mobile\--concurrency\--and\--coroutines.html}} } @misc{MAN:java/fork-join, howpublished = {\href{https://www.baeldung.com/java-fork-join}{https://\-www.baeldung.com/\-java-fork-join}} } @misc{apache, key = {Apache Software Foundation}, title = {{T}he {A}pache Web Server}, howpublished = {\href{http://httpd.apache.org}{http://\-httpd.apache.org}}, note = "[Online; accessed 6-June-2022]" } @misc{memcached, key = {Brad Fitzpatrick}, title = {{M}emcached}, year = {2003}, howpublished = {\href{http://httpd.apache.org}{http://\-httpd.apache.org}}, note = "[Online; accessed 6-June-2022]" } @misc{libuv, author = {libuv team}, title = {libuv: Asynchronous I/O made simple.}, howpublished = {\href{https://libuv.org/}{https://\-libuv.org/}}, note = "[Online; accessed 5-August-2022]" } @misc{SeriallyReusable, author = {IBM}, title = {Serially reusable programs}, month = mar, howpublished= {\href{https://www.ibm.com/docs/en/ztpf/1.1.0.15?topic=structures-serially-reusable-programs}{https://www.ibm.com/\-docs/\-en/\-ztpf/\-1.1.0.15?\-topic=structures\--serially\--reusable-programs}}, year = 2021, } @misc{GITHUB:mutilate, title = {Mutilate: high-performance memcached load generator }, author = { Jacob Leverich }, howpublished = {\href{https://github.com/leverich/mutilate}{https://\-github.com/\-leverich/\-mutilate}}, version = {Change-Id: d65c6ef7c2f78ae05a9db3e37d7f6ddff1c0af64} } @misc{GITHUB:SchedulingBenchmarks, title = {Scheduling Benchmarks}, author = {Thierry Delisle}, howpublished = {\href{https://github.com/cforall/SchedulingBenchmarks_PhD22}{https://\-github.com/\-cforall/\-Scheduling\-Benchmarks\_\-PhD22}}, } % -------------------------------------------------- % Tech documents @techreport{rfc:tcp, title={Transmission control protocol}, author={Postel, Jon}, year={1981} } @manual{win:priority, key = {TaskSettings Priority}, title = {TaskSettings.Priority property}, year = "2020", month = "September", howpublished = {\href{https://docs.microsoft.com/en-us/windows/win32/taskschd/tasksettings-priority}{https://\-docs.microsoft.com/\-en-us/\-windows/\-win32/\-taskschd/\-tasksettings-priority}}, note = "[Online; accessed 5-August-2022]" } @manual{win:overlap, key = {Synchronous and Asynchronous IO}, title = {Synchronous and Asynchronous I\/O}, year = "2021", month = "March", howpublished = {\href{https://docs.microsoft.com/en-us/windows/win32/fileio/synchronous-and-asynchronous-i-o}{https://\-docs.microsoft.com/\-en-us/\-windows/\-win32/\-fileio/\-synchronous-and-asynchronous-i-o}}, note = "[Online; accessed 5-August-2022]" } @book{russinovich2009windows, title={Windows Internals}, author={Russinovich, M.E. and Solomon, D.A. and Ionescu, A.}, isbn={9780735625303}, lccn={2009927697}, series={Developer Reference Series}, url={https://books.google.ca/books?id=SfglSQAACAAJ}, year={2009}, publisher={Microsoft Press} } @manual{apple:gcd, key = {Grand Central Dispatch}, title = {Grand Central Dispatch}, year = "2022", author = {Apple Inc.}, howpublished = {https://developer.apple.com/documentation/DISPATCH}, note = "[Online; accessed 5-August-2022]" } @techreport{apple:gcd2, key = {Grand Central Dispatch}, title = {Grand Central Dispatch, A better way to do multicore.}, year = "2009", month = "August", author = {Apple Inc.}, howpublished = {\href{http://web.archive.org/web/20090920043909/http://images.apple.com/macosx/technology/docs/GrandCentral_TB_brief_20090903.pdf}{http://web.archive.org/web/20090920043909/http://\-images.apple.com/\-macosx/\-technology/\-docs/\-GrandCentral\_TB\_brief\_20090903.pdf}}, note = "[Online; accessed 5-August-2022]" } % -------------------------------------------------- % Man Pages @manual{MAN:open, key = "open", title = "open(2) Linux User's Manual", year = "2020", month = "February", } @manual{MAN:accept, key = "accept", title = "accept(2) Linux User's Manual", year = "2019", month = "March", } @manual{MAN:select, key = "select", title = "select(2) Linux User's Manual", year = "2019", month = "March", } @manual{MAN:poll, key = "poll", title = "poll(2) Linux User's Manual", year = "2019", month = "July", } @manual{MAN:epoll, key = "epoll", title = "epoll(7) Linux User's Manual", year = "2019", month = "March", } @manual{MAN:sendfile, key = "sendfile", title = "sendfile(2) Linux User's Manual", year = "2017", month = "September", } @manual{MAN:splice, key = "splice", title = "splice(2) Linux User's Manual", year = "2019", month = "May", } @manual{MAN:eventfd, key = "eventfd", title = "eventfd(2) Linux User's Manual", year = "2019", month = "March", } @manual{MAN:aio, key = "aio", title = "aio(7) Linux User's Manual", year = "2019", month = "March", } @manual{MAN:bash, title = {Bash Reference Manual}, author = {Chet Ramey and Brian Fox}, year = "2020", month = "December", version = {5,1}, howpublished = {\href{https://www.gnu.org/software/bash/manual/bash.pdf}{https://\-www.gnu.org/\-software/\-bash/\-manual/\-bash.pdf}} } @misc{MAN:io_uring, title = {Efficient IO with io\_uring}, author = {Axboe, Jens}, year = "2019", month = "March", version = {0,4}, howpublished = {\href{https://kernel.dk/io_uring.pdf}{https://\-kernel.dk/\-io\_uring.pdf}} } % -------------------------------------------------- % Wikipedia Entries @misc{wiki:taskparallel, author = "{Wikipedia contributors}", title = "Control theory --- {W}ikipedia{,} The Free Encyclopedia", year = "2020", howpublished = {\href{https://en.wikipedia.org/wiki/Task_parallelism}{https://\-en.wikipedia.org/\-wiki/\-Task\_parallelism}}, note = "[Online; accessed 22-October-2020]" } @misc{wiki:controltheory, author = "{Wikipedia contributors}", title = "Task parallelism --- {W}ikipedia{,} The Free Encyclopedia", year = "2020", howpublished = "\href{https://en.wikipedia.org/wiki/Control_theory}{https://\-en.wikipedia.org/\-wiki/\-Control\_theory}", note = "[Online; accessed 22-October-2020]" } @misc{wiki:implicitpar, author = "{Wikipedia contributors}", title = "Implicit parallelism --- {W}ikipedia{,} The Free Encyclopedia", year = "2020", howpublished = "\href{https://en.wikipedia.org/wiki/Implicit_parallelism}{https://\-en.wikipedia.org/\-wiki/\-Implicit\_parallelism}", note = "[Online; accessed 23-October-2020]" } @misc{wiki:explicitpar, author = "{Wikipedia contributors}", title = "Explicit parallelism --- {W}ikipedia{,} The Free Encyclopedia", year = "2017", howpublished = "\href{https://en.wikipedia.org/wiki/Explicit_parallelism}{https://\-en.wikipedia.org/\-wiki/\-Explicit\_parallelism}", note = "[Online; accessed 23-October-2020]" } @misc{wiki:lcg, author = "{Wikipedia contributors}", title = "Linear congruential generator --- {W}ikipedia{,} The Free Encyclopedia", year = "2020", howpublished = "\href{https://en.wikipedia.org/wiki/Linear_congruential_generator}{https://en.wikipedia.org/wiki/Linear\_congruential\_generator}", note = "[Online; accessed 2-January-2021]" } @misc{wiki:future, author = "{Wikipedia contributors}", title = "Futures and promises --- {W}ikipedia{,} The Free Encyclopedia", year = "2020", howpublished = "\href{https://en.wikipedia.org/wiki/Futures_and_promises}{https://\-en.wikipedia.org/\-wiki/Futures\_and\_promises}", note = "[Online; accessed 9-February-2021]" } @misc{wiki:rcu, author = "{Wikipedia contributors}", title = "Read-copy-update --- {W}ikipedia{,} The Free Encyclopedia", year = "2022", howpublished = "\href{https://en.wikipedia.org/wiki/Linear_congruential_generator}{https://\-en.wikipedia.org/\-wiki/\-Linear\_congruential\_generator}", note = "[Online; accessed 12-April-2022]" } @misc{wiki:rwlock, author = "{Wikipedia contributors}", title = "Readers-writer lock --- {W}ikipedia{,} The Free Encyclopedia", year = "2021", howpublished = "\href{https://en.wikipedia.org/wiki/Readers-writer_lock}{https://\-en.wikipedia.org/\-wiki/\-Readers-writer\_lock}", note = "[Online; accessed 12-April-2022]" } @misc{wiki:binpak, author = "{Wikipedia contributors}", title = "Bin packing problem --- {W}ikipedia{,} The Free Encyclopedia", year = "2022", howpublished = "\href{https://en.wikipedia.org/wiki/Bin_packing_problem}{https://\-en.wikipedia.org/\-wiki/\-Bin\_packing\_problem}", note = "[Online; accessed 29-June-2022]" } @misc{wiki:ma, author = "{Wikipedia contributors}", title = "Bin packing problem --- {W}ikipedia{,} The Free Encyclopedia", year = "2022", howpublished = "\href{https://en.wikipedia.org/wiki/Moving_average#Exponential_moving_average}{https://\-en.wikipedia.org/\-wiki/\-Moving\_average\#Exponential\_moving\_average}", note = "[Online; accessed 5-August-2022]" } @misc{wiki:jni, author = "{Wikipedia contributors}", title = "Java Native Interface --- {W}ikipedia{,} The Free Encyclopedia", year = "2021", howpublished = "\href{https://en.wikipedia.org/wiki/Java_Native_Interface}{https://\-en.wikipedia.org/\-wiki/\-Java\_Native\_Interface}", note = "[Online; accessed 5-August-2022]" } @misc{wiki:zipf, author = "{Wikipedia contributors}", title = "Zipf's law --- {W}ikipedia{,} The Free Encyclopedia", year = "2021", howpublished = "\href{https://en.wikipedia.org/wiki/Zipf%27s_law}{https://\-en.wikipedia.org/\-wiki/\-Zipf\%27s\-\_law}", note = "[Online; accessed 5-August-2022]" } @misc{wiki:htm, author = "{Wikipedia contributors}", title = "Transactional memory --- {W}ikipedia{,} The Free Encyclopedia", year = "2022", howpublished = "\href{https://en.wikipedia.org/wiki/Zipf%27s_law}{https://\-en.wikipedia.org/\-wiki/\-Zipf\%27s\-\_law}", note = "[Online; accessed 7-September-2022]" } @misc{wiki:rdtsc, author = "{Wikipedia contributors}", title = "Time Stamp Counter --- {W}ikipedia{,} The Free Encyclopedia", year = "2022", howpublished = "\href{https://en.wikipedia.org/wiki/Time\_Stamp\_Counter}{https://\-en.wikipedia.org/\-wiki/\-Time\-\_Stamp\-\_Counter}", note = "[Online; accessed 14-November-2022]" } @misc{wiki:lockfree, author = "{Wikipedia contributors}", title = "Non-blocking algorithm --- {W}ikipedia{,} The Free Encyclopedia", year = "2022", howpublished = "\href{https://en.wikipedia.org/wiki/Non-blocking_algorithm}{https://en.wikipedia.org/\-wiki/Non\--blocking\-\_algorithm}", note = "[Online; accessed 22-November-2022]" } @misc{wiki:expected, author = "{Wikipedia contributors}", title = "Expected value --- {W}ikipedia{,} The Free Encyclopedia", year = "2022", howpublished = "\href{https://en.wikipedia.org/wiki/Expected_value}{https://en.wikipedia.org/\-wiki/\-Expected\-\_value}", note = "[Online; accessed 22-November-2022]" } @misc{wiki:softirq, author = "{Wikipedia contributors}", title = "Interrupt --- {W}ikipedia{,} The Free Encyclopedia", year = "2022", howpublished = "\href{https://en.wikipedia.org/wiki/Interrupt}{https://en.wikipedia.org/\-wiki/\-Interrupt}", note = "[Online; accessed 24-November-2022]" } @inproceedings{Pai99Flash, contributer = {pabuhr@watmsg}, author = {Vivek S. Pai and Peter Druschel and Willy Zwaenepoel}, title = {{F}lash: An efficient and portable {W}eb server}, booktitle = {Proceedings of the 1999 USENIX Annual Technical Conference}, organization= {USENIX Association}, address = {Monterey, California, U.S.A.}, month = jun, year = {1999}, } @inproceedings{Behren03, contributer = {pabuhr@watmsg}, author = {Rob von Behren and Jeremy Condit and Feng Zhou and George C. Necula and Eric Brewer}, title = {Capriccio: Scalable Threads for Internet Services}, booktitle = {Proceedings of the 19th ACM Symposium on Operating Systems Principles}, year = {2003}, pages = {268-281}, location = {Bolton Landing, NY, USA}, publisher = {ACM Press}, address = {New York, NY, USA}, } @article{Welsh01, contributer = {pabuhr@plg}, author = {Welsh, Matt and Culler, David and Brewer, Eric}, title = {{SEDA}: An Architecture for Well-conditioned, Scalable Internet Services}, journal = {SIGOPS Oper. Syst. Rev.}, volume = {35}, number = {5}, month = oct, year = {2001}, pages = {230--243}, numpages = {14}, publisher = {ACM}, address = {New York, NY, USA}, } @inproceedings{Harji12, keywords = {web server, architecture, multi-core}, contributer = {pabuhr@plg}, author = {Ashif S. Harji and Peter A. Buhr and Tim Brecht}, title = {Comparing High-Performance Multi-core Web-Server Architectures}, booktitle = {Proceedings of the 5th Annual International Systems and Storage Conference}, series = {SYSTOR '12}, publisher = {ACM}, address = {New York, NY, USA}, location = {Haifa, Israel}, month = jun, year = 2012, articleno = 1, pages = {1:1--1:12}, } @inproceedings{Barford98, title = {Generating Representative Web Workloads for Network and Server Performance Evaluation}, author = {Paul Barford and Mark Crovella}, booktitle = {Proc. of ACM SIGMETRICS 1998}, address = {Madison, Wis.}, year = {1998} } @article{httperf, author = {David Mosberger and Tai Jin}, title = {httperf Tool for Measuring Web Server Performance}, journal = {ACM SIGMETRICS}, volume = {26}, number = {3}, year = {1998}, optissn = {0163-5999}, pages = {31-37}, optdoi = {http://doi.acm.org/10.1145/306225.306235}, publisher = {ACM Press}, address = {New York, NY, USA}, } % -------------------------------------------------- % True Misc @misc{AIORant, author = "Linus Torvalds", title = "Re: [PATCH 09/13] aio: add support for async openat()", year = "2016", month = jan, howpublished = "\href{https://lwn.net/Articles/671657}{https://\-lwn.net/\-Articles/671657}", note = "[Online; accessed 6-June-2022]" } @misc{xkcd:dynamicentropy, author = "Randall Munroe", title = "2318: Dynamic Entropy", year = "2020", month = "June", howpublished = "\href{https://xkcd.com/2318/}{https://\-xkcd.com/\-2318/}", note = "[Online; accessed 10-June-2020]" } @misc{xkcd:cloud, author = "Randall Munroe", title = "908: The Cloud", year = "2011", month = "June", howpublished = "\href{https://xkcd.com/908/}{https://\-xkcd.com/\-908/}", note = "[Online; accessed 25-August-2022]" } @misc{go:safepoints, author = "The Go Programming Language", title = "src/runtime/preempt.go", howpublished = {\href{https://go.dev/src/runtime/preempt.go}}, note = "[Online; accessed 5-August-2022]" } @misc{go:cgo, author = "The Go Programming Language", title = "cgo", howpublished = {\href{https://pkg.go.dev/cmd/cgo}}, note = "[Online; accessed 5-August-2022]" } @article{reese2008nginx, title = {NGINX: the high-performance web server and reverse proxy}, author = {Reese, Will}, journal = {Linux Journal}, volume = {2008}, number = {173}, pages = {2}, year = {2008}, publisher = {Belltown Media} } @phdthesis{Harji10, author = {Ashif Harji}, title = {Performance Comparison of Uniprocessor and Multiprocessor Web Server Architectures}, school = {University of Waterloo}, year = 2010, month = feb, address = {Waterloo, Ontario, Canada, N2L 3G1}, note = {\textsf{http://uwspace.uwaterloo.ca/\-bitstream/\-10012/\-5040/\-1/\-Harji\_thesis.pdf}}, }