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.
, 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.
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): .
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 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 palavras e tamanho total de
blocos; diga se é acerto ou falha, supondo cache inicialmente vazia.
Endereços (em decimal):
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
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
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
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:
. - Número de bits do deslocamento de bloco (block offset):
. 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:
. - 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
bits (ver demonstração nos próximos passos), porque as combinações de bits de índice+deslocamento somam
em (a) e
em (b).
Passo 3
Cálculo das quantidades de bits em cada caso (detalhado):
a) Cache com
blocos de uma palavra:
-
bits do índice . - palavras por bloco
bits do deslocamento . - bits da tag
.
b) Cache com blocos de
palavras e tamanho total
blocos:
-
bits do índice . - palavras por bloco
bits do deslocamento . - bits da tag
.
Observação prática que facilita os cálculos: todos os nossos endereços cabem em 8 bits (valores até
). 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):
Lembre: o formato completo em 32 bits é
seguido desses
bits.
Passo 5
Resolução do item (a): cache com
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
: binário 32 bits . Tag (28 bits) = . Índice (4 bits) = . Cache inicialmente vazia → falha. (Agora índice contém tag .) - Endereço
: binário . Tag = . Índice = . Inicialmente vazio → falha. (Índice passa a ter tag .) - Endereço
: binário . Tag = . Índice = . Vazio → falha. - Endereço
: binário . Tag = . Índice = . Vazio → falha. - Endereço
: binário . Tag = . Índice = . Vazio → falha. - Endereço
: binário . Tag = . Índice = . Vazio → falha. - Endereço
: binário . Tag = . Índice = . Vazio → falha. - Endereço
: binário . Tag = . Índice = . Índice atualmente contém tag (do acesso ); tags diferentes → falha por conflito (substitui por tag ). - Endereço
: binário . Tag = . Índice = . Vazio → falha. - Endereço
: binário . Tag = . Índice = . Vazio → falha. - Endereço
: binário . Tag = . Índice = . Vazio → falha. - Endereço
: binário . Tag = . Índice = . 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
palavras e
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
e a de deslocamento
. 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
: binário . Dos 8 bits: . Tag = . Índice bits . Deslocamento . Cache vazia → falha. (Carrega o bloco índice com tag , contendo as palavras com e .) - Endereço
: binário . Bits . Tag = . Índice = . . Vazia → falha. (Carrega bloco índice com tag .) - Endereço
: binário . Bits . Tag = . Índice = . . Vazia → falha. - Endereço
: binário . Bits . Tag = . Índice = . . Agora índice tem tag (carregado pelo acesso ao endereço ); mesmo tag e mesmo índice → acerto (hit). - Endereço
: binário . Bits . Tag = . Índice = . . Vazia → falha. - Endereço
: binário . Bits . Tag = . Índice = . . Vazia → falha. - Endereço
: binário . Bits . Tag = . Índice = . . Índice tem tag carregado por → mesmo tag e índice → acerto (hit). - Endereço
: binário . Bits . Tag = . Índice = . . Índice atualmente contém tag (do acesso a ); tags diferentes → falha (substitui entrada do índice por tag ). - Endereço
: binário . Bits . Tag = . Índice = . . Índice tem tag (carregado por ) → mesmo tag/índice → acerto (hit). - Endereço
: binário . Bits . Tag = . Índice = . . Vazia → falha. - Endereço
: binário . Bits . Tag = . Índice = . . Índice tem tag (do acesso a ); tags diferentes → falha (substitui com tag ). - Endereço
: binário . Bits . Tag = . Índice = . . Índice tem tag (carregado por ); tags diferentes → falha.
Resumo prático do (b): os acessos que foram acerto (hit) são os de
,
e
. Todos os demais são falhas, conforme a simulação acima.
Resposta
a)
endereço binário
, tag
, índice
— falha.
endereço binário
, tag
, índice
— falha.
endereço binário
, tag
, índice
— falha.
endereço binário
, tag
, índice
— falha.
endereço binário
, tag
, índice
— falha.
endereço binário
, tag
, índice
— falha.
endereço binário
, tag
, índice
— falha.
endereço binário
, tag
, índice
— falha.
endereço binário
, tag
, índice
— falha.
endereço binário
, tag
, índice
— falha.
endereço binário
, tag
, índice
— falha.
endereço binário
, tag
, índice
— falha.
b)
endereço binário
, tag
, índice
— falha.
endereço binário
, tag
, índice
— falha.
endereço binário
, tag
, índice
— falha.
endereço binário
, tag
, índice
— acerto.
endereço binário
, tag
, índice
— falha.
endereço binário
, tag
, índice
— falha.
endereço binário
, tag
, índice
— acerto.
endereço binário
, tag
, índice
— falha.
endereço binário
, tag
, índice
— acerto.
endereço binário
, tag
, índice
— falha.
endereço binário
, tag
, índice
— falha.
endereço binário
, tag
, índice
— falha.