高性能计算与性能优化：访存

随便聊聊高性能计算和性能优化，想到哪说到哪。文章分为4个部分，第一个部分聊聊并行算法，第二个部分系统地说一下性能优化的方法论，第三个部分介绍一下性能分析，第四个部分介绍一下小结和感悟。

1. 并行算法 目前单核处理器性能已经碰到了瓶颈，想通过单核上的优化去显著提高算力已经是一个非常困难的事情了。但是，现在对算力的需求却日益剧增，科学与工业领域需要更多的算力进行仿真模拟，游戏渲染需要更多的算力满足人的娱乐需求，人工智能领域需要更多的算力进行模型训练和推理服务。因而，对算力的巨大需求促使了英伟达的股价近十年内一轮又一轮地暴涨以及目前异构加速器遍地开花。所有人都知道这是块肥肉，大家都想吃上一口。而从最底层角度而言，所有的一切都源于一件事情，并行算法可以将单核的任务划分到多核异构设备上从而实现加速。这个事情保证了，在一个可以并行的算法上，计算核心越多，理论上，你的代码就能跑地越快，人类社会的发展也能越快。

不过，说实话，我一直觉得并行算法是一个非常难的课题，并行算法的思维是非常反人类的。对于一堆的事情，如果有相关性的话，人总是习惯于列个计划，比如，要聚会了，一堆人在一起。大家先一起做饭，再一起吃饭，最后一起洗碗。干完一件事，再干下一件事。而并行算法在干一个什么事情呢，就是非得让一些人在做饭，一些人在吃饭，一些人在洗碗，然后加一些乱七八糟的同步保证做饭的时候不会拿脏盘子盛饭，洗碗的时候不会把别人碗里没吃的米饭倒了。正常人去看这个思维，觉得这人脑子多少是有点问题的。但是计算机里面经常要这么干，导致人去理解并行算法的时候就会变得非常困难。比如scan算法，给定一串数，求出这些数中，每一个数前面所有数的和。公式表达是这样子，sum[i]=sum[i-1]+num[i]。这个计算过程有着很强的数据依赖，怎么在GPU里面去做？稍微一想就觉得费劲。再比如排序，给一堆数，怎么在GPU上开一堆线程把这些数排好？又比如图里面的宽度优先遍历和最短路径，怎么样在GPU上跑起来？学计算机的同学学习了数据结构，各种树和图的算法。但是这些玩意怎么在GPU上跑起来，又得再开一门课来介绍。唠唠叨叨说这些多，其实都是想说并行算法的困难，这一点在于图计算领域尤其突出，而对于BLAS这样的线性代数计算库而言，又显得相对容易，毕竟把一个矩阵拆分成多行或者多列，这个事情理解起来基本没什么难度。当然对于一些其他的线性代数计算库，也存在着较多的数据依赖，导致并行较为困难的情况。

2. 性能优化方法论

这一节聊聊性能优化方法论。当不同的人谈论性能优化的时候，脑子里面想的东西还不一定是同一个事。当搞网络的人谈性能优化，想的可能是怎么降低网络延时，想的是网络协议和socket相关的东西。当搞数据库的人谈性能优化，想的可能是怎么减少查询数据库的耗时，想的可能是多级索引，尽可能地减少对磁盘的访问。当搞HPC的人谈性能优化，估计脑子里立马就涌现出cache、分块、SIMD相关的概念。所以这里还是得说明白，这篇文章里面讲的性能优化是HPC相关从业者脑子里的那种性能优化。我读过一些论文，看过一些博客。对于不同问题的性能优化，不用的人可能有不同的方法论术语。在深度学习训练的时候，有的时候先分IO瓶颈、CPU瓶颈、GPU瓶颈。有的时候又分为通信瓶颈、IO瓶颈、访存瓶颈、计算瓶颈。林林总总，都有道理，都是在不同的角度去解析实际的问题。我有的时候想着，是不是能够有一个统一的东西去尽可能地说明所有的问题。自然科学领域有一个词叫做第一性原理，从一个最基础的原理和规律开始，再不断扩展到其他事物。最近有一些搞深度学习理论的科学家用到这个词，深度学习的第一性原理，想要通过一些数学手段来解读深度学习，从而指导模型的优化，并往通用人工智能努力。我想了想，如果HPC也要整一个第一性原理，我觉得应该就是访存优化。所有的技巧和努力都是在试图跨过一道墙，也就是内存墙，memory wall。之前oneflow的一篇博客提到了这个，把内存墙称为AI算力的阿喀琉斯之踵。但我觉得AI可以去掉，内存墙是算力的阿喀琉斯之踵。

