如何將此順序迭代二進制搜索轉換爲並行算法？

Question

我有這個數組（A），其中有n個元素保證被排序，我需要在並行系統中對它們執行二進制搜索。我開始做這個二進制搜索算法。這是迭代的，因爲我不確定如何將遞歸合併到並行處理中。

/* Looking for element k in array A of length n */ 
min = 0; 
max = n - 1; 
while(min <= max) 
{ 
    midpoint = min + ((max-min)/2); //index 
    if(A[midpoint] > k) //discard upper half 
     max = midpoint - 1; 
    else if(A[midpoint] < k) //discard lower half 
     min = midpoint + 1; 
    else 
     return midpoint; //Found k, return index 
} 
return -1; //not found 

在並行算法中，我有權訪問p處理器，它是一個允許併發讀取但獨佔寫入的系統。真正的問題是我仍然在按順序思考。也就是說，我看不出有多個處理器可以做到這一點，因爲如果不先知道中點數據的位置，就不能「丟掉」數組中不需要的部分。這看起來很內在順序。

僞代碼：

Global: //Variables accessible by all processors 
    index; //index of k 
    p;  //number of processors 
    i;  //the i^th processor 
    n;  //number elements in array A 
    A[0, 1, ... , (n-1)]; 
local: //Variables accessible by only the owning processor 
     //Not sure what I need yet 
Begin 
    Spawn(P1, P2 . . . P(p-1)); //"create" the p processors 
    for all P where 0 <= i <= (p-1) do //each processor does the following code 
    //I'm stuck here 
    endfor 
End 

最後一件事：我看到張貼詢問是否有辦法做並行處理的二進制搜索用戶的問題。這個問題沒有真正的決定性答案，因爲這兩個相關答案都獲得了1票。有人說這實際上是不可能的，因爲這是一個循序漸進的過程，而另一個似乎非常確信實施起來會很容易。你怎麼看？

Previous Parallel Binary Search Question

Answer 1

雖然在技術上可以使並行二進制搜索來看，我不會建議它。

並行運行的最佳算法是那些具有分離的元素，可以同時運行。例如，將3D圖形渲染到視頻中是很好的，因爲每個幀都是獨立的，並且可以提供給一個單獨的處理器。

您可以將樹分成不同的片段，以便每個處理器都有一定的工作空間，但考慮到二進制搜索的性質，只有其中一個處理器會找到答案，因此會浪費所有其他處理器的計算工作量在他們的細分中沒有搜索元素。這甚至不考慮線程的開銷。

現在，如果另一方面，你有一系列搜索要做一個單一的二叉樹，這將是一個不同的問題。你可以有一個工作隊列，你的所有線程都來自它，執行二分查找並作出響應。這樣，您可以並行運行多個搜索，而不是搜索的一部分。如果你想進一步優化它，你也可以實現一個緩存。

簡而言之，不要嘗試在處理器之間分割單獨的二進制搜索，因爲除了浪費處理器時間之外，您不會獲得任何內容。但是，如果您正在進行多次搜索，則可以通過並行運行多個搜索來獲得。

Answer 2

與所有需要並行解決的問題一樣......這取決於數據大小，消息/共享內存的速度以及您的需求。

寫入鎖定速度有多快，同步速度有多快？如果速度足夠快（例如，在單臺計算機上使用共享內存）並且數據量足夠大，則可以使用特定類型的「分割和運行」技術。你可以這樣想：

二進制搜索是一種分而治之的方法，在每次迭代後更新你正在檢查的範圍 - 每次迭代時範圍減半。您可以將當前範圍劃分爲2個，而不是將其劃分爲p個部分，其中每個過程負責其中的一個部分;在每次迭代中，「獲勝」片段（目標值在其範圍內的片段）將新搜索範圍寫入內存，並在開始下一次迭代之前同步這些進程。如果你有足夠的數據，每次減少你的數據減少數據p可能是一個勝利。您將從$ O（log_2（x））$到$ O（log_p（x））$。

這種方法只適用於寫入和同步速度足夠快的情況，因爲它取決於編寫和同步的批次。如果你在集羣上做這些，這些會變得很昂貴。如果流程之間的溝通很困難，也許您可​​以做的最好的事情就是您鏈接到的另一篇文章中建議的「分拆並運行」。具體來說，將排序列表中的每個p th元素放在不同的節點上。然後，當請求進入時，在所有節點上執行二進制搜索。如果數組中的值是唯一的，則只有一個節點會找到答案，並且該節點可以返回結果。這是一個相對較差的並行性，因爲您重複了很多工作 - 您忽略了存在於不同節點上的數組之間之間的順序。但它會使您從$ O（log_2（x））$到$ O（log_2（x/p））$加速。

實際上，很難知道什麼方法可以提前在硬件上正常工作。通常，您必須在確保所有流程始終處於活動狀態並確保您不會損失太多通信開銷時間之間達成經驗平衡。