GPGPU/GPU 性能模型

在多核领域,GPU因为其提供的可观的线程并行性和超大的数据吞吐量而越来越受人瞩目。虽然GPU可以提供数以千计的线程并行性,但对这些线程程编程面临很大的挑战。为此专门面向多线程编程的语言应运而生,比如CUDA,OpenCL,尽管这些语言可以可以部分减轻程序员的工作,提高效率,但是能够充分理解GPU的架构特性以及GPU程序的性能瓶颈仍然需要程序员做很多的工作。更具有挑战性的是,在理解GPU上并行编程的性能瓶颈的基础上根据瓶颈来提高性能。现在的普遍做法是依靠程序员不断调优,但是这样做显然没有充分理解GPU程序的特点,并且程序员不可能穷尽所有的配置来找到最优的配置。

为此研究人员今年来进行了大量的研究;为了给GPU程序提供性能瓶颈的指导,文章An Analytical Model for a GPU Architecture with Memory-level and Thread-level Parallelism Awareness提出一种简单估算GPU并行程序执行时间的模型,该模型通过正在运行的线程数量和内存带宽来估计内存请求的并行度(又称为memory Warp的并行度),基于内存请求的并行度来估计内存请求的代价,因为整个程序的运行时间取决于访存的延迟,从而估计整个程序的运行时间。(如果篇幅不够,此处可以详细讲解文章内容)通过和真实程序的运行时间比较,该模型对micro-benchmarks的平均误差在5.4%,对于GPU computing 程序是13.3%。文章 【A Performance Analysis Framework for Identifying Potential Benefits in GPGPU Applications】提出一种称之为 GPUPref的性能预测和寻找瓶颈的性能模型,该模型是上一篇文章中MWP-CWP方法的加强版,该模型提供一种方法,这种方法将通过性能模型的不同组成部分跟踪到的数据联系起来寻找程序瓶颈。
文章【An Adaptive Performance Modeling Tool for GPU Architectures】提出一种GPU性能模型用来指导编译器优化程序,通过一种称之为 work flow graph的技术预测程序的执行时间。以上文章把研究重点集中的预测程序的执行时间上,而文章 【A Quantitative Performance Analysis Model for GPU Architectures 提出一种基于microbenchmark】的性能分析模型,该模型集中精力寻找程序的瓶颈,并且通过量化的方式指导程序员优化程序,该模型包括三个部分:指令流水线,对共享内存的存取,对全局内存的存取。该文章还详细阐述了怎样从模型的三个部分来指导程序员和架构师对程序和架构进行优化。

GPU Warp内的线程如果遇到不同的分支,以CUDA编程模型为例,那么warp内的线程将会线性执行,如果一个warp内有32个线程,那么最坏情况下这个warp要32个cycyle才能执行完毕,所以控制分支会严重的影响GPU程序的并行性。为此文章 【Dynamic Warp Formation and Scheduling for Efficient GPU Control Flow】 提出一种基于硬件的动态warp重组机制,(Figure 9. )演示了动态重组的warp的一个例子,图中每个长方形w0、w1表示一个执行周期,在上方的图中因为遇到分支,每个warp分成两个两个执行周期执行,这显然没有充分利用GPU的器件;运用了动态warp分支重组机制的下图,则将W0,W1的四个分支重组为两个warp,从而提高了程序的性能。文章 【Streamlining GPU Applications On the Fly—Thread Divergence Elimination through Runtime Thread-Data Remapping】 通过内存请求重定向和改变输入数据的顺序两种方法来减少分支,如文章中 Figure 3所示,图a是原始的warp执行;图b是通过内存请求重定向而执行的warp,这种方法将执行在同一个分支的warp2取用相同类型的数据,从而填满真个warp,该方法的一个缺陷是有可能打乱一个warp内部的访存融合,从而使得原来可以被融合的访存现在不得不发出多个访存请求;图3是用物理的交换数据顺序使得相同的执行分支使用相同类型的数据,这项工作是有host端(CPU)来完成的,当然会有一些代价,但研究表明交换数据顺序的代价可以被GPU kernel call掩盖。文章【Reducing Thread Divergence in GPU-based B&B Applied to the Flow-shop problem】 将Branch and Bound(B&B )算法应用在GPU上,为解决分支问题,该文章提出数据重排和分支重构的方法。文章【Reducing Branch Divergence in GPU Programs】提出两种方法:迭代延迟和分布式分支来减少分支。

文章 【An Accurate GPU Performance Model for Effective Control Flow Divergence Optimization】,该文章提出一种精确的GPU性能模型,其在传统的data layout transformation的基础上提出一个分析指标,该指标结合基本块向量(BBV)和基本块的指令pc(basic block instruction count)来衡量一个分支的重要程度,这样在执行不同的分支消除算法的时候就可以首先消除那些对程序整体性能影响较大的分支,从而可以达到提高程序整体性能的目的。 而文章 【Dynamic Warp Subdivision for Integrated Branch and Memory Divergence Tolerance】则不试图消除分支,而是在遇到分支的时候,将原来的warp分成两个小于SIMD宽度的两个分支交替执行,从而达到掩盖访存延迟的目的。该文章同时指出,对于同一个warp中需要访问具有不同访存延迟的线程,同样可以将该warp分割,使具有相同访存延迟的线程作为一个warp,从而和其他warp交替执行。

文章【An Integrated GPU Power and Performance Model】提出一种功耗和性能模型,该模型可以在给定一个程序的情况下预测需要使用多少个SM核来运行该程序,因为当内存带宽到达极限的情况下即使将所有核都用来运算也不能改善程序的性能,反而会增加整个GPU的功耗。