代数简化（Algebraic Reduced）是一种从数学上来指导我们优化计算图的方法。其目的是利用交换率、结合律等规律调整图中算子的执行顺序，或者删除不必要的算子，以提高图整体的计算效率。
代数化简可以通过子图替换的方式完成，具体实现：1）可以先抽象出一套通用的子图替换框架，再对各规则实例化。2）可以针对每一个具体的规则实现专门的优化逻辑。下面我们将介绍三种不同的代数简化方案。
算术简化
顾名思义，算术化简就是通过利用代数之间算术运算法则，在计算图中可以确定优化的运算符执行顺序，从而用新的运算符替换原有复杂的运算符组合。我们给出结合律，分配律，交换律的例子。
结合律
非正式的讲，结合律是说： 不论我们怎样结合数字（即先计算那些数字），答案都是一样的。即：
$$
(a+b)+c = a+(b+c)
$$
形式化的讲，令 $*$ 是非空集合 $S$ 上的二元运算，如果 $\forall x,y,z\in S$，都有
$$
(xy)z = x(yz)
$$
则称运算 $$ 在 $S$ 上是可结合的，或者说运算 $$ 在 $S$ 上满足结合律。
根据这样的思想，我们可以发现以下的规则符合结合律，令 $A,B,C$ 是张量集合 $\Gamma$ 的元素，即 $A,B,C\in \Gamma$，则有
$$
(A\star B)^{-1}\diamond ((A\star B)C)^{-1} \rightarrow(A\star B)^{-2}\diamond C
$$
其中 $\star$ 是卷积 Conv，$\diamond$ 是矩阵乘法 Mul；形式上讲，我们称上述公式为在张量集合 $\Gamma$ 上的二元运算 $\star$、$\diamond$ 满足结合律。
有了这样的规则，便可以指导我们进行实例的优化，例如下面的实例算子，令 $A,B,C$ 为具体的张量，其他算子均为图示，优化规则如上所述：
根据上述结合律规则，我们可以把 A 与 B 的卷积给抽离出来，讲红色方框部分做简化，这样我们就减少运算算子，也减少了运算开销。
当然还有许多符合结合律的化简，我们列几个在下方供读者参考。
$$
Recip(A) \diamond Recipe(A \diamond B) \rightarrow Square(Recip(A)) \diamond B
\
(A \diamond \sqrt B) \diamond (\sqrt B \diamond C) \rightarrow A \diamond B \diamond C
\
(A \diamond ReduceSum(B)) \diamond (ReduceSum(B) \diamond C) \rightarrow A Square(ReduceSum(B)) \diamond C
$$
交换律
交换律是说：我们可以把数的位置对换而答案不变，即：
$$
a+b = b+c \
ab = ba \
$$
形式化的讲，令 $*$ 是非空集合 $S$ 上的二元运算，如果 $\forall x,y\in S$，都有
$$
xy= yx
$$
则称运算 $$ 在 $S$ 上是可交换的，或者说运算 $$ 在 $S$ 上满足交换律。
根据这样简洁优美的思想，我们可以发现以下的规则符合结合律：
$$
ReduceSum(BitShift(A)) \rightarrow BitShift(ReduceSum(A))
$$
根据这样的规则我们可以看到如下实例的优化：
如图所示，A 是一个张量，相比较先位移再 ReduceSum 的操作顺序，我们可以根据结合律，先 ReduceSum，得到一个维度更小的 batch，再进行 BitShift，显然运算的开销减少了。
当然还有许多符合交换律的化简，我们列几个在下方供读者参考。
$$
ReduceProd(Exp(A)) \rightarrow Exp(ReduceSum(A))
$$
分配律
分配律简化，即
$$
a(b+c) = (ac)+(a*b)
$$
形式化的讲，令 $*$ 和 $\circ$ 是非空集合 $S$ 上的二元运算，如果 $\forall x,y,z\in S$，都有
$$
x(y\circ z) = (xy)\circ (xz)
\
(y\circ z)x = (yx)\circ (zx)
$$
则称运算 $$ 对 $\circ$ 在 $S$ 上是可分配的，或者说运算 $$ 对 $\circ$ 在 $S$ 上满足分配律。
这个公式从右往左的过程也可以称为提取公因式。根据上述思想，我们可以发现以下的规则符合分配律：
$$
(A\cdot B)\star C + (A\cdot B)\star D \rightarrow (A\cdot B)\star (C+D)
$$
根据这样的规则我们可以看到如下实例的优化：
我们会发现，$A\cdot B$ 之后与 $C,D$ 分别做乘法操作时没有必要的，于是可以提取公因式，将 $C,D$ 单独加和再做乘法，将 4 次算子操作降低为 3 次操作，减少了运算开销。
当然还有许多符合分配律的化简，我们列几个在下方供读者参考。
$$
A+A\diamond B \rightarrow A \diamond (B+1)
\
Square(A+B)-(A+B)\diamond C \rightarrow (A+B)\diamond(A+B-C)
$$
注：当我们做代数简化时，一定要先注意到算子是否符合例如交换律，结合律等规则，例如矩阵乘法中 $AB \neq BA$。
最后，我们向大家推荐一篇关于算术简化规则的文章：
DNNFusion: accelerating deep neural networks execution with advanced operator fusion.
其中还包括更多复杂的简化规则供读者参考。
运行简化
运算简化，是减少运算或执行时，冗余的算子或者算子对；我们给出两种规则来解释。
-
逆函数等于其自身函数的对合算子化简：
$$
f(f(x)) = x \
f(x) = f^{-1}(x)
$$例如取反操作：$-(-x) = x$，倒数，逻辑非，矩阵转置（以及你键盘中英文切换，当你快速按下两次切换的时候，你会发现什么都没有发生，当然次数太多就不一定了）等。
-
幂等算子化简，即作用再某一元素两次与一次相同：
$$
f(f(x))=f(x)
$$一个具体的实例如下：
$$
Reshape(Reshape(x, shape1),shape2) \rightarrow Reshape(x, shape2)
$$其中，$Shape2$ 的大小小于 $Shape1$。
我们用图来展示上述两中运行化简：
如图所示，对于对合算子 Op1,两次对合后，根据对合性质可得等价于没有操作，所以运行化简后只剩下 Op2。
如图所示，对于幂等算子 Op1，多个幂等算子等价与一次操作，于是运行化简后等价与一个 Op1 算子。
广播简化
当多个张量形状 Shape 不同情况下，需要进行广播（broadcast）将张量的形状拓展为相同 shape 再进行运算，化简为最小计算所需的广播运算数量。
我们还是以一个简单的例子为准，考虑以下 2 个矩阵与 2 个向量的相加：
$$
(S_1+Mat_1)+(S_2+Mat_2) \rightarrow(S_1+S_2)+(Mat_1+Mat_2)
$$
假设矩阵的维度为 4，则一个向量与 4 维矩阵相加时，要先广播为 4 维，再与 Mat 相加，显然左式需要广播两次；但我们可以通过位置替换，将两个向量首先相加再广播，此时就节省了一个广播的开销，达到我们优化的目的。
如果您想了解更多AI知识，与AI专业人士交流，请立即访问昇腾社区官方网站https://www.hiascend.com/或者深入研读《AI系统：原理与架构》一书，这里汇聚了海量的AI学习资源和实践课程，为您的AI技术成长提供强劲动力。不仅如此，您还有机会投身于全国昇腾AI创新大赛和昇腾AI开发者创享日等盛事，发现AI世界的无限奥秘~
转载自：| https://www.cnblogs.com/ZOMI/articles/18560291 | header |
| ---------------------------------------------- | ------ |
| | |