Optimizing for parallelism and data locality
Ken Kennedy, Kathryn S. McKinley · 2014
Previous research has used program transformation to introduce parallelism and to exploit data locality. Unfortunately, these two objectives have usually been considered independently. This work explores the trade-offs between effectively utilizing parallelism and memory hierarchy on shared-memory multiprocessors. We present a simple, but surprisingly accurate, memory model to determine cache line reuse from both multiple accesses to the same memory location and from consecutive memory access. The model is used in memory optimizing and loop parallelization algorithms that effectively exploit data locality and parallelism in concert. We demonstrate the efficacy of this approach with very encouraging experimental results.
Cited by 119 works. doi:10.1145/2591635.2667164
Authors
References
- An extended set of FORTRAN basic linear algebra subprograms
- Dependence graphs and compiler optimizations
- Optimizing supercompilers for supercomputers
- Automatic translation of FORTRAN programs to vector form
- A data locality optimizing algorithm
- The cache performance and optimizations of blocked algorithms
- On the Number of Operations Simultaneously Executable in Fortran-Like Programs and Their Resulting Speedup
- The parallel execution of DO loops
- Strategies for cache and local memory management by global program transformation
- A loop transformation theory and an algorithm to maximize parallelism