Impacto do Projeto de uma Memória Cache em seu Desempenho

Prévia do material em texto

Impacto do Projeto de uma Memória Cache em seu 
Desempenho 
Eduardo Menzen 
Centro de Ciências Exatas, da Natureza e de Tecnologia – Campus Universitário da 
Região dos Vinhedos – Universidade de Caxias do Sul (UCS) 
95.705-266 – Bento Gonçalves – RS – Brasil 
emenzen@ucs.br 
Abstract. This This meta-article describes the use and implementation of a 
fully configurable cache memory simulator. It also describes the simulation of 
several experiments using the developed simulator and the results obtained. 
 Resumo. Este meta-artigo descreve o uso e a implementação de um 
simulador de memória cache totalmente configurável. Também descreve a 
simulação de vários experimentos utilizando o simulador desenvolvido e os 
resultados obtidos. 
1. Utilização de um Simulador de Memória Cache 
Para realizar a análise do impacto do projeto de uma memória cache, sobre o seu 
desempenho foi desenvolvido em linguagem C um simulador de memória cache. O 
código fonte deste simulador se encontra no Anexo B. Este simulador possibilita a 
simulação de uma memória cache totalmente configurável, ou seja, é possível escolher 
ou informar os parâmetros de entrada do simulador, de forma a possibilitar várias 
configurações diferentes de memória cache. 
 Dentre os parâmetros de entrada configuráveis para uma memória cache, o 
simulador possibilita a parametrização da política de escrita, tamanho da linha, números 
de linhas, número de linhas por conjunto, política de substituição e os tempos de leitura 
e escrita na memória principal e tempo de acesso à memória cache no caso de acerto 
(hit). Dentre as políticas de escrita pode-se escolher entre as políticas write-through e 
write-back e em relação às políticas de substituição, foram implementadas as políticas 
LFU (Least Frequently Used), LRU (Least Recently Used) e Aleatória. 
 Para que seja possível simular uma memória cache, deve-se utilizar um arquivo 
de entrada nomeado oficial.cache com um endereço de 32 bits em hexadecimal em cada 
linha, acompanhado de uma letra maiúscula representando a operação de leitura “R” ou 
escrita “W”. A Figura 1 mostra um bloco de exemplo de como deve ser o layout do 
arquivo de entrada. 
 
Figura 1: Bloco do arquivo de entrada official.cache 
 
 O simulador utiliza como estrutura para representar a memória cache, uma 
matriz alocada dinamicamente, visto que a configuração de linhas da cache é 
parametrizável, desta forma cada linha da matriz alocada, representa uma linha da 
memória cache que está sendo simulada. Para a alocação desta matriz dinâmica, foi 
desenvolvida a função alocar_matriz, que recebe como parâmetros o número de linhas e 
de colunas da matriz que deve ser alocada. O número de colunas desta matriz é 
constante e não parametrizável, totalizando cinco colunas, uma coluna para identificar 
se a linha está ocupada (bit_ocupado), uma para armazenar o números de acertos de 
endereço na cache (bit_acerto), uma para armazenar quando a linha é utilizada (bit_uso), 
uma para identificar se a linha foi alterada (dirty_bit) e outra para armazenar o rótulo do 
endereço lido do arquivo de entrada. 
 Como os endereços do arquivo de entrada estão em hexadecimal, durante a 
leitura do arquivo, para cada endereço lido é verificado se o mesmo é de leitura o de 
escrita. Além disso, o simulador possui uma função que transformam este endereço em 
binário, a partir dai outras funções dividem o endereço em rótulo, conjunto e palavra. O 
tamanho dos campos em que o endereço é dividido é de acordo com os parâmetros de 
entrada informados na simulação. Após de realizada a divisão do endereço, de forma a 
simplificar a lógica de armazenamento do rótulo e a identificação do conjunto, ambos 
são transformados em decimais. 
 Identificados o rótulo e o conjunto ao qual o endereço pertence, no passo 
seguinte o algoritmo de simulação da memória cache, verifica se o rótulo já existe na 
cache através da função find_cache que recebe como parâmetros o rótulo, o conjunto, o 
número de linhas por conjunto e a matriz que representa a memória cache. A função 
verifica todas as linhas do conjunto, caso não encontre o rótulo na cache a função 
devolve o valor zero (falso), caso encontre o rótulo, então a função devolve a posição da 
linha em que se localiza o rótulo, adicionada de uma unidade. Esta adição de uma 
unidade na posição da linha se faz necessária, para evitar o retorno zero, também para a 
linha “0” da cache. 
 Caso a função find_cache retornar que o rótulo não existe ainda na memória 
cache, então através da função find_cache_livre, o simulador verifica se ainda existem 
linhas não ocupadas no conjunto do endereço que está sendo processado. Se existir linha 
livre, então o rótulo é gravado na memória cache, na posição livre. Caso não existam 
mais posições livres de uso, então o simulador substitui uma das linhas do conjunto da 
cache através da política de substituição escolhida no início da simulação. 
 A política de substituição LFU (Least Frequently Used), substitui a linha da 
