AI嵌入式系统：算法优化与实现

第七章 AI芯片思考与展望 1. GPU架构与CUDA关系 CUDA（Compute Unified Device Architecture，统一计算设备架构），其具有通用并行计算架构（Parallel Computing Architecture）和编程模型（Programming Model），利用 GPU 的并行处理能力，将 GPU 用作通用并行计算设备，以加速各种计算任务，而不仅限于图形处理 基于 LLVM 构建了 CUDA 编译器，开发人员可使用 CUDA C/C++语言编写并行程序，通过调用 CUDA API 将计算任务发送到 GPU 执行 CUDA 在软件方面组成 1. 一个 CUDA 库 2. 一个应用程序编程接口（API）及其运行库（Runtime） 3. 两个较高级别的通用数学库（即 CUFFT 和 CUBLAS） CUDA 工具包（TOOLKIT）包括 1. 编译和 C++核 2. CUDA DRIVER（驱动器）驱动 GPU 负责内存和图像管理 3. CUDA-X LIBRARIES 主要提供机器学习、深度学习和高性能计算方面的加速库 4. APPS & FRAMEWORKS 主要对接TensorFlow 和 PyTorch 等框架 [图片] CUDA 最基本的执行单位是线程（Thread）、 1. 线程的执行，对应于硬件上的 CUDA Core，每个线程对应于 CUDA Core 2. 软件方面线程数量是超配的，硬件上 CUDA Core 是固定数量的。 3. 线程块只在一个 SM 上通过 Warp 进行调度 4. SM 可同时保存多个线程块 5. 多个 SM 组成的 TPC 和 GPC 硬件实现 GPU 并行计算 [图片] GPU 的算力峰值通常由以下因素决定 1. CUDA 核心数量 2. 核心频率 3. 每个核心的计算能力 4. 并行度 [图片] F 为 GPU 时钟周期内指令执行数 (FLOPS/Cycle)； SMN 是 SM 数量； reqF 是 Tensor Core核心运行频率（GHz） 2. 从GPU对AI芯片思考 DSA 之所以在硬件架构的指令和设计上比较激进，并非因为软件体系做得好，而是在刚开始并没有太多考虑编程体系的问题 CUDA 的成功之处在于通过 SIMT 架构掩盖了流水编排、实现了并行指令隐藏以及提升了 CUDA 的易用性 在指令流水编排方面，最重要的是从硬件设计上解决了 SIMD 数据路径（Data Path）流水编排问题。 程序执行最大的瓶颈是访存和控制流 SIMD 往往依赖于 CPU 自身乱序、投机、缓存和预取等能力来缓解上述问题 英伟达 GPU 则是依靠多线程交错执行，来提升整体并行计算的性能，大量的线程通过不同的线程块和不同的线程来读取数据和执行计算指令。 DSA流水编排仍然需要开发者动手实现，想写出开箱即用、性能较优的代码同样很难 3. AI芯片发展方向 谷歌在 2014 年开始研发基于特定领域架构（DSA）的张量处理单元（TPU），David Patterson 是计算机体系结构领域科学家，他提出： 1. 模型对内存和算力的需求日益变大 1. 推理模型需求增长速度快 1. AI 模型近几年所需的内存空间和算力平均每年增长 50%，模型所需内存和算力的增长为 10~20 倍。 2. 从芯片设计到实际应用需要一定的周期，其中芯片设计需要 1 年，部署需要 1年，实际应用并优化大约需要 3 年，因此共需要 5 年的时间 2. 训练模型参数量的增长速度要比推理模型更快 1. 2016~2023 年，SOTA 训练模型的算力需求年均增长 10 倍； 2. 2019~2020 年中期，GPT-2 模型的参数量从 15 亿增长到 GPT-3 的 1750 亿，提高了约 100 倍。 3. AI 芯片的内存容量增长相对比较缓慢 1. A100 的 HBM 最大内存是 80 GB，H100 最大内存是 188 GB 2. 谷歌 TPU v4 的内存是 32 GB 3. 特斯拉 DOJO 的内存是 16 GB 4. 华为昇腾内存是 64 GB 5. 寒武纪 MLU 370 内存是 24 GB/48 GB 2. 模型结构快速演变 1. 深度神经网络（DNN）是一个发展迅速的领域 1. 2016 年多层感知器（MLP） 2. 2026年长短期记忆网络（LSTM） 3. 2020 年卷积神经网络（CNN） 4. 2020年循环神经网络（RNN） 5. 2020年双向编码器表示（BERT） 2. 大型语言模型（LLM）基于 Transformer 1. 参数规模稳步增长到如今的万亿参数 2. OpenAI 的 GPT-3.5 3. 微软的 Phi-3 4. 谷歌的Gemma 5. Meta 的 Llama 3. 生产部署提供多租户 1. 需要多模型部署在一个NPU上 1. 机器翻译涉及语言对比，需要使用不同的模型； 2. 用一个主模型和配套多个模型进行实验； 3. 对吞吐量和时延有不同要求，不同模型使用不同的 Batch Size 2. 需要多租户技术（Multi-Tenancy）实现算力切分、显存虚拟化、内存寻址、虚拟内存页等 3. 目前常见的 GPU 虚拟化技术包括 NVIDIA vGPU（图 7.3.1）、AMD MxGPU 以及 Intel GVT-g 等虚拟化方案 4. SRAM 与 DRAM 的权衡 1. 多模型时候，如果从 CPU 主机重新加载参数，上下文切换需要 10 s 2. 因此需要更快的 DRAM（片外存储）用于交换多种模型的数据 3. 部分芯片的设计思路是期望利用 SRAM 解决所有任务，减少内存数据搬运时间，但这在多租户场景下很难实现 4. AI 芯片不仅需要更大的 SRAM 片上存储内存空间，更需要存储速度更快的片外存储 DRAM [图片] 5. 内存优先于计算速度 1. 访问片外 DRAM 需要的能耗是访问片上 SRAM 的 100 倍，是算术运算能耗的 5000 ~ 10000 倍 2. 减少内存访问是更有效的办法，GPGPU 的功耗大多浪费在数据搬运上，而非核心计算，而优化数据流正是 AI 芯片的核心价值 6. DSA 既要专业也要灵活 1. DSA 难点在于既要对模型进行针对性的优化，同时还须保持一定的灵活性 7. 半导体供应链的选型 8. 编译器优化和 AI 应用兼容 编译器维度比较多，既有类似于 CUDA 提供编程体系，又有类似于 TVM（深度学习编译器）和 XLA（加速线性代数）提供编译优化，包括对计算图进行图优化、内存优化、并行化、向量化等操作，以提高模型的执行速度和减少资源消耗 1. 实现 4096 个芯片的多核并行； 2. 向量、矩阵、张量等功能单元的数据级并行； 3. 322~400 位超长指令字的指令级并行，一条指令同时包含多个操作，这些操作在同一时钟周期内可并行执行； 4. 编译优化取决于软硬件能否进行缓存，编译器需要管理内存传输； 5. 编译器能够兼容不同功能单元和内存中的数据布局（如 Trans Data） 实际上可以通过算子融合（Operator Fusion）减少内存，从而优化性能。例如可以将矩阵乘法与激活函数融合，省略那些将中间结果写入 HBM 后再读取的步骤 [图片] 4. 超异构计算 异构计算的主要优势有： 1. 性能飞跃：异构架构将 CPU、GPU、FPGA 等计算单元有机结合，充分发挥各自优势，实现 1+1>2 的效果，显著提升计算性能。 2. 灵活定制：针对不同计算任务，灵活选择合适的主张计算单元，实现资源的高效利用。 3. 降低成本：相比于昂贵的专用计算单元，异构架构用更低的成本实现更高的性能，带来更佳的性价比。 4. 降低功耗：异构架构能够根据任务需求动态调整资源分配，降低整体功耗，提升能源利用效率 [图片] [图片] CPU 把数据准备好，并保存在 CPU 内存中； 1. 将待处理的数据从 CPU 内存复制到 GPU 内存（Step1）； 2. CPU 指示 GPU 工作，配置并启动 GPU 内核（Step2）； 3. 多个 GPU 内核并行执行，处理准备好的数据（Step3）； 4. 处理完成后，将处理结果复制回 CPU 内存（Step4）； 5. CPU 对 GPU 的结果进行后续处理 异构架构的优势 1. 适用于处理高性能计算 2. 适用于处理数据中心产生的海量数据 3. 可以共享内存空间，消除冗余内存副本 架构对比 1. GPU 具有较好的灵活性，但性能效率不够极致； 2. DSA 性能优异，但灵活性较差，难以适应复杂计算场景对灵活性的要求； 3. FPGA 的功耗和成本较高，需要进行定制开发，落地案例相对较少； 4. ASIC的功能完全固定，难以适应灵活多变的复杂计算场景 超异构的出现是应运而生的 1. 需求驱动 2. 工艺和封装支撑 3. 系统架构持续创新 [图片] 超异构有以下基本特征 1. 超大规模的计算集群 2. 复杂计算系统 超异构的软件层 1. 开放接口/架构及生态 2. 软件兼容 3. 编程体系 4. 开放架构 [图片] 1. 硬件定义软件（HDW） 1. 强调通过硬件来定义软件的功能和架构 2. 硬件加速器、专用指令集等技术 3. HDW 能够充分利用硬件的并行计算能力，显著提升软件的性能 2. 软件定义硬件（SDH） 1. 它强调通过软件来定义硬件的功能和性能 2. 软件抽象层（SAL）将软件和硬件解耦 3. 为软件提供了统一的硬件接口，屏蔽了不同硬件平台之间的差异 3. 软硬件协同定义（Co-Design） 1. 软件和硬件的设计团队紧密合作，共同探讨系统需求，并提出满足需求的软硬件解决方案 第八章 传统编译器 1. 引言 解释器在程序运行时将代码转换成机器码，编译器在程序运行之前将代码转换成机器码 编译器特点 1. 编译器读取源程序代码，输出可执行机器码 2. 将输入源程序转换为机器语言或低级语言，并在执行前报告程序中出现的错误 3. 编译的过程比较复杂，会消耗比较多的时间分析和处理开发者编写的程序代码。 4. 可执行结果，属于某种形式的特定于机器的二进制码 [图片] 前主流如 LLVM (Low Level Virtual Machine，底层虚拟机)和 GCC (GNU CompilerCollection, GNU 编译器套件) 等经典开源编译器的类型分为 1. 前端编译器： 1. 编译器的分析阶段也称为前端编译器，将程序划分为基本的组成部分，检查代码的词法、语义和语法，然后生成中间代码 2. 中间层编译器 1. 中间层主要是对源程序代码进行分析和优化 2. 分析阶段包括词法分析、语义分析和语法分析； 3. 优化主要是优化中间代码，去掉冗余代码、子表达式消除等工作 3. 后端编译器 1. 编译器的合成阶段也称为后端，针对具体的硬件生成目标代码，合成阶段包括代码优化器和代码生成器 编译器和解释器两者最大的差别在于编译器将一个程序作为一个整体进行翻译，而解释器则一条一条地翻译一个程序 程序主要有两种运行方式： 1. 动态解释是对代码程序边翻译边运行，通常将这种类型称为 JIT（Just in Time），即“即时编译 2. 静态编译是代码程序在执行前全部被翻译为机器码，通常将这种类型称为 AOT（Ahead ofTime），即“提前编译 IT 优点为： 1. 可以根据当前硬件情况实时编译生成最优机器指令。 2. 可以根据当前程序的运行情况生成最优的机器指令序列。 3. 当程序需要支持动态链接时，只能使用 JIT 的编译方式。 4. 可以根据进程中内存的实际情况调整代码，使内存能够更充分地利用。 JIT 缺点也非常明显： 1. 编译需要占用运行时（Runtime）的资源，会导致进程执行时卡顿，对某些代码编译优化不能完全支持，需在流畅和时间之间进行权衡。 2. 在编译准备和识别频繁使用的方法需要占用时间，初始编译不能达到最高性能。 JIT 的缺点也是 AOT 的优点所在： 1. 在程序运行前编译，可以避免在运行时的编译性能消耗和内存消耗。 2. 可以在程序运行初期就达到最高性能。 3. 可以显著加快程序的执行效率。 AOT 除优点之外，也会带来一些问题： 1. 在程序运行前编译会使程序安装的时间增加。 2. 将提前编译的内容保存起来，会占用更多的内存。 3. 牺牲高级语言的一致性问题 MindSpore、TensorFlow 等 AI 框架中默认包含了自己的 AI 编译器。目前 PyTorch2.X 版本升级后，也默认自带 Inductor 功能特性，可以对接多个不同的 AI 编译器 在 AI 领域，目前 AOT 的典型代表有： 1. 推理引擎，在训练之后 AI 编译器把网络模型提前固化下来，然后在推理场景直接使用提前编译好的模型结构，进行推理部署； 2. 静态图生成，通过 AI 编译器对神经网络模型表示称为统一的 IR 描述，接着在真正运行时执行编译后的内容 典型的代表有： 1. PyTorch框架中的 JIT 特性，可以将 Python 代码实时编译成本地机器代码，实现对神经网络模型的优化和加速。 2. 清华发布的计图（Jittor），完全基于动态编译 JIT，内部使用创新的元算子和统一计算图的 AI 框架，元算子和 Numpy 一样易于使用，并且超越 Numpy 能够实现更复杂更高效的操作。基于元算子开发的神经网络模型，可以被计图实时地自动优化并且运行在指定的硬件上 1. Pass 作为编译优化中间层的一个遍历程序或者模块 1. Pass 主要是对源程序语言的一次完整扫描或处理 2. Pass 指所采用的一种结构化技术，用于完成编译对象的分析、优化或转换等功能 3. Pass 的执行就是编译器对编译单元进行分析和优化的过程 4. Pipeline，则是由一个个 Pass 组成的，对于这些 Pass的管理，则是由 PassManager 完成的 5. LLVM 中提供的 Pass 分为三类：Analysis Pass、Transform Pass 和 Utility Pass 1. Analysis Pass 计算相关 IR 单元的高层信息，但不对其进行修改。这些信息可以被其他Pass 使用，或用于调试和程序可视化 2. Transform Pass 可以使用 Analysis Pass 的分析结果，然后以某种方式改变和优化 IR 3. Utility Pass 是一些功能性的实用程序，既不属于 Analysis Pass，也不属于 Transform Pass 2. 中间表示 (Intermediate Representation，IR) 负责串联起编译器内各层级和模块 1. 从广义上看，编译器的运行过程中中间节点的表示都可以统称为 IR。 2. 从狭义上讲编译器的 IR 是指该编译器明确定义的一种具体的数据结构 3. 编译器的前端、优化、后端之间，唯一交换的数据结构类型就是 IR，通过 IR 来实现不同模块的解耦 4. IR 在通常情况下有两种用途，一种是用来做分析和变换，另一种是直接用于解释执行 5. HIR（High IR）主要负责基于源程序语言执行代码的分析和变换 6. MIR（Middle IR），独立于源程序语言和硬件架构执行代码分析和具体优化。这些优化包括部分算术优化、常量和变量传播、死代码消除等，实现分析和优化功能。MIR 跟源程序代码和目标程序代码都无关，所以在编译优化过程中，通常是基于 MIR，比如三地址码（Three-Address Code，TAC） 7. LIR（Low IR），依赖于底层具体硬件架构做优化和代码生成。其指令通常可以与机器指令一一对应，比较容易翻译成机器指令或汇编代码 1. Frontend：主要负责词法和语法分析，将源代码转化为抽象语法树，即将程序划分为基本的组成部分，检查代码的词法、语义和语法，然后生成中间代码； 2. Optimizer：优化则是在前端的基础上，对得到的中间代码进行优化（如去掉冗余代码、子表达式消除等工作），使代码更加高效； 3. Backend：后端则是将已经优化的中间代码，针对具体的硬件生成目标代码，转换成为机器可读的二进制码 2. 传统编译器介绍 [图片] 3. GCC基本介绍与特性（略） 4. LLVM架构设计和原理 低级虚拟机（Low Level Virtual Machine）的首字母缩写 LLVM LLVM 的优化通过多个优化 Pass 来提升中间表示的性能。每个 Pass 都对 IR 进行特定的优化操作，例如： 1. 常量折叠（Constant Folding）：将编译时已知的常量表达式直接计算并替换。 2. 循环优化（Loop Optimizations）：如循环展开、循环交换等，以提高循环执行效率。 3. 死代码消除（Dead Code Elimination）：移除不必要的代码，提高执行效率 LLVM 的后端负责将优化后的中间表示转换为目标平台的机器码。这包含以下步骤： 1. 指令选择（Instruction Selection）：将 IR 转换为目标架构的汇编指令。 2. 寄存器分配（Register Allocation）：为指令分配合适的寄存器。 3. 指令调度（Instruction Scheduling）：优化指令执行顺序，以提高指令流水线的效率。 4. 代码布局（Code Layout）：调整代码的排列顺序，以适应目标硬件的执行特性。 5. 代码生成（Code Generation）：生成目标平台的汇编代码和最终的机器码 在中端优化完成之后会传一个 DAG 图的 IR 给后端，DAG 图能够非常有效地表示硬件的指定的顺序 DAG（Directed Acyclic Graph，有向无环图）是图论中的一种数据结构，它是由顶点和有向边组成的图，其中顶点之间的边是有方向的，并且图中不存在任何环路 在计算机科学中，DAG 图常常用于描述任务之间的依赖关系，例如在编译器和数据流分析中。DAG 图具有拓扑排序的特性，可以方便地对图中的节点进行排序，以确保按照依赖关系正确地执行任务 5. LLVM IR基本概念 在 LLVM IR 中，所生成的 .ll 文件的基本语法为： 1. 指令以分号;开头表示注释。 2. 全局表示以@开头，局部变量以%开头。 3. 使用 define 关键字定义函数，在本例中定义了两个函数：@test 和 @main。 4. alloca 指令用于在堆栈上分配内存，类似于 C 语言中的变量声明。 5. store 指令用于将值存储到指定地址。 6. load 指令用于加载指定地址的值。 7. add 指令用于对两个操作数进行加法运算。 8. i32 是 32 位 4 个字节的意思。 9. align 字节对齐。 10. ret 指令用于从函数返回 11. icmp 指令是根据比较规则，比较两个操作数，将比较的结果以布尔值或者布尔值向量返回，且对于操作数的限定是操作数为整数或整数值向量、指针或指针向量 12. br 指令有两种形式，分别对应于条件分支和无条件分支 6. LLVM IR细节详解 LLVM IR 具有类精简指令集、使用三地址指令格式的特征，使其在编译器设计中非常强大和灵活 三地址码是一种中间表示形式，每条指令最多包含三个操作数：两个源操作数和一个目标操作数 三地址码可以看作是一系列的四元组（4-Tuple），每个四元组表示一个简单的操作，操作符，操作数1，操作数2，目标结果 优点： 1. 简单性：三地址码具有简单的指令格式，极大地方便了编译器进行语义分析和中间代码生成操作。 2. 清晰性：每条指令执行一个简单操作，便于理解和调试。 3. 优化潜力：由于指令简单且结构固定，编译器能够轻松地实现多种优化技术，如常量折叠、死代码消除和寄存器分配。 4. 独立性：三地址码独立于具体机器，可以在不同平台之间移植 LLVM IR 是 LLVM 编译器框架使用的一种中间表示，采用了类似三地址码的设计理念。以下是 LLVM IR 指令集的一些特点： 1. 虚拟寄存器：LLVM IR 使用虚拟寄存器，而不是物理寄存器。这些寄存器以 % 字符开 头命名。 2. 类型系统：LLVM IR 使用强类型系统，每个值都有一个明确的类型。 3. 指令格式：LLVM IR 指令也可以看作三地址指令 LLVM IR 是一种通用的、低级的虚拟指令集，用于编译器和工具链开发 1. LLVM IR 设计为模块化的，代码和数据分为多个模块，每个模块包含多个函数、全局变量和其他定义 2. LLVM IR 是编译过程中的中间表示，位于源代码和机器码之间。这种层次化设计使得不同语言和目标架构可以共享通用的优化和代码生成技术 3. LLVM IR 采用 SSA （静态单赋值）形式，每个变量在代码中只被赋值一次。SSA 形式简化了数据流分析和优化 4. LLVM IR 使用强类型系统，支持基本类型（如整数、浮点数）和复合类型（如数组、结构体） 静态单赋值好处： 1. 每个值都由单一的赋值操作定义，这使得我们可以轻松地从值的使用点直接追溯到其定义的指令。 2. 由于 SSA 形式构建了一个简单的使用——定义链，即一个值到达其使用点的定义列表，这极大地简化了代码优化过程。 一个 LLVM IR 文件的基本单位是 Module。它包含了所有模块的元数据，例如文件名、目标平台、数据布局 在 Module 中，可以定义多个函数（Function），每个函数都有自己的类型签名、参数列表、局部变量列表、基本块列表和属性列表等，Function 类包含有关函数定义和声明的所有对象 每个函数可以有多个基本块（BasicBlock），每个基本块由若干条指令（Instruction）组成，最后以一个终结指令（Terminator Instruction）结束 Instruction 类表示 LLVM IR 的运算原子，即单个指令 7. LLVM前端和优化层 Clang 是一个强大的编译器工具，作为 LLVM 的前端承担着将 C、C++ 和 Objective-C 语言代码转换为 LLVM 中间表示（IR）的任务 通过 Clang 的三个关键步骤：词法分析、语法分析和语义分析，源代码被逐步转化为高效的中间表示形式 1. 词法分析器负责将源代码分解为各种标记的流 2. 语法分析器负责根据编程语言的语法规则，将这些标记流组织成符合语言语法结构的语法树。 3. 语义分析器确保语法树的各部分之间的关系和含义是正确的 LLVM IR 是连接前端和后端的中枢，让 LLVM 能够解析多种源语言，为多种目标生成代码。前端产生 IR，而后端接收 IR LLVM 优化层在输入的时候是一个 AST 语法树，输出的时候已经是一个 DAG 图 优化层每一种优化的方式叫作 Pass，Pass 就是对程序做一次遍历 1. 分析 Pass（Analysis Pass）：分析 Pass 用于分析程序的特定属性或行为而不对程序进行修改 2. 转换 Pass（Transformation Pass）：转换 Pass 用于修改程序代码以进行优化或重构 1. 显式依赖：转换 Pass 需要一种分析，则 Pass 管理器自动地安排它所依赖的分析 Pass 在它之前运行 2. 隐式依赖：转换或者分析 Pass 要求 IR 代码运用特定表达式。需要手动地以正确的顺序把这个 Pass 加到 Pass 队列中，通过命令行工具(clang 或者 opt)或者 Pass 管理器来完成 8. LLVM后端代码生成 LLVM 的后端是与特定硬件平台紧密相关的部分，它负责将经过优化的 LLVM IR 转换成目标代码，这个过程也被称为代码生成 整个后端流水线涉及四种不同层次的指令表示，包括： 1. 内存中的 LLVM IR：LLVM 中间表现形式，提供了高级抽象的表示，用于描述程序的指令和数据流。 2. SelectionDAG 节点：在编译优化阶段生成的一种抽象的数据结构，用以表示程序的计算过程，帮助优化进行高效的指令选择和调度。 3. Machinelnstr：机器相关的指令格式，用于描述特定目标架构下的指令集和操作码。 4. MCInst：机器指令，是具体的目标代码表示，包含了特定架构下的二进制编码指令。 [图片] 5. 编译器的每个模块和 Pass 均可通过 Pass manager 进行管理，可以动态添加、删除或调整 Pass 来优化编译过程中的各个阶段 PASS作用 1. 指令选择的主要任务是将中间表示（例如 LLVM IR）转换为目标特定的 SelectionDAG 节点，生成目标机器码的指令序列，实现从高级语言表示到底层机器指令的转换 1. 将内存中的 LLVM IR 变换为目标特定的 SelectionDAG 节点。 2. 每个 SelectionDAG 节点能够表示单一基本块的计算过程。 3. 在 DAG 图中，节点表示具体执行的指令，而边则编码了指令之间的数据流依赖关系。 4. 目标是让 LLVM 代码生成程序库能够利用基于树的模式匹配指令选择算法，以实现高效的指令选择过程 2. 指令调度是编译器优化的一部分，旨在通过重新排序程序中的指令来提高计算机程序的性能。这个过程通常包括前寄存器分配（Pre-Register Allocation, Pre-RA）调度和后寄存器分配（Post-Register Allocation, Post-RA）调度两个阶段 1. 前寄存器分配调度 2. 寄存器分配 3. 后寄存器分配调度 3. 代码输出（Code Emission）是 LLVM 后端的重要阶段，其目标是将中间表示（IR）转化为高效的目标机器码 1. 指令融合（Instruction Fusion） 2. 启发式优化（Heuristic Optimization） 3. 循环优化（Loop Optimization） 1. 循环展开（Loop Unrolling）：通过展开循环体，减少循环控制开销，提高指令流水线效率。 2. 循环交换（Loop Exchange）：调整嵌套循环的顺序，提高数据局部性。 3. 循环合并（Loop Fusion）：将多个循环合并为一个循环，减少循环开销 4. 在 LLVM 中，代码输出由以下组件共同完成： 1. 指令选择器： 2. 指令调度器 3. 寄存器分配器： 4. 汇编生成器 5. 机器代码生成器 第九章 AI编译器 1. 引言 首先，下一代编译器需要提供硬件抽象，以跨越多样化的加速器 其次，编译器必须支持异构计算平台 此外，随着特定领域计算需求的增长，领域特定语言（DSL）和编程模型变得越来越重要 最后，下一代编译器还需要确保基础设施的质量、可靠性和可扩展性 第一个重要挑战就是对于算子的优化，越来越多的 AI 算法诞生，带来了更多的新算子 这些算子还需要放在特定的 AI 芯片上进行优化，充分发挥硬件性能 目前阶段算子的开发和维护还是以人工手动实现、优化、测试为主的，人工优化算子的工作量是非常大的 第二个重要挑战是性能可移植性十分困难 AI编译器和传统编译器的联系： 1. 实现思路类似：AI 编译器与传统编译器都是通过自动化的方式进行程序优化和代码生成，从而节省大量的人力对不同底层硬件的手动优化。 2. 优化方式类似：在编译优化层，AI 编译器与传统编译器都是通过统一 IR 执行不同的 Pass进行优化，从而提高程序执行时的性能。 3. 软件栈结构类似：它们都采用前端、优化、后端三段式结构，通过 IR 解耦前端和后端实现模块化表示。 4. AI 编译器依赖传统编译器：AI 编译器对 Graph IR 进行优化后，将优化后的 IR 转化成传统编译器 IR，最后依赖传统编译器进行机器码生成 1. 编译目标的差异：传统编译器的起点是高级编程语言，终点则是硬件能够执行的机器码。相对地，AI 编译器 的输入是神经网络模型的计算图，而输出同样是机器码 [图片] 2. 软件栈的差异 [图片] 3. IR差异 1. AI 编译器通常针对的是神经网络模型，它们处理的是高度抽象的 IR，这种 IR 通常是为了描述复杂的数学运算而设计的 2. 传统编译器处理的是更为底层的 IR，这种 IR 更接近于机器指令，用于描述基本的计算操作 4. 优化策略的差异 1. 领域特定优化，AI 编译器面向 AI 领域，优化时会引入更多领域特定知识 2. 计算精度，AI 编译器可以降低计算精度，使用如 int8、fp16、bf16 等较低精度的数据类型 3. 硬件适配，AI 编译器在优化时会考虑特定硬件的特性，如 GPU、TPU 等 2. AI编译器历史阶段 AI 编译器具有以下四个特征 1. 以 Python 语言为前端，AI 编译器拥有以 Python 为主的动态解释器语言前端 2. 有多层 IR 设计，AI 编译器拥有多层 IR 设计，包括图编译 IR、算子编译 IR、代码生成 IR 等 3. 面向神经网络深度优化，这些优化可能包括内存访问模式的优化、并行计算的调度，以及针对特定 AI 框架 的定制化支持 4. 针对 DSA 芯片架构，AI 编译器需要能够理解和利用这些 DSA 芯片的特性，生成能够充分利用这些定制化硬件的代码，从而实现性能的最优化 朴素AI编译器： 1. 硬件无关的优化 1. 表达式化简 2. 常量折叠 3. 自动微分 2. 硬件相关的优化 1. 算子融合 2. 内存分配 专用 AI 编译器 1. PyTorch 框架以其动态图（也称为即时执行模式）而受到欢迎， 2. 编译器需要将动态图转换为静态图，以便于进行进一步的优化 1. 在某些场景下，需要根据运行时信息动态调整计算图结构，而专用编译器在这方面的支持不足 2. 当输入数据的形状（例如批量大小或输入特征维度）在运行时变化时，专用编译器难以适应这种动态性。 3. 对于稀疏数据集，专用编译器可能没有优化计算路径以减少不必要的计算和内存使用。 4. 在多设备或多节点上进行模型训练和推理时，专用编译器可能缺乏有效的并行化策略和优化 3. 专用 AI 编译器在算子实现方面依然缺乏自动化的优化手段，如调度、分块和代码生成 AI编译器基本架构如下图 [图片] 3. AI编译器基本架构 推荐阅读 AI 编译器的一篇综述—— The deep learning compiler: a comprehensive survey（Li et al., 2021） [图片] 1. 编译器前端 编译器前端主要负责接收和处理来自不同 AI 框架的模型，并将其转换为通用的中间表示（IR），进行初步优化 这些模型通过符号表示的转换（如 TVM、nGraph 等）生成计算图；高级 IR/图IR（设备无关）包含了 DAG（有向无环图）表示形式以及张量计算；计算图经过多种优化得到初步优化的计算图；随后通过模式匹配和图重写等方法进一步优化，最终生成优化后的计算图 1. 输入格式：支持多种 AI 框架，如 MindSpore、PyTorch、飞桨（PaddlePaddle）和 ONNX 2. 转换：将来自不同框架的模型转换为统一的表示形式 3. 高级 IR/图 IR：这些 IR 是设备无关的，主要用于表示计算图 4. 计算图优化策略：构建计算图并进行优化，具体优化包括代数简化、算子融合、CSE（公共子表达式消除）、DCE（死代码消除）、静态内存优化、布局转换 5. 优化方法：对计算图进行进一步优化，使用各种方法如 Pattern Matcher（模式匹配）和Graph Rewriting（图重写）等 6. 调试工具 2. 编译器后端 编译器后端负责将优化后的计算图转换为特定硬件平台的低层次表示，并进行硬件特定优化和代码生成 1. 硬件特定优化：针对特定硬件的优化技术，包括：Intrinsic Mapping（内在映射）、Memory Allocation（内存分配）、Memory Latency Hiding（内存时延隐藏）、Loop Oriented Optimization （面向循环的优化）以及 Parallelization（并行化）等。 2. 调度：包括 Auto Scheduling（自动调度），如 Polyhedral（多面体模型）；也包括 Manual Scheduling（手动调度），如 Halide。 3. 自动调优：使用自动调优策略，方法包括 Parameterization（参数化模型）、Cost Model （成本模型）以及 Parameter Searching（参数搜索）等。 4. 使用内核库：使用优化的内核库提高执行效率，如：Intel DNNL、NVIDIA cuDNN/ TensorRT、AMD MIOpen 或者其他定制化库。 5. 低级 IR/操作符 IR：生成设备特定的低层次 IR，包括：基于 Halide 的 IR、基于多面体模型的 IR 或者其他特有的 IR。 6. 编译方案：支持 JIT 和 AOT 等编译方案。 7. 代码生成：生成适用于特定硬件平台的代码，如：LLVM、CUDA、OpenCL、OpenGL 等。 8. 目标平台：最终生成的代码可以在多种硬件平台上运行。例如能在 x86、ARM、RISC-V 等架构的 CPU 上运行；或在英伟达、AMD 的 GPU 上运行；亦可在 ASIC（应用专用集成电路上运行，例如 TPU、Inferentia、NNP 等；也可在 DSP（数字信号处理器）上运行；同时也需要对越来越多新出现的 Accelerators（加速器）拥有一定的兼容性 3. 中间表示IR 1. 高级IR 1. 高级 IR 主要用于表示计算图，它的设计目的是解决传统编译器在表达神经网络模型等复杂运算时遇到的困难，同时为实现更高效的优化提供支持 2. 高级抽象 3. 支持神经网络模型 4. 优化支持 5. 硬件无关性 6. 跨平台支持 2. 低级IR 1. 基于 Halide 的 IR 2. 基于多面体模型的 IR 3. 其他独特的 IR 4. 前端优化 构建计算图后，前端会进行图级优化 前端优化通常由一系列 Pass 定义，通过遍历计算图节点并执行图转换来应用这些优化 除了预定义的 Pass 外，开发人员还可以在前端自定义 Pass，以满足特定的优化需求或实现定制化的优化策略 1. 节点级优化 1. 节点级优化是指针对计算图中的单个节点或操作进行的优化，旨在改进节点级别的计算效率和性能。 2. 常用的节点级优化方法包括 Zero-Dim-Tensor Elimination（零维张量消除）、Nop Elimination（空操作消除）等 2. 块级优化 1. 块级优化是指在计算图中针对连续的一组节点或者局部区域进行的优化。这些优化更关注局部区域的性能改进，而不是单个节点。 2. 局部优化则更广泛地指涉到对一组节点或者一个子图进行的各种优化。常用的方法包括代数简化、常量折叠、算子融合等 3. 数据流级优化 1. 数据流级优化是针对整个计算图或者数据流进行的优化，目标是最大化整体计算效率和性能。 2. 包括流水线调度、内存布局优化、并行化、数据流重构等技术， 3. 常用的方法包括公共子表达式消除、死代码消除等 5. 后端优化 通用 AI 编译器的后端通常包含各种特定硬件优化、自动调整和优化内核库 1. 特定硬件优化 1. 特定硬件优化，也称为目标相关优化，是为了获得针对特定硬件的高性能代码而应用的 2. 实现后端优化的一种方法是将低级 IR 转换为 LLVM IR，利用 LLVM 基础设施来生成优化的 CPU或 GPU 代码。 3. 另一种方法是利用深度学习领域的专业知识设计定制化的优化，更有效地利用目标硬件 2. 自动调优 1. Halide/TVM 方法，Halide 和 TVM 可以自动搜索和评估不同的调度和计算表达组合，从而找到性能最优的配置方案 2. 应用多面体模型进行参数调整 3. 优化内核库 1. 英特尔的 DNNL、英伟达的 cuDNN、AMD 的 MIOpen 6. AI 编译器全栈产品 1. Hardware 2. Kernel Level 3. Graph Level 4. DL Models [图片] 4. AI编译器挑战与思考 [图片] [图片] AI编译器五大挑战是 1. 动态 Shape 泛化，包含动态 Shape 输入或者控制流语义的动态计算图，AI 编译器的支持确实有限 2. Python 编译静态化 3. 充分发挥硬件性能，AI 编译器还将多种优化手段融合在一起，包括垂直融合优化（如 Buffer Fusion 等）和水平并行优化（如 Data Parallel 等），重新组合优化后的子图的 Kernel 代码也将自动生成，包括调度（Scheduling）、分块（Tiling）、向量化（Vectorizing）等操作 4. 特殊算法优化方法，通过规模扩展（Scale Out）利用多维混合并行能力，如数据并行、张量并行和流水并行，通过性能提升（Scale Up）采用重计算、混合精度和异构并行等技术 5. 易用性与性能兼顾 1. 与 AI 框架的边界和对接 2. 对用户透明性问题 3. 编译开销 4. 性能问题 AI编译器的未来 1. 编译器形态 1. 未来的 AI 编译器将分为推理和训练两个阶段，采用 AOT 和 JIT 两种编译方式 2. 在推理阶段，编译器将预先编译模型以实现高效执行 3. 在训练阶段，编译器则倾向于即时编译以应对动态需求 2. IR 形态 1. 未来的 AI 编译器需要一个类似于 MLIR 的统一中间表示（IR） 3. 自动并行 1. 未来的 AI 编译器将具备自动并行的编译优化能力，能够跨机器、跨节点进行任务的并行处理 2. 这种功能的引入将为大模型的训练和推理提供更强大的支持 4. 自动微分 1. 未来的 AI 编译器将提供先进的自动微分功能，能够支持高阶微分的计算方式 5. Kernel 自动生成 1. 未来的 AI 编译器将实现自动化的 Kernel 生成功能，从而降低开发门槛，快速实现高效且泛化性强的算子 2. 这种自动生成 Kernel 的功能将大大简化算法开发和优化的流程，减少了手工调优的时间和精力 第十章 前端优化 1. 引言 [图片] AI 编译器的前端优化中包含许多图层优化的技术点，即优化 Pass，包括算子融合 Pass、内存分配 Pass、内存排布 Pass、常量折叠 Pass 等，不同的 Pass 执行不同的优化逻辑，相互组合共同完成 AI 编译器的前端优化 2. 图算IR AI 框架前端将对 Python 代码进行解析产生 Graph IR AI 编译器前端优化流程中，AI 编译器将对输入的 Graph IR，依次执行包括但不限于常量折叠、常量传播、算子融合、表达式简化、表达式替换、公共子表达式消除等各种前端优化 Pass，各个 Pass 的执行结果仍然为 Graph IR 并输入到下一个 Pass 中，直到前端优化结束并输出最终优化后的 Graph IR 计算图是一个有向无环图（Directed Acyclic Graph，DAG），主要用来表示神经网络模型在训练与推理过程中的计算逻辑与状态，它由基本数据结构张量（Tensor）和基本运算单元算子（Operator）构成 一般将多维数据称为张量 “算子”是 AI 框架的一个概念，在硬件底层实现具体算子执行部分，一般被称为 Kernel [图片] 一般静态图的模型权重文件不仅包含权重数据，还包含了计算图的信息，而动态图一般用于训练阶段，在训练完成后通常不会保存计算图的信息 通常在推理阶段会使用模型的计算图的信息，因此在部署能力方面，静态图优于动态图 动态图转换为静态图 1. 基于追踪转换的方式 2. 基于源码转换的方式 计算图对 AI 编译器作用 1. 方便底层编译优化 2. 分层优化便于扩展 1. 将 AI 编译器的前端优化部分分为三个解耦的优化层 2. 计算图优化 3. 运行时调度优化 4. 算子/内核执行优化 3. 算子融合 算子融合主要为了解决内存墙和并行墙问题 1. 内存墙,存在数据依赖的“生产者-消费者”算子进行融合，从而提升中间 Tensor 数据的访存局部性,Buffer 融合一直是算子融合的主流技术. 2. 并行墙，主要是由芯片多核增加与单算子多核并行度不匹配引起 4. 布局转换原理 空间局部性指的是如果一个内存位置被引用了一次，那么程序很可能在不远的将来引用其附近的一个内存位置，它会影响到程序执行中的缓存及其他性能 数据在内存中存储时相对于起始地址的偏移量是数据大小的整数倍，称为自然对齐，相对应的通过编译器或语言的指令强制变量按照特定的对齐方式存储，称为强制对齐 四个维度分别为 N——批量（Batch）大小，一般指图像数量；C——特征图通道数（Channels）；H——特征图的高度（Height）；W——特征图的宽度（Width） NHWC 排布方式适合多核 CPU 运算，而 NCHW排布方式适合 GPU 并行处理，且张量的连续性取决于其逻辑与物理存储结构的相邻性。 5. 内存分配算法 内存分配主要包括两类情况——静态内存和动态内存 静态内存主要包括三个部分 1. 首先是模型的权重参数（Parameter），指的是神经网络中的可训练参数，这些权重参数在模型训练时会被反复调用和更新，但在 NPU 的内存中始终占用固定大小的相同的内存区域 2. 其次是常量值节点（Constant Value Nodes），通常用于存储训练过程中的常量数据或需要持久化的中间结果，与权重参数类似，内存空间也是预先分配好的，并且内存占用在计算过程中不会改变 3. 最后是模型的输出（Output），指的是网络在推理或训练结束时产生的最终结果，这部分内存同样是固定分配的，在训练或推理过程中不会被重新分配或释放 动态内存与静态内存不同，其内存的分配和释放是动态进行的 首先是输出张量（Output Tensor），指的是在神经网络前向传播过程中每层计算所生成的中间结果 其次是工作区张量（Workspace Tensor），用于存储中间计算结果或者其他临时数据，仅在特定的计算操作中需要 常见的节省内存的算法分为四种类型，包括空间换内存、计算换内存、模型压缩、内存复用等 1. 空间换内存的算法：将 GPU 或 NPU 内存中的部分模块卸载到 CPU 内存中（CPU Offload），该类算法更常见于对 MoE 的模型结构进行算法优化。 2. 计算换内存的算法：在部分场景下重新计算数据的效率比从存储空间中读取数据的效率高，那么可以选择不保存数据而在需要数据时进行重计算，例如使用梯度检查点（Gradient Checkpointing）技术。 3. 模型压缩的算法：在端侧推理场景下应用较多，包括但不限于量化训练 （Quantification）、模型剪枝、模型蒸馏等压缩算法。 4. 内存复用：利用 AI 编译器对计算图中的数据流进行分析，以允许重用内存 在内存复用中存在若干常见操作，例如替换操作 Inplace Operation，即当一块内存不再被需要时，且下一个操作是 element-wise 时，可以在原地覆盖内存 6. 常量折叠原理 常量折叠（Constant Folding）是编译器的一种优化技术，它通过在编译期间对常量表达式进行计算，将其结果替换为常量值，从而减少程序运行时的计算和开销 传统编译器通常是对抽象语法树进行常量折叠优化，而 AI 编译器是对计算图进行常量折叠优化 1. 当计算图中某个节点的数据输入边的源节点均为编译期常量的节点，则可以提前计算出该节点的值来完全替换该节点 2. 以 AddN 为例，对于两个形状大小为(N,C,H,W)四维常量 Tensor，AddN 的计算结果在编译期间是可以确定的，可以生成一个与该结果等值的数据节点替换掉 AddN 3. 输入形状确定的 Shape 类型的操作，比如 Size、Shape 等操作。这些操作都只与输入的形状有关，与输入的具体值无关 4. 数据输入节点不全为编译常量节点，但是这部分节点是可常量折叠的节点，即经过一系列的常量折叠后，该节点会被替换成编译常量节点 7. 公共子表达式消除原理 公共子表达式消除（Common Subexpression Elimination，CSE）也称为冗余表达式消除 在程序中，有时会出现多个地方使用相同的表达式进行计算，并且这些表达式的计算结果相同 公共子表达式消除的目标就是识别出这些重复的计算，并将其提取出来，只计算一次，然后将结果保存起来供后续使用 编译器开发者将公共子表达式消除分成两类。如果这种优化仅限于程序的基本块内，便称为局部公共子表达式消除；如果这种优化范围涵盖了多个基本块，那就称为全局公共子表达式消除 局部值编号（LVN）和缓式代码移动（LCM）是两种常见的公共子表达式消除方法 8. 死代码消除 死代码消除（Dead Code Elimination，DCE）是一种编译器优化技术，旨在删除程序中不会被执行的代码，从而提高程序的执行效率和资源利用率 在传统编译器中，死代码消除通常是通过分析控制流图，从而找到并删除无用和不可达操作对应的代码 1. 不可达操作 2. 无用操作 9. 代数简化 代数简化（Algebraic Simplification）是一种从数学上来指导我们优化计算图的方法。其目的是利用交换律、结合律等规律调整图中算子的执行顺序，或者删除不必要的算子，以提高计算图整体的计算效率 1. 先抽象出一套通用的子图替换框架，再对各规则实例化。 2. 针对每一个具体的规则实现专门的优化逻辑 1. 算术简化 结合律即不论我们怎样结合数字（即先计算哪些数字），答案都是一样的 交换律是说，把数的位置对换而结果不变 分配律，A*(B+C)=A*B+A*C 2. 运行简化 1. 逆函数等于其自身函数的对合算子简化 2. 幂等算子简化，即作用在某一元素两次与一次相同 3. 广播简化 当多个张量形状 (Shape)不同情况下，需要进行广播（Broadcast）将张量的形状拓展为相同的 Shape 再进行运算 第十一章 后端优化 1. 引言 后端优化的流程一般分为三步 1. 生成低级 IR：将高级或计算图级别 IR（Graph IR）转换为低级 IR（Tensor IR） 2. 后端优化：进行后端优化，并将 IR 转换为更低级的 IR 1. 数据形式不同：深度学习中数据形式主要为张量（Tensor）。而传统编译器不擅长对张量计算优化，更擅长对标量进行计算。 2. 缺乏必要的支持：传统编译器主要针对通用编程语言，缺乏对领域特定语言（DSL）的支持，特别是对神经网络，以及相关的特殊优化 3. 代码生成：根据硬件进行代码生成 算子根据其计算形式的特点可分为访存密集型与计算密集型 1. 访存密集（Memory-Bound）型，指的是在执行过程中主要涉及大量内

很多地方不够深入，边缘设备在没有NPU的情况下需要汇编级别的优化

一本讲AI算法硬件加速不错的书。尤其是模型量化这块，原理讲的很透彻，之前看安霸芯片的量化方式，总是云里雾里，看了这本书之后有种醍醐灌顶的感觉。