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

主要观点:探讨将三进制权重打包到接近log(3) / log(2)位/三进制数字的方法,以实现高效的并行解包。
关键信息

  • 三进制数字的一位有 3 种可能值。
  • 目标是找到合适的块大小,使其在信息密度和当前硬件上都高效,通过寻找 3 的幂使得下一个 2 的幂很接近来确定。
  • 以 5 个三进制数字(5 trits)能紧密 fit 到 8 位(8 bits),效率达 99.06%为例。
  • 提出通过乘法解包的快速方法,利用定点数,将 8 位字节乘以 3 从结果的高两位提取数字,比模运算更方便,且在打包三进制数字到字节时只有除法在相关位置。
  • 编写 C 程序验证该方法无损,在llama.cpp的三进制类型中用于 TriLMs 和 BitNet b1.58,有 AVX2 和 ARM NEON 的 SIMD 实现。
    重要细节
  • 引用了https://xkcd.com/356/,初始动机来自llama.cpp初始 BitNet b1.58 拉取请求上的评论
  • log(3) / log(2)即 1.584962500721156。
阅读 6
0 条评论