Detail

Cache-conscious Data Decomposition of Parallel Computations

The MapReduce framework is being increasingly used in the scientific computing and image/video processing fields. Relevant research has tailored it for the field’s specifici-ties but there are still overwhelming limitations when it comes to temporal locality-sensitive computations. The performance of this class of computations is closely tied to an efficient use of the memory hierarchy, concern that is not yet taken into consideration by the existing distributed MapReduce runtimes. Consequently, implementing temporal locality-sensitive computations , such as stencil algorithms, on top of MapReduce is a complex chore not rewarded with proportional dividends. This paper tackles both the complexity and the performance issues by integrating tiling techniques and memory hierarchy information into MapReduce’s split stage. We prototyped our proposal atop the Apache Hadoop framework, and applied it to the context of stencil computations. Our experimental results reveal that, for a typical stencil computation, our prototype clearly outperforms Hadoop MapReduce, specially as the computation scales.