几类典型应用的代数多重网格算法并行可扩展瓶颈分析

Analysis of Parallel Scalability Bottleneck for Algebraic Multigrid in Typical Real Applications

对于大规模稀疏线性代数方程组,代数多重网格(AMG)是具有最优计算复杂度的求解算法,但由于其算法流程复杂,导致难以取得理想的并行可扩展性能,难以定位和分析其并行可扩展瓶颈。通过分析AMG算法的性能骨架和通信模式,归纳了三类可扩展性能瓶颈,并引入稀疏矩阵通信域的概念来刻画稀疏模式对并行通信性能的影响。针对辐射流体力学、结构力学、航空发动机三类实际应用的6个具有不同稀疏模式特征的典型算例,实现了多粒度并行可扩展性能瓶颈的定位与分析,总结了未来AMG并行性能优化方向。

Algebraic multigrid(AMG)is an optimal algorithm for solving large-scale sparse linear systems.However,its complexity makes it challenging to achieve ideal parallel scalability and identify parallel scalability bottlenecks.In this paper,we analyze the performance skeletons and communication patterns of the AMG algorithm to identify three categories of scalability bottlenecks.Additionally,we introduce the concept of the sparse matrix communication domain to characterize the influence of sparse patterns on parallel communication performance.We examine six typical examples with varying sparse pattern features in practical applications such as radiation fluid dynamics,structural mechanics,and aero-engines.Through our analysis,we identify and analyze multi-granularity parallel scalability bottlenecks and provide insights into future directions for improving AMG parallel performance.