Распараллеливание истинных зависимостей - PullRequest
Новая
       32

Распараллеливание истинных зависимостей

0 голосов
/ 23 февраля 2020

стоит ли распараллеливать истинные циклы зависимостей? Какие могут быть плюсы и минусы? Какое ускорение мы можем получить в среднем?

Например: 

    int sum = 0;
    for(i=0;i<2000-1;i++){
            for(j=0;j<2000;j++) {
                curr[i][j] = some_value_here;
                sum += curr[i][j];
            }
    }

Как мне подойти к этому l oop? есть очевидная зависимость RAW, я должен распараллелить это? Если так, как я должен?

1 Ответ

2 голосов
/ 23 февраля 2020

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

int sum = 0;
#pragma omp parallel for collapse(2) reduction(+:sum)
for(i=0;i<2000-1;i++){
        for(j=0;j<2000;j++) {
            curr[i][j] = some_value_here;
            sum += curr[i][j];
        }
}

reduction(+:sum) говорит компилятору создать частные копии sum, а затем применить оператор +, чтобы уменьшить эти частные копии до одиночное значение, которое затем добавляется к значению sum, имеющемуся перед регионом. Код примерно эквивалентен: 

int sum = 0;
#pragma omp parallel
{
   int localsum = 0;
   #pragma omp for collapse(2)
   for(i=0;i<2000-1;i++) {
      for(j=0;j<2000;j++) {
         curr[i][j] = some_value_here;
         localsum += curr[i][j];
      }
   }
   #pragma omp atomic
   sum += localsum;
}

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

...