쿠다에서 n 점 사이의 최소 거리 찾기

Question

쿠다에서 n 점 사이의 최소 거리를 찾으려고합니다. 나는 아래 코드를 썼다. 이것은 1에서 1024 사이의 점수, 즉 1 블록에 대해 잘 작동합니다. 하지만 num_points가 1024보다 큰 경우 최소 거리에 대해 잘못된 값이 표시됩니다. brute force 알고리즘을 사용하여 CPU에서 찾은 값으로 gpu 최소값을 확인합니다. min 값은 커널 기능이 끝날 때 temp1 [0]에 저장됩니다.

나는 이것이 무엇이 잘못 되었는가를 모른다.

#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); 
. 
. 

Answer 1

내가 무엇을 잘못하여 알고리즘의 선택이다라고 말하고 싶지만 .. 저를 도와주세요. O (n^2)보다 확실히 잘 할 수 있습니다 - 비록 당신이 꽤 간단하더라도. 물론, 5,000 포인트에서 끔찍하지는 않지만 50,000 포인트를 시도하면 고통을 느낄 것입니다 ...

Voronoi Diagram 또는 아마도 BSP과 같은 구조를 병렬 처리한다고 생각합니다. 더 적은 코드 차이로 쿼리하는 것이 더 쉬울 수도 있습니다.