OpenMP распараллеливание умножения матриц на тройку для цикла (проблема производительности) - PullRequest
Новая
       29

OpenMP распараллеливание умножения матриц на тройку для цикла (проблема производительности)

7 голосов
/ 18 января 2011

Я пишу программу для умножения матриц с OpenMP, которая для удобства кэша реализует умножение A x B (транспонирование) строк X строк вместо классических A x B строк x столбцов, для лучшей эффективности кэширования. Делая это, я столкнулся с интересным фактом, который для меня нелогичен: если в этом коде я распараллеливаю внешний цикл, программа работает медленнее, чем если бы я поместил директивы OpenMP в самый внутренний цикл, на моем компьютере время составляет 10,9 против 8,1 секунды. 

//A and B are double* allocated with malloc, Nu is the lenght of the matrixes 
//which are square

//#pragma omp parallel for
for (i=0; i<Nu; i++){
  for (j=0; j<Nu; j++){
    *(C+(i*Nu+j)) = 0.;
#pragma omp parallel for
    for(k=0;k<Nu ;k++){
      *(C+(i*Nu+j))+=*(A+(i*Nu+k)) * *(B+(j*Nu+k));//C(i,j)=sum(over k) A(i,k)*B(k,j)
    }
  }
}

Ответы [ 2 ]

4 голосов
/ 18 января 2011

Попробуйте достичь результата реже. Это вызывает совместное использование кэширования и предотвращает параллельное выполнение операции. Вместо этого, использование локальной переменной позволит большинству записей происходить в кэш-памяти L1 каждого ядра.

Также может помочь использование restrict. В противном случае компилятор не может гарантировать, что запись в C не меняется A и B.

Попробуйте: 

for (i=0; i<Nu; i++){
  const double* const Arow = A + i*Nu;
  double* const Crow = C + i*Nu;
#pragma omp parallel for
  for (j=0; j<Nu; j++){
    const double* const Bcol = B + j*Nu;
    double sum = 0.0;
    for(k=0;k<Nu ;k++){
      sum += Arow[k] * Bcol[k]; //C(i,j)=sum(over k) A(i,k)*B(k,j)
    }
    Crow[j] = sum;
  }
}

Кроме того, я думаю, что Элалфер прав в необходимости сокращения, если вы распараллелите самый внутренний цикл.

4 голосов
/ 18 января 2011

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

Скорее всего, он решает, что различные итерации внешнего цикла могут записываться втот же (C+(i*Nu+j)) и добавляет блокировки доступа для его защиты.

Компилятор, вероятно, может выяснить, что нет никаких зависимостей, если вы распараллелите 2-й цикл.Но выяснить, что параллелизации внешнего цикла нет зависимостей, не так тривиально для компилятора.

ОБНОВЛЕНИЕ

Некоторые измерения производительности.

Hiснова.Похоже, 1000 double * и + недостаточно для покрытия затрат на синхронизацию потоков.

Я провел несколько небольших тестов, и простое векторное скалярное умножение не работает с openmp, если только числоэлементов меньше ~ 10'000.По сути, чем больше ваш массив, тем больше вы получите производительности от использования openmp.

Таким образом, распараллеливая самый внутренний цикл, вам придется разделить задачу между различными потоками и собрать данные обратно 1000 000 раз.

PS.Попробуйте Intel ICC, это бесплатно для студентов и проектов с открытым исходным кодом.Я помню, как использовал openmp для меньших, чем 10 000 массивов элементов.

ОБНОВЛЕНИЕ 2: Пример сокращения 

    double sum = 0.0;
    int k=0;
    double *al = A+i*Nu;
    double *bl = A+j*Nu;
    #pragma omp parallel for shared(al, bl) reduction(+:sum)
    for(k=0;k<Nu ;k++){
        sum +=al[k] * bl[k]; //C(i,j)=sum(over k) A(i,k)*B(k,j)
    }
    C[i*Nu+j] = sum;
...