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

4

2 回答 2

3

如果你的数组长度是 2 的幂次方，你可以使用双调排序。只需从最后的蝴蝶步骤（wiki 链接中蓝色/棕色图表的最后一个块）开始，您将在充分利用设备内存速度的同时使 gpu 饱和。如果阵列接近 2 的幂，您也可以填充阵列。我已经使用这种方法成功地对数百万个（例如 2^20 .. 2^24）条目的列表进行了排序。参见：“双音分拣机”维基

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

于 2013-05-14T03:20:30.847 回答
0

最简单的方法是创建三个缓冲区 A、B 和 C，然后调用两个 clEnqueueCopyBuffer()，如下所示：

clEnqueueCopyBuffer( cmdQueue, A, C, 0, 0, m, 0, NULL, NULL );
clEnqueueCopyBuffer( cmdQueue, B, C, 0, m, n, 0, NULL, NULL );

如果你想要一个简单的内核来做这件事，下面的方法会起作用：

__kernel void merge(int m, __global const int* A, __global const int* B, _global int* C )
{
    int id= (int)get_global_id(0);
    if( id<m )
    {
        C[id]=A[id];
    }
    else
    {
        C[id]=B[id-m];
    }
}

这个内核绝不是优化的。有很多方法可以根据设备进行优化。

于 2013-05-14T00:08:23.427 回答