在C++中並行向量的find_first

我有一個相當大的向量。某些矢量成員並行匹配某個條件。我想找到與條件匹配的第一個元素。在C++中並行向量的find_first

我的問題與此問題非常相似（tbb: parallel find first element），但我沒有tbb。檢查條件非常繁瑣（所以我無法順序完成所有這些）。這就是爲什麼我想要並行運行它。我不得不提一提，我想找到第一個元素（所以元素的索引位置對我來說很重要）。

例如，如果我有4個線程。

ThreadNr Index  condition 
1   0   Not Meet 
2   1   Not Meet 
3   2   Not Meet 
4   3   Not Meet 

ThreadNr Index  condition 
1   4   Not Meet 
2   5   Meet 
3   6   Not Meet 
4   7   Meet

該函數必須retun 5. 線程索引號已被分佈和順序迭代塊上工作（塊大小可以是多於1。例如線程1件作品上的前4個元素，螺紋2在第二個4元素等等）。

對於上面的例子，如果線程號4（在索引7中）在線程號2（索引5）之前找到成員，它必須等待所有線程完成作業。正如我之前所說的，最低的指數是目標。

如果你有更好的算法，請糾正我。

注：我可以使用外部庫，如升壓1.62計算，OpenMP 2.0

來源

2016-10-27 H' H

請注意，最好情況下的複雜度從0增加到N/K，其中N是元素的總數，K是線程數。 – rubenvb

這取決於元素的大小以及檢查條件需要多長時間。如果你正在對'std :: vector '做'=='這樣的簡單操作，那麼你不會像這樣交錯，因爲這會對緩存造成嚴重破壞。在這種情況下，您可能希望線程一次檢查整數塊。如果你的矢量對象是1MB一塊，並且需要1-2秒來執行檢查，那麼交錯可能更有意義。 – RyanP

如果tbb呼籲您使用它。在Openmp中，如果我理解這個問題，那麼您將對數據進行分區，因爲您似乎已經使用內部搜索循環進行了分區，將內部結果合併到外部omp歸約firstprivate lastprivate或critical中。 – tim18

由於OpenMP 2.0沒有取消構造，因此您必須自行實施一個構件，例如通過使用共享變量。這也意味着您不能使用for工作共享構造，因爲不允許打破並行循環（這就是OpenMP 4.0引入了取消構造的原因）。如果您在評估每個元素之間執行取消檢查，則可能會發生兩個或更多個線程找到與條件匹配的元素。因此，應該執行對指數形成分鐘還原：

int found = 0; 
int first_index = INVALID_VALUE; 
int iteration = 0; 

#pragma omp parallel 
{ 
    int my_index = INVALID_VALUE; 
    int i; 

    do 
    { 
     // Later versions of OpenMP allow for "atomic capture" 
     // but OpenMP 2.0 requires a critical directive instead 
     #pragma omp critical(iteration) 
     { 
     i = iteration++; 
     } 

     if (i < N && check(i)) 
     { 
     found = 1; 
     my_index = i; 
     } 
    } while (!found && i < N); 

    #pragma omp critical(reduction) 
    if (my_index != INVALID_VALUE) 
    { 
     if (first_index == INVALID_VALUE || my_index < first_index) 
     first_index = my_index; 
    } 

    // Only needed if more code follows before the end of the region 
    #pragma omp barrier 

    ... 
}

此代碼假定檢查第i個元素（check(i)）的條件不改變元件的狀態，並且因此，最壞的可能發生的事情是找到匹配元素的線程可能不得不等待所有其他線程完成檢查他們當前正在工作的元素，並且等待時間將是所有處理時間的最大值。

do循環中使用的critical構造是昂貴的。如果check()並不需要太多時間，那麼你可以考慮用大塊的工作重複，而不是：

do 
{ 
    #pragma omp critical(chunk) 
    { 
     my_chunk = chunk++; 
    } 

    if (my_chunk >= N_chunks) 
     break; 

    for (i = my_chunk * chunk_size; !found && i < (my_chunk+1)*chunk_size; i++) 
    { 
     if (check(i)) 
     { 
     found = 1; 
     my_index = i; 
     break; 
     } 
    } 
} while (!found && my_chunk < N_chunks);

另一種解決方案，合理地發揮作用時，元件的數量並不大，並檢查每一個是昂貴的：

#pragma omp parallel 
{ 
    #pragma omp for schedule(dynamic,x) 
    for (i = 0; i < N; i++) 
    { 
     if (!found && check(i)) 
     { 
     my_index = i; 
     found = 1; 
     } 
    } 

    // Min reduction from the solution above 
    ... 
}

一旦found爲真，循環迭代的其餘部分將運行，因爲&&的shortcutting屬性「空」的機構。

來源

2016-10-27 15:28:45

只是一個問題：對於最後一個解決方案，你不需要在某處刷新'found'嗎？ – Gilles

除了我以前的評論，這兩個第一個解決方案不需要'flush'，因爲循環內的'critical'部分隱含了一些解決方案。但是對於最後的解決方案，沒有隱式或顯式的'found'刷新，因此線程沒有找到解決方案，因此可以在緩存中保持原樣。至少，這是我看到它的方式。我錯了嗎？ – Gilles

'發現'最初是'volatile'，然後我將其刪除。事實上，寬鬆的內存模型允許共享變量在不同的線程中具有臨時的分歧值，但正確使用'flush'是非常棘手的，我寧願不在這裏介紹構造。此外，x86上的大多數OpenMP編譯器傾向於實現更嚴格的內存模型（在僅將寄存器賦值爲共享變量後不保留），並將'flush'編譯爲內存柵欄。沒有刷新可能會導致額外的迭代，所以沒什麼大不了的。但爲了正確，是的，應該有一個。 –

對於OpenMP，你可以嘗試用#pragma omp for schedule(dynamic)建立一個for循環。每個線程將按照與您的向量相同的順序執行一次迭代。如果您想通過線程檢查4個元素，請嘗試#pragma omp for schedule(dynamic, 4)

來源

2016-10-27 13:00:43 Isukthar

謝謝，但它不尊重索引。例如，如果線程號4在線程號2之前找到元素，我可能會得到絞線索引 –

我認爲如果條件成立，您可以在寫入索引值並退出循環之前添加'#pragma omp ordered' 。 – Isukthar

在C++中並行向量的find_first

回答

相關問題