用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的安德魯庫克在這裏。從你的第一次嘗試中，我現在更好地理解了這個問題，並且看到有樣本取決於特徵的選擇是在那裏殺了你。

是樣品的由特徵完全隨機選擇，也可以利用在該規律性（訂購特徵，使得那些使用相同的樣品一起處理）？這是顯而易見的，所以我想這是不可能的。

不幸的是，我不明白你的第二次嘗試。