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];
		}

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.

import processing.video.MovieMaker;
// [...]
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.

Comments   Toot! Tweet Share