Snippet

Cache-Conscious Matrix Traversal via Stride Optimization

C arrays are laid out in row-major order in contiguous memory. Naive matrix operations with large strides cause severe CPU L1/L2 cache misses. Matrix tiling (blocking) breaks down large array traversals into sub-matrix blocks that fit entirely within L1 cache lines, dramatically reducing memory bandwidth bottlenecks.

snippet.c

#include <stdio.h>
 
#define N 1024
 
void transpose_blocked(double src[N][N], double dst[N][N], int block_size) {
    for (int i = 0; i < N; i += block_size) {
        for (int j = 0; j < N; j += block_size) {
            for (int ii = i; ii < i + block_size; ++ii) {
                for (int jj = j; jj < j + block_size; ++jj) {
                    dst[jj][ii] = src[ii][jj];
                }
            }
        }
    }
}

Breakdown

for (int i = 0; i < N; i += block_size)

Iterates through row index tiles by block_size steps to partition working memory.

for (int j = 0; j < N; j += block_size)

Iterates through column index tiles to isolate sub-matrices matching CPU cache line boundaries.

for (int ii = i; ii < i + block_size; ++ii)

Processes rows within the local block where memory addresses remain resident in L1 cache.

dst[jj][ii] = src[ii][jj];

Performs matrix transpose operation with guaranteed high spatial cache locality.

Previous snippet Next snippet

More Expert C exercises →

Cache-Conscious Matrix Traversal via Stride Optimization

Related