並行前綴求和掃描 - 輸入大小不是2的乘方冪

Question

我正在執行前綴求和算法，如http://www.cs.cmu.edu/~guyb/papers/Ble93.pdf中所述。我面臨的問題是輸入大小不是2的冪。我使用此前綴和實現並行快速分類的分區。具體來說，我在接下來的掃描階段算法中遇到了問題。

x[n – 1] = 0 
for d = log2(n) – 1 down to 0 do 
     for all k = 0 to n – 1 by 2^(d+1) in parallel do 
      t = x[k + 2^d – 1] 
      x[k + 2^d – 1] = x[k + 2^(d+1) – 1] 
      x[k + 2^(d+1) – 1] = t + x[k + 2^(d+1) – 1] 

問題1：在上述算法中，假設n = 10，對於d = 2和k = 8，索引k + 2^d-1> n。 k + 2 ^（d + 1）-1> n也是這種情況。這導致應用程序核心轉儲。我們應該如何處理n不是2的權力？
問題2：對於輸入序列1,1,1,0,0,0,0,0,0,0,1正確的前綴和是1,2,3,3,3,3,3,3 ，3,3,4。考慮我忽略索引大於n的操作。如果我手工計算，我會根據上述文件3,4,5,6,6,6,6,6,0,0,0獲得以下前綴總和。

讓我知道如何處理這些問題。

Answer 1

如果您不受某些特定語言的限制，請考慮使用c++和tbb以充分利用existing parallel prefix algorithm implementation。以下是文檔摘錄。

說明

甲parallel_scan（範圍，體）計算一個並行前綴，也稱爲並行掃描。此計算是並行計算中的高級概念，有時在似乎具有固有序列依賴性的情況下很有用。

並行前綴的數學定義如下。令×爲左身份元素id×的關聯操作。 ×的一個序列Z0並行前綴，Z1，...的Zn-1是一個序列Y0，Y1，Y2，...炔-1-其中：

y0 = id× × z0 
yi = yi-1 × zi 

舉例來說，如果是×另外，並行前綴對應於運行總和。並行前綴的串行實現是：

T temp = id×; 
for(int i=1; i<=n; ++i) { 
    temp = temp × z[i]; 
    y[i] = temp; 
} 

並行前綴並行地重新關聯×的應用，並使用兩次通過執行此。它可能會調用×最多兩倍於串行前綴算法。鑑於正確的晶粒尺寸和足夠的硬件線程，它可以執行串行前綴，因爲即使它做了更多的工作，也可以將工作分配到多個硬件線程中。