Membaca paralel yang paralel tampaknya berfungsi dengan baik - mengapa?

Pertimbangkan program komputer yang sangat sederhana berikut ini:

for i = 1 to n:
    y[i] = x[p[i]]

Di sini dan adalah elemen array byte, dan adalah array elemen kata. Di sini berukuran besar, misalnya, (sehingga hanya sebagian kecil dari data yang cocok dengan segala jenis memori cache).$x$$y$$n$$p$$n$$n$$n = 2^{31}$

Asumsikan bahwa terdiri dari angka acak , terdistribusi secara seragam antara dan .1 $p$$1$$n$

Dari perspektif perangkat keras modern, ini harus berarti sebagai berikut:

• membaca murah (membaca berurutan)$p[i]$
• membaca sangat mahal (bacaan acak; hampir semua bacaan adalah kesalahan cache; kita harus mengambil setiap byte individual dari memori utama)$x[p[i]]$
• menulis murah (menulis berurutan).$y[i]$

Dan ini memang yang saya amati. Program ini sangat lambat dibandingkan dengan program yang hanya membaca dan menulis berurutan. Bagus.

Sekarang muncul pertanyaan: seberapa baik program ini berparalel pada platform multi-core modern?

Hipotesis saya adalah bahwa program ini tidak sejajar dengan baik. Bagaimanapun, bottleneck adalah memori utama. Satu core sudah menghabiskan sebagian besar waktunya hanya menunggu beberapa data dari memori utama.

Namun, ini bukan yang saya amati ketika saya mulai bereksperimen dengan beberapa algoritma di mana hambatannya adalah operasi semacam ini!

Saya hanya mengganti naif untuk-loop dengan paralel OpenMP untuk-loop (pada dasarnya, itu hanya akan membagi kisaran ke bagian yang lebih kecil dan menjalankan bagian-bagian ini pada core CPU yang berbeda secara paralel).$[1,n]$

Pada komputer low-end, speedup memang kecil. Tetapi pada platform yang lebih tinggi saya terkejut bahwa saya mendapatkan speedup dekat-linear yang sangat baik. Beberapa contoh konkret (ketepatan waktu mungkin sedikit tidak tepat, ada banyak variasi acak; ini hanya eksperimen cepat):

• 2 x 4-core Xeon (total 8 core): faktor 5-8 percepatan dibandingkan dengan versi single-threaded.

• 2 x 6-core Xeon (total 12 core): faktor 8-14 percepatan dibandingkan dengan versi single-threaded.

Sekarang ini sama sekali tidak terduga. Pertanyaan:

1. Justru mengapa program semacam ini berparalel dengan sangat baik ? Apa yang terjadi pada perangkat keras? (Dugaan saya saat ini adalah sesuatu di sepanjang baris ini: pembacaan acak dari utas berbeda adalah "pipelined" dan tingkat rata-rata untuk mendapatkan jawaban untuk ini jauh lebih tinggi daripada dalam hal satu utas.)

2. Apakah perlu menggunakan beberapa utas dan beberapa inti untuk mendapatkan speedup? Jika semacam pipelining memang terjadi di antarmuka antara memori utama dan CPU, tidak bisakah aplikasi berulir tunggal membiarkan memori utama tahu bahwa itu akan segera membutuhkan , x [ p [ i + 1 ] ] , ... dan komputer bisa mulai mengambil garis cache yang relevan dari memori utama? Jika ini mungkin pada prinsipnya, bagaimana cara mencapainya dalam praktik?$x[p[i]]$$x[p[i+1]]$

3. Apa hak model teoritis yang bisa kita gunakan untuk menganalisis jenis program (dan membuat yang benar prediksi kinerja)?

Sunting: Sekarang ada beberapa kode sumber dan hasil benchmark tersedia di sini: https://github.com/suomela/parallel-random-read

Beberapa contoh angka rata-rata ( ):$n = 2^{32}$

• sekitar 42 ns per iterasi (baca acak) dengan utas tunggal
• sekitar 5 ns per iterasi (baca acak) dengan 12 core.

$p$$\left\lfloor {\frac{n}{p}} \right\rfloor$$\left\lceil {\frac{n}{p}} \right\rceil$$p$

Sekarang, mari kita perhatikan masalah memori. Speedup super-linear yang Anda amati pada node berbasis Xeon high-end Anda dibenarkan sebagai berikut.

$n$$n/p$$p$

$n = 2^{31}$

$n$

Akhirnya, selain QSM (Antrian Memori Bersama) , saya tidak mengetahui adanya model paralel teoretis lainnya yang memperhitungkan pada tingkat yang sama pertentangan untuk akses ke memori bersama (dalam kasus Anda, ketika menggunakan OpenMP, memori utama dibagi di antara inti. , dan cache selalu dibagikan juga di antara core). Lagi pula, meskipun modelnya menarik, itu tidak mendapatkan kesuksesan besar.