cache dentro do conjunto, cujo rótulo teve menos acerto (hit). Esta verificação é 
realizada através da coluna bit_acerto, pois a mesma é incrementada cada vez que 
ocorre um hit. Desta forma a função politica_LFU verifica dentro do conjunto a linha 
que possuí o menor número de acerto e retorna a posição da mesma. 
 No caso da política de substituição LRU (Least Recently Used) a linha menos 
recente mente usada é substituída, a função politica_LRU verifica dentro do conjunto a 
linha menos recentemente usada retornando a posição da mesma. O controle da linha 
menos recentemente usada é realizado através da coluna bit_uso da matriz que 
representa a memória cache, pois a cada novo endereço lido do arquivo de entrada, uma 
variável de controle é incrementada, desta forma quando uma linha da memória cache é 
 
utilizada para escrita ou leitura, a coluna bit_uso recebe o valor desta variável de 
controle. Assim, a função politica_LRU retorna a linha que tiver o menor valor para esta 
coluna dentro do conjunto, pois as colunas com valores maiores indicam que foram 
recentemente usadas. 
 Para a política de substituição Aleatória, são utilizadas as funções srand() e 
rand() da biblioteca time.h do próprio C, de forma que a função rand() gere uma posição 
aleatória dentro do conjunto do endereço que está sendo processado. 
 
2. Impacto do Tamanho da Cache 
Nesta análise foram realizados experimentos com um bloco de 128 bytes, política de 
escrita write-through e de substituição LRU. Foram utilizados conjuntos com 
associatividade de 4 blocos (linhas) por conjunto, variando-se o número de blocos da 
cache em potências de 2, de 16 blocos até que a taxa de acerto ficou insensitiva. 
 A Figura 2 mostra o comportamento da taxa de acerto em relação ao tamanho da 
memória cache, construído à partir dos dados da tabela 1 do anexo A. Verifica-se no 
gráfico que para memórias pequenas, na ordem de 2 a 4Kbytes (2.048 e 4.096 bytes), 
qualquer alteração no tamanho da cache implica numa variação significativa na taxa de 
acerto, porém para memórias acima de 32Kbytes (32.768 bytes) qualquer acréscimo de 
tamanho na cache não resulta em ganho de taxa de acerto apreciável. 
 
 
Figura 2: Gráfico da taxa de acerto em função do tamanho da memória cache. 
 
 O comportamento acima se deve ao fato de que a partir de determinado tamanho 
de memória cache um maior número de conjuntos são mapeados na memória cache, 
porém esta grande quantidade de conjuntos na cache não irá resultar em ganho de 
 
acertos de memória cache, pois quando maior a memória cache e o número de conjuntos 
da mesma, menos endereços da memória principal serão mapeados num mesmo 
conjunto da memória cache. 
 
3. Impacto do Tamanho do Bloco 
A análise do impacto do tamanho do bloco foi utilizada uma memória cache de 
8 Kbytes com política de escrita write-through e LRU para substituição.O tamanho do 
bloco foi variado de 4 a 4 Kb bytes, em potência de 2, com associatividade de 2 linhas 
por conjunto. 
 A Figura 3 mostra o gráfico da taxa de acerto em função do tamanho do bloco, 
obtido a partir dos dados coletados e listados na Tabela 4 do Anexo A. A curva mostra 
que para uma memória cache de tamanho fixo, quanto maior o bloco à partir de 
determinado valor, a taxa de acerto cai de forma expressiva. 
 
 
Figura 3: Gráfico da taxa de acerto em função do tamanho do bloco. 
 
 O comportamento da curva acima pode ser melhor visualizado na Figura 4 com 
o tamanho do bloco em escala logarítmica e sugere que quanto maior o tamanho do 
bloco, menor será o número de linhas da cache, desta forma ser perde a vizinhança dos 
endereços que são trazidos da memória principal para a memória cache. Para a memória 
utilizada nesta análise em consulta ao gráfico da Figura 4 e com o auxilio da Tabela 4, o 
tamanho de bloco ideal seria em torno de 16 bytes de forma que a cache teria 512 linhas. 
 
 
 
Figura 4: Gráfico da taxa de acerto em função do tamanho do bloco em escala 
logarítmica. 
 
4. Impacto da Associatividade 
Na análise do impacto da associatividade, foi simulada uma memória cache de 8 Kbytes 
com um bloco com 128 bytes de tamanho, com política de escrita write-back e política 
de substituição LRU. Variou-se a associatividade entre 1 a 64 blocos por conjunto, em 
potência de 2. 
 O resultado da simulação estão tabelados na Tabela 6 do Anexo A, à partir dos 
quais foi construído o gráfico da taxa de acerto em função do número de blocos por 
conjunto (associatividade) da Figura 5. Verifica-se através do gráfico que à partir de 
certa associatividade, não existe ganho na taxa de acerto, pois o aumento do número de 
blocos por conjunto, implica no aumento da vizinhança do endereço que foi buscado na 
memória principal e mapeado na memória cache. 
 Porém uma vizinhança muito grande não se faz necessário para a maioria das 
