1 <§5.3> As caches são importantes para fornecer uma hierarquia de memória de alto desempenho aos processadores. A seguir se encontra uma lista de referências a endereços de memória de 32 bits, dadas como endereços de palavra. 3,180,43,2,191,88,190,14, 181, 44, 186, 253
a) Para cada uma dessas referências, identifique o endereço binário, a tag e o índice dado uma cache de mapeamento direto com 16 blocos de uma palavra. Além disso, indique se cada referência é um acerto ou uma falha, supondo que a cache esteja inicialmente vazia.
b) Para cada uma dessas referências, identifique o endereço binário, a tag e o índice dado uma cache de mapeamento direto com blocos de duas palavras e um tamanho total de oito blocos. Liste também se cada referência é um acerto ou uma falha, supondo que a cache esteja inicialmente vazia.

Passo 1

O enunciado dá uma sequência de referências de endereço (endereços de palavra) e pede duas análises diferentes de mapeamento direto.
Endereços (em decimal): 3,\,180,\,43,\,2,\,191,\,88,\,190,\,14,\,181,\,44,\,186,\,253.
Perguntas:
a) Para cada referência: escreva o endereço binário (32 bits), a tag e o índice considerando uma cache de mapeamento direto com 16 blocos de uma palavra; diga se é acerto ou falha, supondo cache inicialmente vazia.
b) Para cada referência: escreva o endereço binário (32 bits), a tag e o índice considerando uma cache de mapeamento direto com blocos de 2 palavras e tamanho total de 8 blocos; diga se é acerto ou falha, supondo cache inicialmente vazia.
Informações relevantes dadas no enunciado (resumidas, sem resolver ainda): cada endereço é um endereço de palavra; a cache é direta (um único lugar por índice); a cache começa vazia.

Passo 2

Entendimento das partes importantes para resolver (como extrair tag/índice de um endereço de palavra). Vou explicar calmamente para você poder aplicar num exercício parecido na prova:
  • Os endereços são de 32 bits. Para montar o formato (tag | índice | deslocamento de bloco) precisamos saber: número de blocos e número de palavras por bloco.
  • Número de bits do índice: \log_2(\text{número de linhas/blocos})ú.
  • Número de bits do deslocamento de bloco (block offset): \log_2(\text{palavras por bloco}). Aqui, porque endereços são palavras, não precisamos subtrair bits de byte — usamos diretamente como se cada incremento de endereço andasse por palavra.
  • Número de bits da tag: 32 - (\text{bits do índice}) - (\text{bits de deslocamento})í.
  • Extração prática: escrevemos o endereço em binário 32 bits; os bits mais significativos (MSB) formam a tag, os seguintes formam o índice, e os menos significativos formam o deslocamento de bloco.
Agora vamos aplicar isso para os dois casos do enunciado. Em ambos os casos teremos tag com 28 bits (ver demonstração nos próximos passos), porque as combinações de bits de índice+deslocamento somam 4 em (a) e 4 em (b).

Passo 3

Cálculo das quantidades de bits em cada caso (detalhado):
a) Cache com 16 blocos de uma palavra:
  • \text{blocos} = 16 \Rightarrow bits do índice =\log_2(16)=4.
  • palavras por bloco =1 \Rightarrow bits do deslocamento =\log_2(1)=0.
  • bits da tag =32-4-0=28.
b) Cache com blocos de 2 palavras e tamanho total 8 blocos:
  • \text{blocos}=8 \Rightarrow bits do índice =\log_2(8)=3.
  • palavras por bloco =2 \Rightarrow bits do deslocamento =\log_2(2)=1.
  • bits da tag =32-3-1=28.
Observação prática que facilita os cálculos: todos os nossos endereços cabem em 8 bits (valores até 253). Assim, em binário 32 bits cada endereço é 24 zeros seguidos dos 8 bits do valor. Como a tag tem 28 bits, a tag será: 24 zeros seguido pelos 4 bits mais significativos dos 8 bits do valor. O índice e deslocamento vêm dos 4 bits menos significativos (para o caso (a) índice = 4 bits; para o caso (b) índice = 3 bits e deslocamento = 1 bit).

Passo 4

Convertemos cada endereço decimal dado para binário de 8 bits (os 24 MSB serão zeros). Listei aqui os 8 bits baixos de cada endereço (em grupos de 4 para facilitar a separação tag/index/deslocamento depois):
  • 3 = 0000\;0011
  • 180 = 1011\;0100
  • 43 = 0010\;1011
  • 2 = 0000\;0010
  • 191 = 1011\;1111
  • 88 = 0101\;1000
  • 190 = 1011\;1110
  • 14 = 0000\;1110
  • 181 = 1011\;0101
  • 44 = 0010\;1100
  • 186 = 1011\;1010
  • 253 = 1111\;1101
Lembre: o formato completo em 32 bits é 00000000\,00000000\,00000000 seguido desses 8 bits.

Passo 5