对于现代的计算机而言，相比于访存，计算已经足够快了。为了让访存尽可能地快一点，延时尽可能地少一点，科研人员绞尽脑汁，因而有了多层cache，有了TLB，有了现代计算机架构。近些年来又有人在折腾存算一体，也是挺有意思的一个领域。当然，前面是硬件的角度，软件的角度来说，那就是HPC。我觉得高性能计算这个领域本身的存在就是通过软件的方式来减少memory wall的影响。我们试想一下，如果没有了memory wall，访存足够地快，所有的计算单元都能在瞬间拿到数据并进行计算，那么pipeline可以全部跑满，计算单元一直保持在100%的利用率，那么HPC这个领域就没有什么可以研究的东西了。

当我们假定了访存优化是第一性原理之后，其实，从某种角度而言，其他的东西也可以被涵盖到访存优化这个大目录下面。IO优化本质上就是对最底层的存储结构-访存磁盘数据的优化。通信优化本质上就是尽可能地加快不同计算节点访问其他计算节点存储单元的速度。而计算优化，当访存已经优化地足够好了之后，计算其实就基本上已经没有什么可以优化的，无非是将循环展开，将地址对齐，将SIMD单元打满。说完了访存优化这个第一性原理之后，接下来扩展，说些具体的优化技巧。当我们在说访存优化的时候，我们具体需要做些什么。总的来说，就是三板斧。一是减少数据搬运，二是减少数据访存延时，三是保证负载均衡。

2.1. 减少数据搬运。

现代计算架构都是多级存储，需要一级一级地将数据往计算单元上搬。如何减少数据搬运，最主要的手段就是分块，或者说tiling。

为什么是三级分块，不是四级或者两级。因为NV的GPU内存结构是三级的，global mem->shared mem，shared mem->register。通过三级分块可以尽可能地提高数据的复用性。也就是尽可能地将数据放到更近的存储结构上进行多次利用。而如果存储结构是四级的话，那就需要再多一次分块。再举个例子，对于稀疏矩阵的计算而言，常常会使用不同的存储结构，本质上也是为了减少对于内存的访问，压缩效率越高，对于内存的访问就越少。而sparse里面五花八门的各种算法，核心也是根据数据排布的不同特性，尽可能地将数据放到shared mem或者其他更近的存储结构上cache住，从而获得加速。

再比如我们一直在强调cache命中率，要尽可能地提高cache命中率，为什么提高cache命中率可以提高性能。原因就是：如果cache不命中，那么就要到更下层的存储结构上去搬运数据，这个开销就立马上去了。所以我们说，要尽可能地保证数据连续访问，其中最主要的一个原因就是提高cache命中率，从而避免不必要的数据搬运。当然，尽可能地保证数据连续访问，还有一个原因是为了让DMA搬运数据的时候更加高效。这个可以归纳为减少数据访存延时。接下来介绍一下减少数据访存延时。

2.2. 减少数据访存延时。

这个部分跟减少数据搬运的区别在于，减少数据搬运是减少数据搬运的次数，但减少数据访存延时指的是当数据搬运的次数已经确定了之后，怎么让每一次数据搬运尽可能地更快。这个部分跟硬件绑定在一起，没有办法撇开硬件单独去说这个事情。总的来说有这么几个点。

首先是减少bank冲突，如何减少shared memory上的bank冲突，如何减少register上的bank冲突，这需要对于硬件的深入理解以及如何通过合理的数据排布来避免bank冲突。

