Повторяющиеся короткие идентичные параллельные работы
У меня есть алгоритм, который требует множества параллельных повторов одного и того же кода. Код короткий и завершается менее чем за микросекунду. Это будет выполняться миллионы раз, что создает некоторые проблемы при использовании потоков. Я пытаюсь использовать потоки POSIX, но, поскольку накладные расходы на создание новых потоков невозможны, мне нужно вместо этого использовать какой-то вращающийся рабочий поток, который работает постоянно.
Ниже приведен упрощенный случай, иллюстрирующий, как я пытаюсь выполнить две одинаково длинные работы: Calc_x и Calc_y. Мне нужно иметь возможность запускать их параллельно, чтобы общее время, затраченное на выполнение только одного (или очень близкого к этому).
#include <pthread.h>
#include <time.h>
#include <stdatomic.h>
#include <stdio.h>
static int nloops = 100;
static int x;
static int y;
static pthread_t tid;
static atomic_bool trun;
static atomic_bool texit;
static int cnt = 0;
static const int MILLION = 1000000;
void calc_x() {
x = 0;
for (int i = 0; i < nloops; ++i) {
x += i;
}
}
void calc_y() {
y = 0;
for (int i = 0; i < nloops; ++i) {
y += i;
}
}
void *worker() {
while (1) {
if (trun) {
calc_x();
trun = false;
}
if (texit) {
break;
}
}
return NULL;
}
float run_x() {
struct timespec start, end;
clock_gettime(CLOCK_MONOTONIC, &start);
for (int i = 0; i < MILLION; ++i) {
calc_x();
}
clock_gettime(CLOCK_MONOTONIC, &end);
return (end.tv_sec - start.tv_sec) + (end.tv_nsec - start.tv_nsec)*0.000000001;
}
float run_y() {
struct timespec start, end;
clock_gettime(CLOCK_MONOTONIC, &start);
for (int i = 0; i < MILLION; ++i) {
calc_y();
}
clock_gettime(CLOCK_MONOTONIC, &end);
return (end.tv_sec - start.tv_sec) + (end.tv_nsec - start.tv_nsec)*0.000000001;
}
float run_xy() {
struct timespec start, end;
clock_gettime(CLOCK_MONOTONIC, &start);
for (int i = 0; i < MILLION; ++i) {
calc_x();
calc_y();
}
clock_gettime(CLOCK_MONOTONIC, &end);
return (end.tv_sec - start.tv_sec) + (end.tv_nsec - start.tv_nsec)*0.000000001;
}
float run_xy_parallel() {
struct timespec start, end;
clock_gettime(CLOCK_MONOTONIC, &start);
for (int i = 0; i < MILLION; ++i) {
trun = true;
calc_y();
while(trun) ++cnt;
}
clock_gettime(CLOCK_MONOTONIC, &end);
return (end.tv_sec - start.tv_sec) + (end.tv_nsec - start.tv_nsec)*0.000000001;
}
int main() {
trun = false;
texit = false;
pthread_create(&tid, NULL, &worker, NULL);
printf("run_x: %.4f s\n", run_x());
printf("run_y: %.4f s\n", run_y());
printf("run_xy: %.4f s\n", run_xy());
printf("run_xy_parallel: %.4f s\n", run_xy_parallel());
printf("average nr of waiting loops: %.1f\n", (float)cnt/MILLION);
texit = true;
pthread_join(tid, NULL);
return 0;
}
Результаты:
run_x: 0.3049 s
run_y: 0.2559 s
run_xy: 0.5074 s
run_xy_parallel: 0.4744 s
average nr of waiting loops: 34.9
Как видите, пользы от использования параллельного воркера практически нет. Счетчик (cnt), который я использую, чтобы попытаться измерить, сколько времени затрачивается на ожидание, предполагает, что 35/nloops = 35% времени Calc_x тратится на ожидание завершения другого потока, что кажется правильным, поскольку существует разница во времени между run_x и run_y. Поэтому я изменил nloops на 1000, чтобы посмотреть, изменилось ли что-нибудь. Я получил следующие результаты:
run_x: 2.4921 s
run_y: 2.4965 s
run_xy: 5.0950 s
run_xy_parallel: 3.3477 s
average nr of waiting loops: 44.8
Теперь количество ожиданий составляет менее 5% от Calc_x. Но все равно это на 1/3 медленнее, чем я ожидал.
Мне кажется, что установка trun занимает много времени, но не имеет смысла, что это время увеличивается с увеличением nloops. Может ли кто-нибудь объяснить мне это?
Вы также пробовали использовать openmp? Он использует пул потоков, который ограничивает количество создаваемых потоков.
Спасибо за помощь. Я читал об этом, и это, кажется, имеет смысл, поскольку с увеличением nloops накладные расходы увеличиваются. Поэтому я добавил отступы разных размеров между x и y, но, к сожалению, безрезультатно. Я еще не пробовал openmp. Думаю, мне нужен ответ на этот вопрос, прежде чем я смогу перейти к другим альтернативам.
Поскольку ваши потоки совместно используют данные, их планирование на разных процессорах, скорее всего, снизит производительность.
@stark, как так? Я не понимаю, почему
Прости, @CarlHR, но я не понимаю твоей логики. Честно говоря, я не думаю, что вы понимаете код. В run_xy_parallel Calc_x вызывается, когда рабочий цикл достигает значения trun, значение которого изменено на true. Нет ничего, что гарантировало бы, что Calc_x запустится раньше Calc_y или наоборот.
@CarlHR, нет, это не то, что происходит. Я знаю, что здесь делаю, с логикой у меня все в порядке, проблема не в этом. Проблема в том, что происходит за капотом. Как упомянул АхмедАЕК, это может быть связано с ложным распространением информации. Я до сих пор не знаю. Но я совершенно уверен, что Calc_x и Calc_y по крайней мере перекрываются.
Я не уверен, почему ваши потоки вращаются, ожидая завершения другого потока. Почему вы не можете позволить потокам завершить работу, когда они завершат свою работу, или использовать что-то вроде семафора для ожидания?
1. Вам действительно следует включить оптимизацию всего, что связано с профилированием и бенчмаркингом. Здесь тайминги имеют тенденцию указывать на то, что оптимизация отключена. Если вы включите -O2 или -O3, и Clang, и GCC оптимизируют ваши циклы (так что тест будет смещен). 2. Выравнивание действительно помогает, хотя одного этого недостаточно, чтобы сделать параллельную версию значительно быстрее на моей машине. 3. Межъядерная связь имеет значительную задержку по нескольким причинам. 4. глобальные переменные вообще плохие (особенно непостоянные). Они имеют тенденцию увеличивать условия гонки, проблемы с разделением ложных/истинных данных.
5. Вам следует убедиться, что масштабирование частоты и миграция потоков не являются проблемой. Серверы часто имеют более высокую межъядерную задержку, поэтому 1 мкс — довольно жесткий предел для такой машины. 6. Некоторые включения явно отсутствуют в вашем коде C (например, stdbool.h и time.h, не говоря уже о том, что некоторые функции кажутся нестандартными и требуют определения GNU/POSIX).
7. Использование атомарной переменной может отрицательно сказаться на производительности. В целом, спин-блокировки в некоторых случаях имеют тенденцию быть быстрее, но также намного опаснее, а иногда и медленнее, чем блокировки, но для ограничения в 1 мкс они кажутся подходящими, если использовать их с особой осторожностью (переключение контекста обычно обходится дороже). ). Возможно, вам тоже следует использовать ОС реального времени.
8. Имейте в виду, что 1 мкс обычно считается слишком малым для того, чтобы многопоточность могла быть полезна на нескольких ядрах (хотя на самом деле это зависит от целевой машины). Возможно, вам следует разместить два потока на одном ядре и получить выгоду от SMT. Это должно значительно сократить задержку атомарности (и, в более общем плане, обмена данными). Однако каждый поток будет медленнее, чем на двух ядрах. Обратите внимание, что в этом случае удары по спин-блокировке, безусловно, сильно снизят производительность, поэтому вам следует сначала это исправить.
Ответы 2
Не знаю, почему ваш вопрос так сильно отвергается. Мне пришлось провести такой анализ производительности, и это одновременно сложно и необходимо для определенных типов приложений (например, финансовых услуг).
Моя лучшая догадка — прикрепить потоки к ядрам. Большинство серверов приличного размера имеют несколько сокетов ЦП, поэтому вам следует настроить процесс так, чтобы он работал на ядрах, ограниченных одной зоной NUMA. Даже если ваш сервер имеет только один сокет ЦП, Linux любит переносить потоки между ядрами, что препятствует оптимальному использованию кэша. В идеале вы должны явно привязать потоки к ядрам, выбранным как можно ближе с точки зрения кэша. Я обнаружил, что даже в системе с одним процессором выбор ядер для подключения оказывает значительное влияние на производительность. Пробуйте разные, пока не найдете пару, которая обеспечит наилучшие результаты.
Я думаю, что «ложное разделение» было хорошей догадкой. Все процессоры X86 имеют 64-байтовые строки кэша, поэтому вам обязательно следует добавить массив символов (64-sizeof(int)) между каждым из глобальных переменных (или, по крайней мере, «горячими»). На самом деле, я не уверен, что C гарантирует, что глобальные переменные будут упакованы предсказуемым образом, поэтому вы можете поместить их в структуру.
И ваша идея увеличить число циклов была хорошей. Синхронизировать потоки после 100 циклов недостаточно.
Большая часть моей работы была связана с производительностью сети с использованием драйверов обхода ядра, таких как Onload. Конфигурация оборудования играет свою роль, пытаясь убедиться, что все обращения к памяти, включая сетевой адаптер, являются локальными. Прерывания также играют роль, крадя циклы у процессора, который вы пытаетесь монополизировать. Существует множество хаков, которые можно использовать, чтобы изолировать ядра от планировщика Linux и обработки прерываний, хотя это может оказаться настоящей кроличьей норой. Вот несколько ссылок, сделанных несколько лет назад, когда я провел кучу исследований:
- https://www.kernel.org/doc/Documentation/kernel-per-CPU-kthreads.txt
- https://jeremyeder.com/2013/11/15/nohz_fullgodmode/
- https://www.codethink.co.uk/articles/2018/configuring-linux-to-stabilise-latency/
- https://www.brendangregg.com/linuxperf.html
- https://engineering.linkedin.com/ Performance/optimizing-linux-memory-management-low-latency-high-throughput-databases
Вот еще один замечательный ресурс, где можно увидеть последствия различных подходов к кодированию: https://godbolt.org/
Спасибо. Читая об этом больше, я понимаю, какую большую роль здесь играет локальность памяти. Ваше объяснение помогло мне найти нужные мне ответы. Теперь я попытался подключиться к разным ядрам, и результаты сильно различаются. Очевидно, есть много вещей, которые следует учитывать, если кто-то сделает эту работу. Возможно, можно собрать или настроить компьютер специально для этого случая. мне придется об этом подумать..
Я только что добавил список ссылок в конец ответа для вашего удовольствия от чтения поздно вечером.
Большое спасибо! Я вчитываюсь в это. Очень интересно посмотреть, сколько на самом деле можно контролировать. Я попробую немного настроить, осознавая при этом ограничения.
Я провел кое-какое расследование. Пробовал менять МИЛЛИОН - не помогло. Потом я прочитал о ложном совместном использовании и попробовал работать с локальными копиями x и y. новый код Calc_x, Calc_y:
void calc_x() {
int xloc = 0;
for (int i = 0; i < nloops; ++i) {
xloc += i;
}
x = xloc;
}
void calc_y() {
y = 0;
int yloc = 0;
for (int i = 0; i < nloops; ++i) {
yloc += i;
}
y = yloc;
}
И проблема полностью исчезла! Вот времена:
# non local version (MILLION is 10000 nloops = 100000)
run_x: 6.1838 s
run_y: 6.1812 s
run_xy: 12.3375 s
run_xy_parallel: 7.8648 s
average nr of waiting loops: 2741.4
# static version with x and y divided by buf[100]
static int x;
static int buf[100];
static int y;
... Result times: ...
run_x: 1.8734 s
run_y: 1.8513 s
run_xy: 3.7081 s
run_xy_parallel: 1.8359 s
average nr of waiting loops: 143.8
# MILLION is 10000 nloops = 100000
run_x: 1.7826 s
run_y: 1.7460 s
run_xy: 3.5052 s
run_xy_parallel: 1.7342 s
average nr of waiting loops: 242.5
# MILLION is 100000 nloops = 10000
run_x: 1.7939 s
run_y: 1.7632 s
run_xy: 3.5415 s
run_xy_parallel: 1.7667 s
average nr of waiting loops: 52.2
программа ускорилась примерно в 5 раз (может локальную переменную можно легко перенести в регистр???), а параллельная версия работает ровно в 2 раза быстрее, как и должно быть. Почти такое же ускорение и эффективность параллельного выполнения были достигнуты за счет размещения 400-байтового буфера между x и y, чтобы их можно было кэшировать независимо. Возможно, в вашей версии статические x и y рядом друг с другом действительно мешают кэшированию, как писали здесь некоторые люди. И вообще, чтобы получить выгоду от параллельных вычислений, вам следует сделать программы как можно более независимыми.
Что мне нравится в этом ответе, так это предложение заставить «работу» вычислений происходить с местными жителями, что, как показывает Мишагам, значительно ускоряет их. Помимо прочего, это позволяет оптимизатору выполнять свою работу. Затем в конце локальной работы просто передайте результаты. Эта модель часто используется при параллельной обработке. К вашему сведению @mishagam: использование статических глобальных переменных не предотвращает кеширование, но не позволяет оптимизатору создавать эффективный код.
Это звучит великолепно. Я проверил себя, но не смог получить тех же результатов, независимо от значения nloops. Кроме того, результаты различаются в зависимости от прогона. Я думаю, что происходит много вещей, хотя я считаю, что это может быть частью решения.
Ответ на @SreveFord Я попробовал версию со статическими x и y, разделенными буфером в 400 байт - и она дала почти такое же ускорение, я указал время в ответе - так что основная проблема, по-видимому, заключалась в нарушении кеширования.
@mishagam - Интересно. Я попытаюсь воспроизвести ваши результаты и поиграть с ними. Если я найду что-нибудь интересное, я опубликую здесь и свяжусь с вами.