{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,11]],"date-time":"2025-09-11T05:09:48Z","timestamp":1757567388963,"version":"3.41.0"},"reference-count":27,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2021,6,30]],"date-time":"2021-06-30T00:00:00Z","timestamp":1625011200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Model. Perform. Eval. Comput. Syst."],"published-print":{"date-parts":[[2021,6,30]]},"abstract":"<jats:p>Randomized work stealing is used in distributed systems to increase performance and improve resource utilization. In this article, we consider randomized work stealing in a large system of homogeneous processors where parent jobs spawn child jobs that can feasibly be executed in parallel with the parent job. We analyse the performance of two work stealing strategies: one where only child jobs can be transferred across servers and the other where parent jobs are transferred. We define a mean-field model to derive the response time distribution in a large-scale system with Poisson arrivals and exponential parent and child job durations. We prove that the model has a unique fixed point that corresponds to the steady state of a structured Markov chain, allowing us to use matrix analytic methods to compute the unique fixed point. The accuracy of the mean-field model is validated using simulation. Using numerical examples, we illustrate the effect of different probe rates, load, and different child job size distributions on performance with respect to the two stealing strategies, individually, and compared to each other.<\/jats:p>","DOI":"10.1145\/3470887","type":"journal-article","created":{"date-parts":[[2021,9,4]],"date-time":"2021-09-04T04:07:45Z","timestamp":1630728465000},"page":"1-28","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Performance Analysis of Work Stealing in Large-scale Multithreaded Computing"],"prefix":"10.1145","volume":"6","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2133-9842","authenticated-orcid":false,"given":"Nikki","family":"Sonenberg","sequence":"first","affiliation":[{"name":"The Alan Turing Institute, United Kingdom"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Grzegorz","family":"Kielanski","sequence":"additional","affiliation":[{"name":"University of Antwerp, Antwerpen, Belgium"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Benny","family":"Van Houdt","sequence":"additional","affiliation":[{"name":"University of Antwerp, Antwerpen, Belgium"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,9,3]]},"reference":[{"volume-title":"Proceedings of the 2006 Workshop on Tools for Solving Structured Markov Chains. 14\u2013es.","author":"Bini D. A.","key":"e_1_2_1_1_1","unstructured":"D. A. Bini , B. Meini , S. Steffe , and B. Van Houdt . 2006. Structured markov chains solver: Software tools . In Proceedings of the 2006 Workshop on Tools for Solving Structured Markov Chains. 14\u2013es. D. A. Bini, B. Meini, S. Steffe, and B. Van Houdt. 2006. Structured markov chains solver: Software tools. In Proceedings of the 2006 Workshop on Tools for Solving Structured Markov Chains. 14\u2013es."},{"key":"e_1_2_1_2_1","doi-asserted-by":"crossref","unstructured":"M. Bladt and B. F. Nielsen. 2017. Matrix-exponential Distributions in Applied Probability. Vol. 81. Springer.  M. Bladt and B. F. Nielsen. 2017. Matrix-exponential Distributions in Applied Probability. Vol. 81. Springer.","DOI":"10.1007\/978-1-4939-7049-0"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1006\/jpdc.1996.0107"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/324133.324234"},{"key":"e_1_2_1_5_1","first-page":"247","article-title":"Asymptotic independence of queues under randomized load balancing. Queue","volume":"71","author":"Bramson M.","year":"2012","unstructured":"M. Bramson , Y. Lu , and B. Prabhakar . 2012 . Asymptotic independence of queues under randomized load balancing. Queue . Syst. 71 , 3 (2012), 247 \u2013 292 . M. Bramson, Y. Lu, and B. Prabhakar. 2012. Asymptotic independence of queues under randomized load balancing. Queue. Syst. 71, 3 (2012), 247\u2013292.","journal-title":"Syst."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-5316(86)90008-8"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3154491"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1811099.1811042"},{"volume-title":"Proceedings of the 2007 International Workshop on Parallel Symbolic Computation. 15\u201323","author":"Gautier T.","key":"e_1_2_1_9_1","unstructured":"T. Gautier , X. Besseron , and L. Pigeon . 2007. Kaapi: A thread scheduling runtime system for data flow computations on cluster of multi-processors . In Proceedings of the 2007 International Workshop on Parallel Symbolic Computation. 15\u201323 . T. Gautier, X. Besseron, and L. Pigeon. 2007. Kaapi: A thread scheduling runtime system for data flow computations on cluster of multi-processors. In Proceedings of the 2007 International Workshop on Parallel Symbolic Computation. 15\u201323."},{"volume-title":"Matrix Computations","author":"Golub G.","key":"e_1_2_1_10_1","unstructured":"G. Golub and C. Van Loan . 2012. Matrix Computations . Vol. 3 . JHU Press . G. Golub and C. Van Loan. 2012. Matrix Computations. Vol. 3. JHU Press."},{"key":"e_1_2_1_11_1","first-page":"3","article-title":"Open problems in queueing theory inspired by datacenter computing. Queue","volume":"97","author":"Harchol-Balter M.","year":"2021","unstructured":"M. Harchol-Balter . 2021 . Open problems in queueing theory inspired by datacenter computing. Queue . Syst. 97 , 1 (2021), 3 \u2013 37 . M. Harchol-Balter. 2021. Open problems in queueing theory inspired by datacenter computing. Queue. Syst. 97, 1 (2021), 3\u201337.","journal-title":"Syst."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1080\/15326349.2014.930669"},{"volume-title":"Approximation of Population Processes","author":"Kurtz T. G.","key":"e_1_2_1_13_1","unstructured":"T. G. Kurtz . 1981. Approximation of Population Processes . Vol. 36 . SIAM. T. G. Kurtz. 1981. Approximation of Population Processes. Vol. 36. SIAM."},{"key":"e_1_2_1_14_1","doi-asserted-by":"crossref","unstructured":"G. Latouche and V. Ramaswami. 1999. Introduction to Matrix Analytic Methods in Stochastic Modeling. Vol. 5. SIAM.  G. Latouche and V. Ramaswami. 1999. Introduction to Matrix Analytic Methods in Stochastic Modeling. Vol. 5. SIAM.","DOI":"10.1137\/1.9780898719734"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.peva.2017.04.004"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2013.2270445"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/0743-7315(90)90118-9"},{"volume-title":"Matrix-geometric Solutions in Stochastic Models: An Algorithmic Approach","author":"Neuts M. F.","key":"e_1_2_1_18_1","unstructured":"M. F. Neuts . 1981. Matrix-geometric Solutions in Stochastic Models: An Algorithmic Approach . John Hopkins University Press . M. F. Neuts. 1981. Matrix-geometric Solutions in Stochastic Models: An Algorithmic Approach. John Hopkins University Press."},{"key":"e_1_2_1_19_1","first-page":"203","article-title":"Sojourn time distributions in the queue defined by a general QBD process. Queue","volume":"53","author":"Ozawa T.","year":"2006","unstructured":"T. Ozawa . 2006 . Sojourn time distributions in the queue defined by a general QBD process. Queue . Syst. 53 , 4 (2006), 203 \u2013 211 . T. Ozawa. 2006. Sojourn time distributions in the queue defined by a general QBD process. Queue. Syst. 53, 4 (2006), 203\u2013211.","journal-title":"Syst."},{"volume-title":"Proceedings of the 2008 IEEE International Symposium on Parallel and Distributed Processing. IEEE, 1\u20138.","author":"Robison A.","key":"e_1_2_1_20_1","unstructured":"A. Robison , M. Voss , and A. Kukanov . 2008. Optimization via reflection on work stealing in TBB . In Proceedings of the 2008 IEEE International Symposium on Parallel and Distributed Processing. IEEE, 1\u20138. A. Robison, M. Voss, and A. Kukanov. 2008. Optimization via reflection on work stealing in TBB. In Proceedings of the 2008 IEEE International Symposium on Parallel and Distributed Processing. IEEE, 1\u20138."},{"key":"e_1_2_1_21_1","first-page":"21","article-title":"Large-scale parallel server system with multi-component jobs. Queue","volume":"98","author":"Shneer S.","year":"2021","unstructured":"S. Shneer and A. Stolyar . 2021 . Large-scale parallel server system with multi-component jobs. Queue . Syst. 98 , 1 (2021), 21 \u2013 48 . S. Shneer and A. Stolyar. 2021. Large-scale parallel server system with multi-component jobs. Queue. Syst. 98, 1 (2021), 21\u201348.","journal-title":"Syst."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.peva.2015.06.002"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/107972.107987"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3341617.3326137"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2019.2939040"},{"key":"e_1_2_1_26_1","volume-title":"Tasks versus threads: An alternative multiprocessing paradigm. Softw. Concepts Tools 17 (01","author":"Wirth N.","year":"1996","unstructured":"N. Wirth . 1996. Tasks versus threads: An alternative multiprocessing paradigm. Softw. Concepts Tools 17 (01 1996 ), 6\u201312. N. Wirth. 1996. Tasks versus threads: An alternative multiprocessing paradigm. Softw. Concepts Tools 17 (01 1996), 6\u201312."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10766-016-0484-8"}],"container-title":["ACM Transactions on Modeling and Performance Evaluation of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3470887","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3470887","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:18:55Z","timestamp":1750191535000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3470887"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,30]]},"references-count":27,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,6,30]]}},"alternative-id":["10.1145\/3470887"],"URL":"https:\/\/doi.org\/10.1145\/3470887","relation":{},"ISSN":["2376-3639","2376-3647"],"issn-type":[{"type":"print","value":"2376-3639"},{"type":"electronic","value":"2376-3647"}],"subject":[],"published":{"date-parts":[[2021,6,30]]},"assertion":[{"value":"2020-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-09-03","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}