平行比賽。如何返回數組最大值的位置

Question

我需要編寫一個算法來使用平行比賽來查找最大值的位置。我有此代碼以找到最大值：

//共享存儲器變量n爲值M [0..N-1]：數組值

//程序並行

torneoMaxParalelo(M,n) 
int incr=1; 
int grande, temp0, temp1; 
while (incr < n) 

    temp0 ← M[pid]; 
    if (pid + incr < n) 
     temp1 ← M[pid + incr]; 
    else 
     temp1 ← -infinite; 
    grande ← max(temp0, temp1); 
    M[pid] ← grande; 
    incr = 2 * incr; 

該算法應該花費O（log n）時間。非常感謝你。

Answer 1

這是僞代碼。

parTournMaxIndex(M, idx, n) 
int incr; 
Write -infinite (some very 
small value) into M[n]. 
Write pid into idx[pid] and write n into idx[pid+n]. 
incr = 1; 
int idx0, idx1, idxBig; 
Key key0, key1; 
while (incr < n) 
    Read idx[pid] into idx0 and read idx[pid+incr] into idx1. 
    Read M[idx0] into key0 and read M[idx1] into key1. 
    if (key1 > key0) idxBig = idx1; 
    else idxBig = idx0; 
    Write idxBig into idx[pid]. 
    incr = 2 * incr;