Loop Tiling - Example

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, b, c; int n = 100; for (i = 0; i < n; i++) { c = 0; for (j = 0; j < n; j++) { c = c + a * b; } }

After we apply loop tiling using 2 * 2 blocks, our code looks like:

int i, j, x, y, a, b, c; int n = 100; for (i = 0; i < n; i += 2) { c = 0; c = 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 = c + a * b; } } } }

The original loop iteration space is n by n. The accessed chunk of array a 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) also plays an important role in achieving better cache performance.