Seamless integration of parallelism and memory hierarchy

Abstract. 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 hierarchyconscious sequential algorithms from efficient fine-grained ones.