如何对GPU中的矩阵乘法（GEMM）进行优化
本篇文章主要是介绍如何对gpu中的矩阵乘法（gemm）进行优化。目前针对gemm的优化，网络上已经有非常多的教程和示例了。大部分的重要资料我都看了看。但总的来说，还是不够接地气，然后理解起来还是会比较费解。所以希望写这么一篇文章，尽可能地去把gpu的gemm优化说清楚，说明白。然后让小白读者也能通过这么一两篇文章去更好地了解gemm优化的相关技术。
不像上次的reduce优化一样，能一篇文章说完。这次的gemm优化会分为三个部分。第一个部分只说优化思路和分析，没有任何代码，这么做考虑也是为了减轻读者的负担，看代码太累， 尽可能地让读者先明白原理，为什么要这么做。第二个部分是对代码的详细解析，这个里面就是一行一行地去分析代码。因为之前的很多博客进行了分析，但是代码本身并没有开源，或者说开源了代码，但没有解析，看起来太累了。我希望提供一个尽可能详细的代码解析，读者看完之后能明白相关优化技巧，并且可以直接把代码拿去验证使用。第三个部分主要涉及到汇编器，最重要的是说明在nv的卡上，怎么去解决寄存器的bank冲突来获取极致的性能。
本篇文章是gemm优化的第一个部分，在这篇文章中，只说优化思路和分析。
前言
在高性能领域，对于矩阵乘（gemm）的优化是一个非常重要的课题。gemm可以非常广泛地应用于航空航天、流体力学等科学计算领域，这也是之前hpc的主要应用场景。后来深度学习开展地如火如荼，由于对高算力的需要，也成为hpc的主要应用场景之一。这些年涌现了一系列的深度学习模型。模型里面最耗时的东西，包括卷积、全连接层、attention，都可以转换成gemm操作。所以说，gemm优化的重要性，怎么突出都不过分。
目前网上能找到的针对gemm优化的资料主要有这么几个方面：（1）论文，目前针对gpu进行gemm优化的论文非常多，这里主要推荐understanding the gpu microarchitecture和fast implementation of dgemm on fermi gpu以及dissecting the nvidia volta gpu architecture via microbenchmarking。这几篇论文在业界都比较有影响力，就是代码开源方面做的不算太好。（2）官方博客，主要是cutlass和nervanasystems-sgemm优化。还有前段时间旷视发的文章cuda矩阵乘法优化，写的都很详细。（3）github的一些demo，代码量不大，看起来比较舒服。我是看了这两个：
demo1 ：
https://github.com/cjkkkk/cuda_gemm
demo2 ：
https://github.com/yzhaiustc/optimizing-sgemm-on-nvidia-turing-gpus
demo1代码写的好理解一些，但是优化工作没做完全，没有做到prefetch。demo2是效果很好，11个优化技巧，不断逼近cublas。但是代码真的看起来比较难受，最重要的很多参数写死了，不好去调。 总而言之，目前列举的上述资料存在着这么两个问题：（1）文档方面，读起来还是比较费劲，对于小白来说，还是不够简单不够傻，看起来太累了；（2）代码方面，要么是没公开代码，要么是代码太多了，看不下去；还有的就是代码可读性很强，但是优化工作还不是特别深，或者就是代码优化做的很好，但是可读性差了。方方面面总是有点欠缺，所以希望能够写一篇尽可能地在文档上简单明了，在代码上详细且可读性好的文章。当然，这是一个逐步迭代的过程，所以这篇文章也会持续进行更新哈。 本篇文章主要是采纳了cutlass的行文思路，主要介绍gemm中的数据分块和如何在多级存储进行数据搬运。这也是hpc优化的核心思想，怎么样让数据放在更近的存储上来掩盖计算的延时，从而减少存储墙的影响。文章分为四个方面进行叙述，首先介绍在global memory层面如何进行分块以及数据搬运，随后介绍在shared memory层面如何进行分块以及数据搬运，而后介绍在register层面如何进行分块以及避免bank冲突，最后介绍如何进行prefetch以更好地掩盖访存时延。
一、从global memory到shared memory
假设有矩阵a、b，需要计算矩阵a和b的乘，即矩阵c。a、b、c三个矩阵的维度分别为 ，，，且三个矩阵中的数据都是单精度浮点数。对于c中每一个元素，c[i][j]，可以看作是a的一行和b的一列进行一次归约操作。采用最naive的gemm算法，在gpu中，一共开启 个线程，每个线程需要读取矩阵a的一行与矩阵b的一列，而后将计算结果写回至矩阵c中。因而，完成计算一共需要从global memory中进行 次读操作和 次写操作。大量的访存操作使得gemm效率难以提高，因而考虑global memory中进行分块，并将矩阵块放置到shared memory中。其示意图如下： 对global memory进行分块的gemm算法示意图见上图右侧。首先将a、b、c三个矩阵划分为多个维度为 ，， 的小矩阵块。三个矩阵形成 ，， 的小矩阵网格。其中，，，。随后在gpu中开启 个block，每个block负责c中一个维度为 的小矩阵块的计算。计算中一共有k次迭代，每一次迭代都需要读取a中一个维度为 的小矩阵块和b中一个维度为 的小矩阵块，并将其放置在shared memory中。因而，完成c中所有元素的计算一共需要从global memory中读取 ，即 个单精度浮点数。相比于naive的gemm算法，访存量减少为原来的 。通过global memory中分块算法极大地减少了对global memory的访存量。并且，相比于naive算法，对global进行分块可以更充分地利用数据局部性。在naive算法中，每一个线程都需要直接从global memory中取数，其时延非常长，计算性能非常差。而进行分块后，将维度为 ， 的小矩阵块先存储到shared memory之中。而后计算单元进行计算时可以直接从shared memory中取数，大大减少了访存所需要的时延。
二、从shared memory到register
随后，我们进一步考虑从shared memory到register的过程。在这里，只分析一个block中的计算。当进行k轮迭代中某一轮迭代时，gpu将维度为 ， 的小矩阵块存储到shared memory中，而后各个线程将shared memory中的数据存入register中进行计算。 在不对shared memory分块时，一个block中含有 个线程，每一个线程负责c中一个元素的计算。则一个block一共需要对shared memory进行 次读操作。而后考虑对shared memory进行分块，对 的小矩阵进行再一次划分，将其划分为多个维度为 的子矩阵。则一个block需要负责 个子矩阵。其中，，。随后，在一个block中开启 个线程，每个线程负责一个维度为 的子矩阵的计算。在计算中，一个block一共需要从shared memory读取 ，即 个单精度浮点数。相比于未分块的算法，对于shared memory中的访存量减少为原来的 。并且，由于将数据放入register中，可以直接对数据进行运算，减少了从shared memory中取数的时延。
三、register分块
在这里，我们考虑最后一层，即register中的计算，并且只分析一个thread。在完成以上的过程后，对于一个线程而言，它现在拥有： 个a矩阵的寄存器值， 个b矩阵的寄存器值，以及 个c矩阵的寄存器值。通过这些寄存器的值，需要计算个数。这需要 条ffma指令。 这个时候会涉及到寄存器的bank conflict。在nv的gpu中，每个sm不仅会产生shared memroy之间的bank 冲突，也会产生寄存器之间的bank冲突。这一点对于计算密集型的算子十分重要。像shared memory一样，寄存器的register file也会被分为几个bank，如果一条指令的的源寄存器有2个以上来自同一bank，就会产生冲突。指令会重发射，浪费一个cycle。ps：这个地方是从旷视的博客中看的。然后对于maxwell架构的gpu而言，bank数为4，寄存器id%4即所属bank。 我们假设对这个thread来说，、。并且计算c的寄存器以一种非常naive的情况分配，如下图左侧所示。则需要产生16条ffma指令，列举如下：
ffma r0, r16, r20, r0 ffma r1, r16, r21, r1 ……
可以从中看出，这会产生大量的register bank冲突，所以需要对参与计算的寄存器重新进行分配和排布,如上图右侧所示。在有些地方，这种方式也可以叫做register分块。
四、数据的prefetch
最后，我们来讲讲如何通过对数据进行prefetch来减少访存的latency。我们再来回顾gemm的过程，并且仔细地看看这个访存的latency到底是怎么导致的。对于一个block而言，需要计算一个 的矩阵块，这个时候需要进行k次迭代，每次迭代都需要先将来自a和b的两个小块送到shared memory中再进行计算。而从global中访存实际上是非常慢的，所以导致了latency。虽然gpu中可以通过block的切换来掩盖这种latency，但是由于分配的shared memory比较多，活跃的block并不太多，这种延时很难被掩盖。对于一个thread，需要计算一个 的小矩阵，但是必须先将数据从shared memory传到寄存器上，才能开始进行计算。所以导致了每进行一次迭代，计算单元就需要停下来等待，计算单元不能被喂饱。
为此，需要进行数据的prefetch来尽可能地掩盖这种latency。思想也比较简单，需要多开一个buffer，进行读写分离。示意图如下。当block进行第2轮迭代时，需要对a2和b2进行计算，在计算单元进行计算的同时，我们将a3和b3提前放置到shared memory。而后，在进行第3轮迭代时，就可以直接对shared memory中的a3和b3进行计算，而不需要等待从global memory搬运到shared memory的时间。寄存器上的prefetch也是同理。
总结
gemm的优化思想，基本上就是这么几方面的内容。希望大家通过介绍能够对gemm的优化有一个比较直观且具体的理解。
LT3088 宽安全工作区电源线性稳压器，1.5Vout @ 800mA
车载硬盘播放机
韩国研发出的新材料或将能打破Idemitsu Kosan和SFC的寡头结构
台湾多家连接器厂落户徐州
MAX64180 高清摄像机SoC
如何对GPU中的矩阵乘法（GEMM）进行优化
补课18年,把“不可能”变为现实的龙芯团队
亿图AI助手，你的职场咨询顾问
三维尺寸测量常用的设备有哪些
基于SPMP8000系列设计的多媒体播放器解决方案
电机名牌的参数你知道有多少？
MS8416助力2.4G无线音频模块发展
确保锂电池容量和寿命的注意事项
如何分别对机器人上的多个伺服进行独立操控
螺钉布置对底部散热型表贴式功率器件热表现的影响
想了解STM32，看这一篇就够了
凌科电气电动摩托车专业连接解决方案全解析
实现树莓派加密的方法
华为在内的多家公司完成了5G毫米波功能、射频和外场性能
无人机倾斜摄影三维建模技术助力整体智慧城市空间数据的搭建
不像上次的reduce优化一样，能一篇文章说完。这次的gemm优化会分为三个部分。第一个部分只说优化思路和分析，没有任何代码，这么做考虑也是为了减轻读者的负担，看代码太累， 尽可能地让读者先明白原理，为什么要这么做。第二个部分是对代码的详细解析，这个里面就是一行一行地去分析代码。因为之前的很多博客进行了分析，但是代码本身并没有开源，或者说开源了代码，但没有解析，看起来太累了。我希望提供一个尽可能详细的代码解析，读者看完之后能明白相关优化技巧，并且可以直接把代码拿去验证使用。第三个部分主要涉及到汇编器，最重要的是说明在nv的卡上，怎么去解决寄存器的bank冲突来获取极致的性能。
本篇文章是gemm优化的第一个部分，在这篇文章中，只说优化思路和分析。
前言
在高性能领域，对于矩阵乘（gemm）的优化是一个非常重要的课题。gemm可以非常广泛地应用于航空航天、流体力学等科学计算领域，这也是之前hpc的主要应用场景。后来深度学习开展地如火如荼，由于对高算力的需要，也成为hpc的主要应用场景之一。这些年涌现了一系列的深度学习模型。模型里面最耗时的东西，包括卷积、全连接层、attention，都可以转换成gemm操作。所以说，gemm优化的重要性，怎么突出都不过分。
目前网上能找到的针对gemm优化的资料主要有这么几个方面：（1）论文，目前针对gpu进行gemm优化的论文非常多，这里主要推荐understanding the gpu microarchitecture和fast implementation of dgemm on fermi gpu以及dissecting the nvidia volta gpu architecture via microbenchmarking。这几篇论文在业界都比较有影响力，就是代码开源方面做的不算太好。（2）官方博客，主要是cutlass和nervanasystems-sgemm优化。还有前段时间旷视发的文章cuda矩阵乘法优化，写的都很详细。（3）github的一些demo，代码量不大，看起来比较舒服。我是看了这两个：
demo1 ：
https://github.com/cjkkkk/cuda_gemm
demo2 ：
https://github.com/yzhaiustc/optimizing-sgemm-on-nvidia-turing-gpus
demo1代码写的好理解一些，但是优化工作没做完全，没有做到prefetch。demo2是效果很好，11个优化技巧，不断逼近cublas。但是代码真的看起来比较难受，最重要的很多参数写死了，不好去调。 总而言之，目前列举的上述资料存在着这么两个问题：（1）文档方面，读起来还是比较费劲，对于小白来说，还是不够简单不够傻，看起来太累了；（2）代码方面，要么是没公开代码，要么是代码太多了，看不下去；还有的就是代码可读性很强，但是优化工作还不是特别深，或者就是代码优化做的很好，但是可读性差了。方方面面总是有点欠缺，所以希望能够写一篇尽可能地在文档上简单明了，在代码上详细且可读性好的文章。当然，这是一个逐步迭代的过程，所以这篇文章也会持续进行更新哈。 本篇文章主要是采纳了cutlass的行文思路，主要介绍gemm中的数据分块和如何在多级存储进行数据搬运。这也是hpc优化的核心思想，怎么样让数据放在更近的存储上来掩盖计算的延时，从而减少存储墙的影响。文章分为四个方面进行叙述，首先介绍在global memory层面如何进行分块以及数据搬运，随后介绍在shared memory层面如何进行分块以及数据搬运，而后介绍在register层面如何进行分块以及避免bank冲突，最后介绍如何进行prefetch以更好地掩盖访存时延。
一、从global memory到shared memory
假设有矩阵a、b，需要计算矩阵a和b的乘，即矩阵c。a、b、c三个矩阵的维度分别为 ，，，且三个矩阵中的数据都是单精度浮点数。对于c中每一个元素，c[i][j]，可以看作是a的一行和b的一列进行一次归约操作。采用最naive的gemm算法，在gpu中，一共开启 个线程，每个线程需要读取矩阵a的一行与矩阵b的一列，而后将计算结果写回至矩阵c中。因而，完成计算一共需要从global memory中进行 次读操作和 次写操作。大量的访存操作使得gemm效率难以提高，因而考虑global memory中进行分块，并将矩阵块放置到shared memory中。其示意图如下： 对global memory进行分块的gemm算法示意图见上图右侧。首先将a、b、c三个矩阵划分为多个维度为 ，， 的小矩阵块。三个矩阵形成 ，， 的小矩阵网格。其中，，，。随后在gpu中开启 个block，每个block负责c中一个维度为 的小矩阵块的计算。计算中一共有k次迭代，每一次迭代都需要读取a中一个维度为 的小矩阵块和b中一个维度为 的小矩阵块，并将其放置在shared memory中。因而，完成c中所有元素的计算一共需要从global memory中读取 ，即 个单精度浮点数。相比于naive的gemm算法，访存量减少为原来的 。通过global memory中分块算法极大地减少了对global memory的访存量。并且，相比于naive算法，对global进行分块可以更充分地利用数据局部性。在naive算法中，每一个线程都需要直接从global memory中取数，其时延非常长，计算性能非常差。而进行分块后，将维度为 ， 的小矩阵块先存储到shared memory之中。而后计算单元进行计算时可以直接从shared memory中取数，大大减少了访存所需要的时延。
二、从shared memory到register
随后，我们进一步考虑从shared memory到register的过程。在这里，只分析一个block中的计算。当进行k轮迭代中某一轮迭代时，gpu将维度为 ， 的小矩阵块存储到shared memory中，而后各个线程将shared memory中的数据存入register中进行计算。 在不对shared memory分块时，一个block中含有 个线程，每一个线程负责c中一个元素的计算。则一个block一共需要对shared memory进行 次读操作。而后考虑对shared memory进行分块，对 的小矩阵进行再一次划分，将其划分为多个维度为 的子矩阵。则一个block需要负责 个子矩阵。其中，，。随后，在一个block中开启 个线程，每个线程负责一个维度为 的子矩阵的计算。在计算中，一个block一共需要从shared memory读取 ，即 个单精度浮点数。相比于未分块的算法，对于shared memory中的访存量减少为原来的 。并且，由于将数据放入register中，可以直接对数据进行运算，减少了从shared memory中取数的时延。
三、register分块
在这里，我们考虑最后一层，即register中的计算，并且只分析一个thread。在完成以上的过程后，对于一个线程而言，它现在拥有： 个a矩阵的寄存器值， 个b矩阵的寄存器值，以及 个c矩阵的寄存器值。通过这些寄存器的值，需要计算个数。这需要 条ffma指令。 这个时候会涉及到寄存器的bank conflict。在nv的gpu中，每个sm不仅会产生shared memroy之间的bank 冲突，也会产生寄存器之间的bank冲突。这一点对于计算密集型的算子十分重要。像shared memory一样，寄存器的register file也会被分为几个bank，如果一条指令的的源寄存器有2个以上来自同一bank，就会产生冲突。指令会重发射，浪费一个cycle。ps：这个地方是从旷视的博客中看的。然后对于maxwell架构的gpu而言，bank数为4，寄存器id%4即所属bank。 我们假设对这个thread来说，、。并且计算c的寄存器以一种非常naive的情况分配，如下图左侧所示。则需要产生16条ffma指令，列举如下：
ffma r0, r16, r20, r0 ffma r1, r16, r21, r1 ……
可以从中看出，这会产生大量的register bank冲突，所以需要对参与计算的寄存器重新进行分配和排布,如上图右侧所示。在有些地方，这种方式也可以叫做register分块。
四、数据的prefetch
最后，我们来讲讲如何通过对数据进行prefetch来减少访存的latency。我们再来回顾gemm的过程，并且仔细地看看这个访存的latency到底是怎么导致的。对于一个block而言，需要计算一个 的矩阵块，这个时候需要进行k次迭代，每次迭代都需要先将来自a和b的两个小块送到shared memory中再进行计算。而从global中访存实际上是非常慢的，所以导致了latency。虽然gpu中可以通过block的切换来掩盖这种latency，但是由于分配的shared memory比较多，活跃的block并不太多，这种延时很难被掩盖。对于一个thread，需要计算一个 的小矩阵，但是必须先将数据从shared memory传到寄存器上，才能开始进行计算。所以导致了每进行一次迭代，计算单元就需要停下来等待，计算单元不能被喂饱。
为此，需要进行数据的prefetch来尽可能地掩盖这种latency。思想也比较简单，需要多开一个buffer，进行读写分离。示意图如下。当block进行第2轮迭代时，需要对a2和b2进行计算，在计算单元进行计算的同时，我们将a3和b3提前放置到shared memory。而后，在进行第3轮迭代时，就可以直接对shared memory中的a3和b3进行计算，而不需要等待从global memory搬运到shared memory的时间。寄存器上的prefetch也是同理。
总结
gemm的优化思想，基本上就是这么几方面的内容。希望大家通过介绍能够对gemm的优化有一个比较直观且具体的理解。
LT3088 宽安全工作区电源线性稳压器，1.5Vout @ 800mA
车载硬盘播放机
韩国研发出的新材料或将能打破Idemitsu Kosan和SFC的寡头结构
台湾多家连接器厂落户徐州
MAX64180 高清摄像机SoC
如何对GPU中的矩阵乘法（GEMM）进行优化
补课18年,把“不可能”变为现实的龙芯团队
亿图AI助手，你的职场咨询顾问
三维尺寸测量常用的设备有哪些
基于SPMP8000系列设计的多媒体播放器解决方案
电机名牌的参数你知道有多少？
MS8416助力2.4G无线音频模块发展
确保锂电池容量和寿命的注意事项
如何分别对机器人上的多个伺服进行独立操控
螺钉布置对底部散热型表贴式功率器件热表现的影响
想了解STM32，看这一篇就够了
凌科电气电动摩托车专业连接解决方案全解析
实现树莓派加密的方法
华为在内的多家公司完成了5G毫米波功能、射频和外场性能
无人机倾斜摄影三维建模技术助力整体智慧城市空间数据的搭建