응용 프로그램은 두 개의 정렬 된 정수 목록 (교차 설정)을 말합니다 (예 : list1과 list2).CUDA를 사용하여 이진 탐색의 분기 차이를 줄이는 방법
list1의 각 요소에는 GPU 스레드가 할당되고, 이진 검색을 통해 list2에 나타나는지 확인합니다. 이 응용 프로그램에는 엄청난 양의 스레드 차이가 있음을 쉽게 알 수 있습니다. thread divergences를 줄이기위한 좋은 접근법이 있는지 궁금합니다. 이 응용 프로그램을 구현하기 위해 CUDA를 사용하고 있습니다.
P-ary 검색이라고하는 방법이 있지만 바이너리 검색의 스레드 차이를 줄이는 것이 중요합니다. 또한 추력이라는 라이브러리가 있다는 것을 알고 있습니다. 그러나 그 차이를 줄이려는 시도는없는 것 같습니다.
두 목록을 모두 정렬하면 이진 검색이 수행 할 수있는 최상의 알고리즘이 아닙니다. 이진 검색은 O(n lg n)을 제공하지만 병합과 같은 알고리즘 만 수행하면 교차 부분 만 가져오고 O(n)이됩니다.
GPU를 사용하는 바보 같은 알고리즘입니다. 내가 보는 유일한 경우는 방금 GPU에서 데이터를 생성 한 것입니다. 어떤 경우에는 문제를 여러 개의 작은 교차로로 나누고 각각에 스레드를 할당하려고합니다.
그렇게하려면 k 등 간격의 list1 요소를 선택하고 이진 검색을 사용하여 list2에서 찾습니다. 마찬가지로 list2의 등 간격 요소 k을 선택하고 list1에서 찾으십시오. 이제 각 목록에 2k 개의 범위가 있으며 각 범위의 범위는 최대로 N/k입니다. 이제 그 범위를 평행하게 교차하십시오. (당신이 원하는 스레드 수의 절반으로 k를 설정합니다.)
첫 번째 목록의 두 번째 목록에서 검색하는 이유는 무엇입니까? –
각 하위 목록에 최대 N/k 개의 요소가 있는지 확인하려고합니다. 하나의 목록에서 분할 점을 선택한 경우 다른 목록의 하위 범위가 너무 클 수 있습니다. –
추적 할 수없는 가망 코드 :
bool end = false;
bool found = false;
while(!end && !found)
{
int diff = max-min;
int middle = min + (diff/2);
end = diff < 1;
found = element[middle] == element;
if (index < elements[middle])
max = middle-1;
else //(index > elements[middle+1])
min = middle + 2;
}
return found;
경고 :이 코드는
이 얼마나 큰의 집합입니다 범위의 메모리가 액세스하여 예외를 생성 할 수 정수? divergences에서, 길이가 n 인 두리스트를 합치는 것은 O (n) 비교를 포함하는데, 각각의 차이는 발산 될 것입니다. 나는 당신이 많은 갈등을 가질 것이라는 점을 받아 들여야한다고 생각한다. (더 큰 문제는 병렬로 메모리 블록을로드하는 것입니다.) – btilly
동의합니다 - 메모리 액세스는 발산과 관련된 더 큰 문제입니다. 이진 탐색 단계와 종료 - 내가 볼 수있는 한 두 가지 발산 원천이 있습니다. 그 스레드는 어쨌든 끝났기 때문에 종료에 대해서는별로 신경 쓰지 않고 루프의 바이너리 단계는 if/else 만 인덱스를 업데이트하는 것입니다. 그보다 훨씬 더 나쁜 것은 두 번째 목록의 모든 곳에서 읽는 것입니다. 나는 두 목록을 먼저 정렬하는 것이 조금 도움이 될 것 같아요. –
duh. 정렬 list1. –