Resolução do item (a): cache com 16 blocos de 1 palavra (índice = 4 bits, deslocamento = 0 bits, tag = 28 bits).
Regra prática aplicada aqui: com índice 4 bits pegamos os 4 bits menos significativos do byte (os 4 mais baixos dos 8 bits mostrados) como índice; a tag será 24 zeros + os 4 bits mais significativos do byte.
Agora eu simulo cada acesso, lembrando que a cache começa vazia; portanto a primeira vez que um índice recebe uma entrada é falha; se mais tarde vier uma referência que tem o mesmo índice e a mesma tag, é acerto; se mesmo índice tiver tag diferente, é falha por conflito e a linha é substituída.
Vou mostrar para cada referência: endereço 32 bits, tag (28 bits), índice (4 bits) e se foi falha (miss) ou acerto (hit), com breve justificativa.
  • Endereço 3: binário 32 bits 00000000000000000000000000000011. Tag (28 bits) = 0000000000000000000000000000. Índice (4 bits) = 0011. Cache inicialmente vazia → falha. (Agora índice 0011 contém tag 0000\ldots0000.)
  • Endereço 180: binário 00000000000000000000000010110100. Tag = 0000000000000000000000001011. Índice = 0100. Inicialmente vazio → falha. (Índice 0100 passa a ter tag 1011.)
  • Endereço 43: binário 00000000000000000000000000101011. Tag = 0000000000000000000000000010. Índice = 1011. Vazio → falha.
  • Endereço 2: binário 00000000000000000000000000000010. Tag = 0000000000000000000000000000. Índice = 0010. Vazio → falha.
  • Endereço 191: binário 00000000000000000000000010111111. Tag = 0000000000000000000000001011. Índice = 1111. Vazio → falha.
  • Endereço 88: binário 00000000000000000000000001011000. Tag = 0000000000000000000000000101. Índice = 1000. Vazio → falha.
  • Endereço 190: binário 00000000000000000000000010111110. Tag = 0000000000000000000000001011. Índice = 1110. Vazio → falha.
  • Endereço 14: binário 00000000000000000000000000001110. Tag = 0000000000000000000000000000. Índice = 1110. Índice 1110 atualmente contém tag 0000000000000000000000001011 (do acesso 190); tags diferentes → falha por conflito (substitui por tag 0000\ldots).
  • Endereço 181: binário 00000000000000000000000010110101. Tag = 0000000000000000000000001011. Índice = 0101. Vazio → falha.
  • Endereço 44: binário 00000000000000000000000000101100. Tag = 0000000000000000000000000010. Índice = 1100. Vazio → falha.
  • Endereço 186: binário 00000000000000000000000010111010. Tag = 0000000000000000000000001011. Índice = 1010. Vazio → falha.
  • Endereço 253: binário 00000000000000000000000011111101. Tag = 0000000000000000000000001111. Índice = 1101. Vazio → falha.
Observação final do (a): nenhum acesso gerou um acerto porque não houve nenhuma referência subsequente com mesmo índice e mesma tag (além de substituições por conflito). Cada acesso foi falha conforme a simulação acima.

Passo 6

