快速整数矩阵乘法和位旋转黑客

Question

我在问是否可以通过按位运算来改善相当大的整数矩阵乘法。矩阵很小，元素是小的非负整数（small表示最多20个）。

为了使我们专注，我们要非常具体，说我有两个3x3矩阵，它们的整数项0 <= x <15。

以下简单的C ++实现执行了100万次，执行时间约为1s（以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的评论在这里无济于事。
3. 让我们尝试不使用间接的观察，在这个特定问题的矩阵A[]，并B[]可以被编码为一个单一的 64位整数。想一想在更大的矩阵中会发生什么。
4. 计算是单线程的。

   ---

相关文章：二进制矩阵乘法位使黑客动摇，2048游戏的最佳算法是什么？

Answer 1

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

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

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

打包与非打包字节存储格式

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

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

uint8_t编译器在 x86 的标量 C 代码中对此很糟糕。请参阅 @Richard 的答案的评论： gcc 和 clang 都喜欢使用mul r8for uint8_t，这迫使它们将数据移入eax（单操作数乘法的隐式输入/输出），而不是使用imul r32, r32和忽略留在低 8 之外的垃圾目标寄存器的位。

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

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

Intel SSSE3 具有向量字节乘法，但仅限于相邻元素的相加。使用它需要将矩阵解压缩为行之间有一些零或其他内容的向量，因此您不会从一行中获取与另一行中的数据混合的数据。幸运的是，pshufb可以将元素归零并复制它们。

如果将每个矩阵元素解压到单独的 16 位向量元素中，则SSE2PMADDWD可能更有用。因此，给定一个向量中的一行，以及另一个向量中的转置列，pmaddwd( )距离给出 所需的点积结果_mm_madd_epi16只有一个水平距离。addC[i][j]

您可以将多个结果打包pmaddwd到一个向量中，以便一次性存储，而不是C[i][0..2]单独执行每个添加。