ysh329

# A Note on Auto-tuning GEMM for GPUs 这篇文章是2009年1月12日发表的，作者是Yinan Li、Jack Dongarra、Stanimire Tomov。本文的工作是由于作者受CPU的Auto-tuning启发，在GPU上提出模板化kernel的方式来做自动化调优。 对GPU的性能调优比方GEMM，都需要一定的GPU专业知识、深入理解其架构特点，而这些往往不是能从文档上看到的。为解决这个问题，因而作者提出在当前的GPU上引入Auto-tuning。 在这之前，AMD、Intel、IBM、NVDIA都在未来微处理架构和大规模的HPC系统上做了很多工作，一般 来说大规模的HPC系统有两个组成： 1. 多核技术。持续增加核心数量，避免陷入功耗墙（power wall）、指令集级别的并行墙（instruction leecl parallelism wall）、内存墙（memory wall）等； 2. 特定目的的硬件或加速器，比方GPU。 在未来对高性能计算架构的这两种组件的占比上，也并不明晰，可能未来会有更多异构的硬件组成。但，新兴的体系结构推动了新算法的开发，这些算法的设计空间比以前需要的要大得多，举个例子，原本早期的autotuner仅限于BLAS，而且基于一定数量的参数如分块大小，来获取尝试的参数空间，在引入多核前也确实能在足够达到还不错的性能。但当前环境下，新硬件新架构层出，本文也是想通过GEMM Auto-tuning，来加快对GPU的新特性如双精度下的计算支持，而且也加快算法最初的设计。新硬件环境、体系结构是一方面，同一问题的不同规模大小，也需要进行相应调整，所以最好是自动调优。 ------ ## Auto-tuning for...

## GEMM Autotuner for GPUs 作者基于NVIDIA GPU来完成这部分工作，这里的autotuner是指：auto-tuning系统，即一个包含了自动生成、并能搜索算法空间的系统。 - 代码生成器：生成不同参数变体下的代码，生成器是预设的代码模板； - 参数搜索引擎：评估不同实现，得到耗时和最优实现。 因为本文集中在GEMM Kernel即`C=αA×B + βC`的优化，所以下面给出其计算示意图： **图：GEMM计算示意图** 矩阵A为M行K列，矩阵B为K行N列，矩阵C为M行N列，而M、N、K可以被BM、BN、BK整除，作者对齐做了补0操作以支持BM/BN/BK的整除对齐。 计算过程矩阵A、B、C被分成各自独立的BA、BB、BC，`B`在这里为分块(block)的含义。如上图第一行中矩阵A最浅色的矩形映射到第二行。 矩阵C的BM×BN分块由一个线程块内的`tx × ty`完成，每次计算迭代，矩阵A上的BM×BK维度的BA块会先搬到片上的shared memory上，然后直到BC完全被计算完。而矩阵C和矩阵B则一直在global memory里，在计算过程中则是将BB从B的global memory中代入片上寄存器中完成计算。作者指出，现代GPU的每个处理器都有容量很大的寄存器文件，大量的计算足以在寄存器中完成。 因为shared memory被划分为多个内存块即banks，在GPU多线程访问下同时对同一个内存块访问容易导致bank冲突，而对矩阵分块的BA在shared memory做转置可以减少bank冲突的可能性，对BA转置也进一步提升了性能。 因此，GEMM的代码模板中有6个参数： - BM、BK、BN：分块大小；...

## 2.1 策略一： TuningType::FAST （通用） 通用FAST策略的代码比较简单。可以看出按照z、x、y的顺序依次设置work group： 1. 首先，找z方向的local work size，找寻过程是来找grid.z（即z方向的global work size）最大能被`max_divisor`（默认为8）整除的数。从8往下找，若grid.z能被8整除则8就是z方向的local work size，否则再尝试4、2，如果都不满足则以传入的max_divisor作为上界往下找； 2. 当z方向确定了，则就有x和y方向的local work size的乘积上限也确定了。即使用`kernel_info.max_work_group_size`，，每个CLKernel对象都有一个`struct KernelInfo`包含了`private_memory_size`和`max_work_group_size`，当[`CLKernel::CreateFromProgram`执行时](https://github.com/tensorflow/tensorflow/blob/0a7a6220981cedb1cdaf858a563e73aeae90543b/tensorflow/lite/delegates/gpu/cl/cl_kernel.cc#L104-L124)，这二者均是通过查询OpenCL内置的`CL_KERNEL_PRIVATE_MEM_SIZE`和`CL_KERNEL_WORK_GROUP_SIZE `信息分别获取到每个work item的private mem，以及GPU设备最大支持的work group，来除去刚得到的z方向的local work size； 3. 确定x方向的local work size。用grid.x除以2并向上取整，与wg_xy_size比较大小，取小的作为x方向的local...

