利用扭曲比特的快速整数矩阵乘法

Question

我想问的是，是否有可能用按位运算大大改进整数矩阵乘法。矩阵很小，元素是小的非负整数（小表示最多20个）。

为了保持我们的注意力集中，让我们非常具体，假设我有两个3x3矩阵，有整数条目0<=x<15。

下面这个朴素的C++实现被执行了一百万次，使用linuxtime来衡量，它的性能大约为1秒。

#include <random>

int main() {
//Random number generator
std::random_device rd;
std::mt19937 eng(rd());
std::uniform_int_distribution<> distr(0, 15);

int A[3][3];
int B[3][3];
int C[3][3];
for (int trials = 0; trials <= 1000000; trials++) {
    //Set up A[] and B[]
    for (int i = 0; i < 3; ++i) {
        for (int j = 0; j < 3; ++j) {
            A[i][j] = distr(eng);
            B[i][j] = distr(eng);
            C[i][j] = 0;
        }
    }
    //Compute C[]=A[]*B[]
    for (int i = 0; i < 3; ++i) {
        for (int j = 0; j < 3; ++j) {
            for (int k = 0; k < 3; ++k) {
                C[i][j] = C[i][j] + A[i][k] * B[k][j];
            }
        }
    }
}
return 0;
}

备注：

1. 矩阵不一定是稀疏的。
2. 类似Strassen的注释在这里没有帮助。
3. 让我们尽量不使用间接观察，即在这个具体问题中，矩阵a[]和B[]可以被编码为单个64位整数。想想稍微大一点的矩阵会发生什么。
4. 计算是单线程的。

   ---

相关：二进制矩阵乘法，比特旋转黑客和什么是游戏的最佳算法2048？

Answer 1

你链接的问题是关于一个矩阵，其中每个元素都是一个位。对于一位值A和B，A*B与A&B完全等效。

对于添加2位元素，基本上从头开始添加，使用XOR（carryless-add)，然后使用and、shift和mask off carry跨元素边界生成carry可能是合理的（而且比解包更快）。

第3位将需要检测当添加进位时产生另一进位。我认为与使用SIMD相比，即使是模拟3位加法器或乘法器也不会是一个胜利。如果没有SIMD（即在带有uint64_t的纯C中），它可能是有意义的。对于add，您可以尝试使用普通的add，然后尝试撤消元素边界之间的进位，而不是通过异或/与/移位操作自己构建一个加法器。

如果您有很多这样的小矩阵，以压缩的形式（例如，打包的4位元素）将它们存储在内存中可以帮助增加缓存占用空间/内存带宽。4bit元素很容易解包，使每个元素都在向量的一个单独的字节元素中。

否则，每字节存储一个矩阵元素。从那里，根据目标SIMD指令集提供的元素大小，如果需要，您可以轻松地将它们解包为每个元素16bit或32bit。您可以将局部变量中的一些矩阵保留为未打包格式，以便在乘法中重用，但将它们打包为每个元素的4bits以存储在数组中。

编译器在x86的标量C代码中使用uint8_t来解决这一问题。参见@Richard's Answer的评论：gcc和clang都喜欢对uint8_t使用mul r8，这迫使它们将数据移入eax（一个操作数乘法的隐式输入/输出），而不是使用imul r32,r32并忽略目标寄存器低8位之外的垃圾。

uint8_t版本实际上比uint16_t版本运行得慢，尽管它的缓存占用面积只有uint8_t版本的一半。

Intel SSSE3有一个向量字节乘法器，但仅与相邻元素相加。使用它需要将矩阵拆分成一个向量，在行之间加上一些零或其他东西，这样就不会得到一行的数据和另一行的数据混在一起。幸运的是，pshufb可以零元素，也可以复制它们。

更有用的是SSE2pmaddwd，如果您在一个单独的16bit向量元素中解包到每个矩阵元素。因此，给定一个向量中的一行和另一个向量中的转置列，pmaddwd(_mm_madd_epi16)只需要一个水平的add，就可以得到C[i][j]所需的点积结果。

您可以将多个pmaddwd结果打包到一个向量中，这样就可以一次性存储c[i][0..2]。