OpenMP 没有减少运行时间，即使多个线程正在运行ning。怎么会这样

Question

我正在尝试对更大的矩阵（1000x1000 到 5000x5000 双精度）进行乘法运算。我必须使用 OpenMP 来并行化乘法。并行 for 循环由 p 个线程处理，我猜它们是根据打印出来的 omp_get_thread_num() 正确安排的。我运行宁在 4 核心 CPU 上，并已确认最大线程数为 4。如果有任何区别，CPU 是虚拟的。问题是当我改变线程的 nb 时运行时间不会减少。

lscpu results

我检查过 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;
}

Answer 1

您使用不正确的算法以 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]按行遍历。每八次迭代将只有两次未命中，而不是每次迭代一次未命中，内存带宽将不再是限制因素。您的计算时间将大大减少，并且会随着使用的内核数量的增加而扩展。

Time taken (N=2000, p=1): 4.62s
Time taken (N=2000, p=2): 3.03s
Time taken (N=2000, p=4): 2.34s

ikj 不是唯一的方法。您还可以使用块矩阵乘法，其中乘法由 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;
        }
        }

  }

该算法稍长一些，但由于它避免了缓存未命中，它也是核心有限的，可以通过并行化来改进。

Time taken (N=2000, p=1): 7.22s
Time taken (N=2000, p=2): 3.78s
Time taken (N=2000, p=4): 3.08s

但是，如果您在内存受限问题上使用 open-MP，您将永远不会有任何收获。

OpenMP 没有减少运行时间，即使多个线程正在运行ning。怎么会这样

OpenMP is not reducing run time even though multiple threads are running. How can this be

c

parallel-processing

openmp

OpenMP 没有减少 运行 时间，即使多个线程正在 运行ning。怎么会这样

OpenMP is not reducing run time even though multiple threads are running. How can this be

c

parallel-processing

openmp

OpenMP 没有减少运行时间，即使多个线程正在运行ning。怎么会这样