並行處理的計算順序

給定一個未排序的數組，我已經讀過一篇文章，可以使用n平方處理器來獲得O（1）複雜度中數組的最大元素。任何人都可以解釋它背後的機制嗎？並行處理的計算順序

2013-10-06 user2784234

請參閱這篇文章？ –

你確定它不是一個概率算法嗎？ – Leeor

這是可能的併發隨機訪問機器。 – arshajii

該算法背後的機制是基於我只能稱之爲骯髒的伎倆。也就是說，我們允許所有處理器同時寫入相同的共享內存位置。如果它們都寫入相同的值，則結果被認爲是明確的。

這可以用來實現並行運算符和並行運算符。這裏是例如parallel-OR：

result := false 
for i in 0 to N-1 parallel do 
    if a[i] then 
    result := a[i]

我們還允許同時讀取。

這裏的MAX算法：

N := a.length 

for i in 0 to N-1 parallel do 
    m[i] := true 

for i in 0 to N-1 parallel do 
    for j in 0 to N-1 parallel do 
    if a[i] < a[j]    /* dirty trick: simultaneous read by many processors */ 
     then m[i] := false   /* dirty trick: many processors write to m[i] at once */ 

for i in 0 to N-1 parallel do 
    if m[i] 
     then max := a[i]   /* dirty trick: many processors write to max at once */ 

return max

抽象的體系結構，允許這些技巧被稱爲CRCW PRAM。

來源

2013-10-06 15:06:56

哇。非常好。 – RBarryYoung

這是一個後續| V |廣告的答案（這已被刪除），

您使用大小n的附加陣列（讓叫它B），現在你使用n-1處理器比較任意元素a[i], i=0,...,n-1與所有其他元素a[0],...,a[i-1],a[i+1],...,a[n-1]，每一個發現，即發現a[0] > a[j]，處理器j={1,...,n-1}將適用B[i]=B[i]+1，此外，它會檢查是否B[i]=n-1，如果是的話，它會宣佈元素我是最大的元素。

來源

2013-10-06 14:58:05

雖然看起來它有同樣的問題，但多個處理器將如何執行B [我] = B [我] + 1'一次？ – IVlad

並行處理的計算順序

回答

相關問題