基于多核平台SpMV并行技术研究

论文摘要

目前各个领域都有大量的多核体系结构处理器投入使用,从手机芯片到超级计算机,多核体系结构都占据着越来越重要的地位。多核已经成为了当今处理器体系结构发展的主流和趋势。在高性能计算领域,多核处理器平台的潜力并未充分发掘出来。为了使得具有更高并行度需求的应用能充分利用多核处理器提供的强大计算能力,非常有必要对不同应用中的各类算法针对多核结构进行研究。稀疏矩阵向量乘（Sparse Matrix-Vector Multiplication, SpMV）作为多类科学计算过程不可缺少的一部分,其计算效率对科学计算程序的最终性能有着重要的影响。本文以SpMV为例,研究数值算法在多核平台上的性能优化过程,主要的工作如下：1、研究了现有的SpMV优化的方法,分析了各种方法的特点及适用范围,重点关注了数据存储结构和线程优化两方面；2、研究了多核处理器的体系结构,分析体系结构中对并行计算性能的重要影响因素,尤其是存储结构对并行计算性能的影响；3、设计了一种线程与处理器内核问的绑定方案,详细阐述了具体的方法及该方案的实际意义；4、提出了一种线程划分方案：该方案可增强线程间的数据共享关系,同时结合线程绑定技术,可提高SpMV的二级缓存命中率,进而提高SpMV的计算效率；以国际上公认的矩阵测试集为基准程序,同时利用PAPI工具访问硬件性能计数器,获取程序的二级缓存失效等性能数据,对本文提出的方案进行了实验验证；数值试验表明,合理的线程绑定可以提升程序执行的性能；而本文提出的线程划分方案,也提高了SpMV计算性能。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 课题背景介绍
• 1.1.1 多核时代到来
• 1.1.2 数值并行计算
• 1.1.3 多核平台SpMV优化
• 1.2 国内外研究的现状
• 1.2.1 多核处理器研究现状
• 1.2.2 数值并行算法研究现状
• 1.2.3 多核平台SpMV优化研究现状
• 1.3 论文主要工作和文章结构
• 第二章 主要优化方法研究
• 2.1 数据存储结构
• 2.1.1 稠密格式
• 2.1.2 坐标格式
• 2.1.3 CSR格式
• 2.1.4 BCSR格式
• 2.1.5 对角格式
• 2.2 线程级优化
• 2.2.1 线程划分
• 2.2.2 线程同步
• 2.3 Cache与本地存储划分
• 2.4 其他优化方法
• 2.4.1 寄存器划分与格式选择
• 2.4.2 TLB划分
• 2.4.3 索引尺寸
• 2.4.4 循环优化
• 2.4.5 软件预取
• 2.5 本章小结
• 第三章 多核平台与矩阵测试集
• 3.1 多核平台的特征
• 3.1.1 Cache结构
• 3.1.2 核间通信
• 3.2 Intel Clovertown平台
• 3.3 矩阵测试集
• 3.3.1 矩阵测试集
• 3.3.2 矩阵结构对性能的影响
• 3.4 本章小结
• 第四章 优化方案设计
• 4.1 线程绑定方案设计
• 4.1.1 方案设计依据
• 4.1.2 方案设计过程
• 4.2 SpMV优化方案设计
• 4.2.1 方案设计依据
• 4.2.2 方案设计过程
• 4.3 本章小结
• 第五章 优化方案实现与验证
• 5.1 实验环境与工具
• 5.1.1 内核位置与绑定
• 5.1.2 缓存数据查看
• 5.2 线程绑定方案实现与验证
• 5.2.1 实验设计过程
• 5.2.2 实验测试结果
• 5.2.3 实验结果分析
• 5.3 SpMV优化方案实现与验证
• 5.3.1 实验设计过程
• 5.3.2 实验测试结果
• 5.3.3 实验结果分析
• 5.4 本章小结
• 第六章 总结与展望
• 6.1 工作总结
• 6.2 工作展望
• 致谢
• 参考文献
• 作者在学期间取得的学术成果