如何在8位字节中打包三进制数

# 如何将三进制数打包进8位字节 来源：https://compilade.net/blog/ternary-packing 并可进行高效的SIMD解包 --- 发布日期：2024-06-26 三进制数的每一位有3种可能的值。这3种可能的值实际上可以是任何东西。 最近我因为一个技术彩蛋[¹](https://compilade.net/blog/ternary-packing#fn:1)而试图将 BitNet b1.58[²](https://arxiv.org/abs/2402.17764) 的三进制权重打包到接近理论极限 `log(3) / log(2)` [³](https://compilade.net/blog/ternary-packing#fn:2) 位每三进制位的程度。 我将“三进制位”称为“trit”，就像“二进制位”称为“bit”一样。 ## 块大小 由于目标是实现快速的***并行***解包，三进制位的块不能无限大。需要找到一个较小的“块”大小，既能在信息密度上高效，又能在当前硬件上方便使用。 要找到合适的块大小，我们需要找到一个3的幂，使其下一个2的幂非常接近。 很幸运，5个三进制位可以非常紧凑地放入8位中，达到每三进制位`1.6位`。与完美打包相比，效率为`99.06%`。 ## 每三进制位1.6位 这种打包方案的基本思路很简单：用三进制位组成一个数字。 将三进制位打包进字节的方式应该类似。 ### 快速乘法解包 虽然可以通过反复取余和除法来提取数字的各位，但在 SIMD 编程中，除法和取模通常不受支持。 解决这个问题的方法*显然*是以不同的方式看待数字。 如果我们能通过乘法提取最高有效位，而不是通过取模提取最低有效位，那该多好啊？ 定点数来拯救！ 瞧！ 现在，当用这个8位字节乘以3时，可以从得到的10位数字的高两位轻松提取出三进制位。 与使用取模相比，这在 SIMD 解包时方便得多。 在这个方案中，只有将三进制位打包进字节时才会用到除法。这假设打包操作比解包操作少，这在 LLM 权重的上下文中确实如此。 相关的关键代码如下： 它实现了上图所示的操作，但由于是整数运算，所以先进行乘法。这里使用向上取整除法是为了消除后续提取数字时截断导致的偏移误差。 要*不*使用取模运算符进行解包： 为了让自己相信这是可行的，我写了一个 C 程序来验证它确实是无损的： 用以下命令编译并运行： 对于所有能放入8位的243个三进制数，我都得到了`PASS`结果。 这就是在 `llama.cpp` 中用于 TriLM 和 BitNet b1.58 的三进制类型所使用的技术，相应的拉取请求在 https://github.com/ggml-org/llama.cpp/pull/8151，并且包含了针对 AVX2 和 ARM NEON 的 SIMD 实现。