Ubios’ Blog. AI & Sys.

在编写算子和框架的时候，经常需要分析程序的性能瓶颈。我们需要一个合适的指标和指导方法，Roofline model给出了一个简洁的定量分析方法。Roofline模型引入了一种基于Operational Intensity的定量分析方法，它定义了在计算平台上可实现的理论最大计算效率。该模型还提供了一个公式，用以计算在特定计算环境中可能达到的最高理论性能。 我们先来看下roofline model的直观表示： Roofline ModelRoofline: An Insightful Visual Performance Model for Floating-Point Programs and Multicore Architectures 我们先来看下图中指标的定义： 计算强度 $I$ : 每Byte内存在交换后用于进行了多少浮点运算，即FLOPs/Bytes。模型的计算强度$I$越大，对于内存带宽的压力越小，内存的使用效率越高。 算力的大小决定了屋顶的高度，带宽决定了斜率。 在达到屋顶的转折点之前都是Memory Bound，在之后是Compute Bound。在Compute Bound的区域，不管计算强度$I$有多大，它的计算性能都由机器的实际最大计算性能所限制。 Note: roofline model讲的是程序理论上可以达到的最好性能，而不是实际达到的性能。如cache大小的限制，网络限制，未必能达到roofline模型定义的边界。

0x01 前言 XNNPACK是一个由Google维护的算子库，在TensorFlowLite，ExecuTorch，ONNX RT等众多知名框架中使用。笔者最近在做mllm的xnnpack后端适配工作，因xnnpack缺少文档，在此记录。 xnnpack的test中展示了大部分xnnpack的API和使用方式，读者在碰到API使用问题的时候不妨去test文件夹下面找找答案；xnnpack遵循标准的doxygen注释，也较好的说明了函数和class的使用方法。 在xnn中使用的是静态图构建的方法，在开始构建静态图之前，需要初始化xnn： xnn_initialize(nullptr /* allocator */) 使用如下API可以构建出一张subgraph，接下来的所有操作都在更改这张子图， xnn_subgraph_t subgraph_ = nullptr; auto status = xnn_create_subgraph(external_nums, 0, &subgraph_); 0x02 定义 Tensor 定义未经过量化的Tensor使用的API是： uint32_t uuid; status = xnn_define_tensor_value( /*subgraph*/..., /*dtype*/..., dims.size(), dims.data(), /*data=*/..., /*external id*/XNN_INVALID_VALUE_ID, /*flag*/0, /*id*/&uuid); 这里需要特殊解释的是external_id、flag和uuid三个值： external_id 是对于EXternal Inputs和Outputs才需要设置的，对于xnnpack内部管理的Tensor，不需要设置这个值，给出默认的XNN_INVALID_VALUE_ID就行。external_id的作用是让xnnpack可以从runtime中传入的external_values中索引到需要的Tensor值。详细解释如下： 在xnnpack中，每个Tensor都会有一个uuid，对于xnnpack自己管理的Tensor，uuid在定义的时候会由xnnpack自己生成。还记得在xnn_create_subgraph创建的时候需要传入external_nums吗？这里的external_nums就是用户侧预留的uuid。比如external_nums是3的时候，xnn_define_tensor_value就会从4开始计数给新创建的Tensor。而前3个Tensor，即external Tensor的uuid(external_id)就是1，2，3。 flag flag是用来标识这个Tensor是不是External Inputs，Outputs或者是其他类型的Tensor。比如inputs tensor的flag是flags = XNN_VALUE_FLAG_EXTERNAL_INPUT;, outputs 是 flags = XNN_VALUE_FLAG_EXTERNAL_OUTPUT; uuid 是每个Tensor的全局索引标识 题外话： 在mllm中，Tensor的define过程如下： void defineXpTensor(XnnpackBackend *xpb, Tensor *t, XpTensorType ttype) { if (t->uuid() !...

本文主要总结两篇文章：Deja Vu 和 Apple 的 LLM in a flash。这两篇文章的内容都是端侧推理加速的尝试，他们主要使用了大致的思路–利用MLP的稀疏性，各自的工程实现各有一些创新。 Deja Vu: Contextual Sparsity for Efficient LLMs at Inference Time LLM in a flash: Efficient Large Language Model Inference with Limited Memory 端侧推理有着比较大的应用前景，随着端侧设备的算力跟进，端侧设备已经具有了运行7B模型的能力。在端侧运行小参数模型可以极大的减少云端的压力，从而减少运营成本。相比于云端的大模型，端侧大模型处理复杂问题能力不足，所以端侧和云端应该是相辅相成的。轻量级任务给端侧，需要长逻辑理解的任务交给云端。 端侧和云的协同工作，也是一个很好的研究方向。 0x01 Deja Vu 1. 问题分析和动机 作者通过分析OPT-175B模型的上下文稀疏性发现对于大部分的Transformer Layer，他们的稀疏性都在85%左右。上下文稀疏性就是：对于特定的输入，仅有一小部分的模型参数对最终结果有着重要的影响。 如图1-3所示： Fig 1. Contextual SparsityDeja Vu: Contextual Sparsity for Efficient LLMs at Inference Time Fig 3. Contextual sparsity in Attention HeadDeja Vu: Contextual Sparsity for Efficient LLMs at Inference Time...

GEMM/GEMV in MLLM Slides 在本文中我以mllm的实现为例。mllm中的大部分混合精度的矩阵乘法是从llama.cpp中更改过来的。我们先来看下Q8_0和Q4_0代表什么。Huggingface的Doc中给出了一张表，大家可以去看一下：GGUF Quantization Type，我在这里也截图给出来 Fig 1. Q8_0和Q4_0含义GGUF Quantization Type FROM Huggingface 对于量化操作不是很熟悉的读者可以看下我之前的blog: [Fundamental] 模型量化 在mllm中，Q8_0和Q4_0的实现是这样的： typedef struct { mllm_fp16_t d; // delta int8_t qs[QK8_0]; // quants QK8_0 = 32 } block_q8_0; // QK4_0 = 32 typedef struct { mllm_fp16_t d; // delta uint8_t qs[QK4_0 / 2]; // nibbles / quants } block_q4_0; 而Q4_0x4实际上就是将4个Q4_0打包成一组，这样在GEMM的时候可以利用起指令并行性。 我们首先来看下GEMV问题定义，然后再推广到GEMM上。我们有两个矩阵，分别是A($1 \times nr$), B($nc \times nr$)，矩阵乘法后的结果是C$1 \times nc$。一个不是非常恰当的图例如下图所示： Fig 2. Q8_0和Q4_0x4的GEMV 为了更好的理解怎么分块，我们先来看下Q4_0x4的数据排布是怎么样的：Q4_0x4实际上是在$nc$的方向上以4分块，在$nr$的方向上以32分块，最终得到的block形状如下图所示： Fig 3. Q8_0和Q4_0x4的GEMV Tiled 我们在$nc$的方向上以4分块，在$nr$的方向上以32分块，将gemv拆解成一个更小的子问题。...

0x00 前沿和阅读材料 FlashDecoding系列的文章是对FA在推理场景下的改进，目前包含两篇文章： Flash-Decoding for long-context inference, Torch团队的Blog FlashDecoding++: Faster Large Language Model Inference on GPUs 我们知道，在FA2中特别对Seq方向做了并行化，但是在推理的时候Seq=1。此时，并不能占用满GPU的全部的SM，导致性能损失，FlashDecoding就是对此的优化。 0x01 FlashDecoding 在解码过程中，生成的每个新Token都需要考虑之前的所有Token，以便进行注意力计算。 在训练的时候，Attention这一算子已使用FlashAttentionV2算法进行了优化，其瓶颈在于读写中间结果（例如 Q @ K^T）的内存带宽不足。但是，这些优化并不能直接应用于推理，因为推理的时候不在是内存带宽的瓶颈。在训练过程中，FlashAttention 会在Batch和Seq两个维度上进行并行处理。在推理过程中，Seq=1，这意味着，如果Batch大小小于 GPU 上的SM数量（A100 为 108），则这个Attention操作只会使用 GPU 的一小部分！在使用长上下文时尤其如此。当Batch大小为 1 时，FlashAttention 将使用不到 1%的 GPU！ Fig 1. Regular AttentionFlash-Decoding for long-context inference 为此我们不难想到可以实用Split-K的方法来使得Attention在推理的时候也有很好的并行性。如下图所示： Fig 1. Split-K AttentionFlash-Decoding for long-context inference 非常的好理解，但是这里需要注意的是，在最后的Reduce Op这里还是要做Online Softmax的，所以在SRAM里面保存的东西是比原来多的，除了Output，还有exp Sum和Max。 0x02 FlashDecoding++ flashdecoding++不是meta官方出品的。 FA中，求解Max需要遍历迭代，之后的子块依赖于之前的子块。Safe-softmax的计算公式中，需要先求每行x的最大值，然后减去这个max(x)之后，再做softmax以防止数值溢出。FlashDecoding++提出的创新点就是，我们可以实用一个先验的$\phi$来作为max值，只要它能让数值稳定就可以了。从Safe Softmax的公式上来看，无论是$\phi$还是max(x)，他们的结果是一致的，我们需要追求的是数值上的稳定与否。 FlashDecoding++认为一个合理的先验值 $\phi$，可以直接从数据集中进行统计获得。对于不同的模型，这个先验值也是不一样的。在实现的时候，FlashDecoding++还使用了Fallback的思路，当出现数值溢出的时候，使用传统的FlashDecoding。 那为什么FalshDecoding++能异步，而FlashDecoding不行呢？ 在FalshDecoding Split-K分成的几个区间内，还是使用的FA2的方法来计算，但是FA2的一次迭代是依赖于上一次迭代的结果的，也就是需要rescale。但是FlashDecoding++不需要，它大致上是这样的： $$\begin{aligned} &\ell^{(1)}=\mathrm{rowsum}\Big(e^{\mathbf{S}^{(1)}-\phi}\Big)\in\mathbb{R}^{B_{r}} \\ &\tilde{\mathbf{O}}^{(1)}=e^{\mathbf{S}^{(1)}-\phi}\mathbf{V}^{(1)}\in\mathbb{R}^{B_{r}\times d} \\ &\ell^{(2)}=\mathrm{rowsum}\left(e^{\mathbf{S}^{(2)}-\phi}\right) \\ &\tilde{\mathbf{O}}^{(2)}=e^{s^{(2)}-\phi}\mathbf{V}^{(2)} \\ &\mathbf{O}^{(2)}=\mathrm{diag}\left(\ell^{(1)}+\ell^{(2)}\right)^{-1}(\tilde{\mathbf{O}}^{(1)}+\tilde{\mathbf{O}}^{(2)})=\mathbf{O} \end{aligned}$$

RoPE from Fundamental Series

0. 前言 本问分析的两篇文章是： 2024-05, SpinQuant: LLM quantization with learned rotations from meta，一作是 Zechun Liu 2024-04, QuaRot: Outlier-Free 4-Bit Inference in Rotated LLMs from ETH Zurich、EPFL、Microsoft Research、IST Austria & NeuralMagic 这两篇文章以相同的视角去解决问题，并且量化后的模型保持了相当好的性能，应该就是未来模型量化的一个主要的跟进方向。QuaRot和SpinQuant可以算作是同一系列的工作，SpinQuant在QuaRot的基础上做了可学习旋转矩阵的改进。 1. Computational Invariance Computational Invariance是Quarot和SpinQuant的基础。 Computational Invariance定理[1]指出，可以使用正交矩阵对Transformer 中的权重和块间激活进行变换，而模型输出不变。这个定理是说，如果$W_{in}$是一个在transformer block(i.e. $W_k,W_q,W_v$等)左边的权重，我们可以左乘上一个正交的矩阵$Q$，为了在最后的结果里消除这个影响，我们可以在输出矩阵(i.e. $W_{out}, W_{down}$)右边乘上$Q_T$。 尽管 RMSNorm 被应用于两个数据块之间，但只要 RMSNorm 数据块中没有重新缩放（在实际操作中，我们会先将任何重新缩放吸收到相邻的权重矩阵中），这一点还是适用的。从概念上讲，这是因为 RMSNorm 将激活值除以它们的模长，而对激活值应用旋转矩阵$Q$不会影响模长（因为正交矩阵的特性）： $$\text{RMSNorm}(\boldsymbol{X}) = \text{RMSNorm}(\boldsymbol{X\boldsymbol{Q}^T})\boldsymbol{Q}$$ 我们这里假设RMSNorm对激活值$\boldsymbol{X}$的每一行做的操作都是$x_{i} \larr x_i/ \Vert x_I \Vert$。这意味着，将输出矩阵乘以 $Q^T$ 会使线性层输出$XQ^T$，$XQ^T$被归一化，然后传入下一个区块，其输入权重矩阵现在是$QW$，因此该线性层不做任何修改就会输出原始激活。 2. 🥕Quarot Quarot有两个阶段，一个阶段是在全精度下操作模型权重，并在模型的前向传递中插入两个额外的乘Hadamard矩阵操作；在第二个阶段使用现在的量化方法来量化夹在Hadamard矩阵中的模型权重，因为这些权重被削减了峰度，outliers减少，可以使量化的压力小很多。 Fig 1. QuaRot workflow 1 Fig 2. QuaRot workflow 2 Quarot文中的图片已经非常清晰的描绘了什么时候做旋转以及何时做量化和量化的数据流。SpinQuant和Quarot比较了实验结果，Quarot的实验结果请看第三章节的SpinQuant的表格。...

以Qwen0.5B为例解析mllm的基本实现，NPU Backend