Multidimensional Intratile Parallelization for Memory-Starved Stencil Computations
Open Access
- 30 September 2017
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Parallel Computing
- Vol. 4 (3) , 1-32
Abstract
Optimizing the performance of stencil algorithms has been the subject of intense research over the last two decades. Since many stencil schemes have low arithmetic intensity, most optimizations focus on increasing the temporal data access locality, thus reducing the data traffic through the main memory interface with the ultimate goal of decoupling from this bottleneck. There are, however, only a few approaches that explicitly leverage the shared cache feature of modern multicore chips. If every thread works on its private, separate cache block, the available cache space can become too small, and sufficient temporal locality may not be achieved. We propose a flexible multidimensional intratile parallelization method for stencil algorithms on multicore CPUs with a shared outer-level cache. This method leads to a significant reduction in the required cache space without adverse effects from hardware prefetching or TLB shortage. Our Girih framework includes an autotuner to select optimal parameter configurations on the target hardware. We conduct performance experiments on two contemporary Intel processors and compare with the state-of-the-art stencil frameworks Pluto and Pochoir, using four corner-case stencil schemes and a wide range of problem sizes. Girih shows substantial performance advantages and best arithmetic intensity at almost all problem sizes, especially on low-intensity stencils with variable coefficients. We study in detail the performance behavior at varying grid sizes using phenomenological performance modeling. Our analysis of energy consumption reveals that our method can save energy through reduced DRAM bandwidth usage even at a marginal performance gain. It is thus well suited for future architectures that will be strongly challenged by the cost of data movement, be it in terms of performance or energy consumption.Keywords
All Related Versions
Funding Information
- Extreme Computing Research Center
- ECRC
This publication has 32 references indexed in Scilit:
- Optimizing the performance of streaming numerical kernels on the IBM Blue Gene/P PowerPC 450 processorThe International Journal of High Performance Computing Applications, 2012
- Efficient multicore-aware parallelization strategies for iterative stencil computationsJournal of Computational Science, 2011
- Locality Optimization of Stencil Applications Using Data Dependency Graphs2011
- LEVERAGING SHARED CACHES FOR PARALLEL TEMPORAL BLOCKING OF STENCIL CODES ON MULTICORE PROCESSORS AND CLUSTERSParallel Processing Letters, 2010
- RooflineCommunications of the ACM, 2009
- Optimization and Performance Modeling of Stencil Computations on Modern MicroprocessorsSIAM Review, 2009
- A practical automatic polyhedral parallelizer and locality optimizerACM SIGPLAN Notices, 2008
- : A parameter to characterize memory and communication bottlenecksParallel Computing, 1989
- Estimating interlock and improving balance for pipelined architecturesJournal of Parallel and Distributed Computing, 1988
- The parallel execution of DO loopsCommunications of the ACM, 1974