Können SIMD-Anweisungen auf Intel-CPUs die Leistung des Präfixsummenalgorithmus erheblich verbessern?

SIMD-Präfixsumme auf Intel-Prozessoren

Einführung

Präfixsummenalgorithmen ermitteln die kumulative Summe eines gegebenen Arrays. Diese Operation kommt bei verschiedenen Rechenproblemen vor und erfordert eine hohe Leistung für eine effiziente Verarbeitung. In diesem Artikel befassen wir uns mit der Frage, ob SIMD-Anweisungen auf Intel-CPUs die Leistung eines Präfixsummenalgorithmus verbessern können.

Parallele Präfixsumme mit SIMD

Ein paralleler Präfixsummenalgorithmus beinhaltet die Durchführung von Vorgängen in zwei Durchgängen. Im ersten Durchgang werden Teilsummen parallel berechnet, gefolgt von der Akkumulation der Gesamtsummen für jede Teilsumme. In einem zweiten Durchgang wird die Gesamtsumme jeder Teilsumme zur nächsten addiert. Die Verwendung mehrerer Threads über OpenMP für Parallelität und SIMD-Anweisungen für den zweiten Durchgang kann die Effizienz verbessern.

Code für SIMD-Präfixsumme

Hier ist ein Beispiel für den Code für über Algorithmus:

__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(&amp;a[4 * i]);
        __m128 out = scan_SSE(x);
        out = _mm_add_ps(out, offset);
        _mm_store_ps(&amp;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(&amp;s[4 * i]);
        tmp1 = _mm_add_ps(tmp1, offset);
        _mm_store_ps(&amp;s[4 * i], tmp1);
    }
}

Diskussion

Diese Optimierungen ermöglichen erhebliche Leistungsverbesserungen für Präfixsummenoperationen auf großen Arrays. Die Verwendung von SIMD für beide Durchgänge steigert die Effizienz weiter und reduziert die Rechenzeit. Der bereitgestellte Code nutzt SIMD für den zweiten Durchgang und erreicht eine Leistungssteigerung von etwa dem Siebenfachen auf einem Quad-Core-System.

Das obige ist der detaillierte Inhalt vonKönnen SIMD-Anweisungen auf Intel-CPUs die Leistung des Präfixsummenalgorithmus erheblich verbessern?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!