aplicações. Na prática um aumento expressivo na associatividade implicaria numa maior 
complexidade e custo no momento de localizar um endereço na memória cache, o que 
poderia provocar lentidão no processo de busca na memória cache. 
 
 
 
Figura 5: Gráfico da taxa de acerto em função do número de blocos por 
conjunto. 
 
5. Impacto da Política de Substituição 
A análise do impacto da política de substituição foi realizada simulando uma memória 
cache com um bloco com tamanho de 128 bytes, com política de escrita write-through, 
com associatividade de 4 blocos por conjunto. O número de blocos começou com 16 
blocos e foi aumentado em potência de 2, até que a taxa de acerto ficasse insensitiva ao 
tamanho da cache. Foram repetidas as simulação, variando-se as políticas de 
substituição entre LFU, LRU e Aleatória. 
 Nas tabelas 8, 10 e 12 do Anexo A, constam os resultados dos testes, que a partir 
dos quais foi construído o gráfico da Figura 6 que representa a taxa de acerto em função 
do tamanho da memória cache. No mesmo gráfico temos o resultado para cada uma das 
políticas de substituição utilizadas em cada simulação. 
 
 
 
Figura 6: Gráfico da taxa de acerto em função do tamanho da memória cache, 
para várias políticas de substituição. 
 
 Verifica-se pelo gráfico da Figura 6, que a partir de certo tamanho de memória 
cache, o algoritmo de substituição empregado se torna irrelevante, pois a taxa de acerto 
se torna insensitiva e praticamente a mesma independentemente da política utilizada e 
do tamanho da memória cache. Isto se deve ao fato que quanto maior a memória, menos 
endereços da memória principal são mapeados num mesmo conjunto da memória cache. 
Assim não se torna relevante as diferenças entre um endereço da cache que está à mais 
tempo na mesma ou que é menos frequentemente utilizado. O que ocorre o mesmo na 
escolha de um bloco qualquer para ser substituído. 
 
6. Largura de Banda de Memória 
Foram realizados experimentos para medir o tráfego total da memória gerado por caches 
com política write-through versus write-back. Para esta simulação foram utilizadas 
memórias de 8 Kbytes e 16 Kbytes, com tamanhos de blocos com 64 e 128 bytes e 
associatividades de 2 e 4 blocos com política de substituição LRU. 
 A Tabela 1 abaixo mostra os resultados obtidos para a política de escrita write-
through, e substituição LRU. 
 
Tabela 1: Largura de banda de memória para write-through 
Tamanho 
da Cache 
(Kbyte) 
Tamanho 
do bloco 
(bytes) 
Blocos por 
Conjunto 
Leituras 
na MP 
Escritas 
na MP 
Total de 
Leituras 
Total de 
Escritas 
 
8 64 2 5170 6144 45056 6144 
8 64 4 3126 6144 45056 6144 
8 128 2 6176 6144 45056 6144 
8 128 4 3621 6144 45056 6144 
16 64 2 2615 6144 45056 6144 
16 64 4 2615 6144 45056 6144 
16 128 2 3621 6144 45056 6144 
16 128 4 2599 6144 45056 6144 
 Média dos 
valores 
3693 6144 
 
 Analisando a média dos valores acima, verificamos que na política de escrita 
write-through, cada escrita na cache resulta em escrita na memória principal. Se 
compararmos a tabela acima com a tabela 14 do anexo A, verificaremos que a politica 
de escrita write-back causa menos tráfego com a memória principal, pois não são todas 
as escritas na memória cache que resultam em escrita também na memória principal. 
 
7. Avaliação Global 
Dentre todas as simulações realizadas neste artigo, a configuração que se apresentou 
melhor para um projeto de memória cache foi a realizada no item 4 sobre o impacto da 
associatividade, que foi simulada uma memória cache com 8 Kbytes de tamanho, 
tamanho de bloco 128 bytes, com 64 blocos e associatividade de 16 ou 32 blocos por 
conjunto, com política de escrita write-back e algoritmo de substituição LRU. 
 A configuração simulada no item 4, se mostrou bastante eficiente com grande 
taxa de acerto e pequeno tempo de acesso, o que foi somente possível reproduzir com 
memórias de mais de quatro vezes o seu tamanho em outras simulações e configurações. 
 Em relação ao simulador desenvolvido, cujo código fonte se encontra no anexo 
B, não é possível simular outras configurações além das que estão no escopo deste 
artigo, pois o mesmo não está preparado para tais configurações como, por exemplo, a 
política de escrita write-through com buffer. 
 A maior dificuldade no desenvolvimento de um simulador de memória cache 
reside na escolha da estrutura que será utilizada para representar a memória cache e seus 
controles. Pois, além da estrutura ter que possibilitar a adição de controles como, por 
exemplo, o de uso da linha ou de acertos, a estrutura também deve possibilitar o 
armazenamento da estrutura de cada endereço que é processado. 
 
 
 
 
Anexo A 
A.1 Impacto do Tamanho da Cache 
 
Tabela 1 – Parâmetros da Simulação 
 
Parâmetro Valor 
Tamanho do Bloco 128 bytes 
Política de Escrita Write-through 
Algoritmo de Substituição LRU 
Associatividade 4 blocos 
 
