基于异构体系结构的稀疏矩阵分解算法并行化研究

Sparse matrix factorization is the core algorithm and the most computationally intensive component in solving large sparse linear systems in the field of scientific and engineering computing. The recent use of heterogeneous computing platform to accelerate sparse matrix algorithm shows the potential to achieve significant acceleration relative to desktop performance. However, sparse matrix factorization on heterogeneous computing platform has not been explored sufficiently due to the large degree of task and data dependencies and highly irregular memory access patterns. The aim of our project is to accelerate the sparse matrix factorization process, with full consideration of both algorithm and architecture design. Based on the analysis of the algorithm parallel technology on computing platform with the CPU-GPU and the CPU-MIC general heterogeneous architecture, we would design and construct the FPGA-based reconfigurable accelerator. On the basis of the above research, we will built a hybrid heterogeneous computing platform with three types of accelerators, including GPU, MIC and FPGA. Different sub-process of the sparse matrix factorization process will be mapped to different computing units according to its computational characteristics, in order to accelerate the process of sparse matrix factorization and enhance its adaptability.

稀疏矩阵分解是科学与工程计算领域求解大规模稀疏线性方程组的核心算法，也是求解过程中最耗时的部分。近年来，一系列稀疏矩阵算法通过异构体系结构平台获得了显著的加速比，然而，由于任务间大量数据依赖关系以及访存的不规则，面向异构体系结构的稀疏矩阵分解算法研究存在计算效率低、并行性能低等问题。本项目以稀疏矩阵分解为研究对象，从并行算法设计和体系结构设计两方面出发，在研究CPU-GPU和CPU-MIC两类通用异构体系结构计算平台上的算法并行化设计的基础上，设计并实现基于FPGA的可重构算法加速器，进而构建包含GPU、MIC和FPGA三种不同特性的算法加速器的混合异构体系结构计算平台，实现不同计算单元的体系结构特征与稀疏矩阵分解不规则计算特征的适配，从而有效提高稀疏矩阵分解算法的计算性能和适应性。

稀疏矩阵分解是科学与工程计算领域求解大规模稀疏线性方程组的核心算法，也是求解过程中最耗时的部分。由于任务间大量数据依赖关系以及访存的不规则，面向异构体系结构的稀疏矩阵分解算法研究存在计算效率低、并行性能低等问题。.项目以稀疏矩阵分解为研究对象，从并行算法设计和体系结构设计两方面出发，在研究通用异构体系结构计算平台上的算法并行化设计的基础上，设计基于FPGA的可重构算法加速器，进而实现不同计算单元的体系结构特征与稀疏矩阵分解不规则计算特征的适配，从而有效提高稀疏矩阵分解算法的计算性能和适应性。.项目针对稀疏矩阵分解算法的数据相关性和存储访问特征，面向GPU和FPGA异构平台提出了资源受限条件下的数据相关性转换、负载平衡的任务划分和存储调度策略，设计了并行计算结构，对稀疏矩阵算法实现了细粒度并行和硬件加速。综合采用可变粒度运算单元、数据驱动的循环展开执行、不规则访存优化技术，构建了异构计算平台，并以CPU为参照，对并行算法的性能进行分析和评估。研究结果表明，与同构计算平台相比，异构计算平台对稀疏矩阵分解算法具有显著的加速效果。