其次是软流水，有的时候叫double buffer，有的时候叫ping pong操作，我觉得跟预取也差不多，其思想都是一样的，就是访存和计算错开，让流水更加顺畅，减少计算等待访存导致的空泡。而NV则是把这一套思想放到了硬件，SIMT架构和CUDA的这套软硬件一体的方式，做得实在是太漂亮了，每当我仔细地揣摩NV的这套架构时，我都会暗暗说一句，MD，真tm牛逼。通过warp切换来掩盖访存的开销，再配合上标量计算。可以最低程度地减少开发者成本，一个初学者，依葫芦画瓢写个简单的CUDA kernel，很容易就能达到百分之七八十的硬件性能。再详细地说一下这个东西，当数据访存的时候，就让warp stall，而后再选一个warp进行计算，通过这种方式交错开计算和访存，让访存单元一直忙碌，带宽打满。这个操作跟双缓冲或者说pingpong操作里面的思路是一样，缺点也非常一致。双缓冲需要双倍的存储空间来存储额外的数据，而SIMT架构也需要大量的register file从而保证warp被选中后能立马接着工作。也因此，对于NV的GPU，只有极少数情况需要开发者手写double buffer进行流水排布。

最后的技巧其实跟前面的软流水是一个道理，就是切分更多的块，启动更多的warp来掩盖访存延时。举个例子，以sgemv为例，给定矩阵A[M,N]，x[N]计算Ax。比如[50,1024]*100。M比较小，而N相对来说比较大的情况。如果还是按照之前的方式，让一个warp负责一行的计算，那么只有50个warp在工作，而NV的卡上有几十个SM，warp太小，那性能会非常地差.这个时候可以让8个block来负责一行的数据，每个block128线程，负责128个元素。这样的话，更多的warp可以更好地掩盖访存开销，性能自然可以上去。再扩展一下，M很大，N又很小的情况，则可以让一个线程负责一行的计算，这个过程就跟elementwise的优化比较接近了。让多个block负责一行从而切分更多的数据块，有的时候叫做XX2D算法。之前斯坦福和google在SC20上发的一篇叫做《Sparse GPU Kernels for Deep Learning》论文里面最重要的一个优化就是在SPMM里面，让多个block负责一行的计算。

2.3. 保证负载均衡

关于负载均衡的话题，主要是在sparse里面谈的比较多，核心都是保证两个，block/warp之前负载均衡，thread之间负载均衡。要么让一个block负责一个大的和一个小的，保证每个block负责的大数据和小数据加起来差不多。要么在nnz维度上进行切分，天然地保证每个block上的负载是均衡的，但这个时候需要引入额外的开销来进行判断数据是数据哪一行。思想都是朴素且易于理解的。在这里面，我主要想说的是硬件层面的负载均衡。我们设想一个场景，如果有100个block，block的负载是均匀的。GPU上有50个SM，按常理，每个SM负责2个block，那SM之间肯定是负载均衡的。那有没有可能是每个SM需要负责4个block，25个block在忙碌，25个block啥也不干？正常人都会说，不可能吧。那为什么不可能，这个分配具体是什么样的呢？只有清楚地了解了这个硬件运行机制才能清楚地说明白为什么不可能。这个机制其实就是在硬件层面如何进行block索引号和SM索引号的映射，只有清楚这个，才能保证软件层面的负载均衡在硬件层面也是负载均衡的。

这一节介绍了性能优化的核心，也就是访存优化。随后又介绍了访存优化的三板斧，也就是减少数据搬运、减少数据访存延时、保证负载均衡。并通过大量的case来说明为什么这三者能够有效地提高访存性能。但遇到实际问题的时候，还是应该case by case地进行分析，切勿一上来就说我要分块，我要避免哪哪哪的bank冲突，我要做负载均衡。一定要做足够多的profiling工作之后，深刻地了解性能瓶颈之后，再着手进行优化。

3. 性能分析

本节介绍性能分析，也就是profiling。这个部分实在是太过于重要，所以必须单独拎出来放在一节讲。在分析任何具体的问题时，都必须做充足的profiling。其实当我们谈优化的时候，需要做的工作，就是profiling找到性能瓶颈，对性能瓶颈优化，再profiling找到性能瓶颈，再对性能瓶颈优化。不断重复，直到接近硬件瓶颈或者达到想要的目标即可。