Tabela 2 – Resultados da Simulação 
 
Número de 
Blocos 
Taxa de 
Acerto (%) 
Tempo Médio 
de Acesso (ns) 
Leituras na 
MP 
Escritas na 
MP 
16 54,0000 37,6000 23552 6144 
32 65,9805 30,4117 17418 6144 
64 92,9277 14,2434 3621 6144 
128 94,9238 13,0457 2599 6144 
256 99,9141 10,0516 44 6144 
512 99,9141 10,0516 44 6144 
1024 99,9141 10,0516 44 6144 
 
A.2 Impacto do Tamanho do Bloco 
 
Tabela 3 – Parâmetros da Simulação 
 
Parâmetro Valor 
Tamanho da Memória Cache 8 Kbytes 
Política de Escrita Write-through 
Algoritmo de Substituição LRU 
Associatividade 2 blocos 
 
Tabela 4 – Resultados da Simulação 
 
Número de 
Blocos 
Tamanho 
do Bloco 
(bytes) 
Taxa de 
Acerto (%) 
Tempo 
Médio de 
Acesso (ns) 
Leituras na 
MP 
Escritas na 
MP 
2048 4 96,8223 11,9066 1627 6144 
1024 8 96,8223 11,9066 1627 6144 
 
512 16 96,8242 11,9055 1626 6144 
256 32 89,8398 16,0961 5202 6144 
128 64 89,9023 16,0586 5170 6144 
64 128 87,9375 17,2375 6176 6144 
32 256 82,9668 20,2199 87216144 
16 512 76,9883 23,8070 11782 6144 
8 1024 71,0000 27,4000 14848 6144 
4 2048 71,0000 27,4000 14848 6144 
2 4096 62,0000 32,8000 19456 6144 
 
A.3 Impacto da Associatividade 
 
Tabela 5 – Parâmetros da Simulação 
 
Parâmetro Valor 
Tamanho da Memória Cache 8 Kbytes 
Tamanho do Bloco 128 bytes 
Número de Blocos 64 blocos 
Política de Escrita Write-back 
Algoritmo de Substituição LRU 
 
Tabela 6 – Resultados da Simulação 
 
Associatividade Taxa de 
Acerto (%) 
Tempo Médio 
de Acesso (ns) 
Leituras na 
MP 
Escritas na 
MP 
1 74,9570 25,0258 12822 3070 
2 87,9375 17,2375 6176 1537 
4 92,9277 14,2434 3621 1026 
8 89,9336 16,0398 5154 1537 
16 99,9141 10,0516 44 4 
32 99,9141 10,0516 44 4 
64 99,8828 10,0703 60 4 
 
 
 
 
 
 
 
A.4 Impacto da Política de Substituição 
Tabela 7 – Parâmetros da Simulação 
 
Parâmetro Valor 
Tamanho do Bloco 128 bytes 
Política de Escrita Write-through 
Algoritmo de Substituição LFU 
Associatividade 4 blocos 
 
Tabela 8 – Resultados da Simulação 
 
Número de 
Blocos 
Tamanho 
da Cache 
(bytes) 
Taxa de 
Acerto (%) 
Tempo 
Médio de 
Acesso (ns) 
Leituras na 
MP 
Escritas na 
MP 
16 2048 62,9766 32,2141 18956 6144 
32 4096 77,9551 23,2270 11287 6144 
64 8192 95,9219 12,4469 2088 6144 
128 16384 97,9180 11,2492 1066 6144 
256 32768 99,9141 10,0516 44 6144 
512 65536 99,9141 10,0516 44 6144 
1024 131072 99,9141 10,0516 44 6144 
 
Tabela 9 – Parâmetros da Simulação 
 
Parâmetro Valor 
Tamanho do Bloco 128 bytes 
Política de Escrita Write-through 
Algoritmo de Substituição LRU 
Associatividade 4 blocos 
 
Tabela 10 – Resultados da Simulação 
 
Número de 
Blocos 
Tamanho 
da Cache 
(bytes) 
Taxa de 
Acerto (%) 
Tempo 
Médio de 
Acesso (ns) 
Leituras na 
MP 
Escritas na 
MP 
16 2048 54,0000 37,6000 23522 6144 
32 4096 65,9805 30,4117 17418 6144 
64 8192 92,9277 14,2434 3621 6144 
128 16384 94,9238 13,0457 2599 6144 
256 32768 99,9141 10,0516 44 6144 
512 65536 99,9141 10,0516 44 6144 
1024 131072 99,9141 10,0516 44 6144 
 
Tabela 11 – Parâmetros da Simulação 
 
Parâmetro Valor 
Tamanho do Bloco 128 bytes 
Política de Escrita Write-through 
Algoritmo de Substituição Aleatória 
Associatividade 4 blocos 
 
Tabela 12 – Resultados da Simulação 
 
