#include "inst_none.h" #include using namespace std;

const int matrixSize = 10; const int blockingFactor = 5; int a[matrixSize][matrixSize]; int b[matrixSize][matrixSize]; int c[matrixSize][matrixSize]; int main() { int i, j, k, jj, kk, r; // Initialise the matrices arbitrarily for (i=0; i < matrixSize; i++) for (j=0; j < matrixSize; j++) { b[i][j] = i + j; c[i][j] = i - j; a[i][j] = 0; } // Work out a = b * c, using a blocking algorithm jj = 0; kk = 0; while (jj < matrixSize) { while (kk < matrixSize) { for (i=0; i < matrixSize; i++) for (j=jj; j < jj + blockingFactor; j++) { r = 0; for (k=kk; k < kk + blockingFactor; k++) { INST_R(b[i][k]); INST_R(c[k][j]); r += b[i][k] * c[k][j]; } INST_R(a[i][j]); a[i][j] = a[i][j] + r; INST_W(a[i][j]); } kk += blockingFactor; } kk = 0; jj += blockingFactor; } // Display the product for (i=0; i < matrixSize; i++) { for (j=0; j < matrixSize; j++) cerr << a[i][j] << ' '; cerr << endl; } }

Create an instrumented source code (obvious.cc) which implements matrix multiplication (row-column multiplication). In order to quickly complete the task, create a copy of blocking.cc and replace the central part with the new implementation. Suppose matrixSize and blockingFactor in blocking.cc are respectively 6 and 2. List all the instrumented codes in blocking.cc line by line in execution order (indicate the exact number of array index). It should look like:

INST_R(b[0][0]) INST_R(c[0][0]) ... ... ... INST_W(a[3][3]) 

If time permits, consider and answer the following two questions.

Briefly explain your understanding of cache-friendly programs.

Name one programming technique that improves cache-friendliness.