Editing Loop nest optimization (section)

== 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.

<syntaxhighlight lang="c">
  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];
    }
  }
</syntaxhighlight>

After loop tiling is applied using 2 * 2 blocks, the code looks like:

<syntaxhighlight lang="c">
  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];
        }
      }
    }
  }
</syntaxhighlight>

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, <code>i = 1</code>, <code>j = 1 to n</code>) may cross cache lines, causing cache misses.