Número de 
Blocos 
Tamanho 
da Cache 
(bytes) 
Taxa de 
Acerto (%) 
Tempo 
Médio de 
Acesso (ns) 
Leituras na 
MP 
Escritas na 
MP 
16 2048 54,7988 37,1207 23143 6144 
32 4096 72,6992 26,3805 13978 6144 
64 8192 94,7207 13,1676 2703 6144 
128 16384 97,9141 11,2516 1068 6144 
256 32768 99,9141 10,0516 44 6144 
512 65536 99,9141 10,0516 44 6144 
1024 131072 99,9141 10,0516 44 6144 
 
A.5 Impacto de Banda de Memória 
Tabela 13 – Parâmetros da Simulação 
 
Parâmetro Valor 
Política de Escrita Write-back 
Algoritmo de Substituição LRU 
Tabela 14 – Resultados da Simulação 
 
Tamanho 
da Cache 
(Kbyte) 
Tamanho 
do bloco 
(bytes) 
Blocos por 
Conjunto 
Leituras 
na MP 
Escritas 
na MP 
Total de 
Leituras 
Total de 
Escritas 
8 64 2 5170 1537 45056 6144 
8 64 4 3126 1026 45056 6144 
8 128 2 6176 1537 45056 6144 
8 128 4 3621 1026 45056 6144 
16 64 2 2615 1537 45056 6144 
16 64 4 2615 1026 45056 6144 
16 128 2 3621 1537 45056 6144 
16 128 4 2599 1026 45056 6144 
 Média dos 
valores 
3693 1282 
 
Anexo B 
 
/* 
Memória cache 
 bit_ocupado | bit_acerto | bit_uso | bit_rotulo 
 
*/ 
 
#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 
#include <math.h> 
#include <time.h> 
#include <locale.h> 
 
#define bit_ocupado 0 
#define bit_acerto 1 
#define bit_uso 2 
#define dirty_bit 3 
#define bit_rotulo 4 
#define colunas_MC 5 
#define bool int 
#define true 1 
#define false 0 
 
 
int **alocar_matriz (int m, int n) 
{ 
 int **v, i; 
 
 v = (int **) calloc (m, sizeof(int *)); //Aloca as linhas da matriz 
 if (v == NULL) { 
 printf ("** Erro de alocação - abortando \n**"); 
 return (NULL); 
 } 
 
 for ( i = 0; i < m; i++ ) { //Aloca as colunas da matriz 
 v[i] = (int*) calloc (n, sizeof(int)); 
 if (v[i] == NULL) { 
 printf ("** Erro de alocação - abortando \n**"); 
 return (NULL); 
 } 
 } 
 return (v); 
} 
 
int **liberar_matriz (int m, int n, int **v) 
{ 
 int i; 
 if (v == NULL) return (NULL); 
 
 for (i=0; i<m; i++) free (v[i]); /* libera as linhas da matriz */ 
 free (v); /* libera a matriz */ 
 return (NULL); 
} 
 
int *alocar_vetor(int n) { 
 int *v; 
 
 
 v=(int *)calloc(n+1, sizeof(int)); 
 if (!v) { 
 printf("** Erro de alocação - abortando \n**"); 
 exit(1); 
 } 
 return v; 
} 
 
int *liberar_vetor (int n, int *v){ 
 if (v == NULL) return (NULL); 
 free(v); 
 return (NULL); 
} 
 
int verifica_potencia_2(int n){ 
 
 if (n%2 != 0) return - 1; 
 int expoente = 1; 
 while(n != 2){ 
 n = n/2; 
 if (n%2 == 0){ 
 expoente++; 
 continue; 
 } 
 else return -1; 
 } 
 return expoente; 
} 
 
void converte_hex_bin(char endereco[], int end[]){ 
 int i,j; 
 for(i=0,j=0; i<8; i++){ 
 switch(endereco[i]){ 
 case '0' : end[j] = 0; j++; end[j] = 0; j++; end[j] = 0; j++; end[j] = 0; j++; break; 
 case '1' : end[j] = 0; j++; end[j] = 0; j++; end[j] = 0; j++; end[j] = 1; j++; break; 
 case '2' : end[j] = 0; j++; end[j] = 0; j++; end[j] = 1; j++; end[j] = 0; j++; break; 
 case '3' : end[j] = 0; j++; end[j] = 0; j++; end[j] = 1; j++; end[j] = 1; j++; break; 
 case '4' : end[j] = 0; j++; end[j] = 1; j++; end[j] = 0; j++; end[j] = 0; j++; break; 
 case '5' : end[j] = 0; j++; end[j] = 1; j++; end[j] = 0; j++; end[j] = 1; j++; break; 
 case '6' : end[j] = 0; j++; end[j] = 1; j++; end[j] = 1; j++; end[j] = 0; j++; break; 
 case '7' : end[j] = 0; j++; end[j] = 1; j++; end[j] = 1; j++; end[j] = 1; j++; break; 
 case '8' : end[j] = 1; j++; end[j] = 0; j++; end[j] = 0; j++; end[j] = 0; j++; break; 
 case '9' : end[j] = 1; j++; end[j] = 0; j++; end[j] = 0; j++; end[j] = 1; j++; break; 
 case 'a' : end[j] = 1; j++; end[j] = 0; j++; end[j] = 1; j++; end[j] = 0; j++; break; 
 case 'b' : end[j] = 1; j++; end[j] = 0; j++; end[j] = 1; j++; end[j] = 1; j++; break; 
 case 'c' : end[j] = 1; j++; end[j] = 1; j++; end[j] = 0; j++; end[j] = 0; j++; break; 
 case 'd' : end[j] = 1; j++; end[j] = 1; j++; end[j] = 0; j++; end[j] = 1; j++; break; 
 case 'e' : end[j] = 1; j++; end[j] = 1; j++; end[j] = 1; j++; end[j] = 0; j++; break; 
 case 'f' : end[j] = 1; j++; end[j] = 1; j++; end[j] = 1; j++; end[j] = 1; j++; 
 } 
 } 
} 
 
