Running Valiant’s Algorithm
•PRAM’s don’t exist and
can’t be built
•To run the algorithm
we need a simulator for the CRCWPRAM
•In order to simulate
the concurrent reads and the concurrent
writes, a parallel computer will need W(log P) time per step, though there are bandwidth requirements and serious engineering problems to attain that goal [details in future lecture]
•Observed performance
of Valiant’s Max:
O(log
n loglog n)