Как оптимально распараллелить вложенные циклы?

Question

Я пишу программу, которая должна запускаться как в серийных, так и в параллельных версиях. Как только я получу его, чтобы сделать то, что он должен делать, я начал пытаться распараллелить его с помощью OpenMP (обязательный).

Дело в том, что я не могу найти документацию или ссылки о том, когда следует использовать #pragma. Поэтому я стараюсь изо всех сил угадывать и тестировать. Но тестирование не подходит для вложенных циклов.

Как бы вы распараллеливание серии вложенных циклов, как эти:

for(int i = 0; i < 3; ++i){ 
    for(int j = 0; j < HEIGHT; ++j){ 
     for(int k = 0; k < WIDTH; ++k){ 
      switch(i){ 
       case 0: 
         matrix[j][k].a = matrix[j][k] * someValue1; 
         break; 
       case 1: 
         matrix[j][k].b = matrix[j][k] * someValue2; 
         break; 
       case 2: 
         matrix[j][k].c = matrix[j][k] * someValue3;     
         break; 
      } 
     } 
    } 
} 

• высота и ширина, как правило, тот же размер в тестах, которые я должен выполнить. Некоторые примеры тестов - 32x32 и 4096x4096.
• матрица представляет собой массив пользовательских структур с признаками а, б и в
• SomeValue является двойной

Я знаю, что OpenMP не всегда хорошо для вложенных циклов, но любая помощь приветствуется.

[UPDATE]:

До сих пор я пытался разворачивая петли. Это повышает производительность, но могу ли я добавить лишние накладные расходы здесь? Я повторно использую темы? Я попытался получить идентификатор потоков, используемых в каждом, но не понял.

#pragma omp parallel 
     { 
#pragma omp for collapse(2) 
      for (int j = 0; j < HEIGHT; ++j) { 
       for (int k = 0; k < WIDTH; ++k) { 
        //my previous code here 
       } 
      } 
#pragma omp for collapse(2) 
      for (int j = 0; j < HEIGHT; ++j) { 
       for (int k = 0; k < WIDTH; ++k) { 
        //my previous code here 
       } 
      } 
#pragma omp for collapse(2) 
      for (int j = 0; j < HEIGHT; ++j) { 
       for (int k = 0; k < WIDTH; ++k) { 
        //my previous code here 
       } 
      } 
     } 

[ОБНОВЛЕНИЕ 2]

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

• Серийные: ~ 130 мс
• Loop разворачивая: ~ 49 мс
• Сворачивание две сокровенные петли: ~ 55 мс
• Параллельный внешний цикл: ~ ​​83 мс

Что вас Думаете, самый безопасный вариант? Я имею в виду, что должно быть в целом лучшим для большинства систем, а не только для моего компьютера?

Answer 1

Вы, вероятно, хотите, чтобы распараллелить этот пример for simd поэтому компилятор может векторизации, collapse петли, потому что вы используете j и k только в выражении matrix[j][k], а потому нет никаких зависимостей от любого другого элемента матрицы. Если ничего не изменяет somevalue1 и т. Д., Они должны быть uniform. Поставьте время, чтобы убедиться, что они действительно улучшают вашу скорость.

Answer 2

Проблема с OpenMP заключается в том, что это очень высокоуровневый, что означает, что вы не можете получить доступ к низкоуровневым функциям, таким как размножение потока, а затем повторное использование.Итак, позвольте мне сделать это ясно, что вы можете и что вы не можете сделать:

Предполагая, что вы не нужны никакие семафор для защиты от race conditions, вот ваши варианты:

1. Вы распараллеливать внешнее -Большая цикл, и который будет использовать 3 потока, и это самое мирное решение ты собираешься иметь

2. вы параллелизации первый внутренний цикл с, и тогда вы будете иметь прирост производительности только если накладные расходы размножения новой нити для каждого элемента WIDTH намного меньше ef Форты, необходимые для выполнения самой внутренней петли.

3. Распараллеливание самой внутренней петли, но это худшее решение в мире, потому что вы будете обновлять потоки 3 * HEIGHT раз. Никогда не делай этого!

4. Не использовать OpenMP и использовать что-то низкоуровневое, например std::thread, где вы можете создать свой собственный пул потоков и нажать все операции, которые вы хотите сделать в очереди.

Надеюсь, что это поможет уложить вещи в перспективе.

Answer 3

Вот еще один вариант, один, который признает, что распределение итераций внешней петли, когда есть только 3 из них может привести к очень плохой балансировке нагрузки,

i=0 
#pragma omp parallel for 
for(int j = 0; j < HEIGHT; ++j){ 
    for(int k = 0; k < WIDTH; ++k){ 
    ... 
} 

i=1 
#pragma omp parallel for 
for(int j = 0; j < HEIGHT; ++j){ 
    for(int k = 0; k < WIDTH; ++k){ 
    ... 
} 

i=2 
#pragma omp parallel for 
for(int j = 0; j < HEIGHT; ++j){ 
    for(int k = 0; k < WIDTH; ++k){ 
    ... 
} 

Предупреждения - проверить синтаксис самостоятельно, это это не более чем эскиз ручного разворота петли.

Попробуйте объединить это и свернуть j и k петли.

О, и не жалуйтесь на дублирование кода, вы сказали, что отчасти выигрываете от повышения производительности.