int converte_bin_decimal(int bin[], int tam){ 
 int i, n, num=0; 
 for(i=tam-1, n=0; i>=0; i--, n++) 
 if(bin[i]) 
 num += pow(2,n); 
 
 return num; 
} 
 
 
void find_conjunto(int tam_rotulo, int tam_conjunto, int conjunto_bin[], int end[]){//localiza o conjunto em binário no endereço 
 int i,j; 
 for(i=tam_rotulo, j=0; i<tam_rotulo + tam_conjunto; i++, j++) 
 conjunto_bin[j] = end[i]; 
} 
 
int find_cache(int rotulo, int conjunto, int num_linhas_conj, int **MC){//verifica se o rótulo existe dentro do conjunto na cache 
 int i,inicio, fim; 
 inicio = num_linhas_conj*conjunto; 
 fim = num_linhas_conj*(conjunto + 1); 
 
 for(i=inicio; i<fim; i++){ 
 if(MC[i][bit_rotulo] == rotulo && MC[i][bit_ocupado] == 1) 
 return i+1; //se encontrar o rótulo retorna a posição do mesmo +1 senão 0 
 } 
 return 0; 
} 
 
int politica_LFU(int conjunto, int num_linhas_conj, int **MC){ //menos acerto 
 int i,inicio, fim, min, pos; 
 inicio = num_linhas_conj*conjunto; 
 fim = num_linhas_conj*(conjunto + 1); 
 min = MC[inicio][bit_acerto]; 
 pos = inicio; 
 
 for(i=inicio+1; i<fim; i++){ 
 if(MC[i][bit_acerto] < min){ 
 min = MC[i][bit_acerto]; 
 pos = i; 
 } 
 } 
 return pos; 
} 
 
int politica_LRU(int conjunto, int num_linhas_conj, int **MC){ //menos recentementeusado 
 int i,inicio, fim, min, pos; 
 inicio = num_linhas_conj*conjunto; 
 fim = num_linhas_conj*(conjunto + 1); 
 min = MC[inicio][bit_uso]; 
 pos = inicio; 
 
 for(i=inicio+1; i<fim; i++){ 
 if(MC[i][bit_uso] < min){ 
 min = MC[i][bit_uso]; 
 pos = i; 
 } 
 } 
 return pos; 
} 
 
 
int find_cache_livre(int conjunto, int num_linhas_conj, int **MC){//procura uma posição livre dentro de um conjunto 
 int i,inicio, fim; 
 inicio = num_linhas_conj*conjunto; 
 fim = num_linhas_conj*(conjunto + 1); 
 
 
 for(i=inicio; i<fim; i++){ 
 if(MC[i][bit_ocupado] == 0) 
 return i+1; //se encontrar uma posição livre retorna a posição com uma unidade a mais (para não retornar 0 para a posição 0) 
 } 
 return 0; 
} 
 
