21

C で 2 つの 4x4 行列を乗算するためのより高速でトリッキーな方法を探しています。現在の研究は、SIMD 拡張を使用した x86-64 アセンブリに焦点を当てています。これまでのところ、単純な C 実装よりも約 6 倍高速な関数 witch を作成しました。これは、パフォーマンスの向上に対する私の期待を上回りました。残念ながら、これはコンパイルに最適化フラグが使用されていない場合にのみ当てはまります (GCC 4.7)。では-O2、C が高速になり、私の努力が無意味になります。

最新のコンパイラは、複雑な最適化手法を利用してほぼ完璧なコードを作成し、通常は手作りの精巧なアセンブリよりも高速であることを私は知っています。しかし、パフォーマンスが重要な少数のケースでは、人間がコンパイラでクロック サイクルを争おうとすることがあります。特に、最新の ISA に裏打ちされたいくつかの数学を調査できる場合 (私の場合のように)。

私の関数は次のようになります (AT&T 構文、GNU アセンブラー):

    .text
    .globl matrixMultiplyASM
    .type matrixMultiplyASM, @function
matrixMultiplyASM:
    movaps   (%rdi), %xmm0    # fetch the first matrix (use four registers)
    movaps 16(%rdi), %xmm1
    movaps 32(%rdi), %xmm2
    movaps 48(%rdi), %xmm3
    xorq %rcx, %rcx           # reset (forward) loop iterator
.ROW:
    movss (%rsi), %xmm4       # Compute four values (one row) in parallel:
    shufps $0x0, %xmm4, %xmm4 # 4x 4FP mul's, 3x 4FP add's 6x mov's per row,
    mulps %xmm0, %xmm4        # expressed in four sequences of 5 instructions,
    movaps %xmm4, %xmm5       # executed 4 times for 1 matrix multiplication.
    addq $0x4, %rsi

    movss (%rsi), %xmm4       # movss + shufps comprise _mm_set1_ps intrinsic
    shufps $0x0, %xmm4, %xmm4 #
    mulps %xmm1, %xmm4
    addps %xmm4, %xmm5
    addq $0x4, %rsi           # manual pointer arithmetic simplifies addressing

    movss (%rsi), %xmm4
    shufps $0x0, %xmm4, %xmm4
    mulps %xmm2, %xmm4        # actual computation happens here
    addps %xmm4, %xmm5        #
    addq $0x4, %rsi

    movss (%rsi), %xmm4       # one mulps operand fetched per sequence
    shufps $0x0, %xmm4, %xmm4 #  |
    mulps %xmm3, %xmm4        # the other is already waiting in %xmm[0-3]
    addps %xmm4, %xmm5
    addq $0x4, %rsi           # 5 preceding comments stride among the 4 blocks

    movaps %xmm5, (%rdx,%rcx) # store the resulting row, actually, a column
    addq $0x10, %rcx          # (matrices are stored in column-major order)
    cmpq $0x40, %rcx
    jne .ROW
    ret
.size matrixMultiplyASM, .-matrixMultiplyASM

128 ビット SSE レジスタにパックされた 4 つの float を処理することにより、反復ごとに結果の行列の列全体を計算します。完全なベクトル化は、少しの数学 (操作の並べ替えと集計) と4xfloat パッケージの並列乗算/加算の命令で可能ですmullps。このコードは、パラメーター ( 、、 : GNU/Linux ABI)addpsを渡すためのレジスターを再利用し、(内側の) ループ展開の恩恵を受け、XMM レジスター内に 1 つの行列全体を保持してメモリ読み取りを減らします。ご覧のとおり、私はこのトピックを調査し、できる限り時間をかけて実装しました。%rdi%rsi%rdx

私のコードを征服する単純な C 計算は次のようになります。

void matrixMultiplyNormal(mat4_t *mat_a, mat4_t *mat_b, mat4_t *mat_r) {
    for (unsigned int i = 0; i < 16; i += 4)
        for (unsigned int j = 0; j < 4; ++j)
            mat_r->m[i + j] = (mat_b->m[i + 0] * mat_a->m[j +  0])
                            + (mat_b->m[i + 1] * mat_a->m[j +  4])
                            + (mat_b->m[i + 2] * mat_a->m[j +  8])
                            + (mat_b->m[i + 3] * mat_a->m[j + 12]);
}

上記の C コードの最適化されたアセンブリ出力を調査しました。これは、浮動小数点数を XMM レジスタに格納する一方で、並列操作(スカラー計算、ポインター演算、および条件付きジャンプのみ)を含まないものです。コンパイラのコードは意図的ではないように見えますが、約 4 倍高速であると予想されるベクトル化されたバージョンよりもわずかに効果的です。一般的な考えは正しいと確信しています。プログラマーは同様のことを行い、やりがいのある結果をもたらします。しかし、ここで何が問題なのですか？私が認識していないレジスタ割り当てまたは命令スケジューリングの問題はありますか? マシンとの戦いをサポートする x86-64 アセンブリ ツールまたはトリックを知っていますか?

4

5 に答える 5

36

4x4 行列の乗算は、64 回の乗算と 48 回の加算です。SSE を使用すると、これを 16 回の乗算と 12 回の加算 (および 16 回のブロードキャスト) に減らすことができます。次のコードはこれを行います。SSE ( #include <xmmintrin.h>) のみが必要です。配列A、B、およびCは、16 バイトで整列する必要があります。hadd(SSE3) やdpps(SSE4.1)などの水平方向の命令を使用すると、効率が低下します(特にdpps)。ループ展開が役立つかどうかはわかりません。

void M4x4_SSE(float *A, float *B, float *C) {
    __m128 row1 = _mm_load_ps(&B[0]);
    __m128 row2 = _mm_load_ps(&B[4]);
    __m128 row3 = _mm_load_ps(&B[8]);
    __m128 row4 = _mm_load_ps(&B[12]);
    for(int i=0; i<4; i++) {
        __m128 brod1 = _mm_set1_ps(A[4*i + 0]);
        __m128 brod2 = _mm_set1_ps(A[4*i + 1]);
        __m128 brod3 = _mm_set1_ps(A[4*i + 2]);
        __m128 brod4 = _mm_set1_ps(A[4*i + 3]);
        __m128 row = _mm_add_ps(
                    _mm_add_ps(
                        _mm_mul_ps(brod1, row1),
                        _mm_mul_ps(brod2, row2)),
                    _mm_add_ps(
                        _mm_mul_ps(brod3, row3),
                        _mm_mul_ps(brod4, row4)));
        _mm_store_ps(&C[4*i], row);
    }
}
于 2013-08-29T10:11:31.237 に答える
-3

明らかに、一度に 4 つの行列から項をフェッチし、同じアルゴリズムを使用して 4 つの行列を同時に掛けることができます。

于 2015-11-20T22:06:53.223 に答える