【论文解读】A Note on Auto-tuning GEMM for GPUs

[ysh329]

• https://www.researchgate.net/profile/Stanimire-Tomov/publication/262407593_A_note_on_auto-tuning_GEMM_for_GPUs/links/0c9605283fb55e1dd0000000/A-note-on-auto-tuning-GEMM-for-GPUs.pdf

• A Note on Auto-tuning GEMM for GPUs

• 作者：Y Li，J Dongarra，S Tomov

• 摘要：The development of high performance dense linear algebra (DLA) critically depends on highly optimized BLAS, and especially on the matrix multiplication routine (GEMM). This is especially true for Graphics Processing Units (GPUs), as evidenced by recently published results on DLA for GPUs that rely on highly optimized GEMM. However, the current best GEMM performance, e.g. of up to 375 GFlop/s in single precision and of up to 75 GFlop/s in double precision arithmetic on NVIDIA's GTX 280, is difficult to achieve. The development involves extensive GPU knowledge and even backward engineering to understand some undocumented insides about the architecture that have been of key importance in the development. In this paper, we describe some GPU GEMM auto-tuning optimization techniques that allow us to keep up with changing hardware by rapidly reusing, rather than reinventing, the existing ideas. Auto-tuning, as we show in this paper, is a very practical solution where in addition to getting an easy portability, we can often get substantial speedups even on current GPUs (e.g. up to 27% in certain cases for both single and double precision GEMMs on the GTX 280).

• 关键词：Auto-tuning matrix multiply dense linear algebra GPUs

[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 CPUs

在谈及GPU前，最早开始自动化调优的是CPU，全称为Automatic performance tuning (optimization)，最早也是应用在计算密集型的代数计算库如ATLAS、PHiPAC等BLAS计算库，此外也有用于数字信号处理领域的FFTW库。

auto-tuning在实现方法上有两种，模型驱动优化（model-driver optimization）和经验优化（empirical optimization）：

• 模型驱动优化：来自编译器的思想，即从高级别语言如C/Fortran代码转为机器码的过程中的变换操作（transformation），如循环分块（loop blocking）、循环展开（loop unrolling）、循环排序（loop permutation），融合（fusion）、distribution、预取(prefetching)、软件（software pipeline）等。而这些变换操作的参数如block size，展开的系数是通常由编译器中的分析模型（analytical model）来确定。其特点是有效，但不针对特定问题最初最佳的优化。

  造成这个原因，本质上也是分析模型（analytical model）源自编译器对底层处理器架构的高度简化抽象，需要足够对所有程序可用即高度通用性。

• 经验优化：经验优化则是在给定的算法下，生成巨量的参数化候选代码，其缺点便是需要花时间搜索最佳性能的代码实现。

即模型驱动优化只需要O(1)时间，因为参数的确定是基于分析模型，一种自然而然的想法是结合两种个特点，即在第一阶段用分析模型来限制第二阶段经验优化的巨量参数化搜索。

除上面说的以外，auto-tuning的适应性也需要强调，即最优计算的kernel可以在安装的时候被生成，即平台适应性，这个过程可以在软件安装过程获取硬件信息，从而在安装时根据这些信息来做相应的尝试与编译，安装完成及得到该平台下的最优kernle实现。

[ysh329]

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：分块大小；
• tx、ty：线程块分配的x和y方向的线程大小；
• trans_A：是否对shared memory中的矩阵分块BA做转置。

在模板的代码生成阶段也有相应限制：

1. 硬件限制：一个线程块内的线程数量不能超过512；
2. 分块的大小对于线程块的线程分块，是可以计算完成的，即(tx × ty)%BK = 0, BM%ty = 0, and BN%tx = 0。

性能

下图是CUBLAS2.0与auto-tuned的SGEMM实现的GFlops性能对比，矩阵为方阵维度为NxN，其中能看到二者性能非常接近，因为kernel实现上，作者是基于CUBLAS2.0实现增加了auto-tuned的机制（Our SGEMM）。整体看，平均性能auto-tuning的更好一些。

图：CUBLAS 2.0与auto-tuned的SGEMM(左)与DGEMM(右)对比

总结和未来方向

其实文章主要是说，GEMM的Auto-tuning优化工作，其特点是在新架构上的支持性，以及可以针对已高度优化的kernel再次提升性能。