4 <§5.3> Para um projeto de cache mapeada diretamente com endereço de 32 bits, os bits de endereço a seguir são usados para acessar a cache.
Tag Índice Offset
31-10 9-5 4-0
a) Qualéotamanhodoblocodecache(empalavras)?
b) Quantaspalavraselaécapazdearmazenar?
c) Qual é a razão entre o total de bits exigido para essa implementação de cache e os bits de armazenamento de dados?
Considere que, desde que a alimentação foi ligada, as seguintes referências de cache endereçadas por byte são registradas:
Endereço
0 4 16 132 232 160 1024 30 140 3100
d) Quantos blocos foram substituídos ao final do acesso ao endereço 3100?
e) Qualéataxadehits?
f) Indique o estado final da cache, com cada entrada válida representada como um registro de <índice, tag, dados>.

Passo 1

O enunciado dá um sistema de cache mapeada diretamente com endereço de 32 bits e especifica como os bits do endereço são usados:
\text{Tag: bits }31\text{-}10,\qquad \text{Índice: bits }9\text{-}5,\qquad \text{Offset: bits }4\text{-}0.Í
As perguntas são:
a) Qual é o tamanho do bloco de cache (em palavras)?
b) Quantas palavras a cache é capaz de armazenar (no total)?
c) Qual é a razão entre o total de bits exigidos pela implementação da cache e os bits de armazenamento de dados? (ou seja, total bits incluindo overhead / bits “apenas dados”)
d) Dadas as referências (em bytes) 0,4,16,132,232,160,1024,30,140,3100, quantos blocos foram substituídos ao final do acesso ao endereço 3100?
e) Qual é a taxa de hits?
f) Indique o estado final da cache, com cada entrada válida como um registro \langle \text{índice},\\ \text{tag},\\ \text{dados}\rangleí.
Informações relevantes extraídas do enunciado:
  • Endereço total: 32 bits.
  • Offset: 5 bits (bits 4 0).
  • Índice: 5 bits (bits 9 5).
  • Tag: 22 bits (bits 31 10).
  • Sequência de acessos em bytes: 0,\\\ 4,\\\ 16,\\\ 132,\\\ 232,\\\ 160,\\\ 1024,\\\ 30,\\\ 140,\\\ 3100.
Observação prática (assumida para poder responder a (a) e (b)): quando o enunciado pede tamanho em “palavras”, vou assumir que uma palavra tem 4 bytes (convenção comum em problemas de arquitetura). Vou declarar isso claramente onde for usado.

Passo 2

Entender o significado dos campos e calcular o tamanho do bloco (em bytes e em palavras).
  • O campo Offset tem 5 bits. Isso significa que cada bloco contém
2^{5}=32\\ \text{bytes}.
Explicação didática: o offset seleciona a posição dentro do bloco; com 5 bits podemos endereçar 2^{5} bytes diferentes dentro do bloco, logo o bloco tem 32 bytes.
Agora converter bytes → palavras. Assumimos palavra = 4 bytes. Então o número de palavras por bloco é
\frac{32\\ \text{bytes}}{4\\ \text{bytes/word}}=8\\ \text{palavras}.

Passo 3

Calcular quantas palavras a cache armazena no total.
  • O índice tem 5 bits, logo o número de linhas (entradas) da cache é
2^{5}=32\\ \text{linhas}.
  • Cada linha armazena um bloco com 8 palavras (do Passo 2). Então o total de palavras armazenadas é
32\\ \text{linhas}\times 8\\ \text{palavras/linha}=256\\ \text{palavras}.
Também útil: capacidade de dados em bytes = 32\\ \text{linhas}\times 32\\ \text{bytes/linha}=1024\\ \text{bytes}.

Passo 4

Calcular a razão entre o total de bits exigidos pela implementação e os bits de dados (apenas armazenamento de dados).
Precisamos contar, por linha:
  • bits de dados por linha: 32 bytes =32\cdot 8=256 bits;
  • bits de tag por linha: número de bits de tag = 31-10+1=22 bits (ou simplesmente dado pelo enunciado: bits 31 10);
  • bits de controle por linha: pelo menos 1 bit de válido (assumimos apenas o bit válido; não foi pedido dirty bit etc.).
