Considere um computador com um espaço de endereçamento de 12-bits (isto é, cada endereço de memória tem 12 bits de largura) e a memória é byte endereçável. A organização hierárquica de memória tem um cache de dados (
-cache) com capacidade de 8 blocos, onde cada bloco do cache é de 8 bytes (excluindo qualquer overhead).
Durante a execução de um determinado programa, o processador emite uma sequência de referências de leitura de memória. A string de referência de memória é demonstrada na sequência de endereços a seguir: 0x200, 0x204, 0x208, 0x20C, 0x2F4, 0x2F0, 0x200, 0x204,
.
Este padrão de acesso é repetido quatro (4) vezes (como um laço que itera 4 vezes).
a) Simule a execução do fragmento de código ilustrado acima, considerando a organização de memória descrita e apresente como resposta a configuração final do cache após a execução de cada iteração do laço. Considere que o cache está inicialmente vazio (limpo) e com função de mapeamento direto. Calcule a taxa de acerto (hit rate) da execução.
b) Repita o item (a), considerando um cache de mapeamento totalmente associativo e algoritmo de substituição LRU.
c) Repita o item (a), considerando um cache de mapeamento associativo por conjunto de 4vias e algoritmo de substituição LRU.
Durante a execução de um determinado programa, o processador emite uma sequência de referências de leitura de memória. A string de referência de memória é demonstrada na sequência de endereços a seguir: 0x200, 0x204, 0x208, 0x20C, 0x2F4, 0x2F0, 0x200, 0x204,
Este padrão de acesso é repetido quatro (4) vezes (como um laço que itera 4 vezes).
a) Simule a execução do fragmento de código ilustrado acima, considerando a organização de memória descrita e apresente como resposta a configuração final do cache após a execução de cada iteração do laço. Considere que o cache está inicialmente vazio (limpo) e com função de mapeamento direto. Calcule a taxa de acerto (hit rate) da execução.
b) Repita o item (a), considerando um cache de mapeamento totalmente associativo e algoritmo de substituição LRU.
c) Repita o item (a), considerando um cache de mapeamento associativo por conjunto de 4vias e algoritmo de substituição LRU.
Passo 1
Então, a gente tem uma questão sobre como a memória do computador funciona, especificamente sobre como o cache de dados armazena e acessa informações. Vamos precisar entender conceitos como endereçamento de memória, mapeamento direto de cache e como calcular a taxa de acerto (hit rate). O exercício pede para simular como o cache vai se comportar durante a execução de um programa, mostrando como ele muda a cada repetição de um laço e, no final, calcular quão eficiente ele foi em encontrar os dados que o processador pediu.
Passo 2
Primeiro, vamos entender as especificações:
- Espaço de endereçamento de 12 bits: Isso significa que há
endereços possíveis de memória, de 0x000 a 0xFFF. - Memória byte endereçável: Cada endereço aponta para um byte específico na memória.
- Cache de dados (D-cache):
- Capacidade de 8 blocos: O cache pode armazenar 8 blocos de dados.
- Tamanho de cada bloco: 8 bytes.
Como o cache está usando mapeamento direto, cada bloco de memória vai mapear para exatamente um bloco no cache.
Passo 3
Vamos calcular quantos blocos de memória existem:
- Tamanho total da memória:
- Tamanho de cada bloco no cache: 8 bytes
- Número de blocos de memória:
blocos
Como o cache tem 8 blocos, vamos determinar como os blocos de memória serão mapeados para o cache usando mapeamento direto:
- Fórmula do mapeamento direto:
- Número de linhas no cache: 8
Passo 4
Agora, vamos analisar a sequência de endereços fornecida e ver como eles se mapeiam para o cache:
Sequência de endereços:
0x200, 0x204, 0x208, 0x20C, 0x2F4, 0x2F0, 0x200, 0x204, 0x218, 0x21C, 0x24C, 0x2F4
Essa sequência se repete 4 vezes. Vamos focar em uma iteração primeiro e depois repetir o processo.
Para cada endereço:
- Determinar o número do bloco de memória:
- Determinar a linha do cache usando mapeamento direto.
Vamos fazer isso passo a passo para a primeira iteração:
- 0x200:
- Número do bloco:
- Linha do cache:
- Miss: O bloco 64 é carregado na linha 0.
- Número do bloco:
- 0x204:
- Número do bloco:
(como estamos trabalhando com blocos inteiros, consideramos 64) - Linha do cache:
- Hit: Já está na linha 0.
- Número do bloco:
- 0x208:
- Número do bloco:
- Linha do cache:
- Miss: O bloco 65 é carregado na linha 1.
- Número do bloco:
- 0x20C:
- Número do bloco:
- Linha do cache:
- Hit: Já está na linha 1.
- Número do bloco:
- 0x2F4:
- Número do bloco:
- Linha do cache:
- Miss: O bloco 94 é carregado na linha 6.
- Número do bloco:
- 0x2F0:
- Número do bloco:
- Linha do cache:
- Hit: Já está na linha 6.
- Número do bloco:
- 0x200:
- Número do bloco: 64
- Linha do cache: 0
- Hit: Já está na linha 0.
- 0x204:
- Número do bloco: 64
- Linha do cache: 0
- Hit: Já está na linha 0.
- 0x218:
- Número do bloco:
- Linha do cache:
- Miss: O bloco 67 é carregado na linha 3.
- Número do bloco:
- 0x21C:
- Número do bloco:
- Linha do cache: 3
- Hit: Já está na linha 3.
- Número do bloco:
- 0x24C:
- Número do bloco:
- Linha do cache:
- Miss: O bloco 73 substitui o bloco na linha 1.
- Número do bloco:
- 0x2F4:
- Número do bloco: 94
- Linha do cache: 6
- Hit: Já está na linha 6.
Resposta
Após a primeira iteração do laço, a configuração final do cache é:
Linha do Cache | Bloco de Memória |
---|---|
0 | 64 |
1 | 73 |
2 | - |
3 | 67 |
4 | - |
5 | - |
6 | 94 |
7 | - |
Taxa de acerto (Hit Rate) na primeira iteração:
- Total de acessos: 12
- Hits: 7
- Hit Rate:
Repetindo o processo para as 4 iterações, a configuração final do cache e a taxa de acerto permanecem semelhantes, com possíveis variações dependendo das substituições, mas a taxa de acerto geral será em torno de 58,33%.