c - 使用 OpenCL 合并两个排序数组

Question

我有一些用于合并两个排序数组的 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 内核，最好的方法是什么？或者用 OpenCL 合并两个排序数组的最佳方法是什么？

Answer 1

如果数组的长度是 2 的幂，则可以使用双调排序。只需从最后的蝴蝶步骤(维基链接中蓝色/棕色图表的最后一个块)开始，您就会使 GPU 饱和，同时充分利用设备的内存速度。如果阵列接近 2 的幂，您也可以填充它们。我已经使用这种方法成功地对数百万(例如 2^20 .. 2^24)条目的列表进行了排序。
见:'Bitonic Sorter' Wiki

如果每个数组中有任意数量的元素，则在处理两个已排序的列表时可能不值得花费时间。这是因为您一次只比较两个值，并将其中一个移动到结果列表中。这是对 gpu 的一个可怕的使用，因为你基本上是单线程的。优化可能是将每个源数组中的前 4-8kb 加载到本地内存中，然后将排序后的块也写入本地内存。您仍然只会使用整个 gpu 的一个计算单元，但内存速度会很棒。同样，可能不值得麻烦。在合并任意长度的排序数组时，您的 cpu L1 和 L2 数据缓存和卓越的时钟速度应该优于 gpu。