ในระบบคอมพิวเตอร์สมัยใหม่ การประมวลผลแบบขนานเป็นเทคนิคทั่วไปที่ใช้เพื่อปรับปรุงประสิทธิภาพ อย่างไรก็ตาม มีความท้าทายหลายประการในการบรรลุความเท่าเทียมที่มีประสิทธิภาพ หนึ่งในนั้นคือการแบ่งปันที่ผิดพลาด
การแบ่งปันที่ผิดพลาดเกิดขึ้นเมื่อเธรดที่ทำงานบนคอร์ที่แตกต่างกันของโปรเซสเซอร์เข้าถึงตัวแปรที่แตกต่างกันซึ่งบังเอิญแชร์บรรทัดแคชเดียวกัน ซึ่งอาจนำไปสู่การทำให้แคชใช้งานไม่ได้โดยไม่จำเป็น แคชหายไป จากนั้นโหลดซ้ำจากหน่วยความจำ ส่งผลให้ประสิทธิภาพลดลง
ในบทความนี้ เราจะสำรวจการแบ่งปันที่ผิดพลาดและผลกระทบต่อประสิทธิภาพโดยใช้โค้ดตัวอย่างง่ายๆ นอกจากนี้ เราจะใช้เครื่องมือสร้างโปรไฟล์ที่สมบูรณ์แบบเพื่อวัดผลกระทบของการแบ่งปันที่ผิดพลาด และอภิปรายเทคนิคต่างๆ เพื่อลดผลกระทบ
คุณสามารถเข้าถึงรหัสที่ใช้ในบทความนี้ได้ "ที่นี่"
เส้นแคช
อันดับแรก เพื่อทำความเข้าใจการแบ่งปันที่ผิดพลาด เราจำเป็นต้องรู้เกี่ยวกับ "cache line" เส้นแคชคือหน่วยข้อมูลที่เล็กที่สุดที่สามารถแคชไว้ในแคช CPU ของคอมพิวเตอร์ได้ โดยแสดงถึงบล็อกขนาดคงที่ของหน่วยความจำที่อยู่ติดกันซึ่งโหลดจากหน่วยความจำหลักลงในแคชเมื่อ CPU ร้องขอข้อมูล ขนาดของบรรทัดแคชจะแตกต่างกันไปขึ้นอยู่กับสถาปัตยกรรม CPU เฉพาะ และอาจมีขนาดตั้งแต่ 32 ถึง 512 ไบต์
เมื่อ CPU ร้องขอข้อมูลจากหน่วยความจำ มันจะดึงข้อมูลแคชทั้งหมดซึ่งประกอบด้วยข้อมูลที่ร้องขอรวมถึงข้อมูลเพิ่มเติมที่อยู่ติดกัน สิ่งนี้ทำเพื่อใช้ประโยชน์จากพื้นที่เชิงพื้นที่ ซึ่งเป็นแนวโน้มที่ข้อมูลจะเข้าถึงได้ใกล้กับข้อมูลอื่นๆ ด้วยการแคชบรรทัดแคชทั้งหมด CPU สามารถลดจำนวนการพลาดแคชและการโหลดบรรทัดแคชใหม่ ซึ่งสามารถปรับปรุงประสิทธิภาพได้อย่างมาก
แม้ว่าบรรทัดแคชจะมีไว้เพื่อการปรับปรุงประสิทธิภาพ แต่ก็สามารถนำไปสู่ปัญหาด้านประสิทธิภาพได้ เช่น การแชร์ที่ผิดพลาด
การแบ่งปันที่ผิดพลาดเกิดขึ้นในแอปพลิเคชันแบบมัลติเธรดเมื่อเธรดตั้งแต่สองตัวขึ้นไปเข้าถึงตัวแปรที่แตกต่างกันซึ่งบังเอิญอยู่บนบรรทัดแคชเดียวกัน เมื่อเธรดหนึ่งอัปเดตตัวแปร บรรทัดแคชทั้งหมดจะใช้งานไม่ได้ ซึ่งบังคับให้เธรดอื่นโหลดบรรทัดแคชจากหน่วยความจำอีกครั้ง ส่งผลให้แคชพลาดและโหลดซ้ำ ซึ่งอาจทำให้โปรแกรมช้าลงอย่างมาก
คุณสามารถตรวจสอบขนาดแคชไลน์ของระบบของคุณได้โดยดำเนินการคำสั่งด้านล่างในคอนโซล
cat /sys/devices/system/cpu/cpu0/cache/index0/coherency_line_size 64
คำสั่งนี้พิมพ์ขนาดของบรรทัดแคชของแคชข้อมูล L1 สำหรับ CPU คอร์แรก (cpu0) ในหน่วยไบต์ ค่านี้ได้มาจากไฟล์ coherency_line_size ที่อยู่ในระบบไฟล์ sysfs ซึ่งจัดให้มีอินเทอร์เฟซสำหรับโครงสร้างข้อมูลเคอร์เนลและข้อมูลฮาร์ดแวร์ ในระบบนี้ ขนาดบรรทัดแคชคือ 64 ไบต์
การแบ่งปันอันเป็นเท็จ
เนื่องจากขนาดบรรทัดแคชในระบบคือ 64 ไบต์ ซึ่งหมายความว่าเมื่อมีการโหลดข้อมูลหนึ่งไบต์ลงในแคช บรรทัดแคชขนาด 64 ไบต์ทั้งหมดที่มีไบต์นั้นก็จะถูกโหลดด้วย หากตัวแปรสองตัวอยู่บนบรรทัดแคชเดียวกันและเข้าถึงได้โดยเธรดที่ต่างกัน การแบ่งปันที่ผิดพลาดอาจเกิดขึ้นได้
เมื่อเธรดหนึ่งอัปเดตตัวแปร บรรทัดแคชทั้งหมดจะใช้งานไม่ได้ ซึ่งบังคับให้เธรดอื่นโหลดบรรทัดแคชทั้งหมดจากหน่วยความจำอีกครั้ง ซึ่งอาจทำให้แคชพลาดและโหลดซ้ำสำหรับตัวแปรที่ไม่ได้รับการอัปเดตจริง ๆ แต่บังเอิญอยู่ในบรรทัดแคชเดียวกัน หากเธรดต่างๆ เข้าถึงตัวแปรเหล่านี้บ่อยครั้ง โอเวอร์เฮดของแคชที่พลาดไปและการโหลดซ้ำอาจทำให้โปรแกรมช้าลงอย่างมาก
นี่คือโปรแกรม C++ เพื่อสาธิตผลกระทบของการแบ่งปันที่ผิดพลาด
// 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;
}
รหัสนี้กำหนดโครงสร้างชื่อ Data ซึ่งมีสมาชิกจำนวนเต็มตัวเดียวชื่อ value โครงสร้างถูกกำหนดแบบมีเงื่อนไขตามแมโครตัวประมวลผลล่วงหน้า ALIGNED หากกำหนด ALIGNED โครงสร้าง Data จะถูกกำหนดด้วยการจัดตำแหน่ง 64 ไบต์ และมีอาร์เรย์ของอักขระเสริมเพื่อให้แน่ใจว่าขนาดของโครงสร้างจะเป็นจำนวนเท่าของ 64 ไบต์
การจัดตำแหน่งนี้มีความสำคัญสำหรับการหลีกเลี่ยงการแชร์ที่ผิดพลาดระหว่างเธรดที่เข้าถึงอินสแตนซ์ที่แตกต่างกันของโครงสร้าง Data ในโปรแกรมแบบมัลติเธรด ช่องว่างภายในช่วยให้มั่นใจได้ว่าโครงสร้างจะสอดคล้องกับขนาดเส้นแคช
ด้วยการจัดตำแหน่งโครงสร้างให้ตรงกับขนาดบรรทัดแคช เราจึงมั่นใจได้ว่าแต่ละตัวแปรจะอยู่ในบรรทัดแคชที่แยกจากกัน ป้องกันการแบ่งปันที่ผิดพลาดและปรับปรุงประสิทธิภาพ
หากไม่ได้กำหนด ALIGNED ดังนั้นโครงสร้าง Data จะถูกกำหนดด้วยการจัดตำแหน่ง 32 ไบต์ โดยไม่มีช่องว่างภายใน ดังนั้นองค์ประกอบสองรายการที่อยู่ติดกันจึงอยู่ในบรรทัดแคชเดียวกัน
เรารวบรวมโปรแกรม 2 เวอร์ชัน
ไฟล์ปฏิบัติการแรกคือการใช้ Data ซึ่งจัดแนวเป็น 64 ไบต์ (เช่น ขนาดบรรทัดแคช)
อันที่ 2 ไม่สอดคล้องกับบรรทัดแคชของระบบ
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
ในส่วนถัดไป เราจะใช้เครื่องมือวิเคราะห์ประสิทธิภาพที่เรียกว่า perf เพื่อวิเคราะห์ผลกระทบของการแบ่งปันที่ผิดพลาด
เพอร์เฟค
perf เป็นเครื่องมือวิเคราะห์ประสิทธิภาพอันทรงพลังใน Linux ที่ช่วยให้นักพัฒนาและผู้ดูแลระบบสามารถรวบรวมข้อมูลโปรไฟล์เกี่ยวกับแอปพลิเคชันของตนได้ มันเป็นส่วนหนึ่งของเคอร์เนล Linux และสามารถใช้เพื่อวิเคราะห์ทั้งโปรแกรมเคอร์เนลและพื้นที่ผู้ใช้
มาวิเคราะห์ 2 โปรแกรมที่เราคอมไพล์ไว้ก่อน ขั้นแรกเรารันโปรแกรมเวอร์ชัน "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
คำสั่งนี้ใช้เครื่องมือ perf เพื่อรวบรวมสถิติประสิทธิภาพขณะรันโปรแกรมปฏิบัติการ not_aligned โดยมี 2 เป็นอาร์กิวเมนต์
อาร์กิวเมนต์ 2 ถูกกำหนดไว้เพื่อให้ 2 เธรดที่สร้างขึ้นถูกกำหนดให้กับคอร์ 0 และคอร์ 2 ตามลำดับ (ดูโปรแกรม)
--cpu=0,option ถูกกำหนดไว้เพื่อระบุ CPU ที่จะตรวจสอบสถิติประสิทธิภาพ ในกรณีนี้ CPU 0 และ 2 จะถูกตรวจสอบ -dมอบให้เพื่อรวบรวมข้อมูลเหตุการณ์โดยละเอียดหลายประการ
อย่างที่คุณเห็น โปรแกรม not_aligned นี้ใช้เวลา 660,272 ไมโครวินาที นอกจากนี้ คุณจะเห็นว่ามันทำให้เกิด 19,451,916L1-dcache-load-misses L1-dcache-load-missesระบุความถี่ที่โปรเซสเซอร์ต้องออกนอกแคช L1 เพื่อดึงข้อมูล ซึ่งอาจส่งผลให้เวลาแฝงเพิ่มขึ้นและประสิทธิภาพลดลง ซึ่งคุณสามารถบอกได้โดยดูที่ lineinstructions # 1,31 เป็นการนับคำสั่งสำหรับโปรแกรม และ insn per cycle คือจำนวนคำสั่งเฉลี่ยที่ดำเนินการต่อรอบ ค่า 1,31 หมายความว่าโดยเฉลี่ยแล้ว มีการดำเนินการคำสั่ง 1.31 ต่อรอบ CPU
ตัวชี้วัด stalled-cycles-backend ใน perf stat รายงานเปอร์เซ็นต์ของรอบที่แบ็คเอนด์ของโปรเซสเซอร์ไม่สามารถดำเนินการคำสั่งใดๆ ได้เนื่องจากสาเหตุต่างๆ เช่น ความขัดแย้งของทรัพยากร ไปป์ไลน์หยุดทำงาน หรือความล่าช้าที่เกี่ยวข้องกับหน่วยความจำ เช่น แคชหายไป 79.16% backend cycles idle (61.93%) หมายความว่าในระหว่างการทำงานของโปรแกรม แบ็คเอนด์ของโปรเซสเซอร์ไม่ได้ใช้งานประมาณ 79.16% ของรอบทั้งหมด ด้วยเหตุนี้ ประมาณ 61.93% ของรอบการหยุดทำงานเนื่องจากปัญหาแบ็คเอนด์
ต่อไป มาวิเคราะห์เวอร์ชัน "สอดคล้อง" ของโปรแกรมกัน
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
อย่างที่คุณเห็น มันมีน้อยกว่ามาก L1-dcache-load-misses(น้อยกว่า 99.99%!) ประสิทธิภาพการประมวลผลคือ 3.01 insn per cycle(เพิ่มขึ้น 129.77%)
เวอร์ชันของโปรแกรมที่สอดคล้องจะมีประสิทธิภาพมากกว่า และหลีกเลี่ยงการแชร์ที่ผิดพลาด เนื่องจากจะช่วยลดความขัดแย้งในบรรทัดแคช
ด้วยการจัดตำแหน่งตัวแปรให้เข้ากับขอบเขตของบรรทัดแคช ตัวแปรจะได้รับการรับประกันว่าจะอยู่ในบรรทัดแคชที่แตกต่างกัน ป้องกันการแบ่งปันที่ผิดพลาด และลดจำนวนความขัดแย้งของบรรทัดแคช ซึ่งอาจส่งผลให้ประสิทธิภาพดีขึ้นอย่างเห็นได้ชัด โดยเฉพาะในแอปพลิเคชันแบบมัลติเธรด
สรุป
บทความนี้กล่าวถึงการใช้ร่วมกันที่ผิดพลาดในการเขียนโปรแกรมแบบมัลติเธรด ปัญหาด้านประสิทธิภาพที่อาจเกิดขึ้นเมื่อเธรดตั้งแต่สองตัวขึ้นไปเข้าถึงตัวแปรที่แตกต่างกันซึ่งอยู่บนบรรทัดแคชเดียวกัน
การแชร์ที่ผิดพลาดอาจทำให้แคชใช้งานไม่ได้โดยไม่จำเป็น แคชหายไป และโหลดซ้ำ ส่งผลให้ประสิทธิภาพลดลง
บทความนี้จะอธิบายแนวคิดของบรรทัดแคช ซึ่งเป็นหน่วยข้อมูลที่เล็กที่สุดที่สามารถแคชในแคช CPU ได้ และขนาดของแคชซึ่งจะแตกต่างกันไปขึ้นอยู่กับสถาปัตยกรรมของ CPU
บทความนี้ยังมีโปรแกรม C++ เพื่อสาธิตผลกระทบของการแบ่งปันที่ผิดพลาด และอธิบายวิธีใช้เครื่องมือสร้างโปรไฟล์ perf เพื่อวัดผลกระทบ
บทความนี้สรุปโดยการอภิปรายถึงเทคนิคในการบรรเทาผลกระทบจากการแบ่งปันอันเป็นเท็จ
การเข้ารหัสระดับขึ้น
ขอบคุณที่เป็นส่วนหนึ่งของชุมชนของเรา! ก่อนที่คุณจะไป:
- 👏 ปรบมือให้เรื่องและติดตามผู้เขียน 👉
- 📰 ดูเนื้อหาเพิ่มเติมใน "สิ่งพิมพ์ Level Up Coding"
- 💰 หลักสูตรสัมภาษณ์การเขียนโค้ดฟรี ⇒ ดูหลักสูตร
- 🔔 ติดตามเรา: Twitter | LinkedIn | จดหมายข่าว
🚀 👉 เข้าร่วมกลุ่มผู้มีความสามารถ Level Up และหางานที่น่าทึ่ง