## 2.2 策略二： TuningType::EXHAUSTIVE 这个TuningType没有Conv的特殊版本，这个方法EXHAUSTIVE，英文即为精疲力竭地，也就是穷举搜索所有可能找出最佳，相比Fast复杂了很多。 ```cpp void GetWorkGroupsAlignedToGrid(const DeviceInfo& device_info, const KernelInfo& kernel_info, const int3& grid, std::vector* work_groups) { int3 max_wg_size; max_wg_size.x = device_info.max_work_group_size_x; max_wg_size.y = device_info.max_work_group_size_y; max_wg_size.z = device_info.max_work_group_size_z;...

该方法进入时，会先获取KernelWorkGroups，注意是一个候选表`std::vector possible_work_groups`，然后在最后if-else分支的else情况中，选择这些里最好的best_work_group_index，作为当前Operation最终的work_group。 ```cpp // delegates/gpu/cl/kernels/gpu_operation.cc // https://github.com/tensorflow/tensorflow/blob/b14150088dac1924cf0482f6e456332b3e6211ff/tensorflow/lite/delegates/gpu/cl/kernels/gpu_operation.cc absl::Status GPUOperation::Tune(const TuningParameters& params) { std::vector possible_work_groups; GetPossibleKernelWorkGroups(params.tuning_type, *params.info, kernel_.info_, &possible_work_groups); if (possible_work_groups.empty()) { return absl::NotFoundError( "Can not found work_group size to launch...

## 2.2 继续主线 //当没有检查内核边界时，我们需要精确 //如果有检查，精确或无需校准都可以。 ```cpp // tensorflow/tensorflow/lite/delegates/gpu/common/workgroup_selection.h // https://github.com/tensorflow/tensorflow/blob/b5d2374f5e21ff0aa44ac26b039336d7443d08e3/tensorflow/lite/delegates/gpu/common/workgroup_selection.h#L28 // PRECISE assume that WorkGroupSize * k = GridSize; // NO_ALIGNMENT no restrictions; // We need PRECISE when we don't...

```cpp // tensorflow/tensorflow/lite/delegates/gpu/common/workgroup_selection.cc // https://github.com/tensorflow/tensorflow/blob/master/tensorflow/lite/delegates/gpu/common/workgroup_selection.cc#L30-L87 template void AddCornerCases(const T& grid, int max_work_group_total_size, const T& max_work_group_sizes, WorkGroupSizeAlignment x_alignment, WorkGroupSizeAlignment y_alignment, WorkGroupSizeAlignment z_alignment, std::vector* work_groups) { for (int x = 1; x...

## 2.3 策略TuningType::FAST->GetWorkGroupConv ```cpp void GetPossibleWorkGroupsConv(TuningType tuning_type, const DeviceInfo& device_info, const KernelInfo& kernel_info, const int3& grid, std::vector* work_groups) { switch (tuning_type) { case TuningType::FAST: { int max_z_size = 16; if...

## 3. 选择最优候选work group ```cpp // delegates/gpu/cl/kernels/gpu_operation.cc // https://github.com/tensorflow/tensorflow/blob/b14150088dac1924cf0482f6e456332b3e6211ff/tensorflow/lite/delegates/gpu/cl/kernels/gpu_operation.cc absl::Status GPUOperation::Tune(const TuningParameters& params) { std::vector possible_work_groups; GetPossibleKernelWorkGroups(params.tuning_type, *params.info, kernel_.info_, &possible_work_groups); if (possible_work_groups.empty()) { return absl::NotFoundError( "Can not found work_group size...

上次说如何查看看android gpu是否在使用，通过查看/proc/interrupts中gpu中断的引用计数是否增加，但是我这里在手机上没看到有gpu的列