profiling可以简单地分为粗粒度和细粒度。粗粒度主要是判断瓶颈是不是在GPU上，具体又是哪个kernel，典型代表就是nsight system工具，会显示出整个程序的timeline。可以从timeline上直接清晰明了地看到瓶颈是在CPU还是GPU，如果是GPU，那又是在GPU的哪个kernel上。细粒度主要是判断kernel或者一个函数里面的性能瓶颈在哪。

关于粗粒度的部分，其实需要说的并不多。主要是细粒度的部分需要好好唠一唠。怎么判断一个kernel的性能瓶颈在哪里，这个事情其实并没有那么简单。需要非常丰富的经验才能做到真正游刃有余。上一节说到了性能优化的核心在于访存优化，性能分析里面最重要的也是对于访存的分析。像NV的卡，主要是分为四层，DRAM、L2 cache、L1 cache + shared memory、register。我们需要尽可能地保证每一层的数据搬运效率都足够地高，尽可能地把带宽打满。

如果发现实际带宽比较差，数据搬运效率比较低，这个时候就要去思考，是不是可以有办法，通过分块的一些技巧来减少数据搬运。如果数据搬运不能够再减少了的话，是否可以通过一些方式来提高数据的搬运效率，比如向量化访存、合并访问来提高对DRAM的访存性能、避免bank冲突来提高对shared memory的访存性能、调整分块大小来让更多的warp跑起来从而减少访存的延时，如果不是SIMT架构，就需要精细地设计各级访存的pipeline，让访存操作尽可能地pingpong起来，从而让访存流水尽可能地连续起来不要被打断。理论大概是这样，但是每一个问题都有着不同的处理方式，每一个问题可能都是不同的瓶颈。总之就是万变不离其宗，准确地评估每一级存储的访存效率然后尽可能地提高每一级的访存效率，尽可能地把访存流水打满，不要有空泡。

大概地说了一下profiling，然后再提一下MicroBenchmark。很多时候，硬件厂商给出的性能分析工具不可能覆盖所有的东西，也不可能详细地告诉开发者相应的细节，尤其是一代新硬件出来之后。比如说访问global memory需要多少个cycle，访问L2 cache需要多少个cycle，访问shared memory需要多少个cycle，访问寄存器时寄存器号和bank索引号的映射关系。这些东西都需要进行详细的microbenchmark才能让我们更加了解硬件从而指导优化。至于怎么指导优化，这又可以另外开一个话题详细地说。举个例子，做矩阵乘法的优化时，可以大概地评估从shared memory访存需要多少个cycle，然后再相应地计算出往里面加多少条计算指令差不多可以掩盖shared mem访存的开销。当然这部分跟warp切换也有关系，不同的参数选择会导致不同的warp活跃数，warp切换的话，会产生不同的影响。再比如我们需要知道指令cache的大小，这样的话，对于计算密集型的kernel，可以大概确定分块的大小以及循环展开的次数，这个时候说一下GEMM里面为啥很多介绍都是使用128*8的shared memory块和8*8的寄存器块，因为这个数字所需要的空间开销，可以使得每个SM上跑大概4个左右的block，用上双缓冲能掩盖访存开销，并且计算的部分循环展开到8，使用的指令数差不多刚好可以在指令cache中放下。当然这个数据针对不同的硬件又有所不同，所以每一代硬件都需要单独进行处理。关于这部分的内容有很多的MicroBenchmark和CostModel相关的论文，大家有兴趣可以去查一下。

4. 小结和感悟

4.1. 经验or完善的知识体系

