基于图原语线性代数表达的并行非规则归约计算

Developing the high performance parallel codes for irregular applications are very difficult in traditional science and engineering computation fileds, such as computational fluid mechanics and particle simulations. Now, many irregular applications are also appear in emerging big data fields, for example, data mining and social network analysis. Because of their unpredictable data access pattern, this kind of computations have poor space and time locality, and can not fit well with the current processor architecture. It is difficult to gain high performance for these irregular applications. The kernel of a lot of these irregular applications is the irregular reduction, namely, a set of reduction operations on irregular memory accesses. It is the critical performace factor for these irregular applications. So the studies on high performance parallel irregular reduction algorithms and technologies to support the effective development irregular applications in many fileds have important significance.. This project will study the parallel irregular reduction alorithms and optimization technologies on the high performance computers with new architecture, based on the graph primitives in terms of linear algebra operations. Then a parallel irregular reduction framework will be developed based on the above technologies, to support the rapid development and large-scale simulations of many parallel irregular apllications in traditional science and engineering computation and big data fields. It will have a strong theory and practical application value.

开发高效的非规则应用并行程序是计算流体力学、粒子模拟等许多传统科学与工程计算领域的难点问题。随着新兴大数据领域的发展，在数据挖掘、社会网络分析等研究中也涌现出来许多非规则应用。由于具有不可预料的数据访问模式，这类计算的空间与时间局部性差，不能很好地匹配当前处理器的体系结构特征，使得这类应用难以获得高性能。许多非规则应用的核心是非规则归约问题，它是一组与非规则内存访问相关的归约操作，且是影响非规则应用的关键性能因素。因此，研究高效的并行非规则归约算法和技术，从而支撑多个领域的非规则应用的高效能开发具有重要的科学意义。. 本项目面向新型硬件体系结构，研究基于图原语线性代数表达的并行非规则归约算法和优化技术，进而研制相应的并行非规则归约计算框架，支撑传统科学与工程计算以及大数据领域的若干非规则应用的快速开发和大规模计算模拟，具有很强的理论和实际应用价值。

在流体力学、粒子模拟、大数据等领域，存在着大量的非规则应用。研制高效的非规则应用并行程序是高性能计算领域中一类非常重要但特别复杂的难点问题。这些应用由于在数据结构、控制和通信模式上的不规则性，不能很好地匹配当前体系结构并充分发挥其性能，使得高效的非规则并行应用程序的开发变得相当困难。许多非规则应用的核心通常由一组非规则归约计算构成。研究非规则归约计算的并行特征、匹配高性能计算机的并行算法和技术，对促进大规模非规则并行应用的研制有着重要意义。. 本项目面向实际科学与工程应用，针对大数据、流体力学等领域的非规则应用性能问题展开，系统研究了如下内容：并行非规则归约应用的图计算模型和线性代数表达方法、面向高性能体系结构高效的非规则归约并行算法和图原语实现技术、基于上述方法的并行非规则归约计算框架实现技术。这些并行算法和技术在典型大数据和非结构网格流体力学程序中得到应用，在分布式环境下显现出更大的并行性和更好的可扩展性。其中，一图聚类并行程序采用基于线性代数计算、MPI和OpenMP混合并行，在并行处理2097152个顶点、18305177条边的超大规模图时，在2048核上获得949.5倍加速；非结构网格流体力学拉格朗日网格重分在百亿网格规模下，在1024核上获得90%的并行效率。上述方法和技术可推广使用到更多的非规则并行应用中。