软件学报

作者：陈道琨，杨超，刘芳芳，马文静

单位：陈道琨，中国科学院 软件研究所 并行软件与计算科学实验室, 北京 100190;中国科学院大学, 北京 10004911,杨超，北京大学 数学科学学院, 北京 10087102,刘芳芳，中国科学院 软件研究所 并行软件与计算科学实验室, 北京 100190;中国科学院大学, 北京 10004903,马文静，中国科学院 软件研究所 并行软件与计算科学实验室, 北京 100190;中国科学院大学, 北京 10004904

关键词：稀疏三角线性方程组求解(SpTRSV);模板计算;结构化网格;GPU;异构并行算法

基金：国家重点研发计划高性能计算重点专项(2020YFB0204601)

稀疏三角线性方程组求解(SpTRSV)是预条件子部分的重要操作, 其中结构化SpTRSV问题, 在以迭代方法求解偏微分方程组的科学计算程序中, 是一种较为常见的问题类型, 而且通常是科学计算程序的需要解决的一个性能瓶颈. 针对GPU平台, 目前以CUSPARSE为代表的商用GPU数学库, 采用分层调度(level-scheduling)方法并行化SpTRSV操作. 该方法不仅预处理耗时较长, 而且在处理结构化SpTRSV问题时会出现较为严重GPU线程闲置问题. 针对结构化SpTRSV问题, 提出一种面向结构化SpTRSV问题的并行算法. 该算法利用结构化SpTRSV问题的特殊非零元分布规律进行任务划分, 避免对输入问题的非零元结构进行预处理分析. 并对现有分层调度方法的逐元素处理策略进行改进, 在有效缓解GPU线程闲置问题的基础上, 还隐藏了部分矩阵非零元素的访存延迟. 还根据算法的任务划分特点, 采用状态变量压缩技术, 显著提高算法状态变量操作的缓存命中率. 在此基础上, 还结合谓词执行等GPU硬件特性, 对算法实现进行全面的优化. 所提算法在NVIDIA V100 GPU上的实测性能, 相比CUSPARSE平均有2.71倍的加速效果, 有效访存带宽最高可达225.2 GB/s. 改进后的逐元素处理策略, 配合针对GPU硬件的一系列调优手段, 优化效果显著, 将算法的有效访存带宽提高了约1.15倍.

来源：2023年第11期

《软件学报》期刊编辑部

查看软件学报杂志2023年第11期