Papers

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的表格。...

http://arxiv.org/abs/2310.16795 MLSys 2024 1.背景和动机 为了解决大型模型的高推理成本问题，MoE架构被提出。MoE通过稀疏路由的方式，将输入分配给多个专家（experts）中的一小部分，以实现更快的推理速度和更高的模型质量。但这种架构也带来了巨大的参数量，例如SwitchTransformer-c2048模型就有1.6万亿参数。MoE模型的参数量巨大，需要数TB级的存储空间，这使得它们在实际部署时面临内存和成本的挑战，尤其是在需要大规模并行计算的场合。 为了降低MoE模型的内存和存储需求，同时保持模型性能，模型压缩成为了一个重要的研究方向。传统的压缩技术，如量化和稀疏性，虽然在一定程度上有效，但对于参数量达到万亿级别的模型来说，仍然不足以实现高效的压缩。 本文提出了QMoE，一种新的压缩和执行框架，旨在实现对万亿参数MoE模型的高效压缩和推理。QMoE通过设计一种可扩展的算法，将模型压缩到每个参数不到1比特的大小，并与定制的GPU解码内核协同设计，以实现端到端的高效压缩推理，且运行时开销相对较小。 Fig 1. 量化结果http://arxiv.org/abs/2310.16795 作者首先考虑了Huffman和LZW两种常用于文件压缩的方法。但是Huffman方法的解码依赖于上文已经被解析的参数，并行性低；且变长的编码方式在实现上和存储的时候也是较为困难的。作者总结出了MoE量化的4个难点： 现有的压缩方法，如量化和稀疏性，通常只能在不显著损失精度的情况下将模型的精度降低到每个参数3或4比特，或者达到大约50%的稀疏度。然而，要使万亿参数的MoE模型实用化，需要比16位精度高出10到20倍的压缩率，即平均每个参数少于1比特。 将现有的压缩方法应用于比大型dense模型大一个数量级的MoE模型时，会遇到内存、性能和可靠性方面的障碍。MoE模型由于其稀疏性，需要处理的内存和数据量巨大。即量化过程需要的内存太大，且可能会出现因为corner case导致量化失败的问题。 实现每个参数少于1比特的压缩率需要一个非平凡的自定义压缩格式，并且这种格式需要配备在GPU等加速器上高效的解码算法，以避免在压缩模型上进行推理时出现重大的处理延迟（比如要避免Huffman方法的同步）。 为了应对上述挑战，需要在系统级别进行设计和优化，包括优化激活卸载、使用列表缓冲区来支持样本访问、延迟权重获取以减少内存占用、专家分组以提高GPU利用率，以及进行鲁棒性修改以处理在压缩具有数万个层的模型时可能遇到的罕见corner case。 2. 算法 2.1 使用GPTQ量化 Fig 2. 使用GPTQ量化流程http://arxiv.org/abs/2310.16795 具体来说，我们维护一个大型缓冲区$B$，并按以下方式更新 Transformer 块的Dense部分： 从CPU到GPU抓取一个 “样本” $X$，其中包含数百个Token 通过相应的Dense Layer，得到结果$Y$ 计算并存储$Y$中标记的专家分配 将$Y$送回CPU并覆盖$B$中的$X$ 并且对于稀疏部分，分别对专家进行循环： 从CPU到GPU获取$B$中所有被分配给专家$E$的单独Token，记作$X_{E}$ 使用它们来生成压缩后的专家$E^{’}$（例如，使用GPTQ算法） 通过$E^{’}$模块以获得$Y_{E^{’}}$ 将$Y_{E^{’}}$发送回CPU，并在B中覆盖$X_{E}$ 作者在这里还引入了List Buffering、Lazy Weight Fetching和Expert Grouping技巧 2.1.1 List Buffering 为了有效地支持对Dense模型的访问，以及对专家tokens的完全向量化查询，我们将$B$存储为列表缓冲数据结构。这可以被看作是一个包含所有tokens隐藏状态的巨大连续缓冲区，以及分隔符索引，这些索引标志着各个样本之间的边界。下图展示了这种存储格式。这种数据结构对效率至关重要；对于大量样本计数，通过掩码迭代样本并获取相关tokens的方法是很慢的，而作者提出的方法则有大幅度改进。 Fig 3. list bufferinghttp://arxiv.org/abs/2310.16795 2.1.2 Lazy Weight Fetching 由于1.6万亿参数模型的权重占用了超过3TB的存储空间，它们甚至无法存储在CPU的RAM中。因此，我们按需直接从磁盘存储中懒加载它们。按照推理的流程，我们需要将所有的参数从磁盘搬移到内存中完整的一整次。 2.1.3 Experts Grouping 此外，为了避免GPU的利用率不足，作者将多个专家组合在一起，并应用GPTQ算法的联合批处理变体。 2.2 字典生成 对于量化后得到的Ternary Pair ${w_{min}, 0, w_{max}}$，在很多的情况下，是0居多的，也就是说是稀疏的，那么对于稀疏矩阵可以用CSR等方法来存储。但是使用传统的稀疏矩阵存储方法压缩比还是不够，作者团队使用了一种更加偏向于文件压缩的思路来进行量化后的参数压缩，这个方法就使用到了字典查找的方法。字典查找的方法还是比较通俗易懂的，以下面的例子来举例： 对于“001002003…”我们可以统计该串里面的子串的出现频率，比如001，002，003出现的频率高，那么我们可以将他们编码成 A,B,C然后仅需要三个char的空间“ABC”就可以表示一个压缩后的文件。...

