为什么没有自动生成任意算子fusion kernel的工作?(回答)

First Post:

Blog Link:

其实挺多相关工作的。fusion 这个东西扯起来历史还是挺久远的,本身也算编译器领域的一个经典课题,从上世纪开始就有不少 loop fusion 相关的研究,特别是在 polyhedral model 基础之上进行的 loop fusion,离现在比较近的工作有 PPoPP’14 的 Revisiting loop fusion in the polyhedral framework赵捷大佬的一个有关 polyhedral 的知乎回答也有 loop fusion 相关的内容。loop fusion 的收益来源主要就是减少中间数据的搬移,kernel fusion 在此基础上还减少了一些 kernel launch 的开销(不过实际场景中减少 kernel launch 带来的收益很多时候可以忽略)。

fusion 在学术界的发展基本上可以分为 4 个阶段(阶段之间一般有所重叠,没有明确的界限)。第一阶段,loop fusion 作为编译器后端 loop 优化相关的研究的一部分得到初步发展。第二阶段,image processing pipeline 中各种连续的 stencil 操作带来了新的 fusion 空间,因为 stencil 操作引入了滑窗依赖,因此如何进行任务划分来平衡 访存、通信/同步、重复计算 等要素是挺值得研究的,PolyMageHalide 算是这个阶段的一部分代表性工作,甚至还有做六边形 tiling 的工作

第三阶段,就是深度学习加速器和编译器兴起的阶段,那时候有不少加速器设计相关的工作关注 CNN 相邻层的 fusion(和前文说的 stencil pipeline 一样因为有滑窗依赖所以有不少可以研究的点),比如 MICRO’16 的 Fused-Layer ,还有我们组师兄的 DAC’17 的一篇工作 ,近几年也有 HPCA’23 的 DeFiNESISOSceles 这样的工作。在深度学习编译器这边,做的主要是整个计算图范围内的访存密集型算子之间的自动融合,典型的工作如 DNNFusionAStitchApollo

第四阶段,主要就是 transformer 架构逐渐流行的时候,multi-head attention 计算在形状上的特殊性,导致其中的两个矩阵乘在实质上成为了访存密集型算子,有着超大的融合优化收益。MLSys’22 的 BOLT思泽师兄的 HPCA’23 的 Chimera 都对相邻矩阵乘的融合优化做了探索,不过要说这方面最出名的工作还当属 22 年的 Flash-Attention 和 23 年的 Flash-Attention-2(其实 BOLT 和 Chimera 之类的工作在切分调度上和 FA-2 是一样的,只是没发掘 online-softmax 的用法,因此不能直接用在生产环境中的 attention 上)。然后题主所说的整图范围内的任意算子的 kernel fusion,个人感觉比较接近的是 OSDI’23 的 Welder(今年 OSDI 的 @LeiWang1999Ladder 也可以算)还有今年 ASPLOS 的几篇工作:SouffleKorchPyTorch-2。特别是 PyTorch-2,应该算是目前图层面融合优化做得最好的工业级 ML Compiler,虽然它好像不会做连续矩阵的融合。不过连续矩阵乘的融合收益还是要看具体场景,虽然能减少中间矩阵的搬移,但也会影响并行度以及对旁侧矩阵的复用,最好是中间矩阵足够大、旁侧矩阵足够小才有比较好的收益,主流场景中好像基本只有各类 attention、cnn 的前几层、一些小型 mlp 比较符合这个要求,针对此类少数情况一般手写个算子就差不多得了,特别是现在用 triton 写还很方便……

还有一类 kernel fusion 被称为 horizontal fusion,将不存在依赖任务同时运行在一个 kernel 内增加资源利用率,典型的工作如 CGO’20 的 HFuse ,OSDI’20 的 Rammer ,MLSys’21 的 IOS ,最近的 UW 的 Baris Kasikci 组开源的 NanoFlow 也用到了类似的技术,其创新点在于将大模型的推理沿 batch 切开,将不同 request 的推理错开,人为制造适合进行 horizontal fusion 的异构 task。