PWR040: Consider loop tiling to improve the locality of reference

This recommendation is part of the open catalog of best practice rules for performance that is automatically detected and reported by Codee.

Issue

Inefficient matrix access pattern detected that can be fixed through loop tiling.

Relevance

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. 

Actions

Apply loop tiling to the loop nest.

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.

Code example

The following code shows two nested loops:

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        A[i][j] = B[j][i];
    }
}

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.

By applying loop tiling, we can achieve better locality of reference and better performance:

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

After applying loop tiling, the locality of reference is improved and the performance is better. To learn more about loop tiling, visit this link. 

Related resources

• PWR039 – Consider loop interchange to improve the locality of reference and enable vectorization
• PWR010: Avoid column-major array access in C/C++