Loop tiling - AbsoluteAstronomy.com

Loop tiling, also known as loop blocking, or strip mine and interchange, is a loop optimization

Loop optimization

In compiler theory, loop optimization plays an important role in improving cache performance, making effective use of parallel processing capabilities, and reducing overheads associated with executing loops. Most execution time of a scientific program is spent on loops...

used by compiler

Compiler

A compiler is a computer program that transforms source code written in a programming language into another computer language...

s to make the execution of certain types of loops more efficient.

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

CPU cache

A CPU cache is a cache used by the central processing unit of a computer to reduce the average time to access memory. The cache is a smaller, faster memory which stores copies of the data from the most frequently used main memory locations...

until it is reused. The partitioning of loop iteration space leads to partitioning of 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 ...
}

can be blocked with a block size B by replacing it with

for(j=0; j for(i=j; i ....
}

where min is a function returning the minimum of its arguments.

Example

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 we apply loop tiling using 2 * 2 blocks, our 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;
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 is too small, the accessed array elements in one loop iteration (for example, i = 1, j = 1 to n) may cross cache lines, causing cache misses.

Another example using an algorithm for matrix multiplication:

Original matrix multiplication:
DO I = 1, M
DO K = 1, M
DO J = 1, M
Z(J, I) = Z(J, I) + X(K, I) * Y(J, K)

After loop tiling B*B:
DO K2 = 1, M, B
DO J2 = 1, M, B
DO I = 1, M
DO K1 = K2, MIN(K2 + B - 1, M)
DO J1 = J2, MIN(J2 + B - 1, M)
Z(J1, I) = Z(J1, I) + X(K1, I) * Y(J1, K1)

It is not always easy to decide what value of tiling size is optimal for one loop because it demands an accurate estimate of accessed array regions in the loop and the cache size of the target machine. The order of loop nests (loop interchange

Loop interchange

In compiler theory, loop interchange is the process of exchanging the order of two iteration variables.For example, in the code fragment: for i from 0 to 10 for j from 0 to 20 a[i,j] = i + jloop interchange would result in: for j from 0 to 20...

) also plays an important role in achieving better cache performance.

Overview

Example

Further reading