Snippet

Cache-bewusste Matrixdurchlauf-Optimierung durch Schrittweitenanpassung

C-Arrays werden im zusammenhängenden Speicher in zeilenweiser Anordnung (Row-Major) abgelegt. Naive Matrixoperationen mit großen Schrittweiten verursachen erhebliche L1/L2-Cache-Misses. Matrix-Tiling (Blocking) unterteilt große Array-Durchläufe in Teilmatrix-Blöcke, die vollständig in L1-Cache-Zeilen passen, was Speicherbandbreiten-Engpässe drastisch reduziert.

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

Erklärung

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

Iteriert in Schritten der block_size durch Zeilen-Kacheln, um den Arbeitsspeicher zu partitionieren.

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

Iteriert durch Spalten-Kacheln, um Teilmatrizen passend zu CPU-Cache-Line-Grenzen zu isolieren.

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

Verarbeitet Zeilen innerhalb des lokalen Blocks, wo Speicheradressen im L1-Cache verbleiben.

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

Führt die Matrix-Transponierung mit garantierter hoher lokaler Cache-Räumlichkeit aus.

Vorheriges Snippet Nächstes Snippet

Mehr C-Übungen für Experten →

Cache-bewusste Matrixdurchlauf-Optimierung durch Schrittweitenanpassung

Verwandt