Logo bits por linha total:
256\\ (\text{dados}) + 22\\ (\text{tag}) + 1\\ (\text{válido}) = 279\\ \text{bits/linha}.á
Total para a cache inteira (32 linhas):
279\times 32 = 8928\\ \text{bits}.
Total apenas dados:
256\times 32 = 8192\\ \text{bits}.
A razão pedida (total bits / bits de dados) é
\frac{8928}{8192}=\frac{279}{256}\approx 1,08984375.
Interpretação: para cada bit de dados há um overhead extra que resulta nessa razão (≈ 8{,}98\% de overhead).

Passo 5

Explicar e fixar as fórmulas para simular os acessos (importante para as partes d–f).
Com offset =5 bits e índice =5 bits:
  • número do bloco em memória (em bytes) é
\text{block\_num}=\left\lfloor\frac{\text{address}}{2^{5}}\right\rfloor=\left\lfloor\frac{\text{address}}{32}\right\rfloor.
  • índice na cache é
\text{index} = \text{block\_num}\bmod 2^{5} = (\text{block\_num})\bmod 32.
(Equivalentemente, são os bits 9 5 do endereço.)
  • tag é
\text{tag}=\left\lfloor\frac{\text{address}}{2^{10}}\right\rfloor=\left\lfloor\frac{\text{address}}{1024}\right\rfloor,
(ou seja, bits 31 10).
Regra de decisão de hit/miss em mapeamento direto: se a linha \text{index} está inválida → miss (carrega o bloco); se válida, comparar tag: se igual → hit; se diferente → miss e substituição (evicção) do bloco antigo por novo (contabilizamos esse evento como “substituído”).
A cache começa vazia (todas entradas inválidas).

Passo 6

Simulação passo a passo dos acessos. Vou para cada endereço calcular \text{block\_num}, \text{index}, \text{tag}, decidir hit/miss e, se houver substituição, aumentar o contador de substituições.
  1. Endereço 0:
\text{block\_num}=\left\lfloor\frac{0}{32}\right\rfloor=0,\quad \text{index}=0\bmod 32=0,\quad \text{tag}=\left\lfloor\frac{0}{1024}\right\rfloor=0.
Cache[0] está inválida → miss, carregar bloco 0 em índice 0. Substituições = 0.
  1. Endereço 4:
\text{block\_num}=\left\lfloor\frac{4}{32}\right\rfloor=0,\quad \text{index}=0,\quad \text{tag}=0.
Cache[0] contém tag 0 então → hit. Substituições = 0.
  1. Endereço 16:
\text{block\_num}=\left\lfloor\frac{16}{32}\right\rfloor=0,\\ \text{index}=0,\\ \text{tag}=0.
Ainda cache[0], tag 0 → hit. Substituições = 0.
  1. Endereço 132:
\text{block\_num}=\left\lfloor\frac{132}{32}\right\rfloor=4,\quad \text{index}=4\bmod 32=4,\quad \text{tag}=\left\lfloor\frac{132}{1024}\right\rfloor=0.
Cache[4] inválida → miss, carrega bloco número 4 (tag 0) em índice 4. Substituições = 0.
  1. Endereço 232:
\text{block\_num}=\left\lfloor\frac{232}{32}\right\rfloor=7,\\ \text{index}=7,\\ \text{tag}=0.
Cache[7] inválida → miss, carrega bloco 7 em índice 7. Substituições = 0.
  1. Endereço 160:
\text{block\_num}=\left\lfloor\frac{160}{32}\right\rfloor=5,\\ \text{index}=5,\\ \text{tag}=0.
Cache[5] inválida → miss, carrega bloco 5 em índice 5. Substituições = 0.
  1. Endereço 1024:
\text{block\_num}=\left\lfloor\frac{1024}{32}\right\rfloor=32,\quad \text{index}=32\bmod 32=0,\quad \text{tag}=\left\lfloor\frac{1024}{1024}\right\rfloor=1.
Cache[0] atualmente tem tag 0 (válida) → tag diferente → miss e substituição do bloco antigo por novo (tag 1). Substituições \leftarrow 1.
  1. Endereço 30:
