用opencl解决经典的map-reduce问题？

Question

我试图用OpenCL来并行处理经典的map-reduce问题（它可以与MPI很好地并行），即AMD实现。但结果困扰我。

让我简短的有关该问题的第一位。有两种类型的数据流入系统：特征集（每个30个参数）和样本集（每个9000个维度）。从某种意义上说，这是一个经典的地图缩减问题，我需要计算每个样本（地图）上每个要素的得分。然后，总结每个功能的总体评分（Reduce）。有大约10k功能和30k样本。

我尝试不同的方法来解决这个问题。首先，我试图通过功能分解问题。问题在于分数计算由随机存储器访问组成（选择9000多个维度中的一些并进行加/减计算）。由于我无法合并内存访问，因此需要花费。然后，我尝试用样本分解问题。问题是总结总分，所有线索都争夺少量分数变数。它一直覆盖原来不正确的分数。 （我不能先进行个人得分，因为它需要10k * 30k * 4字节）。

我尝试的第一个方法，让我有8个线程的i7上的CPU 860相同的性能。但是，我认为这个问题不可解决：它与射线追踪问题非常相似（为此，您计算的是数百万条射线对数百万个三角形的计算）。有任何想法吗？

另外，我张贴一些代码，我有：

分解的功能（工程，但慢）：

__kernel void __ccv_cl_pos_error_rate(__global unsigned int* err_rate, 
__constant int* feature, __constant int* data, int num, __constant 
unsigned int* w, int s, int isiz0, int isiz01, int step0, int step1) 
{ 
    int igrid = get_global_id(0); 
    __constant int* of = feature + igrid * 30; 
    unsigned int e = 0; 
    int k, i; 
    int step[] = { step0, step1 }; 
    for (k = 0; k < num; k++) 
    { 
     __constant int* kd = data + k * isiz01; 
     int pmin = kd[of[0] * isiz0 + of[1] + of[2] * step[of[0]]]; 
     int nmax = kd[of[3] * isiz0 + of[4] + of[5] * step[of[3]]]; 
     for (i = 0; i < 5; i++) 
     { 
      if (of[i * 6] >= 0) 
       pmin = min(pmin, kd[of[i * 6] * isiz0 + of[i * 6 + 1] + of[i * 6 + 2] * step[of[i * 6]]]); 
      if (of[i * 6 + 3] >= 0) 
       nmax = max(nmax, kd[of[i * 6 + 3] * isiz0 + of[i * 6 + 4] + of[i * 6 + 5] * step[of[i * 6 + 3]]]); 
     } 
     if (pmin <= nmax) 
      e += w[s + k]; 
    } 
    err_rate[igrid] += e; 
}

分解的样品，不工作：

__kernel void __ccv_cl_pos_error_rate(__global unsigned int* err_rate, 
__constant int* feature, __constant int* data, int num, __constant 
unsigned int* w, int s, int isiz0, int isiz01, int step0, int step1, 
__local int* shared) 
{ 
    int igrid = get_global_id(0); 
    int lsize = get_local_size(0); 
    int lid = get_local_id(0); 
    unsigned int e = 0; 
    int k, i; 
    int ws = w[s + igrid]; 
    int step[] = { step0, step1 }; 
    for (k = 0; k < isiz01; k += lsize) 
     if (k + lid < isiz01) 
      shared[k + lid] = data[igrid * isiz01 + k + lid]; 
    barrier(....); 
    for (k = 0; k < num; k++) 
    { 
     __constant int* of = feature + k * 30; 
     int pmin = shared[of[0] * isiz0 + of[1] + of[2] * step[of[0]]]; 
     int nmax = shared[of[3] * isiz0 + of[4] + of[5] * step[of[3]]]; 
     for (i = 0; i < 5; i++) 
     { 
      if (of[i * 6] >= 0) 
       pmin = min(pmin, shared[of[i * 6] * isiz0 + of[i * 6 + 1] + of[i * 6 + 2] * step[of[i * 6]]]); 
      if (of[i * 6 + 3] >= 0) 
       nmax = max(nmax, shared[of[i * 6 + 3] * isiz0 + of[i * 6 + 4] + of[i * 6 + 5] * step[of[i * 6 + 3]]]); 
     } 
     if (pmin <= nmax) 
      err_rate[k] += ws; // here is wrong. 
    } 
    barrier(....); 
} 

Answer 1

来自hn的安德鲁库克在这里。从你的第一次尝试中，我现在更好地理解了这个问题，并且看到有样本取决于特征的选择是在那里杀了你。

是样品的由特征完全随机选择，也可以利用在该规律性（订购特征，使得那些使用相同的样品一起处理）？这是显而易见的，所以我想这是不可能的。

不幸的是，我不明白你的第二次尝试。