OpenMP не сокращает время выполнения, даже если запущено несколько потоков. Как это может быть - PullRequest
Новая
       6

OpenMP не сокращает время выполнения, даже если запущено несколько потоков. Как это может быть

1 голос
/ 11 мая 2019

Я пытаюсь сделать умножение на более крупные матрицы (от 1000x1000 до 5000x5000 с двойной точностью). Я должен использовать OpenMP для распараллеливания умножения. Параллельный цикл for обрабатывается p числом потоков, и они рассчитаны правильно, я думаю, основываясь на распечатке omp_get_thread_num (). Я работаю на 4-ядерном процессоре и подтвердил, что максимальное количество потоков равно 4. Процессоры являются виртуальными, если это имеет значение. Проблема в том, что время выполнения не уменьшается при изменении nb потоков.

lscpu результаты

  • Я проверил, что библиотека libgomp установлена ​​ldconfig -p | grep -i "gomp".

  • Я попытался изменить место параллельного цикла на один из вложенных циклов.

  • Я попытался изменить расписание и размер куска. 

#include <stdio.h>
#include <stdlib.h>
#include <omp.h>
#include <time.h>

double** createMatrix(int N)
{
  double** rndMatrix;
  srand48((long int)time(NULL));
  rndMatrix = malloc(sizeof(double*)*N);
  int n,m;

  for(n=0; n<N; n++){
      rndMatrix[n] = malloc(sizeof(double*)*N);
      for (m=0;m<N;m++){
          rndMatrix[n][m] = drand48();
      }
  }
  return rndMatrix;
}

void problem1(double** a, double** b, int N, int p){
    int i,k,j;
  int g;
  double** c;
  c = malloc(sizeof(double*)*N);

  for(g=0; g<N; ++g)
      c[g] = malloc(sizeof(double*)*N);

  //Timer start
  clock_t tStart = clock();
  //time_t tStart, tEnd;
  //tStart =time(NULL);

  //Parallelised part
#pragma omp parallel shared(a,b,c,N) private(i,k,j) num_threads(p)
  {
#pragma omp for schedule(static) nowait
      for(i=0; i<N; ++i){
          for(j=0; j<N; ++j){
                  double sum = 0;
                  for(k=0; k<N; ++k){
                      sum += a[i][k] * b[k][j];
                  }
                  c[i][j]=sum;
          }
      }
  }

  //Timer end
  printf("Time taken: %.2fs\n", (double)(clock() - tStart)/CLOCKS_PER_SEC);
  //tEnd = time(NULL);
  //printf("Time taken: %ds\n",  tEnd - tStart);
}


int main(void)
{
  int p=0;
  int N=0;
  //User input:

  printf("Enter matrix dimension:\n");
  scanf("%d", &N);

  printf("Please enter nb of threads:\n");
  scanf("%d", &p);

  double **a;
  double **b;

  a = createMatrix(N);
  sleep(2);
  b = createMatrix(N);

  problem1(a,b,N,p);

  return 0;
}

1 Ответ

0 голосов
/ 14 мая 2019

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

for(i=0; i<N; ++i){
      for(j=0; j<N; ++j){
           double sum = 0;
           for(k=0; k<N; ++k){
                sum += a[i][k] * b[k][j];
           }
           c[i][j]=sum;
       }
}

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

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

Open-MP полезен, только если у вас есть проблемы с ядром, а не для вычислений, связанных с памятью.

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

    for(i=0; i<N; ++i){
      for(k=0; k<N; ++k){
        double r = a[i][k];
        for(j=0; j<N; ++j){
          c[i][j] += r * b[k][j];
        }
      }
    }

Когда внутренний индекс (j) увеличивается, c [i] [j] и b [i] [j] перемещаются в ряд. Вместо одного промаха за итерацию у вас будет только два промаха через каждые восемь итераций, и пропускная способность памяти больше не будет ограничивающим фактором. Ваше время вычислений будет значительно сокращено и будет зависеть от количества используемых ядер.

Времени (N = 2000, р = 1): 4,62 с
Времени (N = 2000, р = 2): 3,03 с
Времени (N = 2000, р = 4): 2,34 с

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

#define BL 40
  for (int jj=0;jj<N;jj+=BL)
    for (int kk=0;kk<N;kk+=BL)
      for (i=0;i<N;i++)
        {
          for (j=jj;j<min(jj+BL-1,N);j++)
        {
          double sum=0.0;
          for (k=kk;k<min(kk+BL-1,N);k++)
            sum += a[i][k]*b[k][j];
          c[i][j]=sum;
        }
        }

  }

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

Время, необходимое (N = 2000, p = 1): 7,22
Требуемое время (N = 2000, р = 2): 3,78 с
Требуемое время (N = 2000, p = 4): 3,08 с

Но вы никогда ничего не получите, если будете использовать open-MP для проблемы с памятью.

...