介绍一下 FlashAttention V1？
- Fast（with IO-Awareness），计算快。在Flash Attention之前，也出现过一些加速Transformer计算的方法，这些方法的着眼点是“减少计算量FLOPs”，例如用一个稀疏attention做近似计算。但是Flash attention就不一样了，它并没有减少总的计算量，因为它发现：计算慢的卡点不在运算能力，而是在读写速度上。所以它通过降低对显存（HBM）的访问次数来加快整体运算速度，这种方法又被称为O-Awareness。Flash Attention通过分块计算（tiling）和核函数融合（kernel fusion）来降低对显存的访问。
- Memory Efficicent，节省显存。在标准attention场景中，forward时我们会计算并保存N*N大小的注意力矩阵；在backward时我们又会读取它做梯度计算，这就给硬件造成了 O(N^2) 的存储压力。在Flash Attention中，则巧妙避开了这点，使得存储压力降至 O(N)。
- Exact Attention，精准注意力。之前的办法会采用类似于“稀疏attention”的方法做近似。这样虽然能减少计算量，但算出来的结果并不完全等同于标准attention下的结果。但是Flash Attention却做到了完全等同于标准attention的实现方式。
FlashAttention V1 O_i 的前向过程推导？
标准 Attention 和 FlashAttention V1 前向过程计算复杂度、IO 复杂度和显存占用？
- 计算量复杂度均为：
$O\left(\frac{N^2}{B_r B_c} B_r B_c d \right) = O(N^2 d)$ - 原始 Attention
- IO 复杂度：
$O\left(N d + N^2 \right)$ - 显存占用：
$O(N^2)$ - FlashAttention V1
- IO 复杂度：
$O(T_c N d) = O\left(\frac{N}{B_c} N d\right) = O\left(\frac{4 N d}{M} N d\right) = O\left(\frac{N^2 d^2}{M}\right)$ - 显存占用：
$O(N)$
介绍一下 FastAttention V2？
V2从以下三个方面做了改进：
- 置换内外循环位置，同时减少非矩阵的计算量。
- 优化Attention部分thread blocks的并行化计算，新增seq_len维度的并行，使SM的利用率尽量打满。这其实也是内外循环置换这个总体思想配套的改进措施
- 优化thread blocks内部warp级别的工作模式，尽量减少warp间的通讯和读取shared memory的次数。
LLM 推理有什么瓶颈？
- 算子计算上分析：decoding 阶段，主要算子是 GEMV，它是 Memory Bound，受限于内存带宽
- 内存容量分析：Large KV cache、Complex decoding algorithms、Complex decoding algorithms
介绍一下 vLLM？vLLM是通过什么技术，动态地为请求分配 KV cache 显存，提升显存利用率的？
vLLM 通过一种名为 PagedAttention 的技术，动态地为请求分配 KV cache 显存，提升显存利用率。
整体上来说，PagedAttention的设计灵感来自操作系统中虚拟内存的分页管理技术。
- 请求（request）可理解为操作系统中的一个进程
- 逻辑内存（logical KV blocks）可理解为操作系统中的虚拟内存，每个block类比于虚拟内存中的一个page。每个block的大小是固定的，在vLLM中默认大小为16，即可装16个token的K/V值
- 块表（block table）可理解为操作系统中的虚拟内存到物理内存的映射表
- 物理内存（physical KV blocks）可理解为操作系统中的物理内存，物理块在gpu显存上，每个block类比于虚拟内存中的一个page
当采用动态分配显存的办法时，虽然明面上同一时刻能处理更多的prompt了，但因为没有为每个prompt预留充足的显存空间，如果在某一时刻整个显存被打满了，而此时所有的prompt都没做完推理，那该怎么办？
- 当一堆请求来到vLLM服务器上时，按照**First-Come-First-Serve（FCFS）**原则，优先处理那些最早到来的请求。
- 当gpu资源不足时，为了让先来的请求能尽快做完推理，vLLM会对那些后到来的请求执行“抢占”，即暂时终止它们的执行。
- 一旦vLLM决定执行抢占操作，它会暂停处理新到来的请求。在此期间，它会将被抢占的请求相关的KV block全部交换（swap）至cpu上。等交换完成后，vLLM才会继续处理新到来的请求。
- 当vLLM认为gpu有足够资源时，它会将cpu上的KV block重新加载回gpu，恢复被抢占请求的执行（recomputation）
vLLM swapping 策略
问题1：该释放哪些KV cache？
问题2：要把这些KV cache释放到哪里去？
- 先看问题1。由前文PagedAttention原理可知，一个请求可能对应多个block。我们既可以选择释放掉部分block，也可以选择释放掉全部block，或者更科学地，我们可以预测一下哪些block被使用的频率最低，然后释放掉这些低频block（但这种方式实现起来难度较大，性价比不是很高）。在vLLM中，采取的是all-or-nothing策略，即释放被抢占请求的所有block。
- 再来看问题2。对于这些被选中要释放的KV block，如果将它们直接丢掉，那未免过于浪费。vLLM采用的做法是将其从gpu上交换（Swap）到cpu上。这样等到gpu显存充份时，再把这些block从cpu上重载回来。
vLLM recomputation 策略
知道了Swapping机制，重计算的过程也很好理解了：对于有些任务（比如parallel sampling中并行采样数n=1的任务），当它们因为资源不足而被抢占时，可以不做swap，而是直接释放它们的物理块，把它们重新放入等待处理的队列中，等后续资源充足时再重新从prefill阶段开始做推理