背景和动机 以KV Cache为启发，探索了对time-to-first-token (TTFT) Latency的优化。类似于KV Cache，Prompt Cache(PC)推理加速的核心思想是复用注意力的中间状态(Attention States)。然而与KV Cache不同的是，PC是在不同的prompt之间进行复用。 在大部分的LLM任务中，prompt有重叠(overlapping)的现象，这些重叠的prompt可以被存储起来，进而在接下来的LLM处理阶段可以像KV Cache一样，提取出来直接使用。在TTFT的推理过程中，免去计算不同prompt中重叠部分的注意力状态，从而缩短TTFT的生成时间。 与KV Cache不同的点是： 相同的文本段可能出现在不同prompt的不同位置，如何对它们的Attention States进行复用。因为不同位置的文本段的Position Encoding进去的值是不一样的。在KV Cache中不需要考虑这一点，因为cache是从前往后线性增长的，但Prompt所在的位置是不确定的。 如何从不同的prompt中识别出已经缓存过的文本。 算法 实验经验 一段prompt的Position值不连续没有关系。只要这一段prompt本身的Position值是连续的就行。意思是部分连续对于LLM就够了，不一定要完全连续。请注意：这是一个实验性验证的结论。 Prompt Schema Fig 1. Prompt Schema 作者团队定义了一个Prompt Markup Language(PML)。上图中的例子有：可以复用的module和不能复用的填充部分，填充部分需要用Param指出，并给出长度。Prompt Attention States中的红色部分是可以被复用的区域。 Fig 2. 原始LLM/KV Cache/Prompt Cache 我们来对比下普通的自回归LLM、使用了KV Cache的LLM和使用了Prompt Cache的LLM。普通的LLM每次都要通过输入的Prompt来预测出下一个Token，Prompt是全量的计算。使用了KV Cache的LLM，每次Token预测不用全量计算了，可以使用上次Attention的中间结果。而使用了Prompt Cache的LLM，在后期预测Token的过程和原来的KV Cache没有什么区别。主要区别是在一开始的Prompt输入的阶段，Prompt Cache中常用的Prompt Attention States可以被利用起来，这会极大的缩减第一个Token输出的时间。 Prompt Schema有很多的细节，这里只讲大致的思路，具体的请看文章和代码仓库。 我对module怎么复用不是很理解，应该是通过将文本内容进行sha256编码来对其进行识别。 本文主要是对首Token输出时间的优化，对于用户来说可以有更好的体验。要是能做个全局的Prompt Cache数据库，应该可以给大规模的LLM Infer系统带来不少的好处。

Transformer-Lite from OPPO

Lin J, Tang J, Tang H, et al. Awq: Activation-aware weight quantization for llm compression and acceleration[j]. Machine Learning System. Best Paper. https://arxiv.org/abs/2306.00978 1. 背景和动机 直接在FP16精度上Round成INT3/INT4会造成极大的性能损失 基于activation distribution对重要的weight做精度保留则可以很大程度上提高模型性能。 但是混合存储FP16和INT3/4，在推理系统实现的时候过于复杂且对于硬件非常的不友好。 2. 算法 2.1 原理和假设 Fig 1. AWQ 原有的Round方法(图a)： $$ Q(\mathbf{w})=\Delta\cdot\mathrm{Round}(\frac{\mathbf{w}}\Delta),\quad\Delta=\frac{\max(|\mathbf{w}|)}{2^{N-1}} $$ 其中$\mathbf{w}$表示一组参数，$Q(\mathbf{w})$表示量化函数，$N$表示量化位数。 改进后的量化方法(图c)： $$ Q(w\cdot s)\cdot\frac xs=\Delta^{’}\cdot\mathrm{Round}(\frac{ws}{\Delta^{’}})\cdot x\cdot\frac1s $$ 其中$w \in \mathbf{W}$。即先对特定的$w$做Scaling然后再Scaling回去。这样做的理由是，误差可以成倍的减小，如下面的公式和观察出来的现象： $$ \begin{aligned}\operatorname{Err}(Q(w)x)&=\Delta\cdot\operatorname{RoundErr}(\frac w\Delta)\cdot x \newline \operatorname{Err}(Q(w\cdot s)(\frac xs))&=\Delta^{’}\cdot\operatorname{RoundErr}(\frac{ws}{\Delta^{’}})\cdot x\cdot\frac1s\end{aligned} $$ 其中由于$\operatorname{Round}$函数是四舍五入，所以误差$\operatorname{RoundErr}\in [0,0.5]$且是一个均匀分布。平均在0.25。不管是否被缩放了，这个分布是不变的。 由于一组权重$\mathbf{w}$的最大值在缩放一个$w$后是基本不变的，所以我们可以认为$\Delta^{’} \approx \Delta$。 在此基础上，我们可以看出使用了Scaling以后得误差变小了，将上述提到的误差做个比值可以看出，$k=\frac{\Delta^{’}}{\Delta} \times \frac{1}{s}$。 2.2 优化：如何找到最优的Scaling值呢？ $$ \mathbf{s}^{*} = \arg \mathop{\min}_{s}\mathcal{L}(\mathbf{s}) $$...