int main(void) { 
 setbuf(stdout, NULL); 
 setlocale(LC_ALL, "Portuguese"); 
 srand(time(NULL)); 
 
 bool read = true; 
 
 int i, politica_substituicao, tam_linha, num_linhas, num_linhas_conj, tam_rotulo, tam_conjunto, tam_palavra, opt = 1, pos, 
 hit_time_mc, rw_time_mp, write_back, end_escrita, end_leitura, rotulo, conjunto, escrita_mp, leitura_mp, 
 acerto_leitura, acerto_escrita, time, *rotulo_bin, *conjunto_bin, end[32], **MC; 
 
 float hit_rate, hit_rate_read, hit_rate_write, tempo_medio; //taxa de acerto de global (hit_rate), taxa de leitura 
(hit_rate_read) e taxa de escrita (hit_rate_write) 
 
 char carac, arq_saida[30], endereco[8]; 
 
 FILE *in, *out; 
 
 
 while(opt != 2){ 
 
 printf("\nInforme uma opcao:\n" 
 "1 - Informar parâmetros\n" 
 "2 - Sair\n"); 
 scanf("%d", &opt); fflush(stdin); 
 
 if(opt == 1){ 
 printf("\n***** Para a Memória Cache *****\n"); 
 
 printf("\nInforme a política de escrita:\n" 
 "0 - Write-through\n" 
 "1 - Write-back\n"); 
 while(1){ 
 scanf("%d", &write_back); fflush(stdin); 
 if(write_back == false || write_back == true) break; 
 printf("\nOpção não válida, informe novamente:\n"); 
 } 
 
 printf("\nInforme o tamanho da linha em bytes:\n"); 
 while(1){ 
 scanf("%d", &tam_linha); fflush(stdin); 
 if(verifica_potencia_2(tam_linha) == -1){ 
 printf("\nTamanho de linha inválido, informe novamente:\n"); 
 }else break; 
 } 
 
 printf("\nInforme o número de linhas:\n"); 
 while(1){ 
 scanf("%d", &num_linhas); fflush(stdin); 
 if(verifica_potencia_2(num_linhas) == -1){ 
 printf("\nNúmero de linhas inválido, informe novamente:\n"); 
 
 }else break; 
 } 
 
 printf("\nInforme o número de linhas por conjunto:\n"); 
 while(1){ 
 scanf("%d", &num_linhas_conj); fflush(stdin); 
 if(verifica_potencia_2(num_linhas_conj) == -1 && num_linhas_conj != 1){ 
 printf("\nNúmero de linhas por conjunto inválido, informe novamente:\n"); 
 }else if(num_linhas_conj > num_linhas){ 
 printf("\nNúmero de linhas por conjunto maior que o número de linhas, informe novamente:\n"); 
 }else break; 
 } 
 printf("\nInforme o tempo de acesso quando encontra (hit time):\n"); 
 scanf("%d", &hit_time_mc); fflush(stdin); 
 
 printf("\nInforme a política de escrita:\n" 
 "0 - LFU (Least Frequently Used)\n" 
 "1 - LRU (Least Recently Used)\n" 
 "2 - Aleatória\n"); 
 while(1){ 
 scanf("%d", &politica_substituicao); fflush(stdin); 
 if(politica_substituicao == 0 || politica_substituicao == 1 || politica_substituicao == 2) break; 
 printf("\nOpção não válida, informe novamente:\n"); 
 } 
 printf("\n***** Para a Memória Principal *****\n" 
 "\nInforme o tempo de leitura/escrita (em ns):\n"); 
 scanf("%d", &rw_time_mp); fflush(stdin); 
 
 printf("\nInforme um nome para o arquivo de saída:\n"); 
 gets(arq_saida); fflush(stdin); 
 
 //inicio da simulação 
 //zerar variáveis 
 end_escrita = 0; 
 end_leitura = 0; 
 escrita_mp = 0; 
 leitura_mp = 0; 
 acerto_leitura = 0; 
 acerto_escrita = 0; 
 time = 0; 
 
 tam_palavra = verifica_potencia_2(tam_linha); //número de bits para representar a palavra 
 tam_conjunto = verifica_potencia_2(num_linhas/num_linhas_conj); //número de bits para representar o conjunto 
 tam_rotulo = 32 - (tam_palavra + tam_conjunto); //retorna o número de bits para representar o rótulo 
 
 MC = alocar_matriz (num_linhas, colunas_MC);//aloca a matriz para representar a memória cache 
 
 rotulo_bin = alocar_vetor(tam_rotulo); // alocar vetor para o rotulo 
 conjunto_bin = alocar_vetor(tam_conjunto); // alocar vetor para o conjunto 
 
 in = fopen("oficial.cache","r");//abre o arquivo de leitura 
 if( in == NULL ) { 
 printf("\nArquivo não pode ser aberto\n\n"); 
 system("pause"); 
 exit(1); 
 } 
 
 while(1){ 
 time++; //variável de controle para saber qual bloco foi menos recentemente usado 
 
 
 fscanf(in, "%s", endereco);//leitura do endereço no arquivo 
 converte_hex_bin(endereco, end); 
 carac = fgetc(in); 
 if(carac == EOF) break; 
 carac = fgetc(in); 
 if(carac == 'R'){ 
 end_leitura++; 
 read=true; 
 }else{ 
 end_escrita++; 
 read=false; 
 } 
 carac = fgetc(in); 
 
 for(i=0; i<tam_rotulo; i++)//encontra o rótulo no endereço 
 rotulo_bin[i] = end[i]; 
 rotulo = converte_bin_decimal(rotulo_bin,tam_rotulo);//converte rótulo para binario 
 
 find_conjunto(tam_rotulo, tam_conjunto, conjunto_bin, end);//procura o conjunto em binário no endereço 
 conjunto = converte_bin_decimal(conjunto_bin,tam_conjunto);//converte conjunto para binario 
 
 pos = find_cache(rotulo, conjunto, num_linhas_conj, MC); //verifica se rótulo já existe na cache, se não existir retorna "0" 
senão retorna posição rótulo +1 
 if(pos){ 
 MC[pos-1][bit_acerto]++; //incrementa bit_acerto para o rótulo 
 MC[pos-1][bit_uso] = time; //marca como recem usado 
 
 if(read == true) 
 acerto_leitura++; //incrementa o numero de acertos para leitura 
 else{ 
 acerto_escrita++; //incrementa o numero de acertos para escrita 
 if(write_back) //no caso de escrita seta dirty bit se write back, senão escreve na MP (no caso de write through) 
 MC[pos-1][dirty_bit] = 1; //seta dirty bit 
 else 
 escrita_mp++; 
 } 
 } 
 else{ 
 pos = find_cache_livre(conjunto, num_linhas_conj, MC);//verifica se existe posição não usada dentro do conjunto, se não existir 
retorna "0" senão retorna posição livre +1 
 if(pos){ 
 MC[pos-1][bit_rotulo] = rotulo;//grava o rótulo na posição livre 
 MC[pos-1][bit_ocupado] = 1; //marca posição como ocupada 
 MC[pos-1][bit_uso] = time; //marca como recem usado 
 if(read) 
 leitura_mp++; //no caso de escrita sempre escreve na MP 
 else{ 
 escrita_mp++; 
 leitura_mp++; 
 } 
 } 
 else{ //aplica politia de substituiçao 
 if(politica_substituicao == 0)//politica menos acerto LFU 
 pos = politica_LFU(conjunto,num_linhas_conj,MC); 
 else{ 
 if(politica_substituicao == 1)//politica menos usado LRU 
 pos = politica_LRU(conjunto,num_linhas_conj,MC); 
 else //politica aleatória dentro do conjunto 
 pos = (rand()%num_linhas_conj + num_linhas_conj*conjunto); 
 
 } 
 if(write_back) 
 if(MC[pos][dirty_bit]){//verifica se rótulo foi alterado na cache, se alterado escreve na MP 
 escrita_mp++; 
 MC[pos][dirty_bit] = 0; //seta dirty bit como não alterado novamente 
 } 
 if(read) 
 leitura_mp++; //no caso de escrita sempre escreve na MP 
 else{escrita_mp++; 
 leitura_mp++; 
 } 
 
 MC[pos][bit_rotulo] = rotulo; 
 MC[pos][bit_uso] = time; 
 MC[pos][bit_acerto] = 0; 
 //leitura_mp++; //incrementa a leitura na memória principal 
 } 
 
 } 
 } 
 fclose(in);//fecha o arquivo de leitura 
 
 
 //Criando arquivo para mostrar os dados de entrada e saída. 
 out = fopen(arq_saida,"w");//abre arquivo de saída 
 if(out == NULL) { 
 printf("Arquivo não pode ser criado\n"); exit(1);} 
 
 fputs("########## DADOS DE ENTRADA ##########\n\n*****Memória Cache*****\n",out); 
 fputs("\nPolítica de escrita: ",out); 
 fputs(write_back == 0 ? "Write-through":"Write-back",out); 
 
 fprintf(out,"\nTamanho da linha: %d bytes" 
 "\nNúmero de linhas: %d" 
 "\nAssociatividade: %d" 
 "\nTempo de acesso quando encontra (hit time): %d ns", 
 tam_linha, num_linhas, num_linhas_conj, hit_time_mc); 
 
 fputs("\nPolítica de Substituição: ",out); 
 fputs(politica_substituicao == 0 ? "LFU (Least Frequently Used)": politica_substituicao == 1 ? "LRU (Least Recently Used)" : 
"Aleatória",out); 
 
 fprintf(out,"\n\n*****Memória Principal*****\n\nTempos de leitura/escrita: %d ns",rw_time_mp); 
 
 hit_rate_write = (float) acerto_escrita/end_escrita*100; //cálcula a taxa de acerto para escrita 
 hit_rate_read = (float) acerto_leitura/end_leitura*100; //cálcula a taxa de acerto para leitura 
 hit_rate = (float) (acerto_escrita + acerto_leitura)/(end_escrita + end_leitura)*100; //cálcula a taxa de acerto global 
 tempo_medio = hit_time_mc + (1 - hit_rate/100)*rw_time_mp; //cálcula o tempo médio de acesso da cache 
 
 
 fprintf(out,"\n\n########## DADOS DE SAÍDA ##########\n" 
 "\nTotal de endereços de entrada: %d" //1 
 "\nEndereços de escrita: %d" //2 
 "\nEndereços de leitura: %d" //3 
 "\nEscritas da memória principal: %d" //4 
 "\nLeituras da memória principal: %d" //5 
 "\nTaxa de acerto global: %0.4f%% Quantidade: %d" //6 
 "\nTaxa de acerto leitura: %0.4f%% Quantidade: %d" //7 
 
 "\nTaxa de acerto escrita: %0.4f%% Quantidade: %d" //8 
 "\nTempo médio de acesso da cache: %0.4f ns", //9 
 end_escrita + end_leitura, //1 
 end_escrita, //2 
 end_leitura, //3 
 escrita_mp, //4 
 leitura_mp, //5 
 hit_rate, (acerto_escrita + acerto_leitura), //6 
 hit_rate_read, acerto_leitura, //7 
 hit_rate_write, acerto_escrita, //8 
 tempo_medio); //9 
 
 fclose(out);//fecha arquivo de saída 
 
 
 //libera objetos criados dinamicamente 
 MC = liberar_matriz (num_linhas, colunas_MC, MC); //liberar matriz 
 rotulo_bin = liberar_vetor(tam_rotulo,rotulo_bin); //libera o vetor para o rotulo 
 conjunto_bin = liberar_vetor(tam_conjunto,conjunto_bin); //libera o vetor para o conjunto 
 } 
 } 
 return EXIT_SUCCESS; 
}