如何改進這種基數排序的實現？

Question

我正在實現一個2字節的基數排序。其概念是使用計數排序來排序整數的低16位，然後排序高16位。這使我可以在2次迭代中運行排序。我有的第一個想法是試圖找出如何處理負面情況。由於符號位將被翻轉爲負數，然後以十六進制形式使負數大於正數。爲了解決這個問題，我在符號位正向時翻轉了符號位，以使[0，2 bil] = [128 000 000 000，255 255 ...）。當它是負數時，我翻轉所有的位，使其範圍從（000 000 ..，127 255 ..）。這site幫助我瞭解這些信息。爲了完成它，我會根據pass將整數分成頂部或底部的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位直方圖的和最快，因爲我只需要運行2次迭代就可以了。根據CUDA網站的建議，我也同時運行前綴總和。在2.5億個元素中，這個運行速度比16位整數慢大約1.5秒。所以，我的前綴和結束這樣看：

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

剩下的唯一的事情是通過數組向後遍歷並把所有的元素融入臨時陣列在各自的點。因爲我只需要經過兩次，而不是從temp複製到數組，然後再次運行代碼。我首先使用數組作爲輸入運行排序，並將temp作爲輸出。然後第二次使用temp作爲輸入和數組作爲輸出運行它。這使我無論從兩次mem複製回數組。代碼看起來像這樣的實際排序：

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會更合適。