[00137448]通讯避免的若干数学库核心算法的设计和优化

针对一大类稠密线性代数中的运算,例如矩阵乘、高斯消去法求解线性方程组等,我们首先从理论上证明了这类运算在并行计算时的通讯复杂度下界。以通讯复杂度为参考,我们设计出了能达到或者接近复杂度下界的算法。为了验证所提算法的可行性和有效性,我们在实际的计算机系统上实现了算法,并做了一系列的对比实验和优化。我们针对高性能计算中广泛应用的基准测试程序HPL （High Performance Linpack）开发了初步的算法运行环境。理论预测表明我们的算法在 Exaflops 的规模下,仍然能取得较高的并行效率。在 10000 个核的实验平台上,测试结果表明,相比之前最好的并行算法,我们的方法能够将并行开销减少75%。LUPP（LU Decomposition with Partial Pivoting）是求解稠密线性方程组最高效的算法,在科学计算中广泛应用。针对 LUPP 算法的并行,我们提出了一种新型的通讯避免及主元寻找方法,相比之前最好的方法兼具时间上的高效性和数值上的稳定性。我们将提出的方法集成到了 LUPP 在基准测试程序 HPL 上的实现中,实验结果表明了所提方法的可行性。理论分析和实验结果均证明了我们的方法在稠密线性代数运算的并行计算中非常高效。 本项目在执行过程中共发表研究论文 18 篇,其中国际学术期刊论文 5 篇,国际学术会议论文 13 篇,其中包括高性能和并行计算领域的著名国际会议 PPoPP（CCF A 类）, ICS （CCF B 类）, ICPP （CCF B 类）,分布式和并行计算及应用领域的著名国际期刊 TPDS （CCF A 类） , IJHPCA （SCI）等。本项目共培养硕士和博士研究生 8 名,其中已毕业博士 4 名,已毕业硕士 3 名,在读博士生 1 名。在国家自然科学基金的资助下,本团队对数学库核心算法并行的通讯避免方向进行了系统研究,发展出一系列新型高效的并行化通讯避免方法。本项目的研究达到了预期目标,我们的工作基本上与这一领域的国际最前沿成果保持同步。