Can SIMD Instructions on Intel CPUs Significantly Improve Prefix Sum Algorithm Performance?

SIMD Prefix Sum on Intel Processors

Introduction

Prefix sum algorithms find the cumulative sum of a given array. This operation is encountered in various computational problems and requires high performance for efficient processing. In this article, we address whether SIMD instructions on Intel CPUs can enhance the performance of a prefix sum algorithm.

Parallel Prefix Sum with SIMD

One parallel prefix sum algorithm involves performing operations in two passes. In the first pass, partial sums are computed in parallel, followed by the accumulation of total sums for each partial sum. A second pass adds each partial sum's total sum to the next. Using multiple threads through OpenMP for parallelism and SIMD instructions for the second pass can improve efficiency.

Code for SIMD Prefix Sum

Here is an example of the code for the above algorithm:

__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;
}

void 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);
    }
}

Discussion

These optimizations allow for significant performance improvements for prefix sum operations on large arrays. Using SIMD for both passes further enhances efficiency, reducing computation time. The provided code utilizes SIMD for the second pass and achieves a performance boost of approximately 7x on a quad-core system.

The above is the detailed content of Can SIMD Instructions on Intel CPUs Significantly Improve Prefix Sum Algorithm Performance?. For more information, please follow other related articles on the PHP Chinese website!