Resolução do item (b): cache com blocos de 2 palavras e 8 blocos (índice = 3 bits, deslocamento = 1 bit, tag = 28 bits).
Regra prática aqui: do byte de 8 bits do endereço (os 8 bits menos significativos), os 4 bits mais altos continuam fazendo parte da tag (juntamente com os 24 zeros prefixos), os próximos 3 bits (b3 b2 b1) são o índice e o bit menos significativo (b0) é o deslocamento dentro do bloco (0 ou 1). Um bloco armazena duas palavras: a de deslocamento 0 e a de deslocamento 1. Se um bloco é carregado (falha inicial), ele traz as duas palavras; uma referência subsequente à outra palavra do mesmo bloco (mesmo tag e mesmo índice, apenas b0 diferente) será acerto.
Vou simular passo a passo (cache inicialmente vazia):
Para cada endereço eu listo: binário 32 bits, tag (28 bits), índice (3 bits), deslocamento (1 bit), e resultado (miss/hit) com razão.
  • Endereço 3: binário 00000000000000000000000000000011. Dos 8 bits: 0000\;0011. Tag = 0000000000000000000000000000. Índice = bits b_3b_2b_1 = 001. Deslocamento b_0=1. Cache vazia → falha. (Carrega o bloco índice 001 com tag 0000\ldots, contendo as palavras com b_0=0 e b_0=1.)
  • Endereço 180: binário 00000000000000000000000010110100. Bits 1011\;0100. Tag = 0000000000000000000000001011. Índice = 010. b_0=0. Vazia → falha. (Carrega bloco índice 010 com tag 1011.)
  • Endereço 43: binário 00000000000000000000000000101011. Bits 0010\;1011. Tag = 0000000000000000000000000010. Índice = 101. b_0=1. Vazia → falha.
  • Endereço 2: binário 00000000000000000000000000000010. Bits 0000\;0010. Tag = 0000000000000000000000000000. Índice = 001. b_0=0. Agora índice 001 tem tag 0000\ldots (carregado pelo acesso ao endereço 3); mesmo tag e mesmo índice → acerto (hit).
  • Endereço 191: binário 00000000000000000000000010111111. Bits 1011\;1111. Tag = 0000000000000000000000001011. Índice = 111. b_0=1. Vazia → falha.
  • Endereço 88: binário 00000000000000000000000001011000. Bits 0101\;1000. Tag = 0000000000000000000000000101. Índice = 100. b_0=0. Vazia → falha.
  • Endereço 190: binário 00000000000000000000000010111110. Bits 1011\;1110. Tag = 0000000000000000000000001011. Índice = 111. b_0=0. Índice 111 tem tag 1011 carregado por 191 → mesmo tag e índice → acerto (hit).
  • Endereço 14: binário 00000000000000000000000000001110. Bits 0000\;1110. Tag = 0000000000000000000000000000. Índice = 111. b_0=0. Índice 111 atualmente contém tag 1011 (do acesso a 191); tags diferentes → falha (substitui entrada do índice 111 por tag 0000\ldots).
  • Endereço 181: binário 00000000000000000000000010110101. Bits 1011\;0101. Tag = 0000000000000000000000001011. Índice = 010. b_0=1. Índice 010 tem tag 1011 (carregado por 180) → mesmo tag/índice → acerto (hit).
  • Endereço 44: binário 00000000000000000000000000101100. Bits 0010\;1100. Tag = 0000000000000000000000000010. Índice = 110. b_0=0. Vazia → falha.
  • Endereço 186: binário 00000000000000000000000010111010. Bits 1011\;1010. Tag = 0000000000000000000000001011. Índice = 101. b_0=0. Índice 101 tem tag 0010 (do acesso a 43); tags diferentes → falha (substitui com tag 1011).
  • Endereço 253: binário 00000000000000000000000011111101. Bits 1111\;1101. Tag = 0000000000000000000000001111. Índice = 110. b_0=1. Índice 110 tem tag 0010 (carregado por 44); tags diferentes → falha.
Resumo prático do (b): os acessos que foram acerto (hit) são os de 2, 190 e 181. Todos os demais são falhas, conforme a simulação acima.

Resposta

a)
3: endereço binário 00000000000000000000000000000011, tag 0000000000000000000000000000, índice 0011 — falha.
180: endereço binário 00000000000000000000000010110100, tag 0000000000000000000000001011, índice 0100 — falha.
43: endereço binário 00000000000000000000000000101011, tag 0000000000000000000000000010, índice 1011 — falha.
2: endereço binário 00000000000000000000000000000010, tag 0000000000000000000000000000, índice 0010 — falha.
191: endereço binário 00000000000000000000000010111111, tag 0000000000000000000000001011, índice 1111 — falha.
88: endereço binário 00000000000000000000000001011000, tag 0000000000000000000000000101, índice 1000 — falha.
190: endereço binário 00000000000000000000000010111110, tag 0000000000000000000000001011, índice 1110 — falha.
14: endereço binário 00000000000000000000000000001110, tag 0000000000000000000000000000, índice 1110 — falha.
181: endereço binário 00000000000000000000000010110101, tag 0000000000000000000000001011, índice 0101 — falha.
44: endereço binário 00000000000000000000000000101100, tag 0000000000000000000000000010, índice 1100 — falha.
186: endereço binário 00000000000000000000000010111010, tag 0000000000000000000000001011, índice 1010 — falha.
253: endereço binário 00000000000000000000000011111101, tag 0000000000000000000000001111, índice 1101 — falha.
b)
3: endereço binário 00000000000000000000000000000011, tag 0000000000000000000000000000, índice 001 — falha.
180: endereço binário 00000000000000000000000010110100, tag 0000000000000000000000001011, índice 010 — falha.
43: endereço binário 00000000000000000000000000101011, tag 0000000000000000000000000010, índice 101 — falha.
2: endereço binário 00000000000000000000000000000010, tag 0000000000000000000000000000, índice 001 — acerto.
191: endereço binário 00000000000000000000000010111111, tag 0000000000000000000000001011, índice 111 — falha.
88: endereço binário 00000000000000000000000001011000, tag 0000000000000000000000000101, índice 100 — falha.
190: endereço binário 00000000000000000000000010111110, tag 0000000000000000000000001011, índice 111 — acerto.
14: endereço binário 00000000000000000000000000001110, tag 0000000000000000000000000000, índice 111 — falha.
181: endereço binário 00000000000000000000000010110101, tag 0000000000000000000000001011, índice 010 — acerto.
44: endereço binário 00000000000000000000000000101100, tag 0000000000000000000000000010, índice 110 — falha.
186: endereço binário 00000000000000000000000010111010, tag 0000000000000000000000001011, índice 101 — falha.
253: endereço binário 00000000000000000000000011111101, tag 0000000000000000000000001111, índice 110 — falha.

Exercícios relacionados