ReDSEa: Automated Acceleration of Triangular Solver on Supercloud Heterogeneous Systems

Georgios Zacharopoulos, Ilias Bournias, Verner Vlacic, Lukas CavigelliarXiv 2023 · DOI · arXiv

Abstract

Modern heterogeneous "Supercloud" systems, which pair general-purpose CPUs with specialized AI accelerators, offer immense theoretical performance but present significant programming challenges. ReDSEa (Recursive Design Space Exploration Automation) is an automated compiler tool-chain designed to optimize the mapping of complex mathematical solvers onto these architectures. By exploring recursive, iterative, and blocked computational models, ReDSEa achieves up to a 16x speedup for Triangular System Solvers (TS) compared to optimized multi-core CPU implementations.

Introduction

The rise of heterogeneous computing has introduced architectures that mix ARM CPUs with specialized hardware like GPUs or AI accelerators (e.g., TPUs, DPUs). While powerful, these systems are notoriously difficult to program due to the complexities of manual offloading, data movement management, and workload balancing. The Triangular System Solver (TS), a fundamental building block in linear algebra for deep learning and high-performance computing (HPC), is particularly sensitive to these trade-offs. ReDSEa addresses this by automating the design space exploration to find optimal computation granularity and minimize communication overhead.

Methodology

ReDSEa is built on the LLVM compiler infrastructure and employs a three-pillar workflow:

  1. Compiler Analysis: Generates a Data Flow Graph (DFG) from C/C++ source code, estimating task latency and communication costs based on hardware bandwidth.
  2. Cost Modeling: Uses mathematical models to estimate the execution's critical path, accounting for CPU/accelerator computation, host-to-device data transfers, and synchronization.
  3. Design Space Exploration (DSE): Employs a branch-and-bound algorithm to compare three computational models: Recursive, Iterative, and Blocked.
Recursive decomposition of the Triangular System Solver (TS) into sub-tasks.

The recursive model, as shown in Figure 1, decomposes the problem into smaller sub-tasks, including smaller TS instances and matrix-vector multiplications (mxv). The tool-chain explores various "refinement levels" to determine the optimal size for these sub-problems.

Visual representation of increasing refinement levels in the triangular matrix decomposition.

As illustrated in Figure 6, increasing the refinement level breaks the problem into more pieces. While this can improve accelerator utilization, ReDSEa's DSE is critical for finding the point where communication overhead begins to outweigh these gains.

Evaluation and Key Insights

The tool-chain was evaluated using a Huawei Kunpeng 48-core ARM CPU and a Huawei Ascend 910 AI accelerator. Key findings include:

  • The Granularity "Sweet Spot": Performance does not scale linearly with refinement. Excessive refinement leads to a "Communication Wall" where data transfer overhead outweighs acceleration gains.
  • CPU Fragmentation: Overly fine-grained sub-tasks can bottleneck the CPU, as it becomes inefficient at handling very small workloads.
  • Model Flexibility: While recursive models are elegant, blocked models often provide superior load balancing and better opportunities to overlap communication with computation.

Results

ReDSEa achieved a maximum speedup of 16x using 48 CPU cores and the Ascend accelerator at a refinement level of 64. Notably, the tool-chain maintained significant speedups even with limited CPU resources (12 or 24 cores) by effectively offloading work to the AI accelerator. The automated DSE successfully identified optimal refinement levels, preventing sub-optimal configurations.

Conclusion and Future Work

ReDSEa demonstrates the potential for automated tools to bridge the gap between complex heterogeneous hardware and high-performance software. Future work will focus on extending the tool-chain to other HPC routines, such as Cholesky and QR Matrix Factorization, and further optimizing the overlap between communication and computation.

Summary updated

Abstract

When utilized effectively, Supercloud heterogeneous systems have the potential to significantly enhance performance. Our ReDSEa tool-chain automates the mapping, load balancing, scheduling, parallelism, and overlapping processes for the Triangular System Solver (TS) on a heterogeneous system consisting of a Huawei Kunpeng ARM multi-core CPU and an Ascend 910 AI HW accelerator. We propose an LLVM compiler tool-chain that a) leverages compiler analysis and b) utilizes novel performance models exploring recursive, iterative, and blocked computation models. Our tool-chain facilitates a speedup of up to 16x compared to an optimized 48-core CPU-only implementation.
BibTeX
@misc{zacharopoulos2023redsea,
  author = {Georgios Zacharopoulos and Ilias Bournias and Verner Vlacic and Lukas Cavigelli},
  title = {{ReDSEa: Automated Acceleration of Triangular Solver on Supercloud Heterogeneous Systems}},
  year = {2023},
  eprint = {2305.19917},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2305.19917},
}
Figure