Loop nest optimization

Loop nest optimization is a compiler technique that applies a set of loop transformations to nested loops, meaning a loop placed inside another loop, in order to improve memory locality, expose parallelism or cut loop overhead. A classical use is to reduce memory access latency, or the cache bandwidth a program needs, by reusing data held in the cache, which matters most for common linear algebra routines such as matrix multiplication. The central method is loop tiling, also called loop blocking or strip mine and interchange, which splits a loop's iteration space into smaller blocks so that the array elements a block touches fit in cache and stay there until they are reused. Choosing a good tile size is not easy, because it depends on the accessed array regions and on the cache size of the target machine, and cache-oblivious algorithms take the opposite route by using any cache efficiently without explicit blocking.