In computer science and particularly in compiler design, loop nest optimization (LNO) is an optimization technique that applies a set of loop transformations for the purpose of locality optimization or parallelization or another loop overhead reduction of the loop nests. (Nested loops occur when one loop is inside of another loop.) One classical usage is to reduce memory access latency or the cache bandwidth necessary due to cache reuse for some common linear algebra algorithms. The technique used to produce this optimization is called loop tiling, also known as loop blocking or strip mine and interchange. Overview Loop tiling partitions a loop's iteration space into smaller chunks or blocks, so as to help ensure data used in a loop stays in the cache until it is reused. The partitioning of loop iteration space leads to partitioning of a large array into smaller blocks, thus fitting accessed array elements into cache size, enhancing cache reuse and eliminating cache size requirements. An ordinary loop for (i=0; i<N; ++i) { ... } can be blocked with a block size B by replacing it with for (j=0; j<N; j+=B) { for (i=j; i<min(N, j+B); ++i) { .... } } where min() is a function returning the minimum of its arguments. Example: matrix-vector multiplication The following is an example of matrix vector multiplication. There are three arrays, each with 100 elements. The code does not partition the arrays into smaller sizes. int i, j, a[100][100], b[100], c[100]; int n = 100; for (i = 0; i < n; i++) { c[i] = 0; for (j = 0; j < n; j++) { c[i] = c[i] + a[i][j] * b[j]; } } After loop tiling is applied using 2 * 2 blocks, the code looks like: int i, j, x, y, a[100][100], b[100], c[100]; int n = 100; for (i = 0; i < n; i += 2) { c[i] = 0; c[i + 1] = 0; for (j = 0; j < n; j += 2) { for (x = i; x < min(i + 2, n); x++) { for (y = j; y < min(j + 2, n); y++) { c[x] = c[x] + a[x][y] * b[y]; } } } } The original loop iteration space is n by n. The accessed chunk of array a[i, j] is also n by n. When n is too large and the cache size of the machine