Alternative Solution
•What
is the best (practical) way of computing max?
–The
tournament algorithm, a variation on global sum
–O(log P) time on P processors (as with sum, the problem size can
be Plog P)
–The
tournament algorithm doesn’t need to be simulated … it runs in the stated time
directly on all existing parallel processors
•Since
O(log n) < O(log n loglog n) the PRAM model mispredicted the best practical
algorithm
The PRAM didn’t help, it hurt our
effort