论文部分内容阅读
当前，图形处理器（GPU）广泛应用在图形图像处理、科学计算、多媒体应用、数据挖掘、金融计算等众多科学和工程领域。GPU采用单指令多数据（SIMD）架构，非常适合规则的应用程序。但是，未来应用程序中普遍包含不规则的计算和访存模式，这些模式极大地限制了GPU的资源利用效率和性能提升。不规则应用程序的特点体现为任务分配不均衡、控制流程分支多、访存地址分布不规则并且不能静态预测以及数据的时间和空间局部性差等，如何提高这些不规则应用的运算性能成为当前GPU计算领域亟待解决的问题，本文针对GPU应用中的不规则模式展开算法和体系结构的研究，主要贡献包括如下四个方面：（1）分析了三种应用广泛的不规则模式的性能瓶颈，提出了针对这些模式的专有优化算法。其中，针对稀疏矩阵向量乘问题，提出了数据填充的方法消除不规则的访存；针对字符串匹配问题，分别提出了数据段划分和数据重排的方法改善任务分配不均衡和消除不规则的访存；针对QR分解问题，提出了流水线式并行的方法，极大地提高了算法的并行度。与多核CPU相比，经过优化处理的计算模式及其应用能够取得数十倍以上的性能改善。（2）系统分析了众多不规则应用程序在GPU上的执行特点，指出了GPU架构在处理不规则应用时的不足。一方面，不规则应用中的各个线程访问内存时，访存延时差异大，不均匀的内存访问延时阻塞计算单元的运行，造成了计算单元使用效率低；另一方面，当前的缓存管理方法简单，不能够适应众多线程访存不规则的特性，因此，数据复用率差，缓存命中率低。（3）分别提出了基于有效地址优先级的缓存管理算法（EABP）和基于分支特性的内存调度算法（DAMS），这两种架构优化技术提高缓存命中率（20%）同时减少不均匀的访存延时，能够取得30%以上的系统性能改善。（4）针对流处理计算模式中任务分配不平衡的问题，提出了一种资源动态分配的硬件调度机制。该机制通过实时监测各个任务的计算量，动态地调节分配给各个任务的计算资源，提高不规则任务的计算资源利用率，并且利用任务间数据流动的特性优化了缓存设计。实验结果显示与现有GPU的成熟调度算法相比，该调度算法能获得20%以上的系统性能提升。