Cache

Nível              Tamanho típico    Tempo de acesso    Custo/GB
─────────────────  ────────────────  ─────────────────  ─────────
Registradores      ~1 KB             <1 ns (~1 ciclo)   $$$$$
Cache L1           32-64 KB          ~1-2 ns (1-4 cc)   $$$$
Cache L2           256 KB - 1 MB     ~3-10 ns (5-20 cc) $$$
Cache L3           4-64 MB           ~10-30 ns           $$
DRAM (RAM)         8-128 GB          ~50-100 ns           $
SSD                256 GB - 8 TB     ~50-100 μs           ¢
HDD                1-20 TB           ~5-10 ms              ¢/10

A cache explora o fato de que programas não acessam memória
de forma aleatória — eles têm LOCALIDADE.

LOCALIDADE TEMPORAL:
  Se um dado foi acessado agora, provavelmente será acessado de novo em breve.
  Exemplos:
    - Variável de loop (i) acessada em toda iteração
    - Instruções dentro de um loop executadas repetidamente
    - Contadores, acumuladores, ponteiros de estrutura

LOCALIDADE ESPACIAL:
  Se um dado foi acessado, dados em endereços próximos serão acessados em breve.
  Exemplos:
    - Percorrer um array sequencialmente: a[0], a[1], a[2], ...
    - Instruções em sequência: PC, PC+4, PC+8, ...
    - Campos de uma struct acessados em conjunto

# Exemplo em C:
for (int i = 0; i < N; i++) {    // i: localidade temporal
    sum += a[i];                  // a[i]: localidade espacial
}                                 // sum: localidade temporal

A cache mantém cópias dos dados mais recentemente acessados
(temporal) e carrega blocos inteiros de memória (espacial).

Endereço de 32 bits:
┌──────────────────┬────────────┬──────────────┐
│    Tag (20 bits)  │ Index (10) │ Offset (2)   │
└──────────────────┴────────────┴──────────────┘

Cache com 1024 linhas (2^10), cada linha = 1 word (4 bytes):

Index   Valid  Tag (20 bits)     Dados (32 bits)
─────   ─────  ────────────────  ──────────────────
  0       1    0x000A3           0xDEADBEEF
  1       0    --------          --------
  2       1    0x00072           0x12345678
  ...
 1023     1    0x000FF           0xCAFEBABE

Acesso ao endereço 0x000A3008:
  Tag    = 0x000A3
  Index  = 0000000010 (= 2)
  Offset = 00

  1. Vai à linha 2
  2. Verifica Valid = 1? Sim.
  3. Compara Tag: 0x000A3 vs 0x00072 → NÃO BATE → MISS!
  4. Busca bloco da memória principal, substitui linha 2
  5. Retorna dado ao processador

Se a Tag batesse → HIT! Retorna dado diretamente (1-2 ciclos).

Vantagem:  Simples, rápido (1 comparação)
Problema:  Conflitos — dois endereços com mesmo index competem
           pela mesma linha (conflict miss)

Cache com 512 conjuntos, 2 vias (ways) por conjunto:
Total = 512 × 2 = 1024 linhas

Endereço de 32 bits:
┌──────────────────┬────────────┬──────────────┐
│    Tag (21 bits)  │ Index (9)  │ Offset (2)   │
└──────────────────┴────────────┴──────────────┘

Set 0:  ┌─ Way 0: [V][Tag][Dados]
        └─ Way 1: [V][Tag][Dados]

Set 1:  ┌─ Way 0: [V][Tag][Dados]
        └─ Way 1: [V][Tag][Dados]
...

Acesso:
  1. Calcula index → vai ao conjunto
  2. Compara tag com TODAS as ways (em paralelo)
  3. Se alguma bater → HIT
  4. Se nenhuma bater → MISS → substitui uma way

Comparação:
  Mapeamento direto:  1-way (1 comparador) — mais rápido, mais conflitos
  2-way:              2 comparadores — bom compromisso
  4-way:              4 comparadores — menos misses, mais área/energia
  8-way:              8 comparadores — retornos decrescentes
  Fully associative:  N comparadores (N = total de linhas)
                      — sem conflict misses, mas muito caro

Típico em processadores reais:
  L1: 4-way ou 8-way (32-64 KB, prioridade: velocidade)
  L2: 8-way a 16-way (256 KB - 1 MB)
  L3: 16-way a 20-way (4-64 MB, prioridade: hit rate)

