面向100PF级计算机的三类共性算法研究及高效实现

Basic algorithms show their powerful bonding capacity between making full use of HPC and solving applied PDE-based problem effectively and efficiently, whose implementation depends on the interdisciplinary research team among applied problem, computational algorithm and computer architecture..Based on domestic 100PF heterogeneous computer, this project will delve into the interdisciplinary research among science and engineering applications, numerical algorithms and computer science. It will make efforts to set up a synthetic evaluation rule and its model among three intrinsic connected graphs originated from interdisciplinary research fields, and get an abstract programming model based on the bottom-up multilevel heterogeneous platform, in order to make full use of the computer’s potential capacity and get more practical performance for infrastructure common algorithm library. The project will implement a new-style nonlinear PDE common solving algorithm named as Schur-NKS solver, which will include a so-called physical-based preconditioner based on both non-equilibrium features of nonlinear problem and eigen-pair information of coefficient matrix. At the same time, this project will study new algorithms for solving sparse/dense matrix eigenvalue/eigenvector problems as well as lost value prevention and fake value recognition. Lastly, this project will study effective parallelizable algorithms of fast multi-pole method..The anticipated gain of our project will include: a comprehensive evaluation method of relation graphs in these three fields, a multilevel heterogeneous programming model, the new-style nonlinear PDE common solving algorithm Schur-NKS, an effective parallel library and solver to sparse/dense matrix eigenvalue/eigenvector problems, and a parallel library of fast multi-pole method.

共性算法是发挥高性能计算机潜力和满足实际问题需求的纽带，其高效实现依赖于应用、算法、机器等多领域的交叉与合作。.本项目围绕科学工程应用、数值算法、计算机科学三个领域间的相互关联与耦合，面向100PF级国产异构计算机，具体研究包括：构建三个领域的关联图及其耦合度综合评价方法；构建多层异构计算模型，有效提升基础设施类共性算法库实际性能；设计并实现非线性问题的Schur-NKS新型算法和求解器，将非线性空间分布特性、特征值/特征向量信息引入预条件子构造；研究稠密/稀疏矩阵特征值求解的新型算法，研究稀疏矩阵特征值求解丢值和伪值的验证和解决算法；研究快速多极子方法的高效多级并行算法。.预期研究成果：应用、算法、机器三个关联图间耦合度评价方法，综合评价模块；非线性问题求解新型算法与求解器Schur-NKS；高效求解稠密/稀疏特征值问题的并行算法库和求解器；快速多极子并行算法库。

面向100PF级计算机的三类共性算法研究及高效实现项目（批准号91430214）目标为:“针对100PF乃至E级异构计算机，采用三个关联图及优化方法，研究三类共性算法的高效并行实现，使其可扩展性提升一个数量级、典型算法运行规模达百万核”。.该项目为应用问题、数值模拟、计算机体系结构抽象构建了各自关联图，并基于关联图研究了提升非线性问题求解共性算法、特征值问题求解共性算法、快速多极子方法等三类共性算法可扩展性的方法，在已有算法和软件实现的基础上，三类共性算法在神威•太湖之光超级计算机上可扩展性提升了一个数量级，典型算法运行规模已超过百万核，发表29篇论文，申请4项软件著作权和3项专利，完成了研究目标。.该项目的主要理论创新为“关联图及其耦合理论”，对于数值求解算法设计、计算资源调度、超级计算机结构设计及众核处理器结构设计等均有指导作用。该项目形成了基于Petal-剖分的大尺度聚类分解、Schur架构的新型Jacobian矩阵构建、面向矩阵二维存储块瓦片级的自适应数据划分和分布、稀疏邻接图重排与映射、树节点间全局通信开销优化等重要算法及程序组件，这些模块在基于图的深度神经网络研究领域存在需求，有望在大数据和人工智能领域发挥作用。.该项目针对分层异构计算机平台，采用了多级剖分方法，底层配合传统数学库，实现与平台解耦，支持三类共性算法在其他100PF级计算机上可扩展性同样大幅度提升；该项目中的基于Petal-剖分的大尺度聚类分解算法，以近似线性的时间代价实现了通讯开销的近似优化（由O(n^(1+ε))提高至O(n((log⁡n)^α)），理论上支持未来三类共性算法在E级计算机上的可扩展性进一步提升。