當循環迭代不獨立時使用OpenMP並行化循環

我有一個數字bessel過濾器的實現，這是我的程序的性能瓶頸。我想用OpenMP並行化主循環。當循環迭代不獨立時使用OpenMP並行化循環

該函數獲取輸入數組paddedsignal和濾波器係數數組dcof和ccof，並生成一個臨時數組temp，該數組被過濾。這個過程的主循環是這樣的：

for (i=order; i<end; i++) 
    { 
     temp[i] = ccof[0]*paddedsignal[i]; 
     for (p=1; p<=order; p++) 
     { 
      temp[i] += ccof[p]*paddedsignal[i-p] - dcof[p]*temp[i-p]; 
     } 
    }

尤其注意，temp[i]價值取決於temp[i-p]以前的值。這混淆了一個簡單的#pragma omp for指令，因爲靠近數組各部分之間的邊界的temp[i]值將由不同線程處理，其競爭條件問題。基本上，如果線程1的索引在0-99之間，線程2的線程需要100-199，那麼100的值將會是錯誤的，因爲它將在它所依賴的值99之前計算。

有沒有辦法挽救這種情況？由於過濾值依賴於相鄰值這一事實使得它本身就是一個串行計算，所以我很遺憾我能做些什麼來平行化。有沒有辦法解決？

來源

2017-02-10 KBriggs

這是一個序列計算。讓速度更快的唯一方法是獲得更快的CPU。另一種可能是使用更適合並行執行的不同類型的過濾器。或者，如果要過濾的數據可以以某種方式進行批處理，則可以通過不同的線程篩選不同的批次。 – bazza

我認爲批處理過濾將是要走的路 – KBriggs

內循環可能像[前綴總和問題]（http://stackoverflow.com/a/35840595/2542702）？ –

由於您正確識別的依賴關係，您基本上無法並行化外部循環。

您可以通過減少來並行化內部循環。但是，這隻對大order有幫助，甚至可能只是導致錯誤的共享，因爲數據混亂了。人們可能會想出一個複雜的數據流，以便在線程間插入signal和temp，這需要分類 - 手動工作共享結構。無論如何，我懷疑它是否值得，因爲減少會增加管理費用。

如果這是您的替代方案，那麼對具有有限脈衝響應的濾波器進行並行化更容易。您也可以將整個信號分成稍微重疊的部分並獨立計算濾波器，但在這些部分的邊界處會出現一些計算錯誤。

來源

2017-02-10 22:51:21 Zulan

這或多或少是我的結論。我將不得不在其他地方尋找更加自然的地方進行並行化。代碼已經實現了一個包裝這個函數的塊過濾策略，所以這可能是一個更自然的做法。 – KBriggs

也許您在尋找#pragma omp for 訂購。它執行它會按順序執行

但請記住以相同的順序代碼：

只能在的動態範圍可用於指示
很「昂貴」（它可能是您的增速也不會如你想象的）

欲瞭解更多信息，請參閱： omp ordered

來源

2017-02-10 21:15:54 QuickSort

以多線程的方式強制執行串行操作有什麼意義？加速從何而來？ – KBriggs

說實話，我從來沒有使用過這個指令，因爲我使用多線程只有當我有獨立工作要做（不像你的例子）。但我可以記得，在某些情況下，合作伙伴項目的順序I/O是有用的。如果你想了解更多有關訂購條款的信息：http://stackoverflow.com/questions/13224155/how-does-the-omp-ordered-clause-work – QuickSort

'ordered'只有在你有重要的部分沒有排序的迭代。對於這個過濾器，你將不得不幾乎整個循環體，幾乎連續化所有的東西。 – Zulan

當循環迭代不獨立時使用OpenMP並行化循環

回答

相關問題