c++ - 快速整数矩阵乘法与 bit-twiddling hacks

Question

我问是否有可能显着改进整数矩阵乘法 bitwise operations .矩阵很小，元素是小的非负整数(小意味着最多 20)。

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

以下简单的 C++ 实现执行了一百万次执行大约 1 秒，用 linux time 测量。

#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-like评论在这里没有帮助。
3. 我们尽量不要使用间接观察，即在这个特定问题中，矩阵A[] 和B[] 可以编码为单个 64 位整数。想一想稍大一点的矩阵会发生什么。
4. 计算是单线程的。

   ---

相关:Binary matrix multiplication bit twiddling hack和 What is the optimal algorithm for the game 2048?

Answer 1

您链接的问题是关于矩阵的，其中每个元素都是一个位。对于一位值 a和 b , a * b完全等同于 a & b .

对于添加 2 位元素，从头开始添加可能是合理的(并且比解包更快)，使用 XOR(无进位加法)，然后使用 AND、移位和屏蔽进位跨元素边界生成进位.

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

---

打包与解包到字节的存储格式

如果您有很多这样的微型矩阵，将它们以压缩形式(例如打包的 4 位元素)存储在内存中有助于减少缓存占用空间/内存带宽。 4 位元素很容易解压缩，使每个元素都位于 vector 的单独字节元素中。

否则，将它们以每个字节一个矩阵元素的方式存储。从那里，如果需要，您可以轻松地将它们解压缩为每个元素 16 位或 32 位，具体取决于目标 SIMD 指令集提供的元素大小。您可以将一些矩阵以解压缩格式保留在局部变量中以在乘法运算中重复使用，但将它们打包回每个元素 4 位以存储在数组中。

---

编译器用 uint8_t 搞砸了在 x86 的标量 C 代码中。查看@Richard 回答的评论:gcc 和 clang 都喜欢使用 mul r8对于 uint8_t ，这迫使他们将数据移动到 eax (单操作数乘法的隐式输入/输出)，而不是 using imul r32, r32 and ignoring the garbage that leaves outside the low 8 bits of the destination register .

uint8_t版本实际运行速度比 uint16_t 慢版本，即使它的缓存占用空间只有一半。

---

您可能会从某种 SIMD 中获得最佳结果。

英特尔 SSSE3 有一个 vector byte multiply, but only with adding of adjacent elements .使用它需要将你的矩阵解包成一个 vector ，在行之间有一些零或其他东西，所以你不会从一行中获取数据与另一行中的数据混合在一起。还好，pshufb可以将元素归零以及复制它们。

更有用的是 SSE2 PMADDWD ，如果您将每个矩阵元素解包到一个单独的 16 位 vector 元素中。因此，给定一个 vector 中的一行，以及另一个 vector 中的转置列，pmaddwd ( _mm_madd_epi16 ) 是一个水平的 add远离为您提供 C[i][j] 所需的点积结果.

与其单独执行这些添加，不如打包多个 pmaddwd结果放入单个 vector 中，因此您可以存储 C[i][0..2]一气呵成。