Многопоточность увеличивает время в С++
Я пытаюсь понять, почему увеличение количества потоков (после определенного числа) увеличивает время процессора, а не уменьшает его.
Краткое изложение того, что делает код: У меня есть основной, который создает большой вектор на основе измерения. Я заполняю его индексами (0..dimension-1), а затем перемешиваю. Затем, чтобы по принципу «разделяй и властвуй», я разделяю этот вектор, предоставляя срез каждому потоку. Я готовлю вектор векторов решений, чтобы отдать каждую запись в потоки. Каждый поток вызывает функцию для каждого элемента своего слайса и передает ссылку на свое подготовленное решение. Эта функция просто изменяет значение решения по заданному индексу на входе, а затем просто увеличивает все элементы в решении (я полагаю, что это немного увеличивает время комп.). Вот код:
#include <algorithm>
#include <random>
#include <thread>
#include <iostream>
#include <chrono>
#include <vector>
#include <numeric>
using namespace std;
template<typename T>
inline double getMs(T start, T end) {
return double(
std::chrono::duration_cast<std::chrono::milliseconds>(end - start)
.count()) /
1000;
}
void fun(const std::vector<int>& slice, int dimension,
vector<int>& internal_sol) {
int size = dimension;
for (auto const& s : slice) {
internal_sol[s] = 45;
internal_sol[int(s/2)] = 45;
if (s != 0) {
internal_sol[s - 1] = 45;
}
if (s != internal_sol.size() - 1) {
internal_sol[s + 1] = 45;
}
for (auto& i_s : internal_sol)
i_s += 1;
}
}
int main(int) {
std::random_device rd;
std::mt19937 g(rd());
unsigned int n = std::thread::hardware_concurrency();
std::cout << n << " concurrent threads are supported.\n";
std::srand(unsigned(std::time(nullptr)));
int number_stops = 50000;
int number_transfers = 3;
int number_structures = 2;
auto dimension = number_stops * (number_transfers + 1) * number_structures;
std::vector<int> v(dimension);
std::iota(std::begin(v), std::end(v), 0);
std::shuffle(std::begin(v), std::end(v), g);
printf("stops:\t%d\ntransfers:\t%d\nstructures:\t%d\n\n", number_stops, number_transfers, number_structures);
for (size_t np = 2; np < 17; np++) {
size_t sz = dimension;
size_t part = sz / np;
auto start = std::chrono::steady_clock::now();
std::cout << np << " threads: ";
std::vector<std::thread> threads(np);
auto start_ext_sol = std::chrono::steady_clock::now();
vector<vector<int>> external_sol; //As TAUs from velociraptor
for (size_t i = 0; i < np; i++) {
external_sol.emplace_back(dimension, -1);
}
double elapsed_ext_sol = getMs(start_ext_sol, std::chrono::steady_clock::now());
auto paraTask = [&](size_t start, size_t end, vector<int>& ext_sol) {
for (size_t l = start; l < end; ++l)
fun({v[l]}, dimension, ext_sol);
for (int i = 0;i < ext_sol.size(); i++)
ext_sol[i] = -1;
};
for (size_t i = 0; i < np; i++) {
size_t start = i * part;
size_t length = (i + 1 == np) ? sz - i * part : part;
threads[i] =
std::thread(paraTask, start, start + length, std::ref(external_sol[i]));
}
// Join the threads
for (auto&& thread : threads) thread.join();
double elapsed = getMs(start, std::chrono::steady_clock::now());
printf("parallel completed: %.3f sec. preparing all vectors ext_sols: %.3f sec\n",
elapsed, elapsed_ext_sol);
}
return 0;
}
Полученный результат:
16 concurrent threads are supported.
stops: 50000
transfers: 3
structures: 2
2 threads: parallel completed: 6.776 sec. preparing all vectors ext_sols: 0.000 sec
3 threads: parallel completed: 5.711 sec. preparing all vectors ext_sols: 0.004 sec
4 threads: parallel completed: 5.285 sec. preparing all vectors ext_sols: 0.003 sec
5 threads: parallel completed: 4.892 sec. preparing all vectors ext_sols: 0.001 sec
6 threads: parallel completed: 4.614 sec. preparing all vectors ext_sols: 0.008 sec
7 threads: parallel completed: 4.726 sec. preparing all vectors ext_sols: 0.001 sec
8 threads: parallel completed: 4.281 sec. preparing all vectors ext_sols: 0.004 sec
9 threads: parallel completed: 4.815 sec. preparing all vectors ext_sols: 0.007 sec
10 threads: parallel completed: 4.791 sec. preparing all vectors ext_sols: 0.008 sec
11 threads: parallel completed: 5.594 sec. preparing all vectors ext_sols: 0.002 sec
12 threads: parallel completed: 5.411 sec. preparing all vectors ext_sols: 0.012 sec
13 threads: parallel completed: 5.213 sec. preparing all vectors ext_sols: 0.010 sec
14 threads: parallel completed: 6.159 sec. preparing all vectors ext_sols: 0.005 sec
15 threads: parallel completed: 8.353 sec. preparing all vectors ext_sols: 0.006 sec
16 threads: parallel completed: 6.769 sec. preparing all vectors ext_sols: 0.012 sec
Как видите, время увеличивается. Я не понимаю, почему это происходит. Размерность здесь составляет 450 000 целых чисел для каждого потока, поэтому около 1,7 МБ (считая 4 байта для каждого целого числа). Таким образом, мы не затрагиваем размер кеша L1, насколько я понимаю. Что происходит?
Вот некоторые подробности о моей машине:
- ЦП — Intel(R) Core(TM) i7-11700KF 11-го поколения с тактовой частотой 3,60 ГГц
- Оперативная память - 16 ГБ DDR4
- Компилятор Windows 11 — MS_VS 2022
А вот отчет об оборудовании памяти от CPU-Z
PS: я также попытался удалить lopp
for (auto& i_s : internal_sol)
i_s += 1
от функции, но тоже самое происходит (конечно с меньшими таймингами)
Этот ЦП имеет базовую частоту 3,60 ГГц для многоядерных нагрузок и повышение до 5,0 ГГц для одноядерных и некоторое промежуточное значение для малоядерных нагрузок. Может быть, это может быть фактором. Вы можете наблюдать за частотой ЦП во время загрузки и/или отключить турбо-ускорение, чтобы увидеть, влияет ли оно на это.
Ваш кэш L1 составляет 80 КБ на ядро.
ок да, я совсем запутался. У меня есть L1 из 80 КБ, L2 из 512 КБ и L3 из 16 МБ, но они разделены между потоками. Поэтому правильно ли говорить, что у меня, вероятно, есть промахи кеша (с большим количеством потоков для L3 слишком много материала), а также проблема с синхронизацией, поскольку уровень L3 является общим?
Я снова предлагаю прочитать о законе Амдала и законе Густавсона. Тенденция, которую вы видите, согласуется с законом Амдалса: при добавлении большего количества потоков вы сначала видите некоторое ускорение, но как только параллельная часть алгоритма уже настолько мала, начинают преобладать накладные расходы, связанные с добавлением большего количества потоков. А закон Густавсона говорит вам, что вы улучшаете использование, увеличивая рабочую нагрузку.
только идеально параллельный алгоритм, и только если создание потоков будет иметь 0 накладных расходов, вы сможете на 100% использовать все доступное оборудование.
в этом случае, где накладные расходы потока?
threads[i] = std::thread(... создание темы не бесплатно. thread.join(); присоединение к треду не бесплатно. Операционная система и язык очень хорошо скрывают от вас некоторые сложности. Накладные расходы невелики, но они увеличиваются по мере того, как вы создаете больше потоков.
Анализ происходящего в этом коде оказался делом далеко не тривиальным. Дикие догадки не сработали. Эмпирическое правило заключается в использовании низкоуровневых профилировщиков для проверки гипотез.
Ответы 2
Ваши наблюдения согласуются с законом Амдала, а также с учетом накладных расходов на использование нескольких потоков.
Грубо говоря и не вдаваясь в подробности, у вас всегда есть какая-то часть вычислений, которая может выиграть от добавления большего количества потоков, назовите это P, какая-то часть, которая не может выиграть от добавления большего количества потоков, назовите это S, и накладные расходы, которые приходятся на каждый поток T .
Больше нитей t убывает P, но не S а увеличивается T:
total time = P/t + S + T*t
Даже если накладные расходы небольшие, в какой-то момент они будут доминировать, потому что добавление большего количества потоков не может сделать P/t меньше, чем 0. В пределе для большого количества потоков вы в конечном итоге увеличиваете время
total time (for huge t) = 0 + S + T*t
Это просто очень простой анализ различных компонентов, влияющих на вашу среду выполнения. Но уже достаточно видеть, что даже для алгоритма, который можно хорошо распараллелить (P > S) и небольших накладных расходов (маленьких T), всегда есть точка, в которой накладные расходы на добавление большего количества потоков будут преобладать.
Амдал не учел накладные расходы, поэтому его общее время (на самом деле он учитывает ускорение, которое равно total time (t=0) / total time) в какой-то момент насыщается. Однако настоящие потоки всегда сопряжены с небольшими накладными расходами. Для дальнейшего исследования, чтобы увидеть, откуда на самом деле берутся накладные расходы, я бы попытался измерить время для данных разного размера. Тогда вы можете увидеть эффекты от cachce.
Для полноты картины я также должен упомянуть Густавсона, который заметил, что параллельная часть P часто увеличивается с размером задачи, а непараллельная часть S — нет. Например, чтение некоторой конфигурации из файла необходимо выполнить один раз, независимо от того, выполняете ли вы 100 или 10000 итераций некоторого алгоритма. С этими предположениями P = p(N) и S = constant можно сделать вывод, что увеличение рабочей нагрузки N улучшает использование оборудования. Вы можете увидеть этот эффект, когда использование меньшего вектора приведет к увеличению времени уже для меньшего количества потоков, а при использовании большего вектора вы можете увидеть увеличение времени только для большего количества потоков.
Я вынужден не согласиться. Я профилировал программу на своей машине и время для создания темы не проблема! Это имеет смысл, так как программа длится несколько секунд, а создание потоков занимает не более нескольких миллисекунд. Проблема возникает из-за доступа к кешу (промах и пробуксовка).
@JérômeRichard, я просто говорю, что есть компонент среды выполнения, который увеличивается с количеством потоков.
@ JérômeRichard хорошо, первое предложение может быть неправильно понято. Я имел в виду все накладные расходы, связанные с созданием большего количества потоков.
Вот более практичное и более точное/конкретное объяснение, почему тайминги увеличиваются с увеличением количества потоков:
- промахи кеша являются основным узким местом масштабируемости, особенно из-за общего кеша L3 и DRAM (также общего между ядрами);
- гиперпоточность мало помогает, поэтому использовать более 8 потоков бесполезно;
- создание потоков определенно не является проблемой (незначительное время).
Ваш процессор i7-11700KF имеет 8 ядер и 2 аппаратных потока на ядро. Таким образом, 8 из 8 ядер могут выполнять поток без особых проблем с масштабируемостью, исходящих от самого оборудования. Использование более 8 потоков приводит к тому, что 2 потока выполняются на одном ядре. Вот почему тайминги уменьшаются до 8 ядер, а затем снова начинают увеличиваться при >=9 потоках. 1 ядро имеет два потока для запуска, в то время как другие, скорее всего, будут выполнять только 1 поток. Обратите внимание, что потоки могут перемещаться с одного ядра на другое (если вы не привязываете их вручную), отсюда и нестабильные тайминги за пределами 8 потоков.
Гиперпоточность (технология Intel, позволяющая ядрам выполнять более 1 потока на ядро) в основном предназначена для повышения эффективности процессора за счет параллельного запуска 2 потоков на одном ядре. Но есть одна загвоздка: аппаратные потоки в основном совместно используют аппаратные ресурсы. Например, кэши L1 и L2 являются общими, поэтому наличие большего количества потоков на одном ядре также означает меньше места на ядро. Это также относится к декодеру инструкций, которому необходимо декодировать инструкцию двух потоков, а не только 1 (в два раза больше инструкций). Вот почему гиперпоточность не делает коды более быстрыми. Фактически, многие коды (немного) медленнее из-за накладных расходов на кеш (например, больше промахов кеша из-за переполнения кеша). Коды, работающие быстрее с гиперпоточностью, обычно связаны с задержкой, особенно те, которые связаны иерархией памяти (например, наивное преобразование матриц). Как говорится, это не всегда верно. Например, блок буфера заполнения строки процессора, ответственный за регистрацию обращений к памяти L2 из-за промахов L1, используется совместно двумя аппаратными потоками, поэтому наличие двух потоков не помогает, если 1 уже может насытить его. Такое бывает в вашем случае. Также нельзя сказать, что коды, выполняющие длинную цепочку зависимых инструкций с высокой задержкой, также могут немного выиграть от гиперпоточности (например, итеративные числовые рецепты с использованием делений FMA), но это не ваш случай. В конце концов, именно поэтому гиперпоточность здесь не поможет.
Тогда вопрос, почему алгоритм не масштабируется даже на 8 ядрах. @ 463035818_is_not_a_number в основном объяснил, почему существует теоретический предел масштабируемости: ожидается, что значительная часть инструкций, выполняемых последовательно, будет узким местом. Однако в целом код выглядит довольно смущающе параллельным, поэтому на самом деле он не помогает. Время создания и объединения потоков (как указано в комментариях) здесь не является проблемой, потому что код выполняется несколько секунд, а время создания потоков не превышает нескольких миллисекунд на большинстве ПК (включая мой).
Дело в том, что ваш алгоритм связан иерархией памяти, а точнее, масштабируемость кода ограничена кешем L3, который используется всеми ядрами. Действительно, есть np векторов, называемых external_sol[i], и каждый из них берет dimension*sizeof(int), который находится в памяти. Таким образом, при 8 потоках используется 12,16 МБ. Каждый вектор не помещается ни в кэш L1, ни в кэш L2 вашего процессора (соответственно 80 КиБ и 512 КиБ на ядро). Векторы выбираются в каждом потоке с использованием случайного целого числа от 0 до размера вектора. Это означает, что извлеченные элементы не могут некоторое время храниться в кеше L1/L2, потому что предыдущие значения будут быстро удалены, чтобы прочитать новые, а 50_000*(3+1)*2*4/1024**2 = 1.52 MiB значения не будут считаны дважды. Одни и те же строки кэша могут быть прочитаны дважды одним и тем же потоком, но данные строки кэша, скорее всего, удаляются задолго до того, как они будут прочитаны снова. Это заставляет потоки загружать строку кэша для каждого значения из кэша L3. Кэш L3 предназначен для масштабирования, но этот код оказывает серьезное давление на L3 (пропускную способность). Есть еще одна большая проблема: слайсы L3 составляют 2 МБ на ядро, а кеш L3 не идеален, поэтому есть некоторые промахи кеша, вызывающие использование DRAM. Это также объясняет, почему ваша программа начинает работать значительно медленнее с гораздо более чем 8 потоками: объем пространства, необходимый для всех векторов, явно слишком велик для L3, и большую часть чтения/сохранения необходимо выполнять непосредственно в DRAM. с гораздо большей задержкой. Например, с 11 потоками вам нужно shuffle, что больше, чем ваш L3, который должен иметь ширину 16 МБ. С 16 потоками это даже 24,32 МБ. И последнее, но не менее важное: существует еще один сложный эффект: при использовании большего количества потоков выполняется меньше обращений к памяти для каждого потока, обращения в большей степени распределяются в памяти, поэтому вероятность повторного использования строк кэша падает по мере роста числа потоков.
Я проанализировал выполнение этого на моем процессоре i5-9600KF с помощью низкоуровневого профилировщика (VTune) и могу подтвердить, что значительная часть обращений выполняется в DRAM с 5 потоками, тогда как с 1 потоком это явно не так. VTune также сообщает, что значительное время тратится на кэш-промахи (в основном L2 на моем процессоре, так как он в два раза меньше вашего).
Обратите внимание, что частота ядра уменьшается по мере увеличения количества активных ядер, чтобы процессор был энергоэффективным (как указано @teapot418). Вот почему ваш процессор (как и многие современные процессоры) не может выполнять алгоритмы в 8 раз быстрее на 8 ядрах (при условии, что целевые алгоритмы эффективны в последовательном режиме).
Идеальный! это был обстоятельный ответ, большое спасибо. Еще немного (но, возможно, потребуется еще один вопрос): возможно ли динамически выбирать максимальное количество потоков в зависимости от оборудования. Например, я получаю размер кеша, физическое ядро, размер того, что я хочу создать, и, таким образом, выбираю оптимальное количество потоков, все внутри c++?
ссылаясь на мой ответ, вы слишком много внимания уделяете «накладным расходам на создание потоков». Это была плохая формулировка с моей стороны, и она уже исправлена. В своем ответе я имею в виду не только накладные расходы на создание потока, но обычно накладные расходы, которые масштабируются линейно с количеством потоков. Да, мой ответ очень сумбурный. Возможно, вы захотите обновить свой ответ, потому что «Меня не убедил принятый ответ ...», и нет необходимости ссылаться на мой, этот ответ может стоять сам по себе.
@ClaudioTomasi Вы можете получить количество аппаратных потоков в C++ с помощью std::thread::hardware_concurrency(). Однако, как правило, это не очень хорошая идея для хорошо оптимизированного кода использовать гиперпоточность. Низкоуровневый API, такой как hwloc, позволяет вам получать интересную информацию, такую как расположение аппаратного ядра, кэши, расстояние между узлами NUMA и т. д. Дело в том, что очень сложно составить общую формулу, чтобы найти наилучшее количество потоков даже для этого. прецедент. Упрощенная формула может быть найдена для основных процессоров данного производителя (например, только основные процессоры Intel, только AMD).
@ClaudioTomasi На практике использование 1 потока на ядро здесь не так уж плохо, поэтому вы можете просто делать это, пока не найдете машину, на которой это явно неоптимально и на которой вам нужно запустить ваше приложение. Это имеет преимущество быть простым.
@ 463035818_is_not_a_number Справедливое замечание. Я удалил первое предложение.
Обратитесь к stackoverflow.com/questions/76007997/…