修改並行掃描

Question

這是一個算法問題，而不是編程問題。我想知道是否可以修改前綴總和（或任何）並行算法來完成以下操作。我想在小於O（N）的時間內從GPU上的兩個輸入列表生成結果。

規則是：執行數據中的第一個數字，直到鍵中的相同索引包含較小值。

每當我嘗試將它映射到並行掃描時，它都不起作用，因爲我無法確定哪些數據值要在upsweep中傳播，因爲無法知道哪些先前的數據可能傳輸的遠遠不足以進行比較反對當前的關鍵。這個問題讓我想起我們需要考慮當前指數和所有過去指數的波動。

再一次，不需要代碼進行平行掃描（儘管那會很好），更多的是要了解如何完成或爲什麼不能完成。

int data[N] = {5, 6, 5, 5, 3, 1, 5, 5}; 
int keys[N] = {5, 6, 5, 5, 4, 2, 5, 5}; 
int result[N]; 

serial_scan(N, keys, data, result); 
// Print result. should be {5, 5, 5, 5, 3, 1, 1, 1, } 

代碼來執行串行掃描低於：

void serial_scan(int N, int *k, int *d, int *r) 
{ 
    r[0] = d[0]; 
    for(int i=1; i<N; i++) 
    { 
     if (k[i] >= r[i-1]) { 
     r[i] = r[i-1]; 
     } else if (k[i] >= d[i]) { 
     r[i] = d[i]; 
     } else { 
     r[i] = 0; 
     } 
    } 
} 

Answer 1

爲並行掃描的一般技術可以發現here，在功能語言標準ML說明。這可以爲任何關聯運營商完成，我認爲你的帳單符合要求。

一個直觀的泵是，你可以通過遞歸計算數組的兩半的總和並將它們加在一起來計算O（log（n））範圍內的數組的總和（無限處理器的運行時間）。在計算掃描時，您只需要知道當前點之前的數組總和。

我們可以計算並行執行兩半的數組的掃描：使用上述技術計算上半部分的總和。然後依次計算兩半的掃描;上半場從0開始，下半場開始於你之前計算的總和。完整的算法有點棘手，但使用相同的想法。

下面是用不同的語言做並行掃描一些僞代碼（用於整數和添加的特定情況下，但邏輯是相同的任何結合運算符）：

//assume input.length is a power of 2 

int[] scanadd(int[] input) { 
    if (input.length == 1) 
    return input 
    else { 
    //calculate a new collapsed sequence which is the sum of sequential even/odd pairs 
    //assume this for loop is done in parallel 

    int[] collapsed = new int[input.length/2] 
    for (i <- 0 until collapsed.length) 
     collapsed[i] = input[2 * i] + input[2*i+1] 

    //recursively scan collapsed values 
    int[] scancollapse = scanadd(collapse) 

    //now we can use the scan of the collapsed seq to calculate the full sequence 

    //also assume this for loop is in parallel 
    int[] output = int[input.length] 
    for (i <- 0 until input.length) 
     //if an index is even then we can just look into the collapsed sequence and get the value 
     // otherwise we can look just before it and add the value at the current index 

     if (i %2 ==0) 
     output[i] = scancollapse[i/2] 
     else 
     output[i] = scancollapse[(i-1)/2] + input[i] 

    return output 
    } 
}