Memahami dan Menyelesaikan Perkongsian Palsu dalam Aplikasi Berbilang Benang dengan isu sebenar yang saya hadapi

Baru-baru ini, saya sedang mengusahakan pelaksanaan berbilang benang bagi fungsi untuk mengira taburan Poisson (amath_pdist). Matlamatnya adalah untuk membahagikan beban kerja merentas berbilang benang untuk meningkatkan prestasi, terutamanya untuk tatasusunan yang besar. Walau bagaimanapun, daripada mencapai kelajuan yang dijangkakan, saya melihat kelembapan yang ketara apabila saiz tatasusunan meningkat.

Selepas beberapa siasatan, saya dapati pelakunya: perkongsian palsu. Dalam siaran ini, saya akan menerangkan maksud perkongsian palsu, menunjukkan kod asal yang menyebabkan masalah dan berkongsi pembetulan yang membawa kepada peningkatan prestasi yang ketara.

---

Masalahnya: Perkongsian Palsu dalam Kod Berbilang Benang

Perkongsian palsu berlaku apabila berbilang urutan berfungsi pada bahagian berlainan tatasusunan kongsi, tetapi datanya berada dalam baris cache yang sama. Baris cache ialah unit terkecil data yang dipindahkan antara memori dan cache CPU (biasanya 64 bait). Jika satu utas menulis kepada sebahagian daripada baris cache, ia akan membatalkan baris untuk utas lain—walaupun jika mereka mengusahakan data bebas secara logik. Pembatalan yang tidak perlu ini membawa kepada kemerosotan prestasi yang ketara akibat pemuatan semula talian cache yang berulang.

Berikut ialah versi ringkas kod asal saya:

void *calculate_pdist_segment(void *data) {
    struct pdist_segment *segment = (struct pdist_segment *)data;
    size_t interval_a = segment->interval_a, interval_b = segment->interval_b;
    double lambda = segment->lambda;
    int *d = segment->data;

    for (size_t i = interval_a; i < interval_b; i++) {
        segment->pdist[i] = pow(lambda, d[i]) * exp(-lambda) / tgamma(d[i] + 1);
    }
    return NULL;
}

double *amath_pdist(int *data, double lambda, size_t n_elements, size_t n_threads) {
    double *pdist = malloc(sizeof(double) * n_elements);
    pthread_t threads[n_threads];
    struct pdist_segment segments[n_threads];
    size_t step = n_elements / n_threads;

    for (size_t i = 0; i < n_threads; i++) {
        segments[i].data = data;
        segments[i].lambda = lambda;
        segments[i].pdist = pdist;
        segments[i].interval_a = step * i;
        segments[i].interval_b = (i == n_threads - 1) ? n_elements : (step * (i + 1));
        pthread_create(&threads[i], NULL, calculate_pdist_segment, &segments[i]);
    }

    for (size_t i = 0; i < n_threads; i++) {
        pthread_join(threads[i], NULL);
    }

    return pdist;
}

---

Tempat Masalah Berlaku

Dalam kod di atas:

• Pdist tatasusunan dikongsi antara semua urutan.
• Setiap urutan menulis pada julat indeks tertentu (selang_a hingga selang_b).
• Di sempadan segmen, indeks bersebelahan mungkin berada dalam baris cache yang sama. Contohnya, jika pdist[249999] dan pdist[250000] berkongsi baris cache, Thread 1 (bekerja pada pdist[249999]) dan Thread 2 (working on pdist[250000]) akan membatalkan baris cache satu sama lain.

Isu ini berskala buruk dengan tatasusunan yang lebih besar. Walaupun isu sempadan mungkin kelihatan kecil, bilangan lelaran yang banyak membesarkan kos ketidaksahihan cache, membawa kepada beberapa saat overhed yang tidak perlu.

---

Penyelesaian: Jajarkan Memori kepada Sempadan Talian Cache

Untuk menyelesaikan masalah, saya menggunakan posix_memalign untuk memastikan tatasusunan pdist diselaraskan dengan sempadan 64 bait. Ini menjamin bahawa urutan beroperasi pada talian cache yang bebas sepenuhnya, menghapuskan perkongsian palsu.

Berikut ialah kod yang dikemas kini:

double *amath_pdist(int *data, double lambda, size_t n_elements, size_t n_threads) {
    double *pdist;
    if (posix_memalign((void **)&pdist, 64, sizeof(double) * n_elements) != 0) {
        perror("Failed to allocate aligned memory");
        return NULL;
    }

    pthread_t threads[n_threads];
    struct pdist_segment segments[n_threads];
    size_t step = n_elements / n_threads;

    for (size_t i = 0; i < n_threads; i++) {
        segments[i].data = data;
        segments[i].lambda = lambda;
        segments[i].pdist = pdist;
        segments[i].interval_a = step * i;
        segments[i].interval_b = (i == n_threads - 1) ? n_elements : (step * (i + 1));
        pthread_create(&threads[i], NULL, calculate_pdist_segment, &segments[i]);
    }

    for (size_t i = 0; i < n_threads; i++) {
        pthread_join(threads[i], NULL);
    }

    return pdist;
}

---

Mengapa Ini Berfungsi?

1. Memori Sejajar:

   • Menggunakan posix_memalign, tatasusunan bermula pada sempadan baris cache.
   • Julat yang ditetapkan setiap utas dijajarkan kemas dengan baris cache, mengelakkan pertindihan.

2. Tiada Perkongsian Talian Cache:

   • Benang beroperasi pada baris cache yang berbeza, menghapuskan ketidaksahihan yang disebabkan oleh perkongsian palsu.

3. Kecekapan Cache yang Diperbaiki:

   • Corak capaian memori berjujukan sejajar dengan prefetcher CPU, meningkatkan lagi prestasi.

---

Keputusan dan Ambilan

Selepas menggunakan pembetulan, masa jalan fungsi amath_pdist menurun dengan ketara. Untuk set data yang saya uji, masa jam dinding menurun daripada 10.92 saat kepada 0.06 saat.

Pengajaran Utama:

1. Perkongsian palsu ialah isu halus namun kritikal dalam aplikasi berbilang benang. Malah pertindihan kecil pada sempadan segmen boleh merendahkan prestasi.
2. Penjajaran memori menggunakan posix_memalign ialah cara yang mudah dan berkesan untuk menyelesaikan perkongsian palsu. Menjajarkan memori kepada sempadan baris cache memastikan urutan beroperasi secara bebas.
3. Sentiasa menganalisis kod anda untuk isu berkaitan cache apabila bekerja dengan tatasusunan besar atau pemprosesan selari. Alat seperti perf atau valgrind boleh membantu menentukan kesesakan.

Terima kasih kerana membaca!

Bagi sesiapa yang ingin tahu tentang kod tersebut, anda boleh menemuinya di sini

Atas ialah kandungan terperinci Memahami dan Menyelesaikan Perkongsian Palsu dalam Aplikasi Berbilang Benang dengan isu sebenar yang saya hadapi. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!