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 ( D-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, 0 times 218,0 times 21 C, 0 times 24 C, 0 times 2 F 4.
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:
  1. Determinar o número do bloco de memória: ç
  2. Determinar a linha do cache usando mapeamento direto.
Vamos fazer isso passo a passo para a primeira iteração:
  1. 0x200:
    • Número do bloco:
    • Linha do cache:
    • Miss: O bloco 64 é carregado na linha 0.
  2. 0x204:
    • Número do bloco: (como estamos trabalhando com blocos inteiros, consideramos 64)
    • Linha do cache:
    • Hit: Já está na linha 0.
  3. 0x208:
    • Número do bloco:
    • Linha do cache:
    • Miss: O bloco 65 é carregado na linha 1.
  4. 0x20C:
    • Número do bloco:
    • Linha do cache:
    • Hit: Já está na linha 1.
  5. 0x2F4:
    • Número do bloco:
    • Linha do cache:
    • Miss: O bloco 94 é carregado na linha 6.
  6. 0x2F0:
    • Número do bloco:
    • Linha do cache:
    • Hit: Já está na linha 6.
  7. 0x200:
    • Número do bloco: 64
    • Linha do cache: 0
    • Hit: Já está na linha 0.
  8. 0x204:
    • Número do bloco: 64
    • Linha do cache: 0
    • Hit: Já está na linha 0.
  9. 0x218:
    • Número do bloco:
    • Linha do cache:
    • Miss: O bloco 67 é carregado na linha 3.
  10. 0x21C:
    • Número do bloco:
    • Linha do cache: 3
    • Hit: Já está na linha 3.
  11. 0x24C:
    • Número do bloco:
    • Linha do cache:
    • Miss: O bloco 73 substitui o bloco na linha 1.
  12. 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%.

Exercícios relacionados