algorithm - Order of computation on parallel processing -

given unsorted array, have read in article n-square processors can used maximum element of array in o(1) complexity. can explain mechanics behind it?

the mechanics behind algorithm based on can call dirty trick. namely, allow processors write simultaneously same shared memory location. if write same value, result considered well-defined.

this can used implement parallel-and , parallel-or operators. here's example parallel-or:

result := false in 0 n-1 parallel   if a[i]     result := a[i] 

we allow simultaneous reads.

here's max algorithm:

n := a.length  in 0 n-1 parallel     m[i] := true  in 0 n-1 parallel   j in 0 n-1 parallel     if a[i] < a[j]               /* dirty trick: simultaneous read many processors */       m[i] := false         /* dirty trick: many processors write m[i] @ once */  in 0 n-1 parallel     if m[i]         max := a[i]         /* dirty trick: many processors write max @ once */  return max 

the abstract architecture allows these tricks called crcw pram.