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:
- Definir o que é cache totalmente associativa.
- Definir o que é cache associativa por conjunto (N-way set-associative).
- 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
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
bytes. - Para localizar se um endereço está na cache, normalmente dividimos o endereço em três campos (dependendo da organização):
-
: identifica o deslocamento dentro do bloco; tem bits. -
: identifica qual linha (ou conjunto) da cache deve ser consultada; tem bits. -
: 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:
. - 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
e bloco bytes. O número de linhas é Então tem bits e tem bits. Para um endereço de bits, a tag tem 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
e . - Divisão do endereço:
. O campo continua com bits; o restante do endereço é tag. - Busca: ao acessar a cache, o controlador compara a
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
e bytes temos linhas. O tem bits, então a ocupa bits. Observe que agora não existe 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
conjuntos; cada conjunto contém linhas (as 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 linhas. - Parâmetros:
-
: grau de associatividade (por ex. -way, -way). -
: número de conjuntos. Relação: , onde é número total de linhas.
-
- Divisão do endereço:
. -
: bits. -
: bits. -
: bits restantes.
-
- Exemplo numérico (continuação): com
, bytes temos linhas. - Para
-way: então conjuntos. tem bits, tem bits, logo tem bits.
- Para
- Operação: ao acessar, usa-se o
para escolher o conjunto (um pequeno número de linhas), e compara-se a tag com as tags daquele conjunto (comparações em paralelo somente dentro do conjunto). - Vantagem: reduz conflitos em relação ao direto mapeado (especialmente com
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 (
possibilidades). - Diretamente mapeada: mínima flexibilidade (exatamente 1 linha).
- Número de comparadores (complexidade hardware por acesso):
- Totalmente associativa: comparadores =
(ou uso de CAM) — caro. - N-way: comparadores =
(paralelos dentro do conjunto) — custo cresce com . - Direto-mapeada: comparador =
— muito barato.
- Totalmente associativa: comparadores =
- 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
. - 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
linhas ( ) e blocos de memória com endereços cujos índices mod sejam todos iguais; então sequências alternadas de acessos a dois blocos que mapeiam ao mesmo índice causarão misses repetidos (thrashing). Numa -way com (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):
- Identifique
(tamanho da cache), (tamanho do bloco) e a largura do endereço (por ex. bits). - Calcule
(nº de linhas). - Se for direto-mapeada:
, , . - Se for totalmente associativa:
, (não há index). - Se for
-way: , , , restante. - 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).
- 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
e
, 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
bits,
,
bytes temos
bits e
bits.
Cache associativa por conjunto (N-way): a cache é dividida em
conjuntos com
linhas cada; o endereço divide-se em
, o bloco mapeia para um conjunto e pode ocupar qualquer das
linhas desse conjunto; exemplo: com
,
bytes e
-way temos
,
,
,
e
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 =
por acesso).