notes of paper, ACM SIGOPS Operating Systems Review, 2010, 44(4): 30-39.

go back to home Paper link Proceedings of the 19th ACM Symposium on Operating Systems Principles, ACM, Bolton Landing, NY (2003), pp. 20-43 Last Edit: Jan 18, 2023 GFS 有非常多的东西，这里只写了一些重要的部分。像是snapshot，文件删除，高可用机制，Replica管理等没有具体提及。 Introduction GFS是google提出的一个可扩展分布式文件系统，为大型分布式数据密集型应用提供服务。可以在大规模的消费级机器集群上提供不错的容错能力。GFS在设计的时候主要依据6个假设(观察得出的): 节点失效经常发生。系统由非常多的消费级机器组成，大量用户同时进行访问，这使得节点很容易因为程序bug、磁盘故障、内存故障等原因失效。 存储以大文件为主。每个文件通常100MB或几GB。系统需要支持小文件，但不需要对其进行特殊的优化。 大容量连续读，小容量随机读取是文件系统中的常态。 写入也已大容量为主，小容量无需特殊优化。 支持原子的文件追加操作。使得大量用户可以并行追加文件，而不需要额外的加锁机制。 高吞吐量比低延时更重要 为什么设计一个优秀的分布式存储系统非常的困难: Performance. 当数据量非常大的时候，数据分片(Sharding)是非常重要的。 Fault Tolerance. 但是由于数据在多台服务器上分片。由于多台服务器，整个系统出现故障的概率会大很多。因此需要容错机制 Replication. 复制数据副本到多台服务器上，但是为了用户能够拿到一致的数据，需要考虑一致性 Consistency. 为了一致性，不得不使用网络(极慢的数据交互方式)进行确认和同步。这又会影响性能(Performance)!!! 世界因此变成了一个美妙的环。:-)。这也是分布式的挑战之处。 GFS讨论了上述的这些主题和在实际生产场景中的应用。 Architecture Fig 1. GFS ArchGoole File System. Sanjay Ghemawat, Howard Gobioff, and Shun-Tak Leung. Proceedings of the 19th ACM Symposium on Operating Systems Principles, ACM, Bolton Landing, NY (2003), pp....

OSDI'04: 6th Symposium on Operating Systems Design and Implementation go back to home Paper link 什么是 MapReduce 在MapReduce原文中是这么说的 MapReduce is a programming model and an associated implementation for processing and generating large data sets. [1] 这是一个较为简单的处理大型问题的分布式编程模型。其产生的原因是因为 google 想要让普通的程序员也能够通过一套简单的编程模型来编写分布式应用程序，以此来处理 google 内部的大数据。然后著名的 Jeff Dean 和 Sanjay Ghemawat 出马搞定了这个问题(在知乎上关于Jeff Dean的轶事:-))。MapReduce 在 google 内部运行很长的时间并且处理了很多业务，但是目前也败下阵来，具体原因参见 MapReduce 缺陷章节(MR早在2004年就出来了，其实是古早的技术了，其没有在性能上做文章，主要在可扩展性上)。 MapReduce 的设计框架和基本流程 MR实际上是一个非常简单的框架，思路也非常的直白。MapReduce 背后的核心思想是将数据集映射到一个 <key, value> pair的集合中，然后使用相同的键对所有pair进行整合。 整体概念很简单，但是如果你设想下下面的情况，MR实际上非常有用: 基本上所有的数据都能被映射到一个 <key, value> 对中，并且key和value可以是任意类型。 在论文中MR使用的样例是在超大的文件里做单词统计。这个框架还可以用来做： 分布式的排序 分布式的搜索 Web链接图遍历 … Fig 1....