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:
- Compiler Analysis: Generates a Data Flow Graph (DFG) from C/C++ source code, estimating task latency and communication costs based on hardware bandwidth.
- Cost Modeling: Uses mathematical models to estimate the execution's critical path, accounting for CPU/accelerator computation, host-to-device data transfers, and synchronization.
- Design Space Exploration (DSE): Employs a branch-and-bound algorithm to compare three computational models: Recursive, Iterative, and Blocked.
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.
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