如何用递归扫描算法实现并行化

我实现了一个递归扫描(前缀和)算法，我在下面包含了它。这里，我简单地生成大小为2到27次幂的随机列表，通过简单的顺序扫描来检查准确性。它的工作原理。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <math.h>
#include <mkl.h>
int *pscan(int *x, int n, int z, int chunk_size);
int reduce(int *x, int n);
int main(int argc, char **argv)
{
  int n;
  int i, j, k;
  int *x, *seq, *r;
  double begin, end;
  srand48(time(0));
  /* Randomly generate array of size n. */
  for (k = 2; k < 28; k++) {
    n = (int) pow(2, k);
    seq = (int *) malloc(sizeof(int) * n);
    x = (int *) malloc(sizeof(int) * n);
    for (i = 0; i < n; i++) {
      x[i] = lrand48() % 100 - 50;
      seq[i] = x[i];
    }
    /* Parallel scan. */
    begin = dsecnd();
    r = pscan(x, n, 0, 2);
    end = dsecnd();
    printf("%d %lfn", n, end - begin);
    /* Sequential check. */
    for (i = 1; i < n; i++) {
      seq[i] = seq[i - 1] + seq[i];
    }
    for (i = 0; i < n; i++) {
      if (r[i] != seq[i]) {
        fprintf(stderr, "AGGGHHH!!! ERROR.  Found with vector: n");
        for (j = 0; j < n; j++) {
          printf("%d ", x[i]);
        }
        printf("n");
        exit(1);
      }
    }
    free(r);
    free(x);
    free(seq);
  }
  return 0;
}
/* Perform parallel scan. */
int *pscan(int *x, int n, int z, int chunk_size)
{
  int i, j;
  int *sums, *sumscan, *scan, **fsum, *rv;
  /* Base case, serially scan a chunk. */
  if (n <= chunk_size) {
    scan = (int *) malloc(sizeof(int) * n);
    scan[0] = x[0] + z;
    for (i = 1; i < n; i++) {
      scan[i] = x[i] + scan[i - 1];
    }
    return scan;
  }
  sums = (int *) malloc(sizeof(int) * (n / chunk_size));
  /* Reduce each chunk of the array. */
  for (i = 0; i < n / chunk_size; i++) {
    sums[i] = reduce(&x[i * chunk_size], chunk_size);
  }
  /* Perform a scan on the sums. */
  sumscan = pscan(sums, n / chunk_size, 0, chunk_size);
  free(sums);
  fsum = (int **) malloc(sizeof(int *) * (n / chunk_size));
  /* Perform a recursive scan on each chunk, using
     the appropriate offset from the sums scan. */
  for (i = 0; i < n / chunk_size; i++) {
    if (i > 0) {
      fsum[i] = pscan(&x[i * chunk_size], chunk_size, sumscan[i - 1], chunk_size);
    } else {
      fsum[i] = pscan(&x[i * chunk_size], chunk_size, 0, chunk_size);
    }
  }
  free(sumscan);
  rv = (int *) malloc(sizeof(int) * n);
  /* Join the arrays. */
  for (i = 0; i < n / chunk_size; i++) {
    for (j = 0; j < chunk_size; j++) {
      rv[i * chunk_size + j] = fsum[i][j];
    }
  }
  for (i = 0; i < n / chunk_size; i++) {
    free(fsum[i]);
  }
  free(fsum);
  return rv;
}
/* Serial reduction. */
int reduce(int *x, int n)
{
  int i;
  int sum;
  sum = 0;
  for (i = 0; i < n; i++) {
    sum += x[i];
  }
  return sum;
}

