{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T01:01:46Z","timestamp":1742950906928,"version":"3.40.3"},"publisher-location":"Cham","reference-count":28,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783031304415"},{"type":"electronic","value":"9783031304422"}],"license":[{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,4,28]],"date-time":"2023-04-28T00:00:00Z","timestamp":1682640000000},"content-version":"vor","delay-in-days":117,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2023]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Load imbalance is often a challenge for applications in parallel systems. Static cost models and pre-partitioning algorithms distribute the load at the beginning. Nevertheless, dynamic changes during execution or inaccurate cost indicators may lead to imbalance at runtime. Reactive work-stealing strategies can help monitor the execution and perform task migration to balance the load. However, the benefits depend on migration overhead and assumption about future execution.<\/jats:p><jats:p>Our proactive approach further improves existing solutions by applying machine learning to online load prediction. Following that, we propose a fully distributed algorithm for adapting the prediction result to guide task offloading. The experiments are performed with an artificial test case and a realistic application named Sam(oa)<jats:inline-formula><jats:alternatives><jats:tex-math>$$^2$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:msup><mml:mrow\/><mml:mn>2<\/mml:mn><\/mml:msup><\/mml:math><\/jats:alternatives><\/jats:inline-formula>on three systems with different communication overhead. Our results confirm improvements for important use cases compared to previous solutions. Furthermore, this approach can support co-scheduling tasks across multiple applications.<\/jats:p>","DOI":"10.1007\/978-3-031-30442-2_20","type":"book-chapter","created":{"date-parts":[[2023,4,27]],"date-time":"2023-04-27T10:02:09Z","timestamp":1682589729000},"page":"263-275","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Proactive Task Offloading for\u00a0Load Balancing in\u00a0Iterative Applications"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6119-3852","authenticated-orcid":false,"given":"Minh Thanh","family":"Chung","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7159-1432","authenticated-orcid":false,"given":"Josef","family":"Weidendorfer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0398-4087","authenticated-orcid":false,"given":"Karl","family":"F\u00fcrlinger","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8319-0123","authenticated-orcid":false,"given":"Dieter","family":"Kranzlm\u00fcller","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,4,28]]},"reference":[{"key":"20_CR1","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1016\/j.jnca.2017.01.016","volume":"82","author":"M Amiri","year":"2017","unstructured":"Amiri, M., et al.: Survey on prediction models of applications for resources provisioning in cloud. J. Netw. Comput. Appl. 82, 93\u2013113 (2017). https:\/\/doi.org\/10.1016\/j.jnca.2017.01.016","journal-title":"J. Netw. Comput. Appl."},{"issue":"8","key":"20_CR2","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1145\/209937.209958","volume":"30","author":"RD Blumofe","year":"1995","unstructured":"Blumofe, R.D., Joerg, C.F., et al.: Cilk: an efficient multithreaded runtime system. SIGPLAN Not. 30(8), 207\u2013216 (1995). https:\/\/doi.org\/10.1145\/209937.209958","journal-title":"SIGPLAN Not."},{"key":"20_CR3","doi-asserted-by":"publisher","unstructured":"Carrington, L.C., Laurenzano, M., et al.: How well can simple metrics represent the performance of HPC applications? In: Proceedings of the ACM\/IEEE Conference on Supercomputing (2015). https:\/\/doi.org\/10.1109\/SC.2005.33","DOI":"10.1109\/SC.2005.33"},{"key":"20_CR4","doi-asserted-by":"publisher","unstructured":"Catalyurek, U.V., Boman, E.G., et al.: Hypergraph-based dynamic load balancing for adaptive scientific computations. In: International Parallel and Distributed Processing Symposium, pp. 1\u201311 (2007). https:\/\/doi.org\/10.1109\/IPDPS.2007.370258","DOI":"10.1109\/IPDPS.2007.370258"},{"key":"20_CR5","doi-asserted-by":"crossref","unstructured":"Chow, Y.C., et al.: Models for dynamic load balancing in a heterogeneous multiple processor system. IEEE Trans. Comput. C-28(5), 354\u2013361 (1979)","DOI":"10.1109\/TC.1979.1675365"},{"key":"20_CR6","doi-asserted-by":"publisher","unstructured":"Chung, M.T., Kranzlm\u00fcller, D.: User-defined tools for characterizing task-parallel applications and predicting load imbalance. In: 15th International Conference on Advanced Computing and Applications (ACOMP), pp. 98\u2013105 (2021). https:\/\/doi.org\/10.1109\/ACOMP53746.2021.00020","DOI":"10.1109\/ACOMP53746.2021.00020"},{"issue":"1","key":"20_CR7","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1109\/4434.749133","volume":"7","author":"A Corradi","year":"1999","unstructured":"Corradi, A., Leonardi, L., Zambonelli, F.: Diffusive load-balancing policies for dynamic applications. IEEE Concurrency 7(1), 22\u201331 (1999). https:\/\/doi.org\/10.1109\/4434.749133","journal-title":"IEEE Concurrency"},{"issue":"4","key":"20_CR8","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1145\/2644865.2541941","volume":"49","author":"C Delimitrou","year":"2014","unstructured":"Delimitrou, C., Kozyrakis, C.: Quasar: resource-efficient and GOS-aware cluster management. SIGPLAN Not. 49(4), 127\u2013144 (2014). https:\/\/doi.org\/10.1145\/2644865.2541941","journal-title":"SIGPLAN Not."},{"key":"20_CR9","doi-asserted-by":"publisher","unstructured":"Dinan, J., Larkins, D.B., et al.: Scalable work stealing. In: Proceedings of the Conference on High Performance Computing Networking, Storage and Analysis (2009). https:\/\/doi.org\/10.1145\/1654059.1654113","DOI":"10.1145\/1654059.1654113"},{"key":"20_CR10","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., et al.: Packsteallb: a scalable distributed load balancer based on work stealing and workload discretization. J. Parallel Distrib. Comput. 150, 34\u201345 (2021)","journal-title":"J. Parallel Distrib. Comput."},{"key":"20_CR11","unstructured":"Goodfellow, I., Bengio, Y., Courville, A.: Deep Learning. MIT Press, Cambridge (2016). http:\/\/www.deeplearningbook.org"},{"key":"20_CR12","unstructured":"Karypis, G., Kumar, V.: A coarse-grain parallel formulation of multilevel k-way graph partitioning algorithm. In: PPSC (1997)"},{"key":"20_CR13","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1016\/j.jpdc.2019.12.005","volume":"138","author":"J Klinkenberg","year":"2020","unstructured":"Klinkenberg, J., Samfass, P., et al.: Chameleon: reactive load balancing for hybrid MPI+OpenMP task-parallel applications. J. Parallel Distrib. Comput. 138, 55\u201364 (2020). https:\/\/doi.org\/10.1016\/j.jpdc.2019.12.005","journal-title":"J. Parallel Distrib. Comput."},{"key":"20_CR14","doi-asserted-by":"publisher","unstructured":"Klinkenberg, J., Samfass, P., et al.: Reactive task migration for hybrid MPI+OpenMP applications. In: Parallel Processing and Applied Mathematics, pp. 59\u201371 (2020). https:\/\/doi.org\/10.1007\/978-3-030-43222-5_6","DOI":"10.1007\/978-3-030-43222-5_6"},{"key":"20_CR15","doi-asserted-by":"crossref","unstructured":"Larkins, D.B., Snyder, J., Dinan, J.: Accelerated work stealing. In: Proceedings of the 48th International Conference on Parallel Processing (2019)","DOI":"10.1145\/3337821.3337878"},{"key":"20_CR16","doi-asserted-by":"crossref","unstructured":"Li, J., Ma, X., et al.: Machine learning based online performance prediction for runtime parallelization and task scheduling. In: IEEE International Symposium on Performance Analysis of Systems and Software, pp. 89\u2013100 (2009)","DOI":"10.1109\/ISPASS.2009.4919641"},{"key":"20_CR17","doi-asserted-by":"crossref","unstructured":"Lifflander, J., et al.: Work stealing and persistence-based load balancers for iterative overdecomposed applications. In: Proceedings of the 21st International Symposium on High-Performance Parallel and Distributed Computing, pp. 137\u2013148 (2012)","DOI":"10.1145\/2287076.2287103"},{"issue":"3","key":"20_CR18","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2947668","volume":"43","author":"O Meister","year":"2016","unstructured":"Meister, O., Rahnema, K., Bader, M.: Parallel memory-efficient adaptive mesh refinement on structured triangular meshes with billions of grid cells. ACM Trans. Math. Softw. (TOMS) 43(3), 1\u201327 (2016)","journal-title":"ACM Trans. Math. Softw. (TOMS)"},{"key":"20_CR19","doi-asserted-by":"publisher","unstructured":"Menon, H., Kal\u00e9, L.: A distributed dynamic load balancer for iterative applications. In: Proceedings of the International Conference on High Performance Computing, Networking, Storage and Analysis, pp. 1\u201311 (2013). https:\/\/doi.org\/10.1145\/2503210.2503284","DOI":"10.1145\/2503210.2503284"},{"key":"20_CR20","doi-asserted-by":"crossref","unstructured":"Munera, A., Royuela, S., et al.: Experiences on the characterization of parallel applications in embedded systems with Extrae\/Paraver. In: 49th International Conference on Parallel Processing (2020)","DOI":"10.1145\/3404397.3404440"},{"key":"20_CR21","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1016\/j.compfluid.2018.01.031","volume":"173","author":"L Rannabauer","year":"2018","unstructured":"Rannabauer, L., Dumbser, M., Bader, M.: ADER-DG with a-posteriori finite-volume limiting to simulate tsunamis in a parallel adaptive mesh refinement framework. Comput. Fluids 173, 299\u2013306 (2018)","journal-title":"Comput. Fluids"},{"key":"20_CR22","doi-asserted-by":"publisher","unstructured":"Renardy, M., Rogers, R.C.: An introduction to partial differential equations, vol. 13. Springer, New York (2006). https:\/\/doi.org\/10.1007\/b97427","DOI":"10.1007\/b97427"},{"key":"20_CR23","doi-asserted-by":"crossref","unstructured":"Samfass, P., Klinkenberg, J., Bader, M.: Hybrid MPI+OpenMP reactive work stealing in distributed memory in the PDE framework Sam(oa)$$^2$$. In: IEEE International Conference on Cluster Computing, pp. 337\u2013347 (2018)","DOI":"10.1109\/CLUSTER.2018.00051"},{"key":"20_CR24","doi-asserted-by":"crossref","unstructured":"Samfass, P., Klinkenberg, J., et al.: Predictive, reactive and replication-based load balancing of tasks in chameleon and Sam(oa)$$^2$$. In: Proceedings of the Platform for Advanced Scientific Computing Conference (2021)","DOI":"10.1145\/3468267.3470574"},{"key":"20_CR25","doi-asserted-by":"crossref","unstructured":"Sharkawi, S., Desota, D., et al.: Performance projection of HPC applications using SPEC CFP2006 benchmarks. In: International Symposium on Parallel & Distributed Processing, pp. 1\u201312 (2009)","DOI":"10.1109\/IPDPS.2009.5161057"},{"key":"20_CR26","doi-asserted-by":"crossref","unstructured":"Shende, S., Malony, A.D., et al.: Portable profiling and tracing for parallel, scientific applications using C++. In: Proceedings of the SIGMETRICS Symposium on Parallel and Distributed Tools, pp. 134\u2013145","DOI":"10.1145\/281035.281049"},{"key":"20_CR27","doi-asserted-by":"publisher","unstructured":"Skinner, D., Kramer, W.: Understanding the causes of performance variability in HPC workloads. In: Proceedings of the IEEE Workload Characterization Symposium, pp. 137\u2013149 (2005). https:\/\/doi.org\/10.1109\/IISWC.2005.1526010","DOI":"10.1109\/IISWC.2005.1526010"},{"issue":"4","key":"20_CR28","doi-asserted-by":"publisher","first-page":"1422","DOI":"10.1007\/s11227-018-2238-4","volume":"74","author":"P Thoman","year":"2018","unstructured":"Thoman, P., et al.: A taxonomy of task-based parallel programming technologies for high-performance computing. J. Supercomput. 74(4), 1422\u20131434 (2018). https:\/\/doi.org\/10.1007\/s11227-018-2238-4","journal-title":"J. Supercomput."}],"container-title":["Lecture Notes in Computer Science","Parallel Processing and Applied Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-30442-2_20","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,19]],"date-time":"2024-10-19T09:02:34Z","timestamp":1729328554000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-30442-2_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023]]},"ISBN":["9783031304415","9783031304422"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-30442-2_20","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2023]]},"assertion":[{"value":"28 April 2023","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"PPAM","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Parallel Processing and Applied Mathematics","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Gdansk","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Poland","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2022","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"11 September 2022","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"14 September 2022","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"14","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"ppam2022","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/ppam.edu.pl\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Easychair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"132","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"77","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"58% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"2","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"No","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}