文献阅读-GPU性能估计框架

博主 2383 2021-10-24

文献名称:A Hybrid Framework for Fast and Accurate GPU Performance Estimation through Source-Level Analysis and Trace-Based Simulation
发表于 2019 IEEE International Symposium on High Performance Computer Architecture (HPCA)

这篇文章提出了一种框架用来预测GPU执行时间,其用于评估运行在GPU上的OpenCL内核的性能。方法:对内核执行流进行静态分析,然后通过基于循环的双向分支搜索生成执行的trace。然后动态模拟trace以生成内核的虚拟执行来获得估计时间。文章实验部分说明作者提出的方法在预测阶段开销只有几秒,能获得平均绝对百分比误差为17.04%的运行时性能。

Introduction部分:

动机:文章提到为了充分利用GPU性能,程序员需要对GPU并行原理有比较深的理解才能写出高效程序。但有的非专业用户也想把GPU用好,但是对并行不甚了解。对于此有两种解决方案,auto-tuning 和 performance estimation。

我缺乏这方面背景,所以对这两种方案解决的痛点不太了解。为啥这两种方法能解决上面提到的帮助非专业用户使用GPU的问题?

作者解释说auto-tuning由于需要使用全局/切片的design space,时间开销大,所以选择了performance estimation方法。

目前GPU性能预测模型的劣势:

  1. 模型的目标程序多变,需要为每个不同的应用调整参数,难以设计通用预测模型。
  2. 性能模型难以跟进GPU体系结构的改变。
  3. 细粒度模型能够给出准确性能估计,但时间开销极大,实用性差。

改进:
提出一种混合框架,基于OpenCL工作负载,评估GPU上并行程序性能。将高级内核源代码转换为LLVM IR,根据GPU的并行思想生成程序执行轨迹trace。开发了轻量级模拟器,在32个工作项(或被称为warps)的粒度下,动态地跟踪执行过程中算术和内存访问操作。

工作贡献:

  1. 提出了一个混合框架,结合源代码分析和基于trace的仿真来预测GPU内核的性能。目标内核的执行trace是静态生成的,然后进行模拟估计运行时性能。
  2. 提出了一种基于循环的双向分支搜索算法来提取内核执行trace,该trace模拟了GPU内核的warp执行流。
  3. 开发了一个轻量级的模拟器来模拟内核的执行,然后预测运行时的性能结果,同时考虑了IR指令管道和cache建模。该模拟器可以在几秒钟内准确预测运行在不同GPU平台上的内核的性能。
  4. 通过Rodinia基准测试和一个真实的应用程序,在4个英伟达gpu上展示了框架的准确性和实用性。

框架概述

框架整体结构:
image.png
首先,源代码经过LLVM/Clang编译为二进制LLVM IR指令,同时源代码通过NVCC编译,获取详细的运行时资源使用情况在内的内核编译信息(例如share memory使用size,片上寄存器使用个数)。源代码分析模块由LLVM analyzeKernel Pass完成,二进制的LLVM代码经过LLVM analyzeKernel Pass处理,随后从内核运行时行为分析中获取执行trace。analyzeKernel pass在基本块中对IR指令剪枝,只保留对内核执行时间有贡献的算术和内存访问操作。执行流信息(如循环语句和分支)将被提取并分析,以用于后续的执行trace生成。

根据控制流图(CFG)和执行流信息,分析内核运行时行为,生成以wrap为粒度的执行轨迹trace。随后,根据cache规范和trace,获取缓存是否命中的信息。仿真模块通过构造IR指令管道并迭代地根据trace来模拟内核运行时的行为。还有一些微基准用于校准目标GPU的执行,如算术操作的延迟、内存访问操作的延迟和cache配置。这些硬件指标,以及硬件规范、内核编译信息、内核执行trace和cache缺失信息,都被提供给模拟器,以估计最终的执行时间。

源代码分析:

