Bagaimanakah Arahan SIMD pada CPU Intel Mengoptimumkan Algoritma Jumlah Awalan?

Jumlah Awalan SIMD pada CPU Intel

Algoritma jumlah awalan biasanya digunakan untuk mengira jumlah kumulatif elemen dalam tatasusunan. Untuk aplikasi kritikal masa, mengoptimumkan algoritma ini adalah penting. Satu pendekatan untuk mencapai ini adalah melalui arahan SIMD (Single Instruction Multiple Data) pada CPU Intel.

Pendekatan Turutan Konvensional

Pelaksanaan naif melibatkan lelaran melalui tatasusunan dan secara rekursif menjumlahkan unsur secara berpasangan. Walaupun mudah, pendekatan ini dihadkan oleh sifat urutannya.

Algoritma Jumlah Awalan SIMD

Untuk pengiraan yang lebih pantas, algoritma jumlah awalan selari boleh digunakan. Ia terdiri daripada dua pas:

Pas 1: Kira jumlah separa secara selari dan simpan jumlah keseluruhan untuk setiap jumlah separa.

Pas 2: Tambah jumlah keseluruhan daripada jumlah separa sebelumnya kepada separa seterusnya sum.

Pengoptimuman SSE

Pas kedua boleh dioptimumkan menggunakan arahan SSE, yang melaksanakan operasi vektor secara selari. Daripada lelaran secara berurutan, nilai malar ditambah kepada berbilang elemen secara serentak.

Analisis Prestasi

Andaikan n elemen dalam tatasusunan, teras m dan lebar SIMD w, kerumitan masa algoritma jumlah awalan SIMD ialah:

(n/m) * (1 1/w),

yang lebih pantas daripada kod jujukan.

Contoh Pelaksanaan

Kod yang disediakan melaksanakan algoritma jumlah awalan SIMD dalam C menggunakan intrinsik SSE dan OpenMP untuk selari.

float 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 scan_omp_SSEp2_SSEp1_chunk(float a[], float s[], int n) {
    // ... (code omitted for brevity)
}

Kesimpulan

Algoritma jumlah awalan SIMD ini menawarkan peningkatan prestasi yang ketara berbanding pendekatan berjujukan konvensional. Dengan memanfaatkan keselarian dan arahan SSE, ia mencapai kerumitan masa yang hampir optimum untuk sumber perkakasan yang tersedia.

Atas ialah kandungan terperinci Bagaimanakah Arahan SIMD pada CPU Intel Mengoptimumkan Algoritma Jumlah Awalan?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!