Seamless Integration of Parallelism and Memory Hierarchy

We prove an analogue of Brent's lemma for BSP-like parallel machines featuring a hierarchical structure for both the interconnection and the memory. Specifically, for these machines we present a uniform scheme to simulate any computation designed for v processors on a v'-processor configuration with v' ≤ v and the same overall memory size. For a wide class of computations the simulation exhibits optimal O (v/v') slowdown. The simulation strategy aims at translating communication locality into temporal locality. As an important special case (v' = 1), our simulation can be employed to obtain efficient hierarchy-conscious sequential algorithms from efficient fine-grained ones.