8

2 つの小さなブール行列を乗算するできるだけ高速な方法を見つけたいと考えています。ここで、小さいとは 8x8、9x9 ... 16x16 を意味します。このルーチンは頻繁に使用されるため、非常に効率的である必要があります。単純なソリューションで十分な速度が得られるとは思わないでください。

特殊なケースである 8x8 と 16x16 については、ここで見つかったソリューションに基づいて、かなり効率的な実装が既にあります。ここでは、行列全体をそれぞれuint64_torとして扱いuint64_t[4]ます。私のマシンでは、これは単純な実装よりも約 70 ～ 80 倍高速です。

ただし、8 < k < 16 の場合、上記のような巧妙なトリックを有効にするために、合理的な表現をどのように活用できるかはよくわかりません。

したがって、基本的には、(行列の) あらゆる種類の表現と関数シグネチャを使用した提案を受け付けています。これは 32 ビットまたは 64 ビット アーキテクチャのいずれかを対象としていると思われるかもしれません (提案に最も適したものを選択してください)。

4

4 に答える 4

7

2 つの 4x4 行列 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 がほぼ限界です)。

各ステップは、Result(n+1) = Result(n) XOR A(n) .& B(n) の累積で構成されます。ここで、Result(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(n) == A からコピーされた列の対角線を選択することです。

    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

EDIT後の読者のために、ポータブル 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
}
于 2013-01-29T12:24:00.340 に答える
5

対角線にすべて「1」を付けて、次の「賢い」サイズ (たとえば、8 または 16) にパディングするのはどうですか?

于 2013-01-29T10:45:53.797 に答える
4

アプリケーションによっては、行列とその転置の両方を一緒に保存すると役立つ場合があります。行列の乗算中に転置するために使用される時間を大幅に節約できますが、メモリと操作がいくらか犠牲になります。

于 2013-01-29T12:41:30.833 に答える