Survey of Parallel Computation

Programming

Everyone thinks shared memory is the natural parallel extension of sequential computing: “Ignore memory reference time like vN model, and let HW give the flat memory illusion”

•Memory reference time is key to good algs:

–Find maximum is the example

•Best ignore-memory-time (PRAM) is Valiant O(log log P)

•Best consider-memory-time (CTA) is tournament O(log P)

•(Actual?) implementation of Valiant’s alg O(log P loglog P)

•Actual implementation of tournament O(log P)

PRAM hides a critical cost => it’s hard to get results