查找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个点之间的最小距离

回答

相关问题