Technique

在编写算子和框架的时候，经常需要分析程序的性能瓶颈。我们需要一个合适的指标和指导方法，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

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

RoPE from Fundamental Series