{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,29]],"date-time":"2026-05-29T10:01:59Z","timestamp":1780048919375,"version":"3.53.1"},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2024,1,19]],"date-time":"2024-01-19T00:00:00Z","timestamp":1705622400000},"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. Archit. Code Optim."],"published-print":{"date-parts":[[2024,3,31]]},"abstract":"<jats:p>Parallel libraries such as OpenMP distribute the iterations of parallel-for-loops among the threads, using a programmer-specified scheduling policy. While the existing scheduling policies perform reasonably well in the context of balanced workloads, in computations that involve highly imbalanced workloads it is extremely non-trivial to obtain an efficient distribution of work (even using non-static scheduling methods like dynamic and guided). In this paper, we present a scheme called COst aware Work Stealing (COWS) to efficiently extend the idea of work-stealing to OpenMP.<\/jats:p>\n          <jats:p>In contrast to the traditional work-stealing schedulers, COWS takes into consideration that (i)\u00a0not all iterations of a parallel-for-loops may take the same amount of time. (ii)\u00a0identifying a suitable victim for stealing is important for load-balancing, and (iii)\u00a0queues lead to significant overheads in traditional work-stealing and should be avoided. We present two variations of COWS: WSRI (a naive work-stealing scheme based on the number of remaining iterations) and WSRW (work-stealing scheme based on the amount of remaining workload). Since in irregular loops like those found in graph analytics it is not possible to statically compute the cost of the iterations of the parallel-for-loops, we use a combined compile-time + runtime approach, where the remaining workload of a loop is computed efficiently at runtime by utilizing the code generated by our compile-time component. We have performed an evaluation over seven different benchmark programs, using five different input datasets, on two different hardware across a varying number of threads; leading to a total number of 275 configurations. We show that in 225 out of 275 configurations, compared to the best OpenMP scheduling scheme for that configuration, our approach achieves clear performance gains.<\/jats:p>","DOI":"10.1145\/3633331","type":"journal-article","created":{"date-parts":[[2023,11,18]],"date-time":"2023-11-18T10:50:38Z","timestamp":1700304638000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["COWS for High Performance: Cost Aware Work Stealing for Irregular Parallel Loop"],"prefix":"10.1145","volume":"21","author":[{"ORCID":"https:\/\/orcid.org\/0009-0001-8796-4229","authenticated-orcid":false,"given":"Prasoon","family":"Mishra","sequence":"first","affiliation":[{"name":"Indian Institute of Technology Madras, India"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5949-0046","authenticated-orcid":false,"given":"V. Krishna","family":"Nandivada","sequence":"additional","affiliation":[{"name":"Indian Institute of Technology Madras, India"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,1,19]]},"reference":[{"issue":"8","key":"e_1_3_2_2_2","first-page":"207216","article-title":"Cilk: An efficient multithreaded runtime system","volume":"30","author":"Blumofe Robert D.","year":"1995","unstructured":"Robert D. Blumofe, Christopher F. Joerg, Bradley C. Kuszmaul, Charles E. Leiserson, Keith H. Randall, and Yuli Zhou. 1995. Cilk: An efficient multithreaded runtime system. SIGPLAN Not. 30, 8 (Aug.1995), 207216.","journal-title":"SIGPLAN Not."},{"key":"e_1_3_2_3_2","volume-title":"Hood: A User-Level Threads Library for Multiprogrammed Multiprocessors","author":"Blumofe Robert D.","year":"1998","unstructured":"Robert D. Blumofe and Dionisios Papadopoulos. 1998. Hood: A User-Level Threads Library for Multiprogrammed Multiprocessors. Technical Report."},{"issue":"6","key":"e_1_3_2_4_2","article-title":"An adaptive self-scheduling loop scheduler","volume":"34","author":"Booth Joshua Dennis","year":"2022","unstructured":"Joshua Dennis Booth and Phillip Allen Lane. 2022. An adaptive self-scheduling loop scheduler. CCPE 34, 6 (2022).","journal-title":"CCPE"},{"key":"e_1_3_2_5_2","first-page":"377","volume-title":"EuroPar","author":"Bull J. Mark","year":"1998","unstructured":"J. Mark Bull. 1998. Feedback guided dynamic loop scheduling: Algorithms and experiments. In EuroPar. 377\u2013382."},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","unstructured":"Vincent Cav\u00e9 Jisheng Zhao Jun Shirako and Vivek Sarkar. 2011. Habanero-Java: The new adventures of old X10. ACM 51\u201361. DOI:10.1145\/2093157.2093165","DOI":"10.1145\/2093157.2093165"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1177\/1094342007078442"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/1103845.1094852"},{"key":"e_1_3_2_9_2","volume-title":"ICS","author":"Chen Hu","year":"2006","unstructured":"Hu Chen, Wenguang Chen, Jian Huang, Bob Robert, and H. Kuhn. 2006. MPIPP: An automatic profile-guided parallel process placement toolset for SMP clusters and multiclusters. In ICS."},{"key":"e_1_3_2_10_2","volume-title":"ICS","author":"Chen Q.","year":"2012","unstructured":"Q. Chen, M. Guo, and Z. Huang. 2012. CATS: Cache aware task-stealing based on online profiling in multi-socket multi-core architectures. In ICS."},{"key":"e_1_3_2_11_2","first-page":"1","volume-title":"SC \u201908: Proceedings of the 2008 ACM\/IEEE Conference on Supercomputing","author":"Duran Alejandro","year":"2008","unstructured":"Alejandro Duran, Julita Corbalan, and Eduard Ayguade. 2008. An adaptive cut-off for task parallelism. In SC \u201908: Proceedings of the 2008 ACM\/IEEE Conference on Supercomputing. 1\u201311. DOI:10.1109\/SC.2008.5213927"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","unstructured":"Marie Durand Fran\u00e7ois Broquedis Thierry Gautier and Bruno Raffin. 2013. An efficient OpenMP loop scheduler for irregular applications on large-scale NUMA machines Vol. 8122. DOI:10.1007\/978-3-642-40698-0_11","DOI":"10.1007\/978-3-642-40698-0_11"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/277652.277725"},{"issue":"0","key":"e_1_3_2_14_2","first-page":"1","article-title":"IMSuite: A benchmark suite for simulating distributed algorithms","volume":"75","author":"Gupta Suyash","year":"2015","unstructured":"Suyash Gupta and V. Krishna Nandivada. 2015. IMSuite: A benchmark suite for simulating distributed algorithms. JPDC 75, 0 (2015), 1\u201319.","journal-title":"JPDC"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/4472.4478"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1109\/71.888636"},{"key":"e_1_3_2_17_2","first-page":"39","volume-title":"ICPP","author":"Hamidzadeh B.","year":"1994","unstructured":"B. Hamidzadeh and D. J. Lilja. 1994. Self-adjusting scheduling: An on-line optimization technique for locality management and load balancing. In ICPP. 39\u201346."},{"key":"e_1_3_2_18_2","first-page":"610","volume-title":"Proceedings of SC","author":"Hummel Susan Flynn","year":"1991","unstructured":"Susan Flynn Hummel, Edith Schonberg, and Lawrence E. Flynn. 1991. Factoring: A practical and robust method for scheduling parallel loops. In Proceedings of SC. ACM, 610\u2013632."},{"key":"e_1_3_2_19_2","unstructured":"IBM Corporation. 2021. Distribution Techniques. (2021). https:\/\/www.ibm.com\/docs\/en\/pessl\/5.3.0?topic=distributions-distribution-techniques"},{"key":"e_1_3_2_20_2","first-page":"131","volume-title":"ISPDC","author":"Kasielke Franziska","year":"2019","unstructured":"Franziska Kasielke, Ronny Tsch\u00fcter, Christian Iwainsky, Markus Velten, Florina M. Ciorba, and Ioana Banicescu. 2019. Exploring loop scheduling enhancements in OpenMP: An LLVM case study. In ISPDC. 131\u2013138."},{"key":"e_1_3_2_21_2","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1109\/ICPP.2006.49","volume-title":"2006 International Conference on Parallel Processing (ICPP\u201906)","author":"Kejariwal Arun","year":"2006","unstructured":"Arun Kejariwal, Alexandru Nicolau, and Constantine D. Polychronopoulos. 2006. History-aware self-scheduling. In 2006 International Conference on Parallel Processing (ICPP\u201906). 185\u2013192. DOI:10.1109\/ICPP.2006.49"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.1985.231547"},{"key":"e_1_3_2_23_2","first-page":"251","volume-title":"HiPC","author":"Kumar Vivek","year":"2020","unstructured":"Vivek Kumar. 2020. PufferFish: NUMA-aware work-stealing library using elastic tasks. In HiPC. 251\u2013260."},{"key":"e_1_3_2_24_2","article-title":"SNAP Datasets: Stanford Large Network Dataset Collection","author":"Leskovec Jure","year":"2014","unstructured":"Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. http:\/\/snap.stanford.edu\/data (June2014).","journal-title":"http:\/\/snap.stanford.edu\/data"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1145\/143103.143134"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/2450136.2450138"},{"key":"e_1_3_2_27_2","unstructured":"A. Nougrahiya and V. Krishna Nandivada. 2018. IIT Madras OpenMP (IMOP) Framework. (2018)."},{"key":"e_1_3_2_28_2","unstructured":"OpenMP Architecture Review Board. 2021. OpenMP Application Program Interface Version 5.2. (Nov.2021). https:\/\/www.openmp.org\/wp-content\/uploads\/OpenMP-API-Specification-5-2.pdf"},{"issue":"18","key":"e_1_3_2_29_2","first-page":"1","article-title":"A comprehensive performance evaluation of the BinLPT workload-aware loop scheduler","volume":"31","author":"Penna P.","year":"2019","unstructured":"P. Penna, A. Gomes, M. Castro, P. D. M. Plentz, H. Freitas, F. Broquedis, and J.-F. M\u00e9haut. 2019. A comprehensive performance evaluation of the BinLPT workload-aware loop scheduler. CCPE 31, 18 (2019), 1\u201322.","journal-title":"CCPE"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1145\/3392717.3392763"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1145\/3414469"},{"key":"e_1_3_2_32_2","doi-asserted-by":"crossref","first-page":"766","DOI":"10.1109\/IPDPSW.2017.141","volume-title":"2017 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW)","author":"Salehian Solmaz","year":"2017","unstructured":"Solmaz Salehian, Jiawen Liu, and Yonghong Yan. 2017. Comparison of threading programming models. In 2017 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW). 766\u2013774."},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","unstructured":"Jun Shirako Jisheng M. Zhao V. Krishna Nandivada and Vivek N. Sarkar. 2009. Chunking parallel loops in the presence of synchronization(ICS\u201909). Association for Computing Machinery 181\u2013192. DOI:10.1145\/1542275.1542304","DOI":"10.1145\/1542275.1542304"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1145\/3136063"},{"key":"e_1_3_2_35_2","first-page":"214","volume-title":"SC","author":"Subramaniam S.","year":"1994","unstructured":"S. Subramaniam and D. L. Eager. 1994. Affinity scheduling of unbalanced workloads. In SC. IEEE Press, 214\u2013226."},{"key":"e_1_3_2_36_2","doi-asserted-by":"crossref","first-page":"88","DOI":"10.1007\/978-3-642-30961-8_7","volume-title":"OpenMP in a Heterogeneous World","author":"Thoman Peter","year":"2012","unstructured":"Peter Thoman, Herbert Jordan, Simone Pellegrini, and Thomas Fahringer. 2012. Automatic OpenMP loop scheduling: A combined compiler and runtime approach. In OpenMP in a Heterogeneous World. 88\u2013101."},{"key":"e_1_3_2_37_2","volume-title":"Euro-Par 2014: Parallel Processing Workshops","author":"Tousimojarad Ashkan","year":"2014","unstructured":"Ashkan Tousimojarad and Wim Vanderbauwhede. 2014. Comparison of three popular parallel programming models on the Intel Xeon Phi. In Euro-Par 2014: Parallel Processing Workshops. Springer International Publishing."},{"key":"e_1_3_2_38_2","volume-title":"Advances in Neural Information Processing Systems","author":"Xie Cong","year":"2014","unstructured":"Cong Xie, Ling Yan, Wu-Jun Li, and Zhihua Zhang. 2014. Distributed power-law graph computing: Theoretical and empirical analysis. In Advances in Neural Information Processing Systems, Vol. 27. Curran Associates, Inc."}],"container-title":["ACM Transactions on Architecture and Code Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3633331","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3633331","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T22:54:01Z","timestamp":1750287241000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3633331"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,1,19]]},"references-count":37,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,3,31]]}},"alternative-id":["10.1145\/3633331"],"URL":"https:\/\/doi.org\/10.1145\/3633331","relation":{},"ISSN":["1544-3566","1544-3973"],"issn-type":[{"value":"1544-3566","type":"print"},{"value":"1544-3973","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,1,19]]},"assertion":[{"value":"2023-07-03","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-11-12","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-01-19","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}