{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,11]],"date-time":"2025-09-11T19:22:38Z","timestamp":1757618558269,"version":"3.44.0"},"reference-count":19,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2025,6,28]],"date-time":"2025-06-28T00:00:00Z","timestamp":1751068800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,6,28]],"date-time":"2025-06-28T00:00:00Z","timestamp":1751068800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100031060","name":"European High Performance Computing Joint Undertaking","doi-asserted-by":"publisher","award":["956137","956137","956137"],"award-info":[{"award-number":["956137","956137","956137"]}],"id":[{"id":"10.13039\/100031060","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004955","name":"\u00d6sterreichische Forschungsf\u00f6rderungsgesellschaft","doi-asserted-by":"publisher","award":["FO999903595"],"award-info":[{"award-number":["FO999903595"]}],"id":[{"id":"10.13039\/501100004955","id-type":"DOI","asserted-by":"publisher"}]},{"name":"University of Innsbruck and Medical University of Innsbruck"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Int J Parallel Prog"],"published-print":{"date-parts":[[2025,8]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>Parameter sweep studies, such as virtual drug screening, may exhibit significant load imbalance during batched execution on large-scale clusters, resulting in idle and thus wasted resources. Work stealing is a popular method for dynamic load balancing in such scenarios. However, we demonstrate that work stealing alone falls short in cases where a few ranks generate long running high-cost jobs, particularly towards the end of a computation. To address this challenge, we propose high-cost probing, a mechanism for distributing high-cost jobs across workers early during program execution by leveraging user-provided cost hints. We extend the Celerity programming model for distributed accelerator computing with a high-level API tailored to expressing parameter sweep-style workflows that may benefit from high-cost probing. We demonstrate the effectiveness of our approach on synthetic benchmarks as well as a real-world virtual screening application with a highly irregular workload, achieving a 73 percentage point reduction in load imbalance on 128 GPUs.\n<\/jats:p>","DOI":"10.1007\/s10766-025-00804-4","type":"journal-article","created":{"date-parts":[[2025,6,28]],"date-time":"2025-06-28T07:00:32Z","timestamp":1751094032000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A High-Level API for Dynamic Load Balancing in Large-Scale Parameter Sweeps"],"prefix":"10.1007","volume":"53","author":[{"given":"Philip","family":"Salzmann","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Peter","family":"Thoman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Thomas","family":"Fahringer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,6,28]]},"reference":[{"issue":"1","key":"804_CR1","doi-asserted-by":"publisher","first-page":"170","DOI":"10.1109\/TETC.2022.3187134","volume":"11","author":"D Gadioli","year":"2023","unstructured":"Gadioli, D., Vitali, E., Ficarelli, F., Latini, C., Manelfi, C., Talarico, C., Silvano, C., Cavazzoni, C., Palermo, G., Beccari, A.R.: EXSCALATE: An Extreme-Scale Virtual Screening Platform for Drug Discovery Targeting Polypharmacology to Fight SARS-CoV-2. IEEE Trans. Emerg. Top. Comput. 11(1), 170\u2013181 (2023). https:\/\/doi.org\/10.1109\/TETC.2022.3187134","journal-title":"IEEE Trans. Emerg. Top. Comput."},{"key":"804_CR2","doi-asserted-by":"publisher","unstructured":"Rudolph, L., Slivkin-Allalouf, M., Upfal, E.: A simple load balancing scheme for task allocation in parallel machines. In: Proceedings of the third annual ACM symposium on parallel algorithms and architectures. SPAA \u201991, pp. 237\u2013245. Association for Computing Machinery, New York, NY, USA (1991). https:\/\/doi.org\/10.1145\/113379.113401","DOI":"10.1145\/113379.113401"},{"issue":"2","key":"804_CR3","doi-asserted-by":"publisher","first-page":"416","DOI":"10.1137\/0117039","volume":"17","author":"RL Graham","year":"1969","unstructured":"Graham, R.L.: Bounds on multiprocessing timing anomalies. SIAM J. Appl. Math. 17(2), 416\u2013429 (1969)","journal-title":"SIAM J. Appl. Math."},{"key":"804_CR4","doi-asserted-by":"publisher","unstructured":"Salzmann, P., Knorr, F., Thoman, P., Gschwandtner, P., Cosenza, B., Fahringer, T.: An asynchronous dataflow-driven execution model for distributed accelerator computing. In: 2023 IEEE\/ACM 23rd International Symposium on Cluster, Cloud and Internet Computing (CCGrid), pp. 82\u201393 (2023). https:\/\/doi.org\/10.1109\/CCGrid57682.2023.00018","DOI":"10.1109\/CCGrid57682.2023.00018"},{"key":"804_CR5","unstructured":"The Khronos Group: SYCL Specification, Version 2020 Revision 8. https:\/\/registry.khronos.org\/SYCL\/specs\/sycl-2020\/html\/sycl-2020.html Accessed 2024-04-11"},{"key":"804_CR6","doi-asserted-by":"publisher","unstructured":"DeRose, L., Homer, B., Johnson, D.: Detecting Application Load Imbalance on High End Massively Parallel Systems. In: Kermarrec, A.-M., Boug\u00e9, L., Priol, T. (eds.) Euro-Par 2007 Parallel Processing, pp. 150\u2013159. Springer, Berlin, Heidelberg (2007). https:\/\/doi.org\/10.1007\/978-3-540-74466-5_17","DOI":"10.1007\/978-3-540-74466-5_17"},{"key":"804_CR7","doi-asserted-by":"publisher","unstructured":"Demers, A., Greene, D., Hauser, C., Irish, W., Larson, J., Shenker, S., Sturgis, H., Swinehart, D., Terry, D.: Epidemic algorithms for replicated database maintenance. In: Proceedings of the Sixth Annual ACM Symposium on Principles of Distributed Computing. PODC \u201987, pp. 1\u201312. Association for Computing Machinery, New York, NY, USA (1987).https:\/\/doi.org\/10.1145\/41840.41841","DOI":"10.1145\/41840.41841"},{"key":"804_CR8","doi-asserted-by":"publisher","unstructured":"Vitali, E., Ficarelli, F., Bisson, M., Gadioli, D., Accordi, G., Fatica, M., Beccari, A.R., Palermo, G.: GPU-optimized approaches to molecular docking-based virtual screening in drug discovery: A comparative analysis. Journal of Parallel and Distributed Computing 186, 104819 (2024) https:\/\/doi.org\/10.1016\/j.jpdc.2023.104819","DOI":"10.1016\/j.jpdc.2023.104819"},{"key":"804_CR9","doi-asserted-by":"publisher","unstructured":"Perarnau, S., Sato, M.: Victim Selection and Distributed Work Stealing Performance: A Case Study. In: 2014 IEEE 28th International Parallel and Distributed Processing Symposium, pp. 659\u2013668 (2014). https:\/\/doi.org\/10.1109\/IPDPS.2014.74 . ISSN: 1530-2075","DOI":"10.1109\/IPDPS.2014.74"},{"issue":"2","key":"804_CR10","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1007\/s10766-016-0484-8","volume":"46","author":"J Yang","year":"2018","unstructured":"Yang, J., He, Q.: Scheduling Parallel Computations by Work Stealing: A Survey. Int. J. Parallel Prog. 46(2), 173\u2013197 (2018). https:\/\/doi.org\/10.1007\/s10766-016-0484-8","journal-title":"Int. J. Parallel Prog."},{"issue":"5","key":"804_CR11","doi-asserted-by":"publisher","first-page":"720","DOI":"10.1145\/324133.324234","volume":"46","author":"RD Blumofe","year":"1999","unstructured":"Blumofe, R.D., Leiserson, C.E.: Scheduling multithreaded computations by work stealing. J. ACM 46(5), 720\u2013748 (1999). https:\/\/doi.org\/10.1145\/324133.324234","journal-title":"J. ACM"},{"key":"804_CR12","doi-asserted-by":"publisher","unstructured":"Janjic, V., Hammond, K.: How to be a Successful Thief. In: Wolf, F., Mohr, B., Mey, D. (eds.) Euro-Par 2013 Parallel Processing, pp. 114\u2013125. Springer, Berlin, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-40047-6_14","DOI":"10.1007\/978-3-642-40047-6_14"},{"key":"804_CR13","unstructured":"Thibault, S.: On Runtime Systems for Task-based Programming on Heterogeneous Platforms. Thesis, Universit\u00e9 de Bordeaux (December 2018). https:\/\/hal.inria.fr\/tel-01959127"},{"key":"804_CR14","doi-asserted-by":"publisher","first-page":"34","DOI":"10.1016\/j.jpdc.2020.12.005","volume":"150","author":"V Freitas","year":"2021","unstructured":"Freitas, V., Pilla, L.L., Santana, Ad.L., Castro, M., Cohen, J.: PackStealLB: A scalable distributed load balancer based on work stealing and workload discretization. J. Parallel Distrib. Comput. 150, 34\u201345 (2021). https:\/\/doi.org\/10.1016\/j.jpdc.2020.12.005","journal-title":"J. Parallel Distrib. Comput."},{"issue":"4","key":"804_CR15","doi-asserted-by":"publisher","first-page":"1422","DOI":"10.1007\/s11227-018-2238-4","volume":"74","author":"P Thoman","year":"2018","unstructured":"Thoman, P., Dichev, K., Heller, T., Iakymchuk, R., Aguilar, X., Hasanov, K., Gschwandtner, P., Lemarinier, P., Markidis, S., Jordan, H., et al.: A taxonomy of task-based parallel programming technologies for high-performance computing. J. Supercomput. 74(4), 1422\u20131434 (2018)","journal-title":"J. Supercomput."},{"key":"804_CR16","doi-asserted-by":"publisher","unstructured":"John, J., Milthorpe, J., Strazdins, P.: Distributed Work Stealing in a Task-Based Dataflow Runtime. In: Wyrzykowski, R., Dongarra, J., Deelman, E., Karczewski, K. (eds.) Parallel Processing and Applied Mathematics, pp. 225\u2013236. Springer, Cham (2023). https:\/\/doi.org\/10.1007\/978-3-031-30442-2_17","DOI":"10.1007\/978-3-031-30442-2_17"},{"key":"804_CR17","doi-asserted-by":"publisher","first-page":"478","DOI":"10.2197\/ipsjjip.29.478","volume":"29","author":"R Nakashima","year":"2021","unstructured":"Nakashima, R., Yasugi, M., Yoritaka, H., Hiraishi, T., Umatani, S.: Work-stealing strategies that consider work amount and hierarchy. J. Inf. Process. 29, 478\u2013489 (2021). https:\/\/doi.org\/10.2197\/ipsjjip.29.478","journal-title":"J. Inf. Process."},{"key":"804_CR18","doi-asserted-by":"publisher","unstructured":"Imam, S., Sarkar, V.: Load balancing prioritized tasks via work-stealing. In: Tr\u00e4ff, J.L., Hunold, S., Versaci, F. (eds.) Euro-Par 2015: Parallel Processing, pp. 222\u2013234. Springer, Berlin, Heidelberg (2015). https:\/\/doi.org\/10.1007\/978-3-662-48096-0_18","DOI":"10.1007\/978-3-662-48096-0_18"},{"key":"804_CR19","doi-asserted-by":"publisher","unstructured":"Nasir, M.A.U., De\u00a0Francisci\u00a0Morales, G., Garc\u00eda-Soriano, D., Kourtellis, N., Serafini, M.: The power of both choices: Practical load balancing for distributed stream processing engines. In: 2015 IEEE 31st International Conference on Data Engineering, pp. 137\u2013148 (2015).https:\/\/doi.org\/10.1109\/ICDE.2015.7113279 . ISSN: 2375-026X. https:\/\/ieeexplore.ieee.org\/abstract\/document\/7113279 Accessed 2024-03-27","DOI":"10.1109\/ICDE.2015.7113279"}],"container-title":["International Journal of Parallel Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10766-025-00804-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10766-025-00804-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10766-025-00804-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,6]],"date-time":"2025-09-06T23:56:27Z","timestamp":1757202987000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10766-025-00804-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,28]]},"references-count":19,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2025,8]]}},"alternative-id":["804"],"URL":"https:\/\/doi.org\/10.1007\/s10766-025-00804-4","relation":{},"ISSN":["0885-7458","1573-7640"],"issn-type":[{"type":"print","value":"0885-7458"},{"type":"electronic","value":"1573-7640"}],"subject":[],"published":{"date-parts":[[2025,6,28]]},"assertion":[{"value":"26 September 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 May 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 June 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no financial or non-financial interests to disclose that are relevant to the content of this article.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"25"}}