TVM Fuse | 实在之路

type

status

date

slug

summary

Step1. 构建支配树

支配树定义

对一个节点A的支配节点S，其实就是A的所有input节点的LCA（最近公共祖先）。

支配点算法

TVM使用的算法：

这里实际有更优的算法。

LCA(a，b)

TVM使用的也是最暴力的办法，两个节点向上跳，直至相遇。这里也有更优的算法。

Step2. Fuse

OP分类

下面举一些op例子：

kElemWise

kBroadcast

其实上面的这些kBroadcast也是Elementwise的

kInjective

我理解就是output的每一维是和input的某一维度有映射关系？相比broadcast, injective不要求ouput的维度和input的维度保持顺序一致。

kCommReduce

kOutEWiseFusable

kTuple kOpaque

Combine pattern

可以看见不能将两个高于kBroadcast类型的op合并到一起

两种类型的OP在fuse之后的类型为其中类型更高的一个。

RunFuse

核心函数实现在：tvm::relay::GraphPartitioner::RunFuse

总共这里分了3个phase

Pattern

(phase 0)

(phase 0,1,2)

(phase 1)

这里分了3个phase的原因我认为主要是为了控制pattern间的顺序。

Fuse逻辑

因为在Fuse时候是在一棵树上进行的，在选择和哪个/些节点时，有很多种方案，同时还要避免成环。

上面的pattern可以总结为：

起始节点（+中间节点）+ 结束节点

TVM的要求起始节点必须是结束节点的支配节点。

检查当前节点是否匹配pattern的起始节点

检查当前节点的支配节点是否匹配pattern的结束节点

检查起始节点到结束节点的所有路径上的节点，是否匹配中间节点的要求

Codegen for fused op

To be done

💾TVM Fuse