现在，我想并行化它。因为我觉得自己有点潮，所以我编写了一个Cilk实现。我只是替换了两个主要的for循环来并行化1)减少和2)每个块的递归扫描，使用块减少的适当扫描作为偏移量。看起来是这样。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <math.h>
#include <cilk/cilk.h>
#include <mkl.h>
int *pscan(int *x, int n, int z, int chunk_size);
int reduce(int *x, int n);
int main(int argc, char **argv)
{
  int n;
  int i, j, k;
  int *x, *seq, *r;
  double begin, end;
  srand48(time(0));
  /* Randomly generate array of size n. */
  for (k = 2; k < 28; k++) {
    n = (int) pow(2, k);
    seq = (int *) malloc(sizeof(int) * n);
    x = (int *) malloc(sizeof(int) * n);
    for (i = 0; i < n; i++) {
      x[i] = lrand48() % 100 - 50;
      seq[i] = x[i];
    }
    /* Parallel scan. */
    begin = dsecnd();
    r = pscan(x, n, 0, 2);
    end = dsecnd();
    printf("%d %lfn", n, end - begin);
    /* Sequential check. */
    for (i = 1; i < n; i++) {
      seq[i] = seq[i - 1] + seq[i];
    }
    for (i = 0; i < n; i++) {
      if (r[i] != seq[i]) {
        fprintf(stderr, "AGGGHHH!!! ERROR.  Found with vector: n");
        for (j = 0; j < n; j++) {
          printf("%d ", x[i]);
        }
        printf("n");
        exit(1);
      }
    }
    free(r);
    free(x);
    free(seq);
  }
  return 0;
}
/* Perform parallel scan. */
int *pscan(int *x, int n, int z, int chunk_size)
{
  int i, j;
  int *sums, *sumscan, *scan, **fsum, *rv;
  /* Base case, serially scan a chunk. */
  if (n <= chunk_size) {
    scan = (int *) malloc(sizeof(int) * n);
    scan[0] = x[0] + z;
    for (i = 1; i < n; i++) {
      scan[i] = x[i] + scan[i - 1];
    }
    return scan;
  }
  sums = (int *) malloc(sizeof(int) * (n / chunk_size));
  /* Reduce each chunk of the array. */
  cilk_for (i = 0; i < n / chunk_size; i++) {
    sums[i] = reduce(&x[i * chunk_size], chunk_size);
  }
  /* Perform a scan on the sums. */
  sumscan = pscan(sums, n / chunk_size, 0, chunk_size);
  free(sums);
  fsum = (int **) malloc(sizeof(int *) * (n / chunk_size));
  /* Perform a recursive scan on each chunk, using
     the appropriate offset from the sums scan. */
  cilk_for (i = 0; i < n / chunk_size; i++) {
    if (i > 0) {
      fsum[i] = pscan(&x[i * chunk_size], chunk_size, sumscan[i - 1], chunk_size);
    } else {
      fsum[i] = pscan(&x[i * chunk_size], chunk_size, 0, chunk_size);
    }
  }
  free(sumscan);
  rv = (int *) malloc(sizeof(int) * n);
  /* Join the arrays. */
  for (i = 0; i < n / chunk_size; i++) {
    for (j = 0; j < chunk_size; j++) {
      rv[i * chunk_size + j] = fsum[i][j];
    }
  }
  for (i = 0; i < n / chunk_size; i++) {
    free(fsum[i]);
  }
  free(fsum);
  return rv;
}
/* Serial reduction. */
int reduce(int *x, int n)
{
  int i;
  int sum;
  sum = 0;
  for (i = 0; i < n; i++) {
    sum += x[i];
  }
  return sum;
}

它有效!它返回正确的结果。它没有达到我所希望的效果。原表演为

4 0.000004
8 0.000001
16 0.000002
32 0.000003
64 0.000005
128 0.000011
256 0.000019
512 0.000035
1024 0.000068
2048 0.000130
4096 0.000257
8192 0.000512
16384 0.001129
32768 0.002262
65536 0.004519
131072 0.009065
262144 0.018297
524288 0.037416
1048576 0.078307
2097152 0.157448
4194304 0.313855
8388608 0.625689
16777216 1.251949
33554432 2.589439
67108864 5.084731
134217728 10.402186

适用于单线程应用程序，但Cilk版本的性能更差，使用以下运行时

4 0.005383
8 0.000011
16 0.000009
32 0.000111
64 0.000055
128 0.000579
256 0.000339
512 0.000544
1024 0.000701
2048 0.001086
4096 0.001265
8192 0.001742
16384 0.002283
32768 0.003891
65536 0.005398
131072 0.009255
262144 0.020736
524288 0.058156
1048576 0.103893
2097152 0.215460
4194304 0.419988
8388608 0.749368
16777216 1.650938
33554432 2.960451
67108864 5.799836
134217728 11.294398

我有一台24核的机器，所以我们显然没有看到我们希望在这里看到的加速。我的第一个想法是Cilk错误地处理了递归，导致了超额认购，但Cilk确实应该很好地处理递归。关于如何正确地实现这一点，有什么建议吗?我尝试将cilk_for添加到底部的for循环(释放所有内容)和倒数第二组循环的内部for循环(加入数组)，但这会进一步降低性能。

任何建议都是非常感谢的。

但是，请不要告诉我切换到这里讨论的Belloch并行扫描算法。我已经在《Cilk》中实现了这一点，并且效果非常好。

我想看看是否可以用这个递归解决方案来匹配它的性能。

我通过为每个问题找到最佳块大小来解决性能问题。在该块大小下，(相同的)并行版本比顺序版本执行得更好。

总的来说，我的一般方法有一些问题，特别是两个的块大小:

我的基准方法。在带有调优参数的代码中，使用相同的调优参数值来绘制运行时与问题大小的关系没有多大意义，因为最佳值取决于问题大小。
块大小为2可能是有问题的，因为虽然它最大化了并行性，但它也最大化了递归级别的数量，同样，它也带来了开销。
块大小为2可以防止矢量化。
正如Leeor所建议的，块大小为2也可能导致缓存中的错误共享。

感谢Leeor为我指引了正确的方向。

相关内容

最新更新

热门标签：