thrust :: sort_by_key가 qsort보다 훨씬 느림

Question

thrust :: sort_by_key가 qsort보다 훨씬 느리다는 것을 알게되었습니다. 병렬 정렬의 성능이 낮아서 필자는 왜 그런가?

데이터 세트는 100입니다. qsort 시간은 0.000026 (s)입니다. GPU_sort 시간은 0.000912 (s)입니다.

데이터 집합은 1000입니다. qsort 시간은 0.000205입니다. GPU_sort 시간은 0.003177입니다.

데이터 세트는 10000입니다. qsort 시간은 0.001598입니다. GPU_sort 시간은 0.031547입니다.

데이터 세트는 100000입니다. qsort 시간은 0.018564입니다. GPU_sort 시간은 0.31230입니다.

데이터 세트는 1000000입니다. qsort 시간은 0.219892입니다. GPU_sort 시간은 3.138608입니다.

데이터 세트는 10000000입니다. qsort 시간은 2.581469입니다. GPU_sort 시간은 85.456543입니다.

struct HashValue{ 
int id_; 
float proj_; 
}; 

int HashValueQsortComp(const void* e1, const void* e2)      

{ 

int ret = 0; 

HashValue* value1 = (HashValue *) e1; 

HashValue* value2 = (HashValue *) e2; 

if (value1->proj_ < value2->proj_) { 
    ret = -1; 
} else if (value1->proj_ > value2->proj_) { 
    ret = 1; 
} else { 
    if (value1->id_ < value2->id_) ret = -1; 
    else if (value1->id_ > value2->id_) ret = 1; 
} 
return ret; 
} 


const int N = 10; 

void sort_test() 
{ 

clock_t start_time = (clock_t)-1.0; 
clock_t end_Time = (clock_t)-1.0; 

HashValue *hashValue = new HashValue[N]; 
srand((unsigned)time(NULL)); 

for(int i=0; i < N; i++) 
{ 
    hashValue[i].id_ = i; 
    hashValue[i].proj_ = rand()/(float)(RAND_MAX/1000); 
} 

start_time = clock(); 
qsort(hashValue, N, sizeof(HashValue), HashValueQsortComp); 
end_Time = clock(); 
printf("The qsort time is %.6f\n", ((float)end_Time - start_time)/CLOCKS_PER_SEC); 

float *keys = new float[N]; 
int *values = new int[N]; 
for(int i=0; i<N; i++) 
{ 
    keys[i] = hashValue[i].proj_; 
    values[i] = hashValue[i].id_; 
} 
start_time = clock(); 
thrust::sort_by_key(keys, keys+N, values); 
end_Time = clock(); 
printf("The GPU_sort time is %.6f\n", ((float)end_Time - start_time)/CLOCKS_PER_SEC); 

delete[] hashValue; 
hashValue = NULL; 

delete[] keys; 
keys = NULL; 

delete[] values; 
values = NULL; 
} 

Answer 1

변수 (keys, values)는 추력 정렬에 전달됩니다 :

thrust::sort_by_key(keys, keys+N, values); 

이 호스트 변수

여기 내 코드입니다. 이는 GPU에서 실행되지 않는 알고리즘에 대해 thrust will dispatch the host path을 의미합니다. 추력에 대한 자세한 내용은 thrust quickstart guide을 참조하고, here은 추력을 장치 변수와 함께 사용한 작업 예제입니다.

호스트 전달 스러스트 정렬이 qsort 구현보다 느립니다. 장치 경로를 사용하고 추력 정렬 작업 만 수행하는 경우 속도가 빨라질 수 있습니다.