Extending paratreet, a framework for spatial tree based algorithms, with gpu kernels and load balancers

Liu, Simeng

Permalink

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

Description

Title

Extending paratreet, a framework for spatial tree based algorithms, with gpu kernels and load balancers

Author(s)

Liu, Simeng

Issue Date

2022-04-28

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

Kale, Laxmikant

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)

• Parallel Computing
• N-Body
• GPGPU
• load balancing
• Charm++

Language

eng

Abstract

Improving the performance of iterative, computationally heavy applications with frequent memory access is challenging and exciting. This thesis shows the performance improvement efforts of the paraTreeT library. ParaTreeT is a parallel tree toolkit inspired by the N body simulation problem to model and investigate the dynamic motion of astronomical bodies given a set of initial conditions. ParaTreeT provides a generic parallel tree traversal framework targeting high scalability and programmability. The inputs from the user are partitioned and decomposed into leaf nodes of a chosen tree structure. The interactions among particles are done through traversals of a global tree. Users apply their custom structs of user data and define the tree type into which the data is partitioned, as well as the partition algorithm used. In addition, the library is extendable with custom traversal algorithms. ParaTreeT has achieved better central processing unit (CPU) performance compared to its predecessor ChaNGa by providing tree data using a shared-memory cache model, as well as separating the data computation functionality from its spatial tree representation. ParaTreeT demonstrated a 2-3x speedup over ChaNGa using up to 256 nodes (21504 threads) on the Summit’s POWER9 machine. This thesis focuses on improving the performance of the ParaTreeT framework through two approaches. The first approach is to implement load balancing strategies to speed up the iterative code with growing load imbalance. This thesis presents different load balancing algorithms and efforts to make them scalable. With theoretical runtime analysis of each algorithm, together with scaling experiments, the thesis identifies the scaling bottleneck and scalability of each algorithm. The second approach is to add general-purpose computing on graphics processing units (GPGPU) kernels to offload highly parallel computationally intensive work from CPU hosts to graphics processing units (GPUs). This thesis identifies the computationally heavy blocks of the CPU implementation and proposes multiple GPU kernels to speed up the computation. The thesis also analyzes the overhead of the GPU implementation, with discussion of plans for future improvements.

Graduation Semester

2022-05

Type of Resource

Thesis

Handle URL

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

Copyright and License Information

© 2022 Simeng Liu

Owning Collections