Base-Delta-Immediate Compression | 乌龙波霸七分甜

Base-Delta-Immediate Compression:Practical Data Compression for On-Chip Caches。原文链接很多基于软件的缓存压缩算法主要有两大缺点：造成很高的硬件复杂度；无法接受的解压延迟。本文提出了一种新的压缩算法Base-Delta-Immediate (B∆I) ，关键思想是：大多数cache line有一个特点，同一cache line中存储的数据差异很小。基于这一观察，cache line的数据可以用一个基值（Base）+ 一组差异值（Delta）来表示，所需存储空间必然会比原始cache line大小小得多。

背景

为了缓解CPU和主存之间速度不匹配的问题，在主存与CPU之间插入一级或多级cache。然而cache并不是越大越好，虽然更大的cache通常会带来更少的cache miss，但是这种好处是以更长的访问延迟、更大的cache面积（昂贵）和更大的功耗为代价的。

基于这些限制，为了提高cache的利用率，可能会想到通过数据压缩来减少数据量，然而数据压缩并没有被现代商用微处理器作为一种提高有效缓存容量的方法，为什么？理想的缓存压缩技术应该是快速（压缩/解压延迟低）、简单（硬件复杂度低）、高效（高压缩率）的，而如果在商用微处理器中采用缓存压缩，会面临的最大障碍可能是解压延迟，解压与压缩不同，压缩是在缓存写入时(在提供关键字之后)在后台进行的，而解压缩位于cache hit的关键路径上，在此路径上最小化延迟对于性能非常重要。

因此，快速、简单、高效的缓存压缩方案，不可兼得，怎么办？只能权衡得到最佳方案，要么压缩率低、要么硬件复杂度高、要么解压延迟高，总会有缺陷，方案是否可行就看好处是否大于坏处，为了在降低硬件复杂度和解压缩延迟的同时达到显著的压缩比，本文提出了一种新的缓存压缩技术Base-Delta-Immediate(B∆I)压缩。

BASE + DELTA ENCODING: BASIC IDEA

基于两个特点：

数据在内存中分配的规律性（相似的数据值和类型分组在一起）。
缓存/内存数据的动态范围较低（例如，同一cache line的数据差异很小）。

设计了Base+Delta 压缩方案，通过存储一个Base和一组Delta来减少冗余从而提高Cache line的利用率。接下来通过两个直观的例子来更好地理解。

images

应用程序h264ref的32-byte cache line利用Base+Delta 方案压缩如上图所示，该cache line包含一组（8个）以4字节整数形式存储的窄值。

窄值是使用大数据类型存储的小值。例如，一个one-byte的值存储为一个four-byte整型数。程序员通常在各种数据结构中以最坏的情况为标准提供数据类型，即使大多数数值可能适合较小的数据类型。

从Figure 3我们看到，cache line通过一个全0的base+一组八个1-byte的差异值即可表示所有存储的数值，只要4+8*1共12 byte就能表示整个cache line，这样消除冗余之后相比原来节省了20 byte的空间。看到这里就很容易联想到一个问题，如果说base的byte数太大，差异值节省出来的空间不够多，那么压缩还不如不压缩对不对？这个问题作者在下文考虑到了，base数目、base字节数、差异值的字节数多少才最合适？选择哪个value做base效果会一样吗？不一样的话那如何确定呢？都是我们需要考虑权衡的点。

images

由Figure 4，在perlbench应用程序负载上，同样是一个32-byte的cache line，存储的是pointer，可以看到，同一cache line的pointer值依然具有很高的相似度。

注意：虽然这里例子使用的是32-byte的cache line，最后实验评估部分有考虑更常见的64-byte cache line。

Compression Algorithm

关于该算法的具体描述，论文里面给出了公式（貌似有误，反了），也很容易理解，就是通过简单的向量减法得到Delta。

1	∆i = Vi - B* ，其中V表示原始值的集合，∆表示差异值的集合，B*表示base值，若cache line的大小为C byte，其中每个value的大小为k byte，那么i的取值为1~C/k

这里有两个观察：

若存在任意一个Vi和所选base相似度为0，即Delta(i)的大小等于k，那么该缓存行不能压缩。因为本来引入base就加重了开销，压缩效果不好不如不压缩。
如何确定哪个value被选为base？要么Vi的最小值或最大值，要么中间值，被认为是最佳的。理论上是这样的，实际上的做法呢？

我们除了确定base，还需要确定k，即每个value的大小，决定了一个cache line能容纳多少个value。

Determining k

k在2、4、8之间选择最佳压缩率的k值。选择2、4、8是因为几乎所有由各种编程语言支持的基本数据类型都有这三种大小之一。

Determining B*

