2

2 つの並べ替えられた配列をマージするための C コードがあります。

void merge(int m, int n, int A[], int B[], int C[]) {
  int i, j, k;
  i = 0;
  j = 0;
  k = 0;
  while (i < m && j < n) {
        if (A[i] <= B[j]) {
              C[k] = A[i];
              i++;
        } else {
              C[k] = B[j];
              j++;
        }
        k++;
  }
  if (i < m) {
        for (int p = i; p < m; p++) {
              C[k] = A[p];
              k++;
        }
  } else {
        for (int p = j; p < n; p++) {
              C[k] = B[p];
              k++;
        }
  }
}

マージ部分を OpenCL カーネルに配置したいのですが、これを行う最善の方法は何ですか? または、ソートされた 2 つの配列を OpenCL でマージする最良の方法は何ですか?

4

2 に答える 2

3

配列の長さが同じ 2 の累乗である場合は、バイトニック ソートを使用できます。最後のバタフライ ステップ (Wiki リンクの青/茶色の図の最後のブロック) から開始するだけで、デバイスのメモリ速度を最大限に活用しながら GPU を飽和状態にできます。配列が 2 の累乗に近い場合は、配列をパディングすることもできます。このメソッドを使用して、数百万 (たとえば 2^20 .. 2^24) のエントリのリストを正常に並べ替えました。参照: 「Bitonic Sorter」ウィキ

各配列に任意の数の要素がある場合、既にソートされている 2 つのリストを扱っている場合、転送時間の価値がない可能性があります。これは、一度に 2 つの値のみを比較し、そのうちの 1 つを結果リストに移動するためです。基本的にシングルスレッドであるため、これは GPU のひどい使い方です。最適化は、各ソース配列から最初の 4 ～ 8kb をローカル メモリにロードし、次に並べ替えられたブロックをローカル メモリにも書き込むことです。GPU 全体の計算ユニットを 1 つしか使用しませんが、メモリ速度は優れています。繰り返しますが、おそらく苦労する価値はありません。CPU の L1 および L2 データ キャッシュと優れたクロック速度は、任意の長さの並べ替えられた配列をマージするときに GPU を上回るはずです。

于 2013-05-14T03:20:30.847 に答える