Translating submachine locality into locality of reference

The design of algorithms exhibiting a high degree of tem-poral and spatial locality of reference is crucial to attain good performance on current and foreseeable computing systems featuring ever deeper memory hierarchies. Previ-ous work has demonstrated that task parallelism can be ef-ficiently transformed into locality of reference in two-level hierarchies. Recently, we moved a step forward and showed how the more structured type of parallelism exposed by sub-machine locality can be efficiently turned into temporal lo-cality on arbitrarily deep hierarchies. In this work, we com-plete and extend the above result by encompassing also spa-tial locality. Specifically, we present a scheme to simulate parallel algorithms designed for the Decomposable BSP (a BSP variant which captures submachine locality) on the Hi-erarchical Memory Model with Block Transfer. The simula-tion yields good hierarchy-conscious sequential algorithms from parallel ones, and provides evidence of the strict re-lation between submachine locality in parallel computation and locality of reference (both temporal and spatial) in the hierarchical memory setting. 1