Hierarquia de Memoria e Cache

O Problema da Lacuna Processador-Memoria

A velocidade dos processadores cresceu exponencialmente a partir dos anos 1980, mas a velocidade da DRAM nao acompanhou esse ritmo. Esse fenomeno, chamado memory wall, cria uma lacuna cada vez maior: o processador consegue consumir dados muito mais rapido do que a memoria principal consegue fornecê-los.

A solucao arquitetural e a hierarquia de memoria: uma serie de niveis de armazenamento com velocidade decrescente, capacidade crescente e custo por bit decrescente.

  Velocidade   Capacidade   Custo/bit
  maxima       minima       maximo
     |            |            |
     v            v            v
  ┌──────────────────┐
  │  Registradores   │  ~1 ns     ~1 KB     $$$$$$
  ├──────────────────┤
  │   Cache L1       │  ~2 ns     32-64 KB  $$$$$
  ├──────────────────┤
  │   Cache L2       │  ~5 ns     256 KB-1 MB $$$$
  ├──────────────────┤
  │   Cache L3       │  ~10 ns    4-64 MB   $$$
  ├──────────────────┤
  │ Memoria Principal│  ~50 ns    8-64 GB   $$
  │    (DRAM)        │
  ├──────────────────┤
  │  Armazenamento   │  ~100 us   256 GB-   $
  │  (SSD/HDD)       │            4 TB
  └──────────────────┘
     ^            ^            ^
     |            |            |
  Velocidade   Capacidade   Custo/bit
  minima       maxima       minimo

Principio da Localidade

A hierarquia de memoria so funciona porque os programas exibem localidade de referencia — a tendência de acessar dados e instrucoes em padroes previsiveis. Ha dois tipos fundamentais:

• Localidade temporal: se um dado foi acessado recentemente, e provavel que seja acessado novamente em breve. Exemplo: variaveis de controle em loops (i, sum).
• Localidade espacial: se um dado foi acessado, e provavel que dados em enderecos proximos sejam acessados em breve. Exemplo: elementos consecutivos de um array, instrucoes sequenciais.

// Exemplo: este codigo exibe ambos os tipos de localidade
int soma_array(int *arr, int n) {
    int sum = 0;           // localidade temporal: sum acessado N vezes
    for (int i = 0; i < n; i++) {
        sum += arr[i];       // localidade espacial: arr[0], arr[1], arr[2]...
    }                        // localidade temporal: i incrementado N vezes
    return sum;
}

Organizacao do Cache

Um cache e uma memoria SRAM pequena e rapida que armazena copias dos dados mais recentemente acessados da memoria principal. A questao central e: dado um endereco de memoria, como o cache decide onde armazenar esse dado e como encontrá-lo depois?

Existem tres estrategias de mapeamento:

Mapeamento Direto (Direct-Mapped)

Cada bloco de memoria so pode ir para uma unica posicao no cache, determinada por indice = endereco_bloco mod numero_linhas.

  Endereco (32 bits):
  ┌──────────┬──────────┬──────────┐
  │   Tag    │  Index   │  Offset  │
  │ (20 bits)│ (8 bits) │ (4 bits) │
  └──────────┴──────────┴──────────┘
                  │
                  v
  Cache (256 linhas, blocos de 16 bytes):
  ┌─────┬──────────┬────────────────────┐
  │Valid│   Tag    │   Dados (16 bytes) │  Linha 0
  ├─────┼──────────┼────────────────────┤
  │Valid│   Tag    │   Dados (16 bytes) │  Linha 1
  ├─────┼──────────┼────────────────────┤
  │ ... │   ...    │       ...          │
  ├─────┼──────────┼────────────────────┤
  │Valid│   Tag    │   Dados (16 bytes) │  Linha 255
  └─────┴──────────┴────────────────────┘

  Vantagem: simples e rapido (1 comparacao)
  Desvantagem: conflitos — dois blocos que mapeiam
               para a mesma linha se expulsam mutuamente

Cache Totalmente Associativo (Fully Associative)

Qualquer bloco pode ir para qualquer linha do cache. Nao ha indice — busca compara a tag com todas as linhas simultaneamente (usando CAM — Content Addressable Memory).

• Vantagem: maximo de flexibilidade, sem conflitos
• Desvantagem: custo proibitivo para caches grandes (muitos comparadores em paralelo)
• Uso: TLBs (Translation Lookaside Buffers) e caches muito pequenos

Cache Associativo por Conjuntos (Set-Associative)

Compromisso entre direto e totalmente associativo. O cache e dividido em conjuntos (sets), cada um com N linhas (N-way). O indice seleciona o conjunto; dentro do conjunto, qualquer linha pode ser usada.

  Endereco:
  ┌──────────┬──────────┬──────────┐
  │   Tag    │Set Index │  Offset  │
  └──────────┴──────────┴──────────┘
                  │
                  v
  Set 0: ┌─────┬─────┬──────┐ ┌─────┬─────┬──────┐
         │Valid│ Tag │Dados │ │Valid│ Tag │Dados │   Way 0 e Way 1
         └─────┴─────┴──────┘ └─────┴─────┴──────┘
  Set 1: ┌─────┬─────┬──────┐ ┌─────┬─────┬──────┐
         │Valid│ Tag │Dados │ │Valid│ Tag │Dados │
         └─────┴─────┴──────┘ └─────┴─────┴──────┘
  ...

  Tipico em CPUs modernas:
  L1: 8-way, L2: 8-16 way, L3: 16-way

