Comment by benlivengood
5 years ago
I think more important is the actual cost of communication. Networks are slow. 100Gbit is still a couple times slower than the memory controllers in our phones.
https://en.m.wikipedia.org/wiki/Bulk_synchronous_parallel is a useful model for incorporating communication costs into design vs. PRAM.
BSP is a specific model for parallel computation, but it still operates on the fundamentals of Amdahl's Law, and the whole reason it exists is find the optimal divide-and-conquer solution given a set of real-world limitations.
One might even say that the cost of implementing your algorithm with BSP is higher than PRAM, because of the extra layers. But you can't ignore some of the things that you can in a strict PRAM model, so you have to incorporate those into the cost as well.
Given Gustafson's law, if you have enough data, enough to work to do, you can sort of ignore the un-parallelizable fraction by throwing enough processors at the computation.
What starts to trip things up at this scale is synchronization.