radix-sort의이 구현을 향상시키는 방법은 무엇입니까?

Question

2 바이트 기수 정렬을 구현하고 있습니다. 개념은 Counting Sort를 사용하여 정수의 하위 16 비트를 정렬 한 다음 상위 16 비트를 정렬하는 것입니다. 이렇게하면 2 개의 반복으로 정렬을 실행할 수 있습니다. 내가 가지고있는 첫 번째 개념은 네거티브를 처리하는 방법을 알아 내려고했습니다. 부호 비트는 음수에 대해 뒤집을 것이므로 16 진수 형식에서는 음수를 양수보다 크게 만듭니다. 이 문제를 해결하기 위해 [0, 2 bil) = [128 000 000 000, 255 255 ...]을 만들기 위해 양수 일 때 부호 비트를 뒤집습니다. 그리고 그것이 음수 일 때 나는 (000 000 .., 127 255 ..)의 범위를 만들기 위해 모든 비트를 뒤집었다. 이 site은 그 정보를 도와주었습니다. 끝내려면 정수를 패스를 기반으로 상위 또는 하위 16 비트로 분할합니다. 다음은이를 수행 할 수있게 해주는 코드입니다.

static uint32_t position(int number, int pass) { 
    int mask; 
    if (number <= 0) mask = 0x80000000; 
    else mask = (number >> 31) | 0x80000000; 
    uint32_t out = number^mask; 
    return pass == 0 ? out & 0xffff : (out >> 16) & 0xffff; 
} 

실제 기수 정렬을 시작하려면 크기 65536 개의 막대 그래프를 형성해야했습니다. 내가 겪었던 문제는 입력 된 요소의 수가 매우 많았던 때였습니다. 히스토그램을 만들려면 시간이 걸릴 것이므로 프로세스와 공유 메모리를 사용하여 병렬로 구현했습니다. 배열을 크기/8의 하위 섹션으로 분할했습니다. 그런 다음 65536 * 8 크기의 공유 메모리 배열을 통해 각 프로세스에서 자체 막대 그래프를 만들었습니다. 그 후에, 나는 그것을 합쳐서 하나의 히스토그램을 형성했다.

for (i=0;i<8;i++) { 
    pid_t pid = fork(); 
    if (pid < 0) _exit(0); 
    if (pid == 0) { 
     const int start = (i * size) >> 3; 
     const int stop = i == 7 ? size : ((i + 1) * size) >> 3; 
     const int curr = i << 16; 
     for (j=start;j<stop;++j) 
      hist[curr + position(array[j], pass)]++; 
     _exit(0); 
    } 
} 
for (i=0;i<8;i++) wait(NULL); 

for (i=1;i<8;i++) { 
    const int pos = i << 16; 
    for (j=0;j<65536;j++) 
     hist[j] += hist[pos + j]; 
} 

다음 부분이었다 내가 캐시 접두사 - 합계의 성능에 영향을 주 었는지 분석하는 대부분의 시간을 보냈다 : 다음은 코드입니다. 8 비트 및 11 비트 패스 기수 정렬을 사용하면 모든 막대 그래프가 L1 캐시에 적합합니다. 16 비트로 L2 캐시에만 적합합니다. 결국 16 비트 히스토그램은 sum을 가장 빠르게 실행했습니다. 그걸로 2 회만 반복해야했기 때문입니다. 또한 CUDA 웹 사이트 권장 사항에 따라 접두사 합계를 병렬로 실행했습니다. 2 억 5 천만 개의 엘리먼트에서, 이것은 16 비트 정수보다 약 1.5 초 느렸다. 그래서 내 접두사 합은 다음과 같이보고 결국 : 왼쪽

for (i=1;i<65536;i++) 
    hist[i] += hist[i-1]; 

유일한 것은 배열을 뒤로 통과하고 임시 배열에서 각각의 장소에 모든 요소를 ​​넣어했다. 필자는 temp에서 배열로 복사하고 코드를 다시 실행하는 대신 두 번 통과해야했습니다. 배열을 입력으로 사용하고 temp를 출력으로 사용하여 정렬을 먼저 실행했습니다. 그런 다음 temp를 입력으로 사용하고 배열을 출력으로 두 번째로 실행했습니다. 이것은 mem-copying를 두 번 다시 배열로 복사하는 것을 막아 주었다. 이 코드는 실제 종류에 대해 다음과 같습니다

histogram(array, size, 0, hist); 
for (i=size-1;i>=0;i--) 
    temp[--hist[position(array[i], 0)]] = array[i]; 

memset(hist, 0, arrSize); 
histogram(temp, size, 1, hist); 
for (i=size-1;i>=0;i--) 
    array[--hist[position(temp[i], 1)]] = temp[i]; 

This link 내가 지금까지 가지고있는 전체 코드가 포함되어 있습니다. 저는 quicksort에 대한 테스트를 실시했으며, 정수 및 부동 소수점으로 5 ~ 10 배, 8 바이트 데이터 유형으로 약 5 배 빠릅니다. 이 문제를 개선 할 수있는 방법이 있습니까?

Answer 1

내 생각 엔 연산 중에 정수의 부호를 처리하는 것이 그럴 가치가 없다고 생각합니다. 코드가 복잡해지고 속도가 느려집니다. 나는 첫 번째 정렬을 위해 unsigned으로 가고 나서 두 개의 반쪽을 재정렬하고 네거티브 중 하나를 반전시키는 두 번째 경로를 수행합니다.

또한 코드에서 나는 서로 다른 프로세스가 어떻게 작동하는지 알지 못합니다. 부모의 히스토그램을 어떻게 수집합니까? 프로세스 공유 변수가 있습니까? 어쨌든 ptrhead를 사용하는 것이 훨씬 더 적절할 것입니다.