8 <§5.3> Defina caches totalmente associativas e associativas por conjunto. Dê exemplos e compare com caches diretamente mapeadas.

Passo 1

O enunciado pede três coisas claras:
  1. Definir o que é cache totalmente associativa.
  2. Definir o que é cache associativa por conjunto (N-way set-associative).
  3. Dar exemplos e comparar esses dois tipos com caches diretamente mapeadas.
Não há dados numéricos fixos no enunciado, então usarei exemplos numéricos ilustrativos para deixar tudo concreto.

Passo 2

Conceitos básicos que vamos usar (explicação passo a passo, sem pular etapas):
  • Um endereço de memória é uma sequência de bits que identifica um byte. Para exercícios padrão vamos supor um espaço de endereçamento de 32 bits, mas o raciocínio vale para qualquer largura.
  • Uma cache é organizada em linhas (ou blocos). Cada linha guarda um bloco de memória contínuo de tamanho B bytes.
  • Para localizar se um endereço está na cache, normalmente dividimos o endereço em três campos (dependendo da organização):
    • \text{offset}: identifica o deslocamento dentro do bloco; tem \log_2 B bits.
    • \text{index}: identifica qual linha (ou conjunto) da cache deve ser consultada; tem \log_2(\text{nº linhas ou nº conjuntos})ºº bits.
    • \text{tag}: os bits restantes do endereço, usados para comparar se o conteúdo daquela linha é o bloco que queremos.
  • Hit: o bloco está na cache (tag bate e válid bit = 1). Miss: não está; aí trazemos o bloco da memória e possivelmente substituímos outra linha.
  • Substituição: quando há múltiplas linhas candidatas (associatividade > 1), precisamos de uma política de substituição (LRU, pseudo-LRU, aleatória, etc.).
Esses conceitos são essenciais para entender as três organizações (direto mapeada, totalmente associativa, por conjunto). A seguir eu defino cada uma e mostro exemplos numéricos.

Passo 3

Cache diretamente mapeada (breve revisão, pois vou comparar depois):
  • Regra de posicionamento: cada bloco de memória só pode ir para uma linha específica da cache. O índice é simplesmente o número da linha.
  • Divisão do endereço: \text{tag} \;|\; \text{index} \;|\; \text{offset}.
  • Vantagem: hardware simples e acesso muito rápido (apenas uma comparação de tag por acesso).
  • Desvantagem: alta probabilidade de “conflict misses” quando dois blocos diferentes mapeiam para a mesma linha.
  • Exemplo numérico (ilustrativo): seja uma cache de tamanho C = 8\,\text{KiB} e bloco B = 32 bytes. O número de linhas é L = \frac{C}{B} = \frac{8192}{32} = 256.Então \text{offset} tem \log_2 32 = 5 bits e \text{index} tem \log_2 256 = 8 bits. Para um endereço de 32 bits, a tag tem 32-8-5 = 19 bits.
  • Como resolver exercício no prova: para cada endereço, extraia offset/index/tag e compare com a linha indicada. Se for miss, registre e atualize a linha.

Passo 4

Cache totalmente associativa (definição e explicação detalhada):
  • Regra de posicionamento: um bloco de memória pode ser colocado em qualquer linha da cache — não há índice. Há apenas \text{tag} e \text{offset}.
  • Divisão do endereço: \text{tag} \;|\; \text{offset}. O campo \text{offset} continua com \log_2 B bits; o restante do endereço é tag.
  • Busca: ao acessar a cache, o controlador compara a \text{tag} procurada com a tag de todas as linhas válidas (comparações em paralelo) — a linha que bater é o hit.
  • Substituição: como o bloco pode ficar em qualquer linha, quando a cache está cheia é necessário escolher uma linha para substituir (LRU, aleatório, etc.).
  • Vantagem: minimiza conflitos de mapeamento — reduz fortemente os conflict misses (é ótima quando blocos que competiriam por uma mesma linha numa cache direto-mapeada precisam todos permanecer).
  • Desvantagem: hardware mais caro e mais lento para grandes caches, porque cada acesso exige comparar a tag procurada com muitas tags (comparadores paralelos ou CAM) e lógica para escolher substituição.
  • Exemplo numérico (mesmos dados do passo anterior): com C = 8\,\text{KiB} e B = 32 bytes temos L = 256 linhas. O \text{offset} tem 5 bits, então a \text{tag} ocupa 32-5 = 27 bits. Observe que agora não existe \text{index} porque qualquer linha é candidata.
  • Como resolver exercício: extraia apenas tag e offset; para cada acesso, compare a tag com as tags de todas as linhas. Implementacionalmente em prova você pode assumir comparações ideais; conceitualmente cite que precisa de política de substituição.

Passo 5

Cache associativa por conjunto (N-way set-associative) — definição e exemplo passo a passo:
  • Ideia: compromisso entre totalmente associativa e diretamente mapeada. A cache é dividida em \text{S} conjuntos; cada conjunto contém \text{N} linhas (as \text{N} linhas formam a “vias” ou “ways”). Um bloco de memória mapeia para exatamente um conjunto, mas dentro desse conjunto pode ocupar qualquer uma das \text{N} linhas.
  • Parâmetros:
    • N: grau de associatividade (por ex. 2-way, 4-way).
    • \text{S}: número de conjuntos. Relação: \text{S} = \dfrac{L}{N}, onde L é número total de linhas.
  • Divisão do endereço: \text{tag} \;|\; \text{set index} \;|\; \text{offset}.
    • \text{offset}: \log_2 B bits.
    • \text{set index}: \log_2 \text{S} bits.
    • \text{tag}: bits restantes.
  • Exemplo numérico (continuação): com C = 8\,\text{KiB}, B = 32 bytes temos L = 256 linhas.
    • Para 4-way: N = 4 então \text{S} = 256/4 = 64 conjuntos. \text{offset} tem 5 bits, \text{set index} tem \log_2 64 = 6 bits, logo \text{tag} tem 32-6-5 = 21 bits.
  • Operação: ao acessar, usa-se o \text{set index} para escolher o conjunto (um pequeno número de linhas), e compara-se a tag com as \text{N} tags daquele conjunto (comparações em paralelo somente dentro do conjunto).
  • Vantagem: reduz conflitos em relação ao direto mapeado (especialmente com N maior) mas com custo e complexidade menores que totalmente associativa.
  • Desvantagem: ainda há conflitos entre blocos que caem no mesmo conjunto; substituição necessária dentro do conjunto.

