Vector load balancing for high-performance parallel applications

Buch, Ronak

Permalink

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

Description

Title

Vector load balancing for high-performance parallel applications

Author(s)

Buch, Ronak

Issue Date

2023-04-14

Director of Research (if dissertation) or Advisor (if thesis)

Kale, Laxmikant V

Doctoral Committee Chair(s)

Kale, Laxmikant V

Committee Member(s)

• Olson, Luke
• Padua, David
• Peña, Antonio

Department of Study

Computer Science

Discipline

Computer Science

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

• load balancing
• hpc
• parallel programming

Abstract

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.

Graduation Semester

2023-05

Type of Resource

Thesis

Copyright and License Information

Copyright 2023 Ronak Buch

Owning Collections