Dalam sistem komputer modern, pemrosesan paralel adalah teknik umum yang digunakan untuk meningkatkan kinerja. Namun, ada beberapa tantangan untuk mencapai paralelisme yang efisien, salah satunya adalah pembagian yang salah.
Pembagian palsu terjadi ketika thread yang berjalan pada inti prosesor berbeda mengakses variabel berbeda yang berbagi baris cache yang sama. Hal ini dapat menyebabkan pembatalan cache yang tidak perlu, cache hilang dan kemudian dimuat ulang dari memori, sehingga mengakibatkan penurunan kinerja.
Pada artikel ini, kita akan mempelajari pembagian palsu dan dampaknya terhadap kinerja menggunakan kode contoh sederhana. Kami juga akan menggunakan alat pembuatan profil kinerja untuk mengukur dampak dari pembagian yang salah dan mendiskusikan teknik untuk mengurangi dampaknya.
Anda dapat mengakses kode yang digunakan dalam artikel ini di sini.
Garis cache
Pertama, Untuk memahami pembagian palsu, kita perlu mengetahui tentang “cache line”. Baris cache adalah unit data terkecil yang dapat disimpan dalam cache di cache CPU komputer. Ini mewakili blok memori berdekatan berukuran tetap yang dimuat dari memori utama ke dalam cache ketika CPU meminta data. Ukuran baris cache bervariasi tergantung pada arsitektur CPU tertentu dan dapat berkisar antara 32 hingga 512 byte.
Ketika CPU meminta data dari memori, ia mengambil seluruh baris cache yang berisi data yang diminta serta data tambahan yang berdekatan. Hal ini dilakukan untuk memanfaatkan lokalitas spasial, yaitu kecenderungan data diakses berdekatan dengan data lain. Dengan melakukan cache seluruh baris cache, CPU dapat mengurangi jumlah cache yang hilang dan pemuatan ulang baris cache, sehingga dapat meningkatkan kinerja secara signifikan.
Meskipun baris cache ada untuk peningkatan kinerja, hal ini juga dapat menyebabkan masalah kinerja seperti pembagian yang salah.
Berbagi palsu terjadi dalam aplikasi multi-thread ketika dua atau lebih thread mengakses variabel berbeda yang kebetulan terletak di baris cache yang sama. Ketika satu thread memperbarui variabel, seluruh baris cache menjadi tidak valid, yang memaksa thread lain memuat ulang baris cache dari memori. Hal ini mengakibatkan cache hilang dan dimuat ulang, yang dapat memperlambat program secara signifikan.
Anda dapat memeriksa ukuran baris cache sistem Anda dengan menjalankan perintah di bawah ini di konsol
cat /sys/devices/system/cpu/cpu0/cache/index0/coherency_line_size 64
Perintah ini mencetak ukuran baris cache dari cache data L1 untuk inti CPU pertama (cpu0) dalam byte. Nilai diperoleh dari file coherency_line_size yang terletak di sistem file sysfs, yang menyediakan antarmuka ke struktur data kernel dan informasi perangkat keras. Dalam sistem ini, ukuran baris cache adalah 64 byte.
Berbagi yang salah
Karena ukuran baris cache dalam sistem adalah 64 byte, yang berarti bahwa ketika satu byte data dimuat ke dalam cache, seluruh baris cache 64 byte yang berisi byte tersebut juga dimuat. Jika dua variabel terletak pada baris cache yang sama dan diakses oleh thread yang berbeda, pembagian yang salah dapat terjadi.
Ketika satu thread memperbarui variabelnya, seluruh baris cache menjadi tidak valid, yang memaksa thread lain memuat ulang seluruh baris cache dari memori. Hal ini dapat menyebabkan cache hilang dan memuat ulang variabel yang sebenarnya tidak diperbarui, namun kebetulan berada pada baris cache yang sama. Jika variabel-variabel ini sering diakses oleh thread yang berbeda, overhead cache yang hilang dan memuat ulang dapat memperlambat program secara signifikan.
Berikut adalah program C++ untuk mendemonstrasikan efek false sharing.
// false_sharing_test.cpp
#include <iostream>
#include <stdexcept>
#include <chrono>
#include <thread>
#include <array>
#include <algorithm>
#include <sstream>
constexpr int NUM_ITERATION = 100000000;
#ifdef ALIGNED
struct alignas(64) Data {
int value;
char padding[64 - sizeof(int)];
};
#else
struct alignas(32) Data {
int value;
};
#endif
void increment(int start, int end, int core_id, std::array<Data, 2>& shared_data)
{
pthread_t thread_id = pthread_self();
cpu_set_t cpuset;
CPU_ZERO(&cpuset);
CPU_SET(core_id, &cpuset);
int rc = pthread_setaffinity_np(thread_id, sizeof(cpu_set_t), &cpuset);
if (rc != 0) {
std::cerr << "Error setting CPU affinity" << std::endl;
} else {
std::cout << "Thread: " << thread_id << " is assigned to Core: " << core_id << std::endl;
}
for (int idx = start; idx < end; idx++) {
for (int i = 0; i < NUM_ITERATION; ++i) {
shared_data[idx].value++;
}
}
}
void initialize(std::array<Data, 2>& shared_data) {
std::for_each(shared_data.begin(), shared_data.end(), [](auto& ele){ele.value = 0;});
}
template <typename F, typename... Args>
auto time_it(F&& f, Args&&... args) {
auto start_time = std::chrono::high_resolution_clock::now();
f(std::forward<Args>(args)...);
auto end_time = std::chrono::high_resolution_clock::now();
return std::chrono::duration_cast<std::chrono::microseconds>(end_time - start_time).count();
}
int main(int argc, char * argv[])
{
int cpu_offset = 0; // default value
std::istringstream ss(argv[1]);
int x;
if (!(ss >> cpu_offset)) {
std::cerr << "Invalid number: " << argv[1] << '\n';
} else if (!ss.eof()) {
std::cerr << "Trailing characters after number: " << argv[1] << '\n';
}
std::array<Data, 2> shared_data;
initialize(shared_data);
// Spawn 2 threads to increment the elements of the array
auto update = [&shared_data](int cpu_offset){
std::array<std::thread, 2> threads;
int core_id = 0;
for (int i = 0; i < 2; i++ ) {
threads[i] = std::thread(increment, i, i + 1, core_id, std::ref(shared_data));
core_id += cpu_offset;
}
// Wait for all threads to finish
for (int i = 0; i < 2; ++i) {
threads[i].join();
}
};
// Measure the time it took to execute the function
auto elapsed_time = time_it(update, cpu_offset);
// Print the elapsed time
std::cout << "Elapsed time: " << elapsed_time << " microseconds" << std::endl;
for (const auto & ele : shared_data) {
if (ele.value != NUM_ITERATION) {
std::cout << "Error!\n";
return 1;
}
}
std::cout << "Finished." << std::endl;
return 0;
}
Kode ini mendefinisikan sebuah struct bernama Data yang memiliki satu anggota bilangan bulat bernama value. Struct didefinisikan secara kondisional berdasarkan makro praprosesor ALIGNED. Jika ALIGNED didefinisikan, maka struct Data didefinisikan dengan penyelarasan 64-byte, dan menyertakan array karakter padding yang memastikan ukuran struct adalah kelipatan 64 byte.
Penyelarasan ini penting untuk menghindari pembagian yang salah antara thread yang mengakses instance berbeda dari Data struct dalam program multi-thread. Padding memastikan bahwa struct selaras dengan ukuran baris cache.
Dengan menyelaraskan struct dengan ukuran baris cache, kami dapat memastikan bahwa setiap variabel ditempatkan di baris cache terpisah, sehingga mencegah pembagian yang salah dan meningkatkan kinerja.
Jika ALIGNED tidak didefinisikan, maka struct Data didefinisikan dengan penyelarasan 32-byte, tanpa padding apa pun, maka dua elemen yang berdekatan terletak di baris cache yang sama.
Kami mengkompilasi 2 versi program.
Eksekusi pertama menggunakan Data yang disejajarkan dengan 64 byte (jadi, ukuran baris cache).
Yang ke-2 tidak selaras dengan baris cache sistem.
g++ -g -DALIGNED -std=c++14 -pthread -o aligned false_sharing_test.cpp g++ -g -std=c++14 -pthread -o not_aligned false_sharing_test.cpp
Di bagian selanjutnya, kita akan menggunakan alat analisis kinerja yang disebut perf untuk menganalisis pengaruh pembagian palsu.
Kinerja
perf adalah alat analisis kinerja yang kuat di Linux yang memungkinkan pengembang dan administrator sistem mengumpulkan informasi profil tentang aplikasi mereka. Ini adalah bagian dari kernel Linux dan dapat digunakan untuk menganalisis program kernel dan ruang pengguna.
Mari kita analisa 2 program yang kita kompilasi sebelumnya, Pertama, kita jalankan versi program yang “not_aligned”.
sudo perf stat -d --cpu=0,2 ./not_aligned 2
Thread: 139717077104192 is assigned to Core: 0
Thread: 139717068711488 is assigned to Core: 2
Elapsed time: 660272 microseconds
Finished.
Performance counter stats for 'CPU(s) 0,2':
1.324,00 msec cpu-clock # 2,000 CPUs utilized
25 context-switches # 18,882 /sec
4 cpu-migrations # 3,021 /sec
8 page-faults # 6,042 /sec
5.601.909.645 cycles # 4,231 GHz (61,93%)
345.034 stalled-cycles-frontend # 0,01% frontend cycles idle (61,93%)
4.434.320.438 stalled-cycles-backend # 79,16% backend cycles idle (61,93%)
7.366.509.121 instructions # 1,31 insn per cycle
# 0,60 stalled cycles per insn (62,29%)
997.791.605 branches # 753,617 M/sec (62,90%)
20.824 branch-misses # 0,00% of all branches (63,45%)
4.452.397.262 L1-dcache-loads # 3,363 G/sec (63,09%)
19.451.916 L1-dcache-load-misses # 0,44% of all L1-dcache accesses (62,48%)
<not supported> LLC-loads
<not supported> LLC-load-misses
0,661940908 seconds time elapsed
Perintah ini menggunakan alat perf untuk mengumpulkan statistik kinerja saat menjalankan program yang dapat dieksekusi not_aligned dengan 2 sebagai argumennya.
Argumen 2 diberikan sehingga 2 thread yang dibuat masing-masing ditugaskan ke inti 0 dan inti 2 (Lihat programnya).
--cpu=0,option diberikan untuk menentukan CPU mana yang akan dipantau untuk statistik kinerja. Dalam hal ini, CPU 0 dan 2 dipantau. -ddiberikan untuk mengumpulkan beberapa informasi acara secara detail.
Seperti yang Anda lihat, program not_aligned ini membutuhkan 660.272 mikrodetik. Selain itu, Anda dapat melihatnya menyebabkan 19.451.916L1-dcache-load-misses. L1-dcache-load-missesmenunjukkan seberapa sering prosesor harus keluar dari cache L1 untuk mengambil data, yang dapat mengakibatkan peningkatan latensi dan penurunan kinerja, yang dapat Anda ketahui dengan melihat lineinstructions # 1,31 . Ini adalah jumlah instruksi untuk proram dan insn per cycle adalah jumlah rata-rata instruksi yang dieksekusi per siklus. Nilai 1,31 berarti rata-rata 1,31 instruksi dieksekusi per siklus CPU.
Metrik stalled-cycles-backend di perf stat melaporkan persentase siklus di mana back-end prosesor tidak dapat menjalankan instruksi apa pun karena berbagai alasan seperti konflik sumber daya, terhentinya saluran pipa, atau penundaan terkait memori seperti cache yang hilang. 79.16% backend cycles idle (61.93%) berarti selama eksekusi program, back-end prosesor menganggur sekitar 79,16% dari total siklus. Dari jumlah tersebut, sekitar 61,93% siklus terhenti karena masalah back-end.
Selanjutnya, mari kita menganalisis versi program yang “selaras”.
sudo perf stat -d --cpu=0,2 ./aligned 2
Thread: 140167891383872 is assigned to Core: 0
Thread: 1401678829911680 is assigned to Core: 2
Elapsed time: 313397 microseconds
Finished.
Performance counter stats for 'CPU(s) 0,2':
629,14 msec cpu-clock # 2,000 CPUs utilized
43 context-switches # 68,347 /sec
5 cpu-migrations # 7,947 /sec
9 page-faults # 14,305 /sec
2.498.645.227 cycles # 3,972 GHz (61,85%)
192.073 stalled-cycles-frontend # 0,01% frontend cycles idle (61,85%)
150.297.658 stalled-cycles-backend # 6,02% backend cycles idle (61,85%)
7.511.449.108 instructions # 3,01 insn per cycle
# 0,02 stalled cycles per insn (61,85%)
1.002.282.314 branches # 1,593 G/sec (62,57%)
15.928 branch-misses # 0,00% of all branches (63,58%)
4.352.833.767 L1-dcache-loads # 6,919 G/sec (63,58%)
55.837 L1-dcache-load-misses # 0,00% of all L1-dcache accesses (62,86%)
<not supported> LLC-loads
<not supported> LLC-load-misses
0,314513605 seconds time elapsed
Seperti yang Anda lihat, jumlahnya jauh lebih sedikit L1-dcache-load-misses(99,99% lebih sedikit!). Efisiensi pemrosesan juga 3.01 insn per cycle(129,77% lebih banyak) .
Versi program yang selaras lebih efisien dan menghindari pembagian yang salah karena mengurangi konflik baris cache.
Dengan menyelaraskan variabel dengan batas baris cache, variabel dijamin ditempatkan di baris cache yang berbeda, mencegah pembagian yang salah dan mengurangi jumlah konflik baris cache. Hal ini dapat menghasilkan peningkatan kinerja yang signifikan, terutama dalam aplikasi multi-thread.
Ringkasan
Artikel ini membahas pembagian palsu dalam pemrograman multithread, masalah kinerja yang dapat terjadi ketika dua atau lebih thread mengakses variabel berbeda yang terletak di baris cache yang sama.
Berbagi yang salah dapat menyebabkan pembatalan cache yang tidak perlu, cache hilang, dan memuat ulang, sehingga mengakibatkan penurunan kinerja.
Artikel ini menjelaskan konsep baris cache, yaitu unit data terkecil yang dapat di-cache dalam cache CPU, dan ukurannya, yang bervariasi bergantung pada arsitektur CPU.
Artikel ini juga menyediakan program C++ untuk mendemonstrasikan efek dari false sharing dan menjelaskan cara menggunakan alat pembuatan profil kinerja untuk mengukur dampaknya.
Artikel ini diakhiri dengan membahas teknik-teknik untuk mengurangi dampak dari pembagian informasi yang salah.
Pengodean Naik Level
Terima kasih telah menjadi bagian dari komunitas kami! Sebelum kamu pergi:
- 👏 Tepuk tangan untuk ceritanya dan ikuti penulisnya 👉
- 📰 Lihat lebih banyak konten di Publikasi Level Up Coding
- 💰 Kursus wawancara coding gratis ⇒ Lihat Kursus
- 🔔 Ikuti kami: Twitter | LinkedIn | Buletin
🚀👉 Bergabunglah dengan kumpulan bakat Level Up dan temukan pekerjaan luar biasa