Passo 6

Comparação direta e exercícios práticos — ponto a ponto, com linguagem clara:
  • Flexibilidade de posicionamento:
    • Totalmente associativa: máxima flexibilidade (qualquer linha).
    • N-way set-associative: flexibilidade limitada ao conjunto ( N possibilidades).
    • Diretamente mapeada: mínima flexibilidade (exatamente 1 linha).
  • Número de comparadores (complexidade hardware por acesso):
    • Totalmente associativa: comparadores = \text{L} (ou uso de CAM) — caro.
    • N-way: comparadores = N (paralelos dentro do conjunto) — custo cresce com N.
    • Direto-mapeada: comparador = 1 — muito barato.
  • Velocidade de acesso:
    • Direto-mapeada costuma ser mais rápido (pipeline simples).
    • Set-associative: um pouco mais lento que direto, mas aceitável para pequenos N.
    • Totalmente associativa: mais lento para caches grandes (comparações e seleção).
  • Miss types:
    • Compulsory misses: independem do mapeamento.
    • Capacity misses: acontecem se cache é pequena; afetam todos os tipos.
    • Conflict misses: alta probabilidade na direto-mapeada; reduzidos na set-associative; mínimos na totalmente associativa.
  • Quando qual usar:
    • Direto-mapeada: designs simples, caches pequenas ou quando custo/latência é crítico.
    • 2-way/4-way set-associative: compromisso prático e muito comum (boa redução de conflitos com custo razoável).
    • Totalmente associativa: usado em caches muito pequenas (TLB é um exemplo clássico) ou em situações onde conflitos são críticos e custo justifica.
  • Exemplo de conflito prático (pequeno exercício mental): suponha uma cache direta com 4 linhas ( L=4) e blocos de memória com endereços cujos índices mod 4 sejam todos iguais; então sequências alternadas de acessos a dois blocos que mapeiam ao mesmo índice causarão misses repetidos (thrashing). Numa 2-way com L=4 (2 conjuntos de 2 ways) esses dois blocos caberiam simultaneamente no mesmo conjunto e faríamos menos misses.

Passo 7

Como resolver perguntas de prova sobre isso (receita prática, passo a passo):
  1. Identifique C (tamanho da cache), B (tamanho do bloco) e a largura do endereço (por ex. 32 bits).
  2. Calcule L = C/B (nº de linhas).
  3. Se for direto-mapeada: \text{offset}=\log_2 B, \text{index}=\log_2 L, \text{tag}= \text{largura do endereço} - \text{index} - \text{offset}ç.
  4. Se for totalmente associativa: \text{offset}=\log_2 B, \text{tag}= \text{largura do endereço} - \text{offset}ç (não há index).
  5. Se for N-way: \text{S}=L/N, \text{offset}=\log_2 B, \text{set index}=\log_2 S, \text{tag}= restante.
  6. Para checar hits/misses: para cada endereço, derive tag/index/offset conforme o tipo, então compare com a(s) tag(s) na(s) linha(s) alvo(s); se miss, aplique a política de substituição indicada (ou LRU por padrão se não dito).
  7. Dica prática: desenhe uma tabela com linhas/conjuntos e atualize passo a passo na prova — isso evita erro mental e é rápido.

Passo 8

Resumo final e incentivo (rápido):
  • Conceitualmente: direto-mapeada = simples e rápido, totalmente associativa = flexível e caro, set-associativa = compromisso prático.
  • Em provas: mostre os cálculos dos campos (offset/index/tag) e simule acessos com uma pequena tabela; cite a política de substituição se necessário.
  • Você consegue — essas questões são repetitivas e viram rotina depois de uns exemplos resolvidos.

Resposta

Cache totalmente associativa: um bloco de memória pode ser colocado em qualquer linha da cache; o endereço é dividido apenas em \text{tag} e \text{offset}, a busca compara a tag procurada com as tags de todas as linhas (necessita política de substituição e hardware mais complexo); exemplo: para endereço de 32 bits, C=8\,\text{KiB}, B=32 bytes temos \text{offset}=5 bits e \text{tag}=27 bits.
Cache associativa por conjunto (N-way): a cache é dividida em \text{S} conjuntos com N linhas cada; o endereço divide-se em \text{tag}\;|\;\text{set index}\;|\;\text{offset}, o bloco mapeia para um conjunto e pode ocupar qualquer das N linhas desse conjunto; exemplo: com C=8\,\text{KiB}, B=32 bytes e 4-way temos L=256, \text{S}=64, \text{offset}=5, \text{set index}=6 e \text{tag}=21 bits.
Comparação com cache diretamente mapeada: direto-mapeada impõe posição única por bloco (índice fixo), é simples e rápida (1 comparador) mas sofre muitos conflict misses; totalmente associativa minimiza conflitos mas é caro e mais lento (comparações em todas as linhas); N-way set-associative é um compromisso prático (reduz conflitos em relação ao direto-mapeado com custo/hardware moderado, comparadores = N por acesso).

Exercícios relacionados