Saya memutuskan untuk mencoba __builtin_prefetch () sendiri. Saya memposting di sini sebagai jawaban kalau-kalau orang lain ingin mengujinya di mesin mereka. Hasilnya mendekati apa yang dijelaskan Jukka: Tentang penurunan 20% dalam waktu berjalan saat mengambil 20 elemen di depan dibandingkan dengan mengambil 0 elemen di depan.

Hasil:

prefetch =   0, time = 1.58000
prefetch =   1, time = 1.47000
prefetch =   2, time = 1.39000
prefetch =   3, time = 1.34000
prefetch =   4, time = 1.31000
prefetch =   5, time = 1.30000
prefetch =   6, time = 1.27000
prefetch =   7, time = 1.28000
prefetch =   8, time = 1.26000
prefetch =   9, time = 1.27000
prefetch =  10, time = 1.27000
prefetch =  11, time = 1.27000
prefetch =  12, time = 1.30000
prefetch =  13, time = 1.29000
prefetch =  14, time = 1.30000
prefetch =  15, time = 1.28000
prefetch =  16, time = 1.24000
prefetch =  17, time = 1.28000
prefetch =  18, time = 1.29000
prefetch =  19, time = 1.25000
prefetch =  20, time = 1.24000
prefetch =  19, time = 1.26000
prefetch =  18, time = 1.27000
prefetch =  17, time = 1.26000
prefetch =  16, time = 1.27000
prefetch =  15, time = 1.28000
prefetch =  14, time = 1.29000
prefetch =  13, time = 1.26000
prefetch =  12, time = 1.28000
prefetch =  11, time = 1.30000
prefetch =  10, time = 1.31000
prefetch =   9, time = 1.27000
prefetch =   8, time = 1.32000
prefetch =   7, time = 1.31000
prefetch =   6, time = 1.30000
prefetch =   5, time = 1.27000
prefetch =   4, time = 1.33000
prefetch =   3, time = 1.38000
prefetch =   2, time = 1.41000
prefetch =   1, time = 1.41000
prefetch =   0, time = 1.59000

Kode:

#include <stdlib.h>
#include <time.h>
#include <stdio.h>

void cracker(int *y, int *x, int *p, int n, int pf) {
    int i;
    int saved = pf;  /* let compiler optimize address computations */

    for (i = 0; i < n; i++) {
        __builtin_prefetch(&x[p[i+saved]]);
        y[i] += x[p[i]];
    }
}

int main(void) {
    int n = 50000000;
    int *x, *y, *p, i, pf, k;
    clock_t start, stop;
    double elapsed;

    /* set up arrays */
    x = malloc(sizeof(int)*n);
    y = malloc(sizeof(int)*n);
    p = malloc(sizeof(int)*n);
    for (i = 0; i < n; i++)
        p[i] = rand()%n;

    /* warm-up exercise */
    cracker(y, x, p, n, pf);

    k = 20;
    for (pf = 0; pf < k; pf++) {
        start = clock();
        cracker(y, x, p, n, pf);
        stop = clock();
        elapsed = ((double)(stop-start))/CLOCKS_PER_SEC;
        printf("prefetch = %3d, time = %.5lf\n", pf, elapsed);
    }
    for (pf = k; pf >= 0; pf--) {
        start = clock();
        cracker(y, x, p, n, pf);
        stop = clock();
        elapsed = ((double)(stop-start))/CLOCKS_PER_SEC;
        printf("prefetch = %3d, time = %.5lf\n", pf, elapsed);
    }

    return 0;
}

1. Akses DDR3 memang disalurkan melalui pipa. http://www.eng.utah.edu/~cs7810/pres/dram-cs7810-protocolx2.pdf slide 20 dan 24 menunjukkan apa yang terjadi di bus memori selama operasi baca yang disalurkan melalui pipa.

2. (sebagian salah, lihat di bawah) Beberapa utas tidak diperlukan jika arsitektur CPU mendukung prefetch cache. Modern x86 dan ARM serta banyak arsitektur lainnya memiliki instruksi prefetch eksplisit. Selain itu banyak upaya untuk mendeteksi pola dalam akses memori dan melakukan pengambilan awal secara otomatis. Dukungan perangkat lunak adalah khusus untuk kompiler, misalnya GCC dan Dentang memiliki __builtin_prefech () intrinsik untuk prefetching eksplisit.

Hyperhreading ala Intel tampaknya bekerja sangat baik untuk program yang menghabiskan sebagian besar waktu mereka menunggu kesalahan cache. Dalam pengalaman saya, dalam beban kerja komputasi intensif percepatan berjalan sangat sedikit di atas jumlah core fisik.

EDIT: Saya salah dalam poin 2. Tampaknya sementara prefetching dapat mengoptimalkan akses memori untuk single core, bandwidth memori gabungan dari beberapa core lebih besar dari bandwidth core tunggal. Seberapa besar, tergantung pada CPU.

Prefetcher perangkat keras dan optimasi lainnya bersama-sama membuat pembandingan sangat rumit. Dimungkinkan untuk membuat kasus-kasus di mana prefetching eksplisit memiliki efek yang sangat terlihat atau tidak ada pada kinerja, tolok ukur ini menjadi salah satu yang terakhir.