SSE SIMD 命令を使用して Intel CPU 上で高速プレフィックス合計アルゴリズムを開発するにはどうすればよいですか?

Intel CPU 上の SIMD プレフィックス サム

質問:

SSE SIMD CPU を使用した高速プレフィックス サム アルゴリズムの開発

答え:

最適解には 2 つの並列パスが含まれます:

パス 1:

• SSE を使用して部分和を並列計算するSIMD.
• 各部分和の合計を保存します。

パス 2:

• から合計を加算します。を使用して、前の部分和から次の部分和までSIMD.

利点:

• 並列処理により、両方のパスでの計算時間が短縮されます。
• パス 2 の SIMD 最適化により、さらに性能が向上します。パフォーマンス。

実装メモ:

• アルゴリズムの時間コストは、(n/m)*(1 1/w) として推定されます。ここで、n は配列サイズ、m はコア数、w は SIMD 幅です。
• このアルゴリズムは次のとおりです。シーケンシャル実装よりも大幅に高速であり、クアッドコア システムで約 7 の高速化係数を提供します。
• 大規模な配列の場合、データをキャッシュに保持しながらチャンクをチャンク化してシーケンシャルに実行することで、2 番目のパスをさらに最適化できます。 .

コード例:

__m128 scan_SSE(__m128 x) {
    x = _mm_add_ps(x, _mm_castsi128_ps(_mm_slli_si128(_mm_castps_si128(x), 4)));
    x = _mm_add_ps(x, _mm_shuffle_ps(_mm_setzero_ps(), x, 0x40));
    return x;
}

float pass1_SSE(float *a, float *s, const int n) {
    __m128 offset = _mm_setzero_ps();
    #pragma omp for schedule(static) nowait
    for (int i = 0; i < n / 4; i++) {
        __m128 x = _mm_load_ps(&a[4 * i]);
        __m128 out = scan_SSE(x);
        out = _mm_add_ps(out, offset);
        _mm_store_ps(&s[4 * i], out);
        offset = _mm_shuffle_ps(out, out, _MM_SHUFFLE(3, 3, 3, 3));
    }
    float tmp[4];
    _mm_store_ps(tmp, offset);
    return tmp[3];
}

void pass2_SSE(float *s, __m128 offset, const int n) {
    #pragma omp for schedule(static)
    for (int i = 0; i<n/4; i++) {
        __m128 tmp1 = _mm_load_ps(&s[4 * i]);
        tmp1 = _mm_add_ps(tmp1, offset);
        _mm_store_ps(&s[4 * i], tmp1);
    }
}

void scan_omp_SSEp2_SSEp1_chunk(float a[], float s[], int n) {
    float *suma;
    const int chunk_size = 1<<18;
    const int nchunks = n%chunk_size == 0 ? n / chunk_size : n / chunk_size + 1;

    #pragma omp parallel
    {
        const int ithread = omp_get_thread_num();
        const int nthreads = omp_get_num_threads();

        #pragma omp single
        {
            suma = new float[nthreads + 1];
            suma[0] = 0;
        }

        float offset2 = 0.0f;
        for (int c = 0; c < nchunks; c++) {
            const int start = c*chunk_size;
            const int chunk = (c + 1)*chunk_size < n ? chunk_size : n - c*chunk_size;
            suma[ithread + 1] = pass1_SSE(&a[start], &s[start], chunk);
            #pragma omp barrier
            #pragma omp single
            {
                float tmp = 0;
                for (int i = 0; i < (nthreads + 1); i++) {
                    tmp += suma[i];
                    suma[i] = tmp;
                }
            }
            __m128 offset = _mm_set1_ps(suma[ithread]+offset2);
            pass2_SSE(&s[start], offset, chunk);
            #pragma omp barrier
            offset2 = s[start + chunk-1];
        }
    }
    delete[] suma;
}

以上がSSE SIMD 命令を使用して Intel CPU 上で高速プレフィックス合計アルゴリズムを開発するにはどうすればよいですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。