|
KV-Cache是一种加速推理的技术, KV-Cache就是将Attention 中的KV缓存下来，通过空间换时间的方式来加速计算Attention。
通过上图的展示可以很容易理解：通过将每次计算的K和V缓存下来，之后新的序列进来时只需要从KV Cache中读取之前的KV值即可，就不需要再去重复计算之前的KV了。
原理非常简单，但llama.cpp的实现源代码却是难以理解的，先看看KV-cache数据结构：
从代码注释可以看出这是一个循环存储的buffer（ring buffer），其中的数据说明如下：
1. has_shift: 表示cell中的位置是否做了偏移操作，而偏移量为cell[i].delta。
2. do_defrag: 表示是否需要执行碎片整理操作。
3. do_copy: 表示是否需要执行复制操作。
4. recurrent:表示是否为循环状态模型，应用于mamba模型。
5. head: 表示需要进行计算的KV头位置，如上图中橙色的格子位置，实际值是cell中有数据的单元数。
6. size:表示缓存的大小，即可以存储的键值对的数量。
7. used:表示已使用的cell单元格数量，即至少有一个sequence id（也是slot id）的单元格。
8. n: 表示cell中位置值非负且具有相应sequence id的单元格个数，即有效cell的个数。
9. type_k 和 type_v: 分别表示键（key）和值（value）的数据类型。
10. cells: 用于存储缓存中的每个单元格的状态。
11. k_l:表示每层的键（key）。
12. v_l:表示每层的值（value）。
13. ctxs: 内存管理数据。
14. bufs: buffer数组。
其中的“ llama_kv_cell”结构体主要是应用于记录token位置的变化，其数据说明如下：
pos: 表示token位置。
delta: 表示当前的pos值与原来的pos值出现偏移时的偏移量。
src: 应用于循环状态模型中复制状态。
seq_id: 表示当前位置的token是属于哪个sequence id,即task id或slot id。
KV-cache相关操作都是在cells中进行，如：
rm: 在指定位置范围内移除sequence id；
add: 在指定位置范围内添加sequence id；
cp: 在指定位置范围内插入sequence id；
clear: 清空cells中的数据，把所有cell单元的pos值置为-1，并去除所有sequence id。
KV-cache初始化过程（llama_kv_cache_init）：
步骤1：设置基本参数，如head、size、used、type_k、type_v等。
步骤2：清空cells数组，并重置cells数据大小为kv_size。
步骤3：计算每种buffer所涉及的decode层数量，buffer会有这些类型：GPU、SYCL（一种计算框架）、VULKAN（一种图像计算框架）、HBM（高内存带宽）、普通CPU，但ggml定义的backend只有三种类型：CPU、GPU、GPU_SPLIT。
步骤4：为每一种buffer分配一个ggml context(ggml 内存管理对象)。
步骤5：为decode每一层建立第一个为空的KV张量。
步骤6：为每一种buffer分配一个buffer。
| 
