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

项目名称： 通讯避免的若干数学库核心算法的设计和优化

项目编号： No.61472395

项目类型： 面上项目

立项/批准年度： 2015

项目学科： 自动化技术、计算机技术

项目作者： 姚二林

作者单位： 中国科学院计算技术研究所

项目金额： 84万元

中文摘要： 随着计算机系统的计算能力和通讯能力之间的差距越来越大，算法执行的总开销中通讯所带来的性能和能耗开销逐渐占主导地位，因此研究算法的通讯避免对于计算系统的性能提高和能耗降低都具有十分重要的意义。数学库中的核心算法对于高性能计算领域具有重要的研究意义，本项目重点针对高性能计算中几个重要的基准测试程序如Top500，Graph500，HPCG等，研究其中核心算法通讯避免的设计和优化。本项目拟从以下三个方向开展研究：1）构建实用的并行计算通讯模型，以反映最新的计算机体系结构特征，并确定在模型的框架下若干核心算法的并行通讯复杂度；2）设计通讯避免的算法，以达到或者尽量接近所确定的通讯复杂度下界；3）在现有主流的体系结构上，实现并优化所设计的通讯避免算法。通过本项目的研究，可以为数学库中的若干核心算法提供通讯避免的设计与优化方法，提高高性能计算实际应用的效率。

中文关键词： 高性能计算；并行计算；计算机系统结构

英文摘要： As the gap between the computation and communication abilities of computing systems is larger and larger, the communication cost in performance and energy in the overall cost of algorithm execution is becoming dominant, so the communication avoiding of algorithm is very important for both the performance improvement and energy reduction of computing systems. Kernel algorithms in math library is very important for the area of high performance computing, this project mainly focuses on several important benchmarks in high performance computing, such as Top 500, Graph500, HPCG etc, and researches on the design and optimization of communication avoiding of kernel algorithms in these benchmarks. This project aims to investigate from the following three important problems. First, to construct practical model of parallel computation and communication, to reflect the latest characteristics of computer architecture, and determine the parallel communication complexity of some kernel algorithms under the framework of constructed model. Second, to design communication avoiding algorithm to attain or approach the lower bound of the determined communication complexity. Third, on existing mainstream architectures, to implement and optimize the designed communication avoiding algorithms. Through the investigation of this project, we can provide methods on the design and optimization of communication avoiding for some kernel algorithms in math library, and enhance the efficiency of practical applications in high performance computing.

英文关键词： High Performance Computing;Parallel Computation;Computer System and Architecture