Analyzing communication impacts of graph-refinement load-balancing in Stencil3D

Yellapragada, Sowmya

Permalink

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

Description

Title

Analyzing communication impacts of graph-refinement load-balancing in Stencil3D

Author(s)

Yellapragada, Sowmya

Issue Date

2024-04-29

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

Kale, Laxmikant V

Department of Study

Computer Science

Discipline

Computer Science

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

M.S.

Degree Level

Thesis

Keyword(s)

• load balancing
• graph partioning strategy
• parallel programming
• Charm++
• object migration, load diffusion

Abstract

Load balancing is a critical aspect of parallel and distributed computing systems, especially in environments characterized by dynamic workloads and high communication volumes. In this thesis, we delve into various load-balancing strategies for Charm++ applications, with a specific focus on communication-aware methods. Our goal is to maximize internal communication and minimize external communication across the nodes. We analyze two primary load-balancing algorithms - GreedyRefineLB and GraphRefineLB. Graph-based partitioning strategies aim to optimize load distribution by considering the communication topology. These algorithms leverage graph partitioning techniques to achieve better load balance. However, they also face challenges related to scalability and adaptability to changing workloads. Our major contribution lies in analyzing the communication impacts of a new algorithm: Communication-aware Diffusion LB. This innovative approach seeks to strike a balance between two critical objectives - reducing object migrations and enhancing communication locality. To assess the efficacy of these strategies, we employ the Stencil3d benchmark—a well-established synthetic standard for evaluating parallel and distributed systems. Our evaluation reveals the trade-offs associated with different load-balancing approaches. Notably, Communication-aware Diffusion LB demonstrates superior performance in managing dynamic workloads with substantial communication requirements. In summary, our research underscores the importance of communication-aware load balancing in parallel computing environments. As applications continue to evolve, finding the right balance between communication optimization and efficient system utilization remains crucial. The Communication-aware Diffusion LB offers a promising avenue for achieving this balance and enhancing the overall performance of Charm++ applications.

Graduation Semester

2024-05

Type of Resource

Thesis

Copyright and License Information

Copyright 2024 Sowmya Yellapragada

Owning Collections