kxk布尔矩阵的快速乘法,其中8 <= k <= 16

Question

我想找到一种尽可能快的方法来乘以两个小布尔矩阵,其中小的意思是8x8,9x9 ... 16x16.这个例程将被大量使用,因此它需要非常高效,所以请不要建议直截了当的解决方案应该足够快.

对于特殊情况8x8和16x16,我已经有了相当高效的实现,基于此处的解决方案,我们将整个矩阵视为uint64_t或uint64_t[4]分别处理.在我的机器上,这比直接实现快大约70-80倍.

但是,在8 <k <16的情况下,我真的不知道如何利用任何合理的表示来实现上述巧妙的技巧.

基本上,我对使用任何类型的表示(矩阵)和函数签名的任何建议持开放态度.您可以假设这是针对32位或64位架构(选择最适合您的建议)

Answer 1

给定两个4×4矩阵a = 0010,0100,1111,0001,b = 1100,0001,0100,0100,可以首先计算转置b'= 1000,1011,0000,0100.

然后得到的矩阵M(i,j)= axb mod 2 == popcount(a [i]&b [j])&1; //或奇偶校验

从那一点可以注意到,只要位向量适合计算机单词,复杂性仅在n ^ 2中增长.

只要有一些特殊的排列和位选择操作可用,这至少可以加速8x8矩阵.可以用向量中的NxN位精确迭代N次.(所以16x16几乎是极限).

每个步骤包括累积,即结果(n + 1)=结果(n)XOR A(n).&B(n),其中结果(0)= 0,A(n)是A <<< n,和' <<<'==元素的逐列旋转和B(n)从矩阵B复制对角线元素:

    a b c          a e i          d h c          g b f
B=  d e f  B(0) =  a e i  B(1) =  d h c   B(2) = g b f
    g h i          a e i          d h c          g b f

在进一步思考之后,更好的选择是^^^(行式旋转)矩阵B并从A中选择A(n)==列复制的对角线:

    a b c         a a a           b b b           c c c 
A=  d e f  A(0) = e e e , A(1) =  f f f,  A(2) =  d d d 
    g h i         i i i           g g g           h h h 

编辑为了让后来的读者受益,我提出了便携式C中W <= 16位矩阵乘法的完整解决方案.

#include <stdint.h>
void matrix_mul_gf2(uint16_t *a, uint16_t *b, uint16_t *c)
{
    // these arrays can be read in two successive xmm registers or in a single ymm
    uint16_t D[16];      // Temporary
    uint16_t C[16]={0};  // result
    uint16_t B[16];  
    uint16_t A[16];
    int i,j;
    uint16_t top_row;
    // Preprocess B (while reading from input) 
    // -- "un-tilt" the diagonal to bit position 0x8000
    for (i=0;i<W;i++) B[i]=(b[i]<<i) | (b[i]>>(W-i));
    for (i=0;i<W;i++) A[i]=a[i];  // Just read in matrix 'a'
    // Loop W times
    // Can be parallelized 4x with MMX, 8x with XMM and 16x with YMM instructions
    for (j=0;j<W;j++) {
        for (i=0;i<W;i++) D[i]=((int16_t)B[i])>>15;  // copy sign bit to rows
        for (i=0;i<W;i++) B[i]<<=1;                  // Prepare B for next round
        for (i=0;i<W;i++) C[i]^= A[i]&D[i];          // Add the partial product

        top_row=A[0];
        for (i=0;i<W-1;i++) A[i]=A[i+1];
        A[W-1]=top_row;
    }
    for (i=0;i<W;i++) c[i]=C[i];      // return result
}

Answer 2

如何将它填充到下一个"聪明"(例如8或16)大小,对角线上的所有"1"？