Низкая производительность многоядерных вычислений в Linux (openMP, boost :: thread и т. Д.)

Я хочу использовать многоядерные вычисления в своих приложениях. Я начинаю развиваться пример приложения с openMP (C ++).

При запуске я обнаружил, что мои многоядерные вычисления не быстрее последовательных (даже многоядерные вычисления медленнее, чем последовательные вычисления в некоторых случаях):

./ openmp_test

Последовательный. Сумма: 1.77544e + 08 время: 21.84

Редукция, 2 темы. Сумма: 1.77544e + 08 время: 21.65

Два раздела. Сумма: 1.77544e + 08 время: 60.65

Моей следующей мыслью было создать boost :: thread application для тестирования двух потоков на ядрах процессора. Результаты:

./ boost_thread_test

Последовательный. Сумма: 1.42146e + 09, время: 179.64

Две форсированные темы. Сумма: 1,42146e + 09, время: 493,34

Я использую ноутбук openSuSe (x64) с процессором Core i3 внутри.

Почему у меня такая плохая производительность многопоточности?

1

Решение

Оба ваших кода, один на основе OpenMP sections и тот, основанный на boost::threadявляются вероятными жертвами ложный обмен. Ложное совместное использование происходит, потому что временные загрузки и хранилища работают на целых строках кэша, а не непосредственно на их операндах. Например, следующее утверждение:

sum = sum + value;

приводит не только к значению sum читается из памяти, обновляется и затем записывается обратно, а точнее — целый небольшой раздел памяти, известный как строка кэша быть прочитанным и затем написанным назад. Строка кэша на современных процессорах x86 обычно имеет порядок 64 байта, что означает, что не только значение sum будет загружен из / сохранен в памяти, но также и 56 байтов вокруг него. Строки кэша также всегда начинаются с адресов, кратных 64. Каковы последствия для вашего кода?

В коде разделов OpenMP у вас есть:

double sum1;
double sum2;

...
// one section operates on sum1
...
// one section operates on sum2
...

sum1 а также sum2 расположены в стеке родительской функции omp_sections (примечание — omp_ префикс зарезервирован для функций в библиотеке времени выполнения OpenMP; не используйте это, чтобы назвать свои собственные функции!). Быть двойником, sum1 а также sum2 выровнены по 8-байтовой границе и в общей сложности занимают 16 байтов. Вероятность того, что они оба попадут в одну и ту же строку кэша, составляет 7/8 или 87,5%. Что происходит, когда первый поток хочет обновить sum1 является следующим:

  • Он читает строку кэша, которая содержит sum1
  • Это обновляет значение sum1
  • Он уведомляет все другие ядра о том, что содержимое строки кэша изменилось, поэтому они должны аннулировать его в своих кэшах.

Последняя часть очень важна — это часть того, что известно как согласованность кэша. поскольку sum1 а также sum2 вероятно, попадут в одну и ту же строку кэша, ядро, которое выполняет поток секунд, должно аннулировать свой кэш и перезагрузить его с более низкого уровня иерархии памяти (например, из общего кэша последнего уровня или из основной памяти). Точно так же происходит, когда второй поток изменяет значение sum2,

Одним из возможных решений является использование reduction пункт, как в случае, когда вы используете директиву OpenMP Worksharing for:

double sum;

#pragma omp parallel sections reduction(+:sum) num_threads(2)
{
...
}

Другое возможное решение — вставить некоторые отступы между двумя значениями, чтобы разделить их на несколько строк кэша:

double sum1;
char pad[64];
double sum2;

Я не знаю, дает ли стандарт C ++ какую-либо гарантию того, как локальные переменные должны быть размещены в стеке, т. Е. Не может быть гарантии, что компилятор не «оптимизирует» размещение переменных и не переупорядочит их как sum1, sum2, pad, Если это так, они могут быть размещены в структуре.

Проблема, по сути, та же самая, что и в вашем случае Члены данных класса принимают:

double *a;   // 4 bytes on x86, 8 bytes on x64
int niter;   // 4 bytes
int start;   // 4 bytes
int end;     // 4 bytes
// 4 bytes padding on x64 because doubles must be aligned
double sum;  // 8 bytes

Члены данных класса занимают 24 байта в x86 и 32 байта в x64 (x86 в 64-битном режиме). Это означает, что два экземпляра класса могут помещаться в одну строку кэша или могут совместно использовать один. Опять же, вы можете добавить элемент данных заполнения после sum размером не менее 32 байт:

class Calc
{
private:
double *a;
int niter;
int start;
int end;
double sum;
char pad[32];
...
};

Обратите внимание, что private переменные, включая неявные частные копии, созданные reduction предложение, скорее всего, находится в стеке отдельных потоков и, следовательно, находится на расстоянии более чем одной строки кэша, следовательно, ложное совместное использование не происходит и код выполняется быстрее параллельно.

Изменить: я забыл упомянуть, что большинство компиляторов удаляют неиспользуемые переменные на этапе оптимизации. В случае с разделами OpenMP заполнение в основном оптимизировано. Это может быть исправлено путем применения атрибутов выравнивания (предупреждение: возможно, специфично для GCC):

double sum1 __attribute__((aligned(64))) = 0;
double sum2 __attribute__((aligned(64))) = 0;

Хотя это удаляет ложное совместное использование, оно по-прежнему не позволяет большинству компиляторов использовать оптимизацию регистра, поскольку sum1 а также sum2 являются общими переменными. Следовательно, он все равно будет медленнее, чем версия, которая использует сокращение. В моей тестовой системе выравнивание обеих переменных на границе строки кэша сокращает время выполнения с 56 до 30 секунд, учитывая время последовательного выполнения 20 секунд. Это только показывает, что иногда конструкции OpenMP портят некоторые оптимизации компилятора, и параллельный код может работать намного медленнее, чем последовательный, поэтому нужно быть осторожным.

Вы можете сделать обе переменные lastprivate и это позволило бы компилятору выполнить оптимизацию регистра для них:

#pragma omp parallel sections num_threads(2) lastprivate(sum1,sum2)

В этой модификации код разделов выполняется так же быстро, как и код с директивой worksharing. Другое возможное решение — накапливать локальные переменные и присваивать sum1 а также sum2 после окончания цикла:

#pragma omp section
{
double s = 0;
for (int i = 0; i < niter / 2; i++)
{
for (int j = 0; j < niter; j++)
{
for (int k = 0; k < niter; k++)
{
double x = sin(a[i]) * cos(a[j]) * sin(a[k]);
s += x;
}
}
}
sum1 = s;
}
// Same for the other section

Этот по сути эквивалентен threadprivate(sum1),

К сожалению у меня нет boost установлен, поэтому я не могу проверить ваш многопоточный код. Попробуйте выполнить весь расчет, используя Calc::run() чтобы увидеть, какое значение имеет использование класса C ++ для скорости.

3

Другие решения

Слишком долго, чтобы поместить это как комментарий

Есть что-то очень странное с реализацией sin а также cos,

(Редактировать: конечно, это не имеет ничего общего с sin а также cos, но с паттерном доступа к массиву a).

(Редактировать 2: а также множество избыточных sin а также cos звонки исключены. В функции single_threadкомпилятор перемещает вызовы инварианта цикла в sin а также cos вне петель, но не перемещает их в Calc::run метод. Так что это объясняет разницу в производительности. Пора открыть вопрос, почему компилятор делает разные вещи 🙂 )

Сравните программу со следующим изменением и без него.

В то время как однопоточная версия выполняется в течение примерно того же времени (около 12 секунд), исходная многопоточная версия выполняется в течение приблизительно 18 секунд (т.е. медленнее, чем однопоточная версия), но измененная многопоточная версия выполняется в течение приблизительно 7 секунд. сек (niter == 1000).

--- thread-smp-orig.cxx        2012-12-10 12:40:03.547640307 +0200
+++ thread-smp.cxx        2012-12-10 12:37:27.990650712 +0200
@@ -26,11 +26,13 @@ public:
double x;
for (int i = start; i < end; i++)
{
+            double sai = sin(a[i]);
for (int j = 0; j < niter; j++)
{
+                double caj = cos(a[j]);
for (int k = 0; k < niter; k++)
{
-                    x = sin(a[i]) * cos(a[j]) * sin(a[k]);
+                    x = sai * caj * sin(a[k]);
sum += x;
}
}
@@ -48,11 +50,13 @@ double single_thread(double a[], const i
double x;
for (int i = 0; i < niter; i++)
{
+        double sai = sin(a[i]);
for (int j = 0; j < niter; j++)
{
+            double caj = cos(a[j]);
for (int k = 0; k < niter; k++)
{
-                x = sin(a[i]) * cos(a[j]) * sin(a[k]);
+                x = sai * caj * sin(a[k]);
sum += x;
}
}
0

По вопросам рекламы [email protected]