c - 并行操作执行时间因分配动态内存与静态内存而异

Question

我编写了一个代码，使用 openmp parallel for(对于外部循环)将两个 n × n 矩阵相乘。我在编译时给出了数组大小。我希望将 n 指定为 2000。但是，作为第二个版本，我通过为三个矩阵动态分配空间并给出 n (2000) 的大小作为参数来编写相同的代码。当 n = 2000 时，我得到的两个版本的执行时间相差很大。对于第一个版本(静态分配)，大约需要 13 秒，对于第二个版本(动态分配)，大约需要 32 秒。但对于 n<=1000，两者给出的时间大约相同。我只测量并行乘法运算的时间。那么这两种方法怎么会给出不同的结果呢？ (唯一的变化是内存分配类型)

这是版本 1

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

#define N 1000
double A[N][N], B[N][N], C[N][N]; // declaring matrices of NxN size
int main ()
{
  /* DECLARING VARIABLES */
  int i, j, m; // indices for matrix multiplication
  double t_1; // Execution time measures
  /* FILLING MATRICES WITH RANDOM NUMBERS */
  srand ( time(NULL) );
  for(i=0;i<N;i++) {
    for(j=0;j<N;j++) {
        A[i][j]= (rand()%10);
        B[i][j]= (rand()%10);
    }
  }
  double st=omp_get_wtime();
  for(i=0;i<N;i++)
  {
    for(j=0;j<N;j++)
    {
        for(m=0;m<N;m++)
        {
            C[i][j]+=A[i][m]*B[m][j];
        }
    }
  }
  /* TIME MEASURE + OUTPUT */
  double en=omp_get_wtime();
  printf("Serial: %lf\n",en-st);
}

这是第二个版本

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

int N = 0; // no of columns and rows of a matrix
double **A, **B, **C; // declaring pointers for matrices of NxN size

void getArguments(int argc, char *argv[]);

int main (int argc, char *argv[])
{
/* DECLARING VARIABLES */
int i, j, m; // indices for matrix multiplication
double t_1; // Execution time MEASURES
getArguments(argc,argv);

/* ALLOCATE MEMORY FOR MATRIX A */
A = (double **) malloc( sizeof(double *) * N);
for(i = 0;i < N; i++)
{
    A[i] = (double *) malloc(sizeof(double *) * N);
}

/* ALLOCATE MEMORY FOR MATRIX B */
B = (double **) malloc( sizeof(double *) * N);
for(i = 0;i < N; i++)
{
    B[i] = (double *) malloc(sizeof(double *) * N);
}

/* ALLOCATE MEMORY FOR MATRIX C */
C = (double **) malloc( sizeof(double *) * N);
for(i = 0;i < N; i++)
{
    C[i] = (double *) malloc(sizeof(double *) * N);
}

/* FILLING MATRICES WITH RANDOM NUMBERS */
srand ( time(NULL) );
for(i = 0;i < N;i++) {
    for(j = 0;j < N;j++) {
        A[i][j] = (rand() % 10);
        B[i][j] = (rand() % 10);
    }
}

double st = omp_get_wtime();
#pragma omp parallel for private(m,j)
for(i = 0;i < N;i++) {
    for(j = 0;j < N;j++) {
        C[i][j] = 0.; // set initial value of resulting matrix C = 0
        for(m = 0;m < N;m++) {
            C[i][j] = A[i][m] * B[m][j] + C[i][j];
        }
    }
}

/* TIME MEASURE */
double en = omp_get_wtime();
printf("Parallel: %lf\n",en - st);

/* FREE MEMORY */
for(i = 0;i < N; i++){
    free(A[i]);
}
free(A);
for(i = 0;i < N; i++){
    free(B[i]);
}
free(B);
for(i = 0;i < N; i++){
    free(C[i]);
}
free(C);
}

void getArguments(int argc, char *argv[]){
// Check the N
if (argc != 2) {
    printf("Please give a valid number for N\n");
    exit(0);
}
N = (int) strtol(argv[1], (char **) NULL, 10);
if (N == 0) {
    printf("Please give a number for N more than 0\n");
    exit(0);    
}

}

Answer 1

动态分配存在三个主要区别:

1. 数据不是连续分配的，因为每行都是单独分配的。这会导致内存访问效率降低，例如由于缓存、预取器。
2. 每个元素访问都是通过行指针间接访问的。这比仅通过两个索引计算内存位置的效率要低。
3. N 在编译时不再已知，因此编译器必须为 N 上的循环生成更通用的代码。