B*可以依据上述观察2来选取，然而，用这种方式寻找base需要计算原始集合的最大value与最小value，这会大大增加硬件的逻辑复杂度，并且会明显增加压缩延迟。所以为了简单起见，选择第一个value作为base即可，并且实验表明，压缩率相比选择理论最优base降低仅仅0.4%，很微不足道了，并且还不会增加硬件复杂度以及压缩延迟。

Decompression Algorithm

通过B*和∆的值能够计算得到V，实现解压：

1	Vi = ∆i + B*

因此，cache line中的值可以使用SIMD-style的向量加法器并行计算得到。即使用一组简单的加法器，可以在执行整数向量加法所需的时间内解压缩整个cache line。

B∆I COMPRESSION

前一部分介绍了Base + Delta，以此为基础怎样能够更完善我们的压缩算法呢？

因为尽管B+∆被证明适用于大多数的应用程序，但是不可能所有的cache line都能用这种形式来表示，有一些基准测试压缩率就不见得好，比如mcf。这是因为有些应用程序在同一cache line中间可能混合有不同类型的数据，比如指针和1-byte的整数。这种情况下，很显然，如果我们选取多个base，一种类型一个base的话是不是压缩效果会好很多呢？

images

如Figure 5所示，我们发现对于在同一cache line可能存储着不同类型的数据的应用程序，多个base压缩效果会更好，但是这会造成更大的base存储开销，所以，存在一个tradeoff，因为显然不是多个base一定会更好，那么选取多少个base才是最优的呢？

光说都是没有依据的，通过实验来说话，作者设计了一个实验，评估了选择不同数量base(使用贪婪算法依次选择次优base)的有效压缩比，Figure 6展示了实验结果。

images

结果表明，就有效压缩比而言，经验上最优的base个数是2，虽然少数benchmark在1或3个base上也有最优，最后的结论还是B+∆在两个base的情况下，性能明显优于B+∆在base为1时(压缩比平均为1.51:1.40)，说明值得考虑实现。结果还表明有两个以上的base并不会为这些工作负载提供额外的压缩比改进，因为存储更多的base的开销要高于压缩更多cache line的好处。

注意：Figure 6中我们发现有0个base，这很必要，因为如果不考虑0个base，对于比如说最简单的全0数据，如果使用简单的压缩去冗余，不需要base，直接压缩到1byte，而base越多，显然，压缩率越低，并且增大存储开销。

那么，如何高效地找到两个base？不增加硬件的复杂度，或者说如何以最小的硬件复杂度寻找两个base来获得最大的压缩好处？下一节介绍

B∆I: Refining B+∆ with Two Bases and Minimal Complexity

我们发现，第二个base直接设置为0能够和任意选取任何一个vaule作为第二个base一样，为什么会这样？因为大多数情况下，是动态范围较小的宽值（比如指针）与窄值（比如小整数）混合，那么第一个base可以使用base+delta编码压缩动态范围较低的宽值，而第二个0 base则可以有效地压缩窄值。基于这一观察，我们额外增加一个隐式（implicit）的0 base来改进B+∆，称为Base-Delta-Immediate或B∆I压缩。

那么两个base的B+∆好还是B∆I好呢？又存在tradeoff。显然，B∆I有一个base是隐式的0，存储开销更小，这意味着对于用这两种技术都可压缩的cache line，B∆I的平均压缩率可能更高。有两个base的B+∆需要更多的存储空间来存储第二个base，但是可以压缩更多的cache line，因为base可以是任何value，从中选择最佳。到底哪个好呢？可能取决于cache line的模式，甲之砒霜，乙之蜜糖。关键时刻依然还是得实验来说话

images

Figure 7表明，虽然有个别负载B+∆的表现比B∆I好，但是总体来说还是B∆I的压缩比（1.53）高于B+∆（1.51），虽然不是高太多，但是考虑到B+∆有两个base，那就有比B∆I更复杂的硬件机制，所以认为缓存压缩设计还是应该基于B∆I的思想。

Design

Compress

在具体的设计中，所有的可能压缩大小是静态已知的，如Table 2。如果cache line有多个压缩选项可用(例如，8-byte base 1-byte ∆或者Zeros压缩)，则Compression Selection 选择压缩cache line大小最小的一个（即选择压缩率最高的）。基于Table 2选择合适的压缩大小，Figure 8中所有压缩单元可并发执行。

images

Figure 9展示了32-byte的cache line在8-byte-base 1-byte-∆时压缩单元的情况，每个V通过减法器进行运算之后，判断是否每个V的运算结果∆前七位均为0或者1，如果是的话，cache line能够以该种模式（8-byte-base 1-byte-∆）存储，否则，说明至少有一个∆不能用1-byte表示，那么不压缩该cache line。

images

Decompress

解压的硬件设计很简单，如上文描述一样，就是一个减法器。如下图所示

imges

关于实现的更多细节，以及实验部分，如果感兴趣的话可以阅读原文，本文的分析重在了解基本思想。