A. LLVM analyzeKernel pass
analyzeKernel pass收集基本block来构建目标内核的控制流图。对于每个基本块,记录IR指令来构造块内执行trace。用于生成执行trace的执行流信息是通过如下所示的三个步骤获得的。

  1. IR指令剪枝:假定执行时间主要由算术和访问操作组成。因此去除掉其他时间消耗无关的指令,比如LLVM内部注释指令等。
    关于函数调用,因为函数调用只在某些特定时候出现,而原代码中调用某个子函数被一个详细的指令替换,因而二进制文件中并不存在子函数。只记录关于函数调用的相关信息,用以在一些时候帮助trace的生成。
  2. 循环边界分析: 首先使用Loopus方法来分析循环边界。当循环变量是固定常数时,Loopus可以处理。更复杂的情况时,通过对循环中的基本block执行LLVM标量演化(Scalar Evolution)分析来确定循环的边界。当Loopus和LLVM SE分析都不能给出输出时,对循环进行额外的静态分析,以进一步获取循环边界。这种静态分析的主要思想是识别循环诱导变量,并跟踪其在整个内核函数范围内的值。关于如何识别诱导变量,作者根据LLVM IR的一些形式上的特点,例如指令的形式、结构和参数等,对所有的情况做了处理,并得出循环边界的估计。
  3. CFG分支提取:分析每个分支路径的头和尾basic block中的phi和br指令来提取每个分支的触发条件。因为br指令与cmp指令关联,可以从中推断出分支条件。

B. Runtime Behavior Analysis

  1. 基于Warp分支分析:分支条件可能命中或miss,以warp的粒度进行分析分支命中情况。因为分支条件变量的值只有3种,在3种情况下基于一些假设,将分支条件命中与否作出决定。
  2. 执行轨迹生成:能力所限,我基本上看不懂。
  3. 缓存行为分析:首先使用micro-benchmarks来获取一些cache的参数,例如本地内存访问的缓存hit和miss的时延。因为OpenCL中的本地内存映射到GPU的共享内存,本地内存访问没有cache机制。如果是常量或者全局内存访问时,存储管理器首先从常量cache或者L2 cache中拉数据,如果没有就去片外DRAM拉数据。基于此,在模拟的时候需要对缓存行为建模,文章假定缓存使用LRU替换,对于memory access,在执行trace时,模拟一个常数和L2缓存的虚拟寻址空间,根据数据大小分配空间中的地址。这样在给定缓存配置下估计内存访问的缓存命中状况。

基于trace的模拟行为

A. IR 指令流水线

  1. 确定活动工作组的数量:每个流式多处理器(Streaming Multiprocessor)的活动工作组数量由3个条件决定:架构限制、寄存器限制和共享内存限制。这些限制条件决定的工作组数量是可以通过数学表达的,分别表示3种条件下工作组的数量,再取最小值。
  2. 确定算术和内存访问操作的延迟:通过OpenCL micro-benchmark测量目标GPU的算术和内存操作延时。对于一组规定的数据操作,例如整数的add、sub,浮点数的sin、cos等,分析他们在OpenCL本地内存、常量内存、全局内存访问上的延迟情况。

B. 计算trace模拟时间
给定内核执行轨迹T,算术和内存访问操作的延迟LAT,以及跟踪中的缓存丢失信息cacheMissInfo来开发一个轻量级模拟器,其使用一轮活动工作组Nawg操纵内核的虚拟执行。其预测的内核执行时间为
image.png

实验部分

使用4种商用GPU:Quadro K600,Quadro K620,GeForce GTX645,GeForce 940M。实验结果如下图:
image.png
实验结果表明:4个GPU上的平均MAPE为17.04%。注意到当内核执行时间很短时(核函数nw_kernel1 and nw_kernel2),预测时间与实际时间出入较大,因为在这种情况下,内核开销占比太大,但内核开销的时间(Wrao调度,内核启动,资源调度等)是不可预测的。对于分支预测性能,例如bpnn adjust weights函数,其流程有大量依赖于线程ID的分支和嵌套分支,由于预测的路径覆盖了尽可能多的分支,会造成预测时间高估。

总的来说,该混合框架在测试集上表现良好,能够跟踪内核执行时间变化趋势。在与其他细粒度模拟器相比,论文提出的框架执行时间要少很多,在测试集上平均0.931秒内给出预测结果。