Параллельный турнир. Как вернуть позицию максимального значения массива - PullRequest
1 голос
/ 26 ноября 2011

Мне нужно написать алгоритм, чтобы найти позицию максимального значения с помощью параллельного турнира. У меня есть этот код, чтобы найти максимальное значение:

// Переменные общей памяти 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) времени. Большое спасибо.

1 Ответ

0 голосов
/ 26 ноября 2011

Вот псевдокод.

 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;
Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...