首页 > 其他分享 >转载:【AI系统】代数简化

转载:【AI系统】代数简化

时间:2024-12-13 21:57:57浏览次数:3  
标签:化简 diamond 运算 AI 代数 结合律 算子 转载 rightarrow

代数简化(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$ 为具体的张量,其他算子均为图示,优化规则如上所述:

image

根据上述结合律规则,我们可以把 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))
$$

根据这样的规则我们可以看到如下实例的优化:

image

如图所示,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)
$$

根据这样的规则我们可以看到如下实例的优化:

image

我们会发现,$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.

其中还包括更多复杂的简化规则供读者参考。

image

运行简化

运算简化,是减少运算或执行时,冗余的算子或者算子对;我们给出两种规则来解释。

  • 逆函数等于其自身函数的对合算子化简:

    $$
    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$。

我们用图来展示上述两中运行化简:

image

如图所示,对于对合算子 Op1,两次对合后,根据对合性质可得等价于没有操作,所以运行化简后只剩下 Op2。

image

如图所示,对于幂等算子 Op1,多个幂等算子等价与一次操作,于是运行化简后等价与一个 Op1 算子。

广播简化

当多个张量形状 Shape 不同情况下,需要进行广播(broadcast)将张量的形状拓展为相同 shape 再进行运算,化简为最小计算所需的广播运算数量。

我们还是以一个简单的例子为准,考虑以下 2 个矩阵与 2 个向量的相加:

$$
(S_1+Mat_1)+(S_2+Mat_2) \rightarrow(S_1+S_2)+(Mat_1+Mat_2)
$$

image

假设矩阵的维度为 4,则一个向量与 4 维矩阵相加时,要先广播为 4 维,再与 Mat 相加,显然左式需要广播两次;但我们可以通过位置替换,将两个向量首先相加再广播,此时就节省了一个广播的开销,达到我们优化的目的。

如果您想了解更多AI知识,与AI专业人士交流,请立即访问昇腾社区官方网站https://www.hiascend.com/或者深入研读《AI系统:原理与架构》一书,这里汇聚了海量的AI学习资源和实践课程,为您的AI技术成长提供强劲动力。不仅如此,您还有机会投身于全国昇腾AI创新大赛和昇腾AI开发者创享日等盛事,发现AI世界的无限奥秘~
转载自:https://www.cnblogs.com/ZOMI/articles/18560291

标签:化简,diamond,运算,AI,代数,结合律,算子,转载,rightarrow
From: https://www.cnblogs.com/khronos0206/p/18605923

相关文章

  • 转载:【AI系统】计算与调度
    上一篇我们了解了什么是算子,神经网络模型中由大量的算子来组成,但是算子之间是如何执行的?组成算子的算法逻辑跟具体的硬件指令代码之间的调度是如何配合?计算与调度计算与调度的来源图像处理在当今物理世界中是十分基础且开销巨大的计算应用。图像处理算法在实践中需要高效的实现......
  • 转载:【AI系统】指令和存储优化
    除了应用极广的循环优化,在AI编译器底层还存在指令和存储这两种不同优化。指令优化指令优化依赖于硬件提供的特殊加速计算指令。这些指令,如向量化和张量化,能够显著提高计算密度和执行效率。向量化允许我们并行处理数据,而张量化则进一步扩展了这一概念,通过将数据组织成更高维度......
  • 转载:【AI系统】算子循环优化
    在具体硬件执行计算的时候,实际会大量地使用for等循环指令不断地去读取不同的数据执行重复的指令(SIMT/SIMD),因此循环优化主要是为了提升数据的局部性或者计算的并行性,从而提升整体算子性能,当然这二者都需要AI芯片硬件的支持。循环优化挑战数据局部性数据的局部性与计算机存储......
  • 转载:【AI系统】算子手工优化
    在上一篇中,探讨了算子计算和调度的概念,并强调了高效调度策略在释放硬件性能和降低延迟方面的重要性。本文,我们将深入讨论手写算子调度时需要考虑的关键因素,并介绍一些著名的高性能算子库。计算分析在优化算子前,首先需要知道当前程序的瓶颈在哪里,是计算瓶颈还是访存瓶颈。对于这......
  • 转载:【AI系统】TVM 实践案例
    在本文我们探讨一下,如何利用AI编译器在新的硬件上部署一个神经网络,从算法设计到实际运行,有哪些需要考虑的地方?本文将以TVM为例,首先介绍一下TVM的工作流:导入模型。TVM可以从TensorFlow、PyTorch、ONNX等框架导入模型。转换为Relay。Relay是TVM的中间表示形式,已导......
  • 转载:【AI系统】Auto-Tuning 原理
    在硬件平台驱动算子运行需要使用各种优化方式来提高性能,然而传统的手工编写算子库面临各种窘境,衍生出了自动生成高性能算子的的方式,称为自动调优。在本文我们首先分析传统算子库面临的挑战,之后介绍基于TVM的业界领先的三个自动调优系统。高性能算子挑战DNN部署的硬件平台越来......
  • 转载:【AI系统】CANN 算子类型
    算子是编程和数学中的重要概念,它们是用于执行特定操作的符号或函数,以便处理输入值并生成输出值。本文将会介绍CANN算子类型及其在AI编程和神经网络中的应用,以及华为CANN算子在AICPU的详细架构和开发要求。算子基本介绍一元算子通过对单个操作数进行操作,如取反或递增,而......
  • 转载:【AI系统】昇腾异构计算架构 CANN
    本文将介绍昇腾AI异构计算架构CANN(ComputeArchitectureforNeuralNetworks),这是一套为高性能神经网络计算需求专门设计和优化的架构。CANN包括硬件层面的达·芬奇架构和软件层面的全栈支持,旨在提供强大的硬件基础和管理网络模型、计算流及数据流的软件栈,以支撑神经网络在异......
  • 转载:【AI系统】Ascend C 编程范式
    AI的发展日新月异,AI系统相关软件的更新迭代也是应接不暇,作为一篇讲授理论的文章,我们将尽可能地讨论编程范式背后的原理和思考,而少体现代码实现,以期让读者理解AscendC为何这样设计,进而随时轻松理解最新的AscendC算子的编写思路。本文将针对AscendC的编程范式进行详细讲......
  • 转载:【AI系统】Ascend C 语法扩展
    AscendC的本质构成其实是标准C++加上一组扩展的语法和API。本文首先对AscendC的基础语法扩展进行简要介绍,随后讨论AscendC的两种API——基础API和高阶API。接下来针对AscendC的几种关键编程对象——数据存储、任务间通信与同步,资源管理以及临时变量进行详细解读......