面向众核平台的高能效大规模图并行算法研究

Many-core platforms become the mainstream architecture of super computer. The multi-granularity parallelism, complexity of the memory hierarchy and memory accessing bandwidth limitation result in serious challenges of algorithm design and performance portability. As the critical foundation of big data problems, large-scale graph parallel algorithms urgently need to be explored for many-core platforms. This proposal researches on many-core platforms in the following items. (1) The presentation and multi-level partition of large-scale graph. This will be mapped to the multi-granularity parallelism and fine-grained multi-level task partitioning; (2) Problem-oriented heuristics loose synchronization mechanism. We will find the relativities between the parallel slackness, type of problem and the size of the problem to design efficient synchronization mechanism based on fine-grained task scheduling; (3) Performance measurement and power calibration method for a specific platform. We will establish a performance prediction model, and energy consumption estimation model. These algorithms will be co-optimized in performance and energy consumption to design an energy-efficient algorithm mechanism; (4) Energy-efficient portable parallel graph algorithm library. Manycore-platform-oriented energy-efficient large-scale parallel graph algorithms library will improve the productivity of application programs.

众核平台成为超级计算机的主流体系结构，其并行的多粒度性、存储层次的复杂性，以及存储带宽的有限性，导致相应的算法设计和性能可移植能力面临严峻挑战。大规模图并行算法作为大数据问题的关键基础，亟需探索面向众核平台的解决方案。本项目将面向众核平台，（1）研究大规模图的表示与多层次划分问题，以适应多粒度并行与多层次细粒度的任务划分；（2）研究面向问题特性的启发式宽松同步机制，发现宽松度与问题类型及问题规模之间的规律，设计基于细粒度任务调度的高效同步机制；（3）研究针对特定平台进行性能度量和功耗标定方法，建立算法级性能预测模型和能耗估计模型，为算法进行性能/能耗的双目标优化，设计高能效算法机制；（4）集成研究成果，构建高能效可移植的图算法库。面向众核平台的高能效大规模图并行算法库将提高应用程序的生产效率。

项目针对众核异构平台上大规模并行计算的线程多粒度性、存储层次复杂性、存储带宽有限性等，面向大数据问题的底层基础数据结构，解决大规模图的并行算法效能问题。主要研究内容和重要结果包括：1）针对GPU的存储层次复杂性和众多线程的读写特性，提出了基于规则化的大规模图等价表示方法和基于重编号的划分方法，大幅提高算法性能；2）针对众核异构计算的并行机制的多粒度性和带宽有限性，设计了分层次多粒度的宽松同步机制，在大规模图的计算性能和计算精度之间，取得合理折中；3）基于PARRAY高层并行接口和Julia脚本语言，设计了基本的原语体系，研究程序员性能感知的程序设计方法和能耗标定与预测方法；4）构建了大规模图的基本算法库，与面向领域的高性能云服务平台连接，提供了面向领域用户的大规模并行图算法的跨平台可移植能力，提高其可用性和程序生产效率；5）面向智能交通、社会网络、图像语义表示、工业设备故障预测等大数据应用领域，提供基于大图模型的解决方案。.大规模图的规则化表示方法，通过优选参数，不同的算法和数据上，取得3-6x加速比；调整宽松同步机制中的迭代充分性控制参数，在保证计算准确率在90%以上的情况下，加速比可进一步提高2x-6x。实现基于Julia语言的基本图算法库，嵌入面向领域的跨平台并行编程云服务环境，提供了一种新型计算模式，支持面向大数据的高性能处理与分析。