\text{block\_num}=\left\lfloor\frac{30}{32}\right\rfloor=0,\\ \text{index}=0,\\ \text{tag}=0.
Cache[0] tem tag 1 → tag diferente → miss e substituição (traz novamente o bloco com tag 0). Substituições \leftarrow 2.
  1. Endereço 140:
\text{block\_num}=\left\lfloor\frac{140}{32}\right\rfloor=4,\\ \text{index}=4,\\ \text{tag}=0.
Cache[4] tem tag 0 → hit. Substituições = 2.
  1. Endereço 3100:
\text{block\_num}=\left\lfloor\frac{3100}{32}\right\rfloor=96,\quad \text{index}=96\bmod 32=0,\quad \text{tag}=\left\lfloor\frac{3100}{1024}\right\rfloor=3.
Cache[0] tem tag 0 (do passo 8) → tag diferente → miss e substituição por tag 3. Substituições \leftarrow 3.
Resumo da sequência de hits/misses:
  • Hits ocorreram nos acessos aos endereços 4,\\\ 16,\\\ 140 3 hits.
  • Total acessos = 10.
  • Substituições (evicções) ocorridas = 3 (nos acessos a 1024,\\\ 30,\\\ 3100).

Passo 7

Calcular a taxa de hits.
Número de hits = 3. Número de acessos = 10. Logo a taxa de hits é
\frac{3}{10}=0,3=30\%.

Passo 8

Determinar o estado final da cache (após o acesso a 3100).
Só as linhas que foram carregadas/validadas aparecem válidas. A partir da simulação, as linhas com conteúdo válido final são (índices onde carregamos blocos): 0,\\\ 4,\\\ 5,\\\ 7. Precisamos indicar para cada uma \langle \text{índice},\\ \text{tag},\\ \text{dados}\rangleí.
Para obter o intervalo dos bytes/words armazenados em cada bloco, usar:
\text{block\_num} = \text{tag}\times 32 + \text{index},
e o bloco armazena bytes
32\cdot\text{block\_num}\\ \text{até}\\\ 32\cdot\text{block\_num}+31,é
que correspondem, em palavras de 4 bytes, às palavras
\left[\frac{32\cdot\text{block\_num}}{4},\\ \frac{32\cdot\text{block\_num}+31}{4}\right]
(8 palavras por bloco).
Calcular para cada linha válida final:
  • Índice 0: tag final = 3 (carregado pelo acesso a 3100).
    block_num =3\cdot 32+0=96. Bytes armazenados: 3072 até 3103. Em palavras (4 bytes): palavras 768 até 775 (pois 3072/4=768 e (3103\!/\!4)=775{,}75 -> inteiros 768 775).
    Então dados = palavras \{768,\dots,775\}.
  • Índice 4: tag = 0 (carregado por 132 e usado por 140).
    block_num =0\cdot 32+4=4. Bytes 128 159. Palavras 32 39.
    Dados = palavras \{32,\dots,39\}.
  • Índice 5: tag = 0 (carregado por 160).
    block_num =5. Bytes 160 191. Palavras 40 47.
    Dados = palavras \{40,\dots,47\}.
  • Índice 7: tag = 0 (carregado por 232).
    block_num =7. Bytes 224 255. Palavras 56 63.
    Dados = palavras \{56,\dots,63\}.
Todas as outras linhas permanecem inválidas (não foram carregadas).

Resposta

a) 8 palavras por bloco
b) 256 palavras no total
c) \dfrac{279}{256}\approx 1,08984375
d) 3
e) \dfrac{3}{10}=0,3=30\%
f) Estado final (cada entrada válida como \langle\text{índice},\\ \text{tag},\\ \text{dados}\rangleí):
\langle 0,\\\ 3,\\ \text{palavras }768\text{–}775\rangle
\langle 4,\\\ 0,\\ \text{palavras }32\text{–}39\rangle
\langle 5,\\\ 0,\\ \text{palavras }40\text{–}47\rangle
\langle 7,\\\ 0,\\ \text{palavras }56\text{–}63\rangle

Exercícios relacionados