平行比赛。如何返回数组最大值的位置

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;