Vector load balancing for high-performance parallel applications

Load balancing, modifying the distribution of work across a system to optimize resource usage, is vital for achieving scalability and high performance for dynamic parallel applications. However, as applications and systems grow increasingly complex, established methods of measuring and balancing load are becoming less effective. Traditionally, load balancing only considered the total amount of execution time, stored as a scalar value, as a metric for load, but this fundamentally cannot capture other performance-limiting execution properties such as phase-based iteration structures due to dependencies between tasks, the simultaneous division of work across host CPUs and accelerator devices, or the impact of other resource constraints such as memory footprint. This inability to accurately characterize the nature of "load" causes balancing strategies to make poor placement decisions, leading to suboptimal performance. In this thesis, we propose vector load balancing, in which load is a vector of values rather than a scalar, and analyze its potential to improve the quality of load balancing for these complex applications and systems. We discuss the mathematical underpinnings of vector load balancing and challenges in measuring and utilizing vector loads, developing several new load balancing algorithms designed specifically for use with vector loads. We demonstrate both simulated and practical speedups across several different applications and programming models using these new techniques. Finally, we develop optimization techniques to improve the performance of vector load balancing strategies to make them viable at scale.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Computer Science

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2023

Author dc:creator

• Buch, Ronak

Contributors dc:contributor

• Kale, Laxmikant V
• Olson, Luke
• Padua, David
• Peña, Antonio

• Load Balancing
• Hpc
• Parallel Programming

Statement dc:rights

• Copyright 2023 Ronak Buch

Language dc:language

en, eng

Handle dc:identifier

https://hdl.handle.net/2142/120263

OAI record oai:identifier

https://www.ideals.illinois.edu/oai-pmh?verb=GetRecord&metadataPrefix=etdms&identifier=oai%3Awww.ideals.illinois.edu%3A2142%2F120263