В современных компьютерных системах параллельная обработка является распространенным методом, используемым для повышения производительности. Однако есть несколько проблем на пути к эффективному параллелизму, одна из которых — ложное совместное использование.
Ложное совместное использование происходит, когда потоки, работающие на разных ядрах процессора, обращаются к разным переменным, которые используют одну и ту же строку кэша. Это может привести к ненужной аннулированию кеша, промахам кеша и последующей перезагрузке из памяти, что приведет к снижению производительности.
В этой статье мы рассмотрим ложный обмен и его влияние на производительность на простых примерах кода. Мы также будем использовать инструмент профилирования производительности, чтобы измерить последствия ложного обмена и обсудить методы смягчения его воздействия.
Вы можете получить доступ к коду, использованному в этой статье, здесь.
Линия кэша
Во-первых, чтобы понять ложное совместное использование, нам нужно знать о «кэш-строке». Строка кэша — это наименьшая единица данных, которая может быть кэширована в кэше процессора компьютера. Он представляет собой блок непрерывной памяти фиксированного размера, который загружается из основной памяти в кэш, когда ЦП запрашивает данные. Размер строки кэша зависит от конкретной архитектуры процессора и может составлять от 32 до 512 байт.
Когда ЦП запрашивает данные из памяти, он извлекает всю строку кэша, содержащую запрошенные данные, а также дополнительные смежные данные. Это делается для того, чтобы воспользоваться преимуществом пространственной локальности, т. е. доступа к данным в непосредственной близости от других данных. Кэшируя целые строки кэша, ЦП может уменьшить количество промахов кэша и перезагрузок строк кэша, что может значительно повысить производительность.
Хотя строка кэша существует для повышения производительности, она также может привести к проблемам с производительностью, таким как ложное совместное использование.
Ложное совместное использование происходит в многопоточных приложениях, когда два или более потока обращаются к разным переменным, расположенным в одной и той же строке кэша. Когда один поток обновляет переменную, вся строка кэша становится недействительной, что заставляет другие потоки перезагружать строку кэша из памяти. Это приводит к промахам кеша и перезагрузке, что может значительно замедлить работу программы.
Вы можете проверить размер строки кэша вашей системы, выполнив команду ниже в консоли
cat /sys/devices/system/cpu/cpu0/cache/index0/coherency_line_size 64
Эта команда выводит размер строки кэша кэша данных L1 для первого ядра ЦП (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 версии программы.
Первый исполняемый файл использует данные, которые выровнены по 64 байтам (таким образом, размер строки кэша).
Второй не выровнен по строке системного кеша.
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 программы, которые мы скомпилировали ранее. Во-первых, мы выполняем «не выровненную» версию программы.
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 0 и 2. -dдан для сбора нескольких подробных сведений о событии.
Как видите, эта программа not_aligned занимает 660 272 микросекунды. Кроме того, вы можете видеть, что это вызвало 19 451 916L1-dcache-load-misses. L1-dcache-load-missesуказывает, как часто процессор должен выходить за пределы кеша L1 для извлечения данных, что может привести к увеличению задержки и снижению производительности, что вы можете определить, взглянув на строкуinstructions # 1,31 . Это количество инструкций для программы, а insn per cycle — среднее количество инструкций, выполняемых за цикл. Значение 1,31 означает, что в среднем за цикл ЦП выполнялась 1,31 инструкция.
Метрика 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% больше).
Выровненная версия программы более эффективна и позволяет избежать ложного совместного использования, поскольку уменьшает конфликты строк кэша.
Выравнивание переменных по границам строк кэша гарантирует, что переменные будут расположены в разных строках кэша, что предотвратит ложное совместное использование и уменьшит количество конфликтов строк кэша. Это может привести к значительному повышению производительности, особенно в многопоточных приложениях.
Краткое содержание
В этой статье обсуждается ложное совместное использование в многопоточном программировании, проблема производительности, которая может возникнуть, когда два или более потока обращаются к разным переменным, расположенным в одной и той же строке кэша.
Ложное совместное использование может привести к ненужной аннулированию кеша, промахам кеша и перезагрузке, что приведет к снижению производительности.
В статье объясняется концепция строки кэша, которая является наименьшей единицей данных, которая может быть кэширована в кэше ЦП, и ее размер, который зависит от архитектуры ЦП.
В статье также представлена программа на C++ для демонстрации эффекта ложного совместного использования и объясняется, как использовать инструмент профилирования производительности для измерения его влияния.
Статья завершается обсуждением методов смягчения последствий ложного обмена.
Повышение уровня кодирования
Спасибо, что являетесь частью нашего сообщества! Перед тем, как ты уйдешь:
- 👏 Хлопайте за историю и подписывайтесь на автора 👉
- 📰 Смотрите больше контента в публикации Level Up Coding
- 💰 Бесплатный курс собеседования по программированию ⇒ Просмотреть курс
- 🔔 Подписывайтесь на нас: Twitter | ЛинкедИн | "Новостная рассылка"
🚀👉 Присоединяйтесь к коллективу талантов Level Up и найдите прекрасную работу
