Bandwidth-based upper bounds on the scalability of micro-grained network machines

This paper presents a method to bound the scalability of algorithms executing on micro-grained network machines based on communication bandwidth, β. The scalability is reported as the rate at which effective work is expended by the machine as a function of problem size. The method yields an upper bound on the effective work-rate of an algorithm A containing work W on host machine H as R=O(β(H)/β(A)W). Highly scalable algorithm-machine pairings exhibit work-rates that grow linearly with problem size, while poorly scaling pairings exhibit work-rates that grow sub-linearly. The cost-to-benefit of scaling to larger problems is easily analyzed by differentiating the effective work rate