查找cuda中n個點之間的最小距離

-1

我正在嘗試查找cuda中n個點之間的最小距離。我寫了下面的代碼。對於從1到1024的點數，即1個塊，這是工作正常的。但是，如果num_points大於1024，我將得到最小距離的錯誤值。我正在使用蠻力算法檢查我在CPU中找到的值，以檢查GPU最小值。最小值存儲在內核函數末尾的temp1 [0]中。查找cuda中n個點之間的最小距離

我不知道這是什麼問題。請幫助我..

#include <stdio.h> 
#include <stdlib.h> 
#include <math.h> 
#include <sys/time.h> 
#define MAX_POINTS 50000 

__global__ void minimum_distance(float * X, float * Y, float * D, int n) { 

__shared__ float temp[1024]; 
float temp1[1024]; 
int tid = threadIdx.x; 
int bid = blockIdx.x; 
int ref = tid+bid*blockDim.x; 
temp[ref] = 1E+37F; 
temp1[bid] = 1E+37F; 
float dx,dy; 
float Dij; 
int i; 

      //each thread will take a point and find min dist to all 
      // points greater than its unique id(ref) 
    for (i = ref + 1; i < n; i++) 
    { 
     dx = X[ref]-X[i]; 
     dy = Y[ref]-Y[i]; 
     Dij = sqrtf(dx*dx+dy*dy); 
     if (temp[tid] > Dij) 
     { 
     temp[tid] = Dij; 
     } 
    } 

    __syncthreads(); 

      //In each block the min value is stored in temp[0] 
    if(tid == 0) 
    { 
     if(bid == (n-1)/1024) { 
     int end = n - (bid) * 1024; 
     for (i = 1; i < end; i++) 
     { 
      if (temp[i] < temp[tid]) 
      temp[tid] = temp[i]; 
     } 
     temp1[bid] = temp[tid]; 
     } 
     else { 
     for (i = 1; i < 1024; i++) 
     { 
      if (temp[i] < temp[tid]) 
      temp[tid] = temp[i]; 
     } 
     temp1[bid] = temp[tid]; 
     } 
    } 

__syncthreads(); 

    //Here the min value is stored in temp1[0] 
if (ref == 0) 
{ 
    for (i = 1; i <= (n-1)/1024; i++) 
     if(temp1[bid] > temp1[i]) 
      temp1[bid] = temp1[i]; 

    *D=temp1[bid]; 
} 
} 

//part of Main function 
//kernel function invocation 
// Invoking kernel of 1D grid and block sizes 
// Vx and Vy are arrays of x-coordinates and y-coordinates respectively 

int main(int argc, char* argv[]) { 
. 
. 
blocks = (num_points-1)/1024 + 1; 
minimum_distance<<<blocks,1024>>>(Vx,Vy,dmin_dist,num_points); 
. 
.

來源

2013-11-24 user3027732

我沒有檢查過你的代碼的一致性，我沒有試圖回答你的問題。就像一個評論一樣，使用兩個內核是否更高效，更不容易出錯？使用兩個內核可以直接實現並計算點之間所有可能的距離，並執行簡化操作（可以使用其中一種算法在CUDA樣本中提供或使用推力庫）如此獲得的距離矩陣？ – JackOLantern

-1

我想說的是你選擇的算法有什麼問題。你當然可以比O（n^2）做得更好 - 即使你的是非常簡單的。當然，在5000點看起來可能並不可怕，但嘗試50,000點，你會感到痛苦...

我想想平行建設一個Voronoi Diagram，或者某種BSP類似結構這可能更容易用較少的代碼分歧進行查詢。

來源

2013-11-24 23:19:33 einpoklum

現在我只是試圖並行化程序，而不是擔心複雜性。上面的代碼給我錯誤的值超過1塊。你能說這個實現有什麼問題嗎？ – user3027732

我不認爲這回答了海報的調試問題。 – JackOLantern

查找cuda中n個點之間的最小距離

回答

相關問題