## A Tiling Demo

Over the past (too many) days I've been preparing my presentation for the ACCU 2009 conference. At one point I wanted to show how loop tiling increases locality of reference and therefore cache hits. Surprisingly, I could not find a demo on the web, so I built one from scratch. Here are two applets demonstrating memory accesses during a matrix raise to the power of two operation.

### Normal Loop

**const**

**int**N = 12;

**double**a[N][N], r[N][N];

**for**(

**int**i = 0; i < N; i++)

**for**(

**int**j = 0; j < N; j++) {

r[i][j] = 0;

**for**(

**int**k = 0; k < N; k++)

r[i][j] += a[i][k] * a[k][j];

}

### Loop with Tiling

**const**

**int**N = 12;

**const**

**int**TILE = 4;

**double**a[N][N], r[N][N];

**for**(

**int**i = 0; i < N; i += TILE)

**for**(

**int**j = 0; j < N; j += TILE)

**for**(

**int**k = 0; k < N; k += TILE)

**for**(

**int**ii = i; ii < i + TILE; ii++)

**for**(

**int**jj = j; jj < j + TILE; jj++) {

r[ii][jj] = 0;

**for**(

**int**kk = k; kk < k + TILE; kk++)

r[ii][jj] += a[ii][kk] * a[kk][jj];

}

**
This browser does not have a Java Plug-in.
Get the latest Java Plug-in here.
**

I elected to write the code in Processing; you can download it from this link. Adopting Processing proved to be a good choice; getting the application up and running was easy, although converting the multiplication loops to work inside Processing's frame loop was a bit tricky. Even better, by adding a few more lines of code I converted the result into a movie. Here are the magic incantations.

// [...]

MovieMaker mm =

**new**MovieMaker(

**this**, width, height, "tiledemo.mov", 30,

MovieMaker.ANIMATION, MovieMaker.LOSSLESS);

// [...]

mm.addFrame();

// [...]

mm.finish();

Note: the original version of this blog entry contained a matrix by a vector multiplication. The first comments refer to the original version.