Inefficient matrix access pattern detected that can be fixed through loop tiling.
Apply loop tiling to the loop nest.
Inefficient memory access patterns and low locality of reference are the main reasons for low performance on modern computer systems. Matrices are stored in a row-major order in C and column-major order in Fortran. Iterating over them column-wise (in C) and row-wise (in Fortran) is inefficient, because it uses the memory subsystem suboptimally.
Nested loops that iterate over matrices in an inefficient manner can be optimized by applying loop tiling. In contrast to loop interchange, loop tiling doesn't remove the inefficient memory access, but instead breaks the problem into smaller subproblems. Smaller subproblems have a much better locality of reference and are faster to solve. Using loop tiling, the pressure on the memory subsystem due to inefficient matrix access is decreased which leads to improvement in program speed.
Note
The benefit of loop tiling directly depends on the size of the dataset. Large datasets profit from loop tiling a lot, in contrast to small datasets that don't profit that much.
The following code shows two nested loops. The matrix B is accessed
column-wise, which is
inefficient. Loop interchange doesn't help
either, because fixing the inefficient memory access pattern for B would
introduce an inefficient memory access pattern for A.
void example(double **A, double **B, int n) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
A[i][j] = B[j][i];
}
}
}After applying loop tiling, the locality of reference is improved and the performance is better. The tiled version of this loop nest is as follows:
for (int ii = 0; ii < n; ii += TILE_SIZE) {
for (int jj = 0; jj < n; jj += TILE_SIZE) {
for (int i = ii; i < MIN(ii + TILE_SIZE, n); i++) {
for (int j = jj; j < MIN(jj + TILE_SIZE, n); j++) {
A[i][j] = B[j][i];
}
}
}
}