LRU (Least Recently Used):
  Substitui a linha acessada há mais tempo.
  Melhor aproveitamento da localidade temporal.
  Custo: precisa manter bits de "ordem de acesso" por conjunto.
  Para 2-way: 1 bit (trivial). Para 8-way: impraticável (exato).
  Processadores reais usam pseudo-LRU para sets grandes.

FIFO (First In, First Out):
  Substitui a linha que está na cache há mais tempo.
  Mais simples que LRU, mas pode substituir linhas ainda úteis.

Random:
  Escolhe uma way aleatória para substituir.
  Surpreendentemente bom! Apenas ~1-2% pior que LRU na prática.
  Muito simples de implementar (contador ou LFSR).
  Usado em caches L2/L3 de alguns processadores ARM.

WRITE-THROUGH:
  Toda escrita atualiza cache E memória principal simultaneamente.
  + Memória sempre consistente com a cache
  + Simples de implementar
  - Toda escrita gera tráfego para memória (lento)
  - Mitigado com write buffer (fila de escritas pendentes)

WRITE-BACK:
  Escrita atualiza APENAS a cache. Memória é atualizada
  só quando a linha é substituída (evicted).
  + Muito menos tráfego para memória (múltiplas escritas na mesma
    linha ficam só na cache)
  + Melhor desempenho
  - Dirty bit necessário (1 = linha modificada, precisa write-back)
  - Mais complexo (cache e memória podem ficar inconsistentes)

Processadores modernos: quase todos usam write-back.

WRITE-ALLOCATE (write miss):
  - Write-allocate: traz bloco para cache, depois escreve nele
    (combina com write-back)
  - No-write-allocate: escreve direto na memória sem trazer para cache
    (combina com write-through)

AMAT = Hit Time + (Miss Rate × Miss Penalty)

Exemplo 1: Cache simples
  Hit time = 1 ciclo
  Miss rate = 5% (0.05)
  Miss penalty = 100 ciclos (acesso à DRAM)

  AMAT = 1 + (0.05 × 100) = 1 + 5 = 6 ciclos

  Sem cache: 100 ciclos (todo acesso vai à DRAM)
  Com cache: 6 ciclos médios → speedup de 16.7×!

Exemplo 2: Cache multinível (L1 + L2)
  L1: hit time = 1 ciclo, miss rate = 5%
  L2: hit time = 10 ciclos, miss rate = 20% (dos misses de L1)
  DRAM: 100 ciclos

  AMAT = 1 + 0.05 × (10 + 0.20 × 100)
       = 1 + 0.05 × (10 + 20)
       = 1 + 0.05 × 30
       = 1 + 1.5
       = 2.5 ciclos

Exemplo 3: L1 + L2 + L3
  L1: 1 ciclo, 5% miss
  L2: 10 ciclos, 20% miss (local)
  L3: 30 ciclos, 30% miss (local)
  DRAM: 100 ciclos

  AMAT = 1 + 0.05 × (10 + 0.20 × (30 + 0.30 × 100))
       = 1 + 0.05 × (10 + 0.20 × 60)
       = 1 + 0.05 × 22
       = 2.1 ciclos

Três tipos de cache miss:
  Compulsory (cold): primeiro acesso ao bloco (inevitável)
  Capacity: cache cheia, blocos são substituídos
  Conflict: múltiplos endereços competem pelo mesmo set

Cache                             harness.os
─────────────────────────────     ──────────────────────────────────────
Hierarquia de memória             Hierarquia de contexto
  L1 (rápida, pequena)              Context window (prompt + tools)
  L2 (média)                         Handoff / session state
  L3 (grande, mais lenta)            Knowledge base (database)
  DRAM                               Arquivos no repositório

Cache hit                         start_session retorna handoff
  Dado já está perto                 Contexto já carregado, sem busca

Cache miss                        get_knowledge() / search_knowledge()
  Precisa buscar de longe            Precisa consultar o banco

Miss penalty                      Latência de tool call
  100 ciclos para DRAM               ~500ms para query no Neon Postgres

Localidade temporal               Sessões frequentes no mesmo projeto
  Dado acessado recentemente         Rules e knowledge já em memória
  provavelmente será de novo         pelo prompt cache do Anthropic

Localidade espacial               Concern-based knowledge loading
  Dados próximos no endereço         Carregar knowledge de concerns
  carregados juntos (bloco)          relacionados de uma vez

Write-back                        Lazy logging
  Escrita só na cache; atualiza      Acumula mudanças na sessão;
  memória quando evicted             persiste tudo no end_session

AMAT da sessão:
  Hit (handoff bom): ~1s para começar a trabalhar
  Miss (handoff vazio): ~10s buscando contexto
  Miss total (projeto novo): ~30s setup completo