Laboratório de Blocagem: Conjunto de Trabalho e Tráfego

Blocagem: o compromisso entre caber e reutilizar

Uma GEMM quadrada N×N×N processada em blocos B×B. Blocos maiores aumentam a reutilização de cada byte carregado e reduzem o tráfego até a DRAM, mas o conjunto de trabalho de três blocos precisa caber em algum nível da hierarquia. As caches simuladas são típicas de um núcleo x86: L1 de 32 KiB e L2 de 1 MiB.

dimensão da matriz: 4096

tamanho do bloco B: 64

tipo numérico

trabalho (2N³)

—

independe da blocagem

conjunto de trabalho (3B²·s)

—

três blocos residentes

intensidade aritmética (blocado)

—

O conjunto de trabalho cabe?

L1 (32 KiB)

—

L2 (1 MiB)

—

Tráfego estimado até a DRAM

ingênuo (sem reuso de B)

—

blocado (blocos B×B)

—

mínimo (cada byte 1 vez)

—

Q_ingenuo ≈ s·(N³ + 2N²) | Q_blocado ≈ s·(2N³/B + 2N²) | Q_min ≈ 3·s·N² | barras em escala logarítmica