Politicas de Escrita

Quando o processador escreve um dado que esta no cache, ha duas politicas para manter a coerência com a memoria principal:

• Write-through: toda escrita no cache e imediatamente propagada para a memoria principal. Simples, mas gera muito trafego no barramento. Pode usar um write buffer para amortecer.
• Write-back: a escrita so ocorre no cache. A linha e marcada como dirty (modificada). So quando a linha e substituida (evicted) o dado e escrito de volta na memoria principal. Reduz trafego, mas adiciona complexidade.

Quando uma escrita resulta em miss:

• Write-allocate: traz o bloco para o cache e depois escreve nele (comum com write-back)
• No-write-allocate (write-around): escreve direto na memoria principal sem trazer para o cache (comum com write-through)

Tipos de Cache Miss

Os misses de cache sao classificados em tres categorias (os "tres Cs"):

1. Compulsory (cold) miss: ocorre no primeiro acesso a um bloco. Inevitavel — o dado nunca esteve no cache. Pode ser reduzido com prefetching.
2. Capacity miss: ocorre quando o cache nao consegue conter todos os blocos necessarios ao mesmo tempo. O working set do programa excede o tamanho do cache. Solucao: cache maior.
3. Conflict miss: ocorre em caches de mapeamento direto ou set-associative quando dois blocos frequentemente usados mapeiam para o mesmo conjunto/linha. Nao ocorre em caches totalmente associativos. Solucao: aumentar a associatividade.

Politicas de Substituicao

Quando ocorre um miss e o conjunto esta cheio, e preciso escolher qual linha substituir:

• LRU (Least Recently Used): substitui a linha menos recentemente acessada. Otimo para localidade temporal, mas complexo de implementar para alta associatividade (precisa manter a ordem de acesso).
• Pseudo-LRU: aproximacao do LRU usando bits de arvore. Comum em caches 8-way e 16-way.
• Random: escolhe uma linha aleatoriamente. Surpreendentemente eficaz e simples de implementar.
• FIFO: substitui a linha mais antiga. Nao considera frequencia de uso.

No harness.os

A hierarquia de memoria e o conceito de cache sao analogias diretas para a arquitetura de conhecimento do harness.os:

• Cache L1 = CLAUDE.md: acesso instantâneo (esta no contexto), capacidade limitada. Contem as regras e informacoes mais importantes.
• Cache L2 = Regras e workflows no MCP: acesso rapido (uma tool call), capacidade moderada. Carregado sob demanda com get_rules() e get_workflow().
• Memoria principal = Knowledge base completa: acesso mais lento (queries SQL), capacidade grande. Todo o conhecimento acumulado.
• Localidade temporal: handoffs recentes sao mais relevantes que handoffs antigos — exatamente como o LRU.
• Localidade espacial: ao buscar conhecimento de um dominio, informacoes de dominios vizinhos geralmente tambem sao relevantes.
• Write-back vs write-through: o harness.os usa "write-through" para decisoes criticas (log imediato no banco) e "write-back" para learnings que podem acumular antes de persistir.

Exercicios

1. Um processador tem cache L1 de 32 KB com blocos de 64 bytes e mapeamento direto. Quantas linhas o cache possui? Quantos bits sao necessarios para tag, indice e offset em enderecos de 32 bits?
2. Dois arrays de 4096 inteiros (16 KB cada) sao acessados alternadamente em um loop. O cache L1 tem 32 KB e mapeamento direto. Pode haver conflict misses? Justifique.
3. Compare LRU e Random como politicas de substituicao para um cache L1 8-way. Qual a complexidade de implementacao de cada uma em hardware?
4. Um programa tem hit rate de 97% no L1 (2 ciclos) e 90% no L2 (10 ciclos). O acesso a memoria principal custa 100 ciclos. Calcule o tempo medio de acesso a memoria (AMAT).
5. Explique por que aumentar a associatividade de um cache reduz conflict misses mas aumenta o tempo de hit.

Resumo

• A hierarquia de memoria resolve a lacuna processador-memoria com niveis de velocidade/capacidade/custo decrescente
• Localidade temporal e espacial sao a base para o funcionamento eficiente do cache
• Mapeamento direto (simples, conflitos), set-associative (equilibrio), fully-associative (flexivel, caro)
• Write-through propaga escritas imediatamente; write-back acumula e escreve ao substituir
• Tres tipos de miss: compulsory (frio), capacity (tamanho insuficiente), conflict (colisao de mapeamento)
• Politicas de substituicao: LRU, pseudo-LRU, random, FIFO