2

再帰スキャン (プレフィックス サム) アルゴリズムを実装しました。これを以下に示します。ここでは、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 %lf\n", 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 の実装をハックしました。チャンク削減の適切なスキャンをオフセットとして使用して、1) リダクションと 2) 各チャンクの再帰スキャンを並列化するために、2 つの主要な for ループを置き換えるだけです。そのように見えます。

#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 %lf\n", 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 は特に再帰をうまく処理するはずです。これを適切に実装する方法に関するヒントはありますか? 一番下の for ループ (すべてを解放) と最後から 2 番目のループ セットの内側の for ループ (配列に結合) に cilk_for を追加しようとしましたが、パフォーマンスがさらに低下しました。

どんなアドバイスでも大歓迎です。

ただし、ここで説明する Belloch の並列スキャン アルゴリズムに切り替えるように言わないでください。私はすでに Cilk でそれを実装しており、非常にうまく機能しました。そのパフォーマンスをこの再帰的なソリューションと一致させることができるかどうかを確認したいと思います。

4

1 に答える 1

0

各問題の最適なチャンク サイズを見つけることで、パフォーマンスの問題を修正しました。そのチャンク サイズでは、(同じ) 並列バージョンは順次バージョンよりも優れたパフォーマンスを発揮します。

要約すると、私の一般的なアプローチと、特に 2 のチャンク サイズの両方にいくつか問題がありました。

  1. 私のベンチマークアプローチ。チューニング パラメーターを含むコードでは、最適な値は問題のサイズに依存するため、チューニング パラメーターに同じ値を使用してランタイムと問題のサイズをプロットしても意味がありません。
  2. 2 のチャンク サイズは、並列処理を最大化する一方で、再帰のレベル数とそれに伴うオーバーヘッドも最大化するため、おそらく問題がありました。
  3. チャンク サイズを 2 にすると、ベクトル化が妨げられます。
  4. Leeor が示唆したように、チャンク サイズが 2 の場合も、キャッシュで誤った共有が発生する可能性があります。

私を正しい方向に導いてくれたLeeorに感謝します。

于 2014-05-28T13:45:19.787 に答える