大家普遍会觉得高性能计算是一个非常注重经验的领域，很多东西都是case by case的方式。每一个问题都需要进行具体的分析，一个新手入门时，遇到性能问题总是容易束手无策，常常会有疑问，“这个kernel性能应该怎么提高？”“为什么别人的代码比我快好几倍？”有的时候苦思冥想都很难找到关键的点，很难提高代码的性能，长久下去就丧失信心，不再愿意做这个方向。这些情况大多数都是因为经验不足，但所有人都是从新手村里出来的。有的时候想想为什么会出现这个原因，我觉得，主要还是因为这个领域目前关注的人还不是很多，而且中国关于这方面的学科建设并不成熟，在本科期间，只有极少数的人接触过CUDA编程或者高性能计算，一般只有研究生才能接触到，而且说实话，目前国内做这方面工作的高校并不多。所以每一年培养出来的合格的人才其实非常少，而且只在少数top高校能够找到合适的人。也因为搞的人少，相关的文档和资料非常少。在网上可以很容易找到某个深度学习算法的解析，但是很难找到详细的中文文档来告诉大家怎么分析性能怎么提高性能、怎么一步步地达到硬件极限。总之高性能计算是一个比较吃经验的领域，什么叫做经验，经验就是有着完善的知识体系，真正去做了很多实践，形成系统的方法论，这就是经验。 4.2. 通用代码or针对性优化。

这些年随着硬件产品的不断涌现，对计算库的需求也越来越多。针对不同的硬件架构、不同的算子、不同的数据排布都要针对性进行优化，这个工作量非常巨大。所以工业界和学术界都在思考着如何减少计算库开发的人力成本，如何让代码在更多的硬件设备上跑起来且性能还OK，如何实现性能可移植可扩展。目前TVM、XLA等相关的深度学习编译器在这方面做出了突出的工作。采用了Halide的思想将一系列成熟的优化技巧封装到schedule中，再通过代码生成的方式，就能达到不错的性能。再加上图优化，通过一系列的fusion就能优化整张图的计算耗时。总得来说，非常牛逼，也解决了一些工业界的问题，于是掀起了一股研究的浪潮。细细去想为什么TVM这样的深度学习编译器能够成功，在某些程度上在于深度学习里面需要的算子相对简单，大部分还是GEMM、reduce、elementwise这样的访存模式，而这些东西在高性能领域研究地足够透彻，并且现在主流的硬件已经做得足够牛逼，所以相对简单的优化策略就能生成性能比较好的kernel。但如果真的要在工业场景落地，还是比较依赖于硬件厂商经过细致调优的计算库，当然这两者也不是对立关系，实际上是相辅相成的，相互配合使用，在不同的应用场景中发挥作用。话再说回来，如果真的能够实现一套通用代码来实现多种硬件设备，且保证性能OK，生产环境能用起来用的好，在科学计算和深度学习等多个领域都能work。这会是一个极其牛逼的工作。但是这里面需要花费巨大的人力成本和时间成本，而且需要一定程度上的理论突破。个人觉得，还是学术界来主导，然后一些天才型的开发者掌握合适的方向，再做几年冷板凳没准会有一些成果出来。然后再由工业界不断地迭代几轮，达到成熟。

4.3. 正确地评估和认识。

这里想说的倒不是profiling那些东西，而是说一下我的一些感悟。就是看待别人的一些工作时，尽可能地理智客观，如果有必要，最好动动手。有的事情，看着比较难，比如说写一个kernel性能超过官方库啥啥的，其实如果针对特定的数据，特定的硬件，特定的库版本，如果还不到硬件极限的话，要超越官方库是一个相对简单的事情，无非是多一些hard code，根据数据特性和硬件特性，总是能把性能提上去。但有一些官方库在特定的硬件上已经做了非常好的优化，尽量就不要再另外花时间去想着超越官方库了，意义不大。有的事情看着比较简单，实际上会有各种阻力，中间可能会遇到各种困难。比如做计算库，很多时候功能可能比较简单，就像blas，但实际上要针对各种硬件，针对各种数据排布都能有一个比较好的性能，这个是非常困难的，里面所需要的精力和耗时也不是外行人能够搞清楚的。

总结一下，就是尽可能地跟专业的团队做专业的事情，如果对其他领域不是那么那么清楚，没有真正写过相关代码，没有踩过相关的坑，那不要乱下结论，不要总是拍脑子想事情。这一点其实非常重要，整个人类社会出现外行领导内行的情况非常多，其实倒不可怕，最可怕的是外行觉得自己是内行，总是瞎指挥。那小到几人的团队，大到一个国家，都容易出现问题。