Lista 3 Infraestrutura de Hardware (cache) respostas

Prévia do material em texto

Lista 3 2020.2 
Infraestrutura de Hardware 
Ciência da Computação 
 
1) 
 
a) O tamanho de uma memória cache deve ser suficientemente pequeno para que o custo 
total médio por bit seja próximo do custo por bit da memória principal, e deve ser 
suficientemente grande para que o tempo médio de acesso à memória seja próximo ao tempo 
de acesso da memória cache. Quanto maior é a memória cache, maior é o número de portas 
envolvidas no seu endereçamento. Como resultado, memórias cache grandes tendem a ser 
ligeiramente mais lentas do que as pequenas. Como o desempenho de uma memória cache 
é muito sensível à natureza da carga de trabalho imposta, é impossível determinar um 
tamanho ótimo. 
 
b) Em se tratando de cache totalmente associativo, onde podemos projetar o cache de forma 
que os dados de qualquer bloco de memória possam ser armazenados em qualquer um dos 
blocos da cache, teríamos como desvantagem a velocidade: apesar de ser o tipo mais “justo” 
de cache, por tratar todos os blocos de forma igual, para descobrir onde colocar o bloco de 
memória, precisamos pesquisar cada um dos blocos da cache para um espaço livre, o que 
demanda bastante tempo. 
 
Já no caso de cache mapeado diretamente, onde podemos projetar o cache para que os 
dados de qualquer bloco de memória possam só ser armazenados em um único bloco de 
cache (solteiro), temos como vantagem o fato de que é o tipo de cache mais rápido: 
precisamos apenas de uma verificação para ver se o item está no cache ou não. A 
desvantagem é que, caso aconteça de termos um padrão de acesso à memória ruim, 
podemos ter dois blocos “chutando” um ao outro sucessivamente, apesar de existirem blocos 
ainda não usados no cache. 
 
Uma alternativa seria usar uma mistura de ambos: mapear um único bloco de memória em 
vários blocos. Isso é o que os processadores reais fazem. 
 
c) O número de conjunto de cache está relacionado com associatividade por conjuntos, onde 
um bloco pode ser alocado a qualquer posição neste conjunto. O aumento nos conjuntos na 
cache aumenta o miss rate e diminui o hit time. Além disso, o número de conjuntos da cache 
depende diretamente do número de blocos e associatividade 
 
d) Quando um bloco que está residente na cache estiver para ser substituído, existem dois 
casos a considerar. Se o bloco antigo na cache não tiver sido alterado, então ele pode ser 
substituído por um novo bloco sem primeiro atualizar o bloco antigo. Se pelo menos uma 
operação de escrita tiver sido realizada em uma palavra nessa linha da cache, então a 
memória principal precisa ser atualizada escrevendo a linha de cache no bloco de memória 
antes de trazer o novo bloco. Diversas políticas de escrita são possíveis, com escolhas 
econômicas de desempenho. Existem dois problemas a combater. Primeiro, mais de um 
dispositivo pode ter acesso à memória principal. Por exemplo, um módulo de E/S pode ser 
capaz de ler/escrever diretamente na memória. Se uma palavra tiver sido alterada apenas na 
cache, então a palavra correspondente da memória é inválida. Além do mais, se o dispositivo 
de E/S tiver alterado a memória principal, então a palavra da cache é inválida. Um problema 
mais complexo ocorre quando múltiplos processadores são conectados ao mesmo 
barramento e cada processador tem sua própria cache local. Então, se uma palavra for 
alterada em uma cache, ela possivelmente poderia invalidar uma palavra em outras caches. 
A técnica mais simples é denominada write‑through. Usando essa técnica, todas as 
operações de escrita são feitas na memória principal e também na cache, garantindo que a 
memória principal sempre seja válida. Qualquer outro módulo processador-cache pode 
monitorar o tráfego para a memória principal para manter a consistência dentro de sua própria 
cache. A principal desvantagem dessa técnica é que ela gera um tráfego de memória 
considerável e podendo vir a ser um gargalo. Uma técnica alternativa, conhecida como 
write‑back, minimiza as escritas na memória. Com write‑back, as atualizações são feitas 
apenas na cache. Quando ocorre uma atualização, um bit de modificação, ou bit de uso, 
associado à linha, é marcado. Depois, quando um bloco é substituído, ele é escrito de volta 
na memória principal se, e somente se, o bit de modificação estiver marcado. O problema 
com o write-back é que partes da memória principal podem ficar inválidas, e daí os acessos 
pelos módulos de E/S só podem ser permitidos pela cache. Isso exige circuitos complexos e 
gera um gargalo em potencial. 
 
e) Uma vez que a cache estiver cheia, e um novo bloco for trazido para a cache, um dos 
blocos existentes precisa ser substituído. Para o mapeamento direto, existe apenas uma linha 
possível para qualquer bloco em particular e nenhuma escolha é possível. Para as técnicas 
associativa e associativa em conjunto, um algoritmo de substituição é necessário. Para 
alcançar alta velocidade, tal algoritmo precisa ser implementado em hardware. Diversos 
algoritmos foram experimentados. Mencionamos quatro dos mais comuns. Provavelmente, o 
mais eficaz seja o usado menos recentemente (LRU, do inglês least recently used): substitua 
aquele bloco no conjunto que permaneceu na cache por mais tempo sem qualquer referência 
a ele. Para a associatividade em conjunto com duas linhas por conjunto, isso é facilmente 
implementado. Cada linha inclui um bit USE. Quando uma linha é referenciada, seu bit USE 
é definido como 1, e o bit USE da outra linha nesse conjunto é definido como 0. Quando um 
bloco tiver que ser lido para o conjunto, a linha cujo bit USE for 0 é utilizada. Como estamos 
supondo que os locais de memória usados mais recentemente são mais prováveis de serem 
referenciados, LRU deverá oferecer a melhor razão de acerto. LRU também é relativamente 
fácil de implementar para uma cache totalmente associativa. O mecanismo de cache mantém 
uma lista separada de índices para todas as linhas na cache. Quando uma linha é 
referenciada, ela passa para a frente da lista. Para substituição, a linha no final da lista é 
usada. Devido à sua simplicidade de implementação, LRU é o algoritmo de substituição mais 
popular. Outra possibilidade é primeiro a entrar, primeiro a sair (FIFO): substitua o bloco no 
conjunto que esteve na cache por mais tempo. O algoritmo FIFO é facilmente implementado 
como uma técnica round-robin ou de buffer circular. Ainda outra possibilidade de algoritmo é 
o usado menos frequentemente (LFU, do inglês least frequently used): substitua aquele bloco 
no conjunto que teve menos referências. O algoritmo LFU poderia ser implementado 
associando um contador a cada linha. Uma técnica não baseada no uso (ou seja, não LRU, 
LFU, FIFO ou alguma variante) é escolher uma linha aleatória dentre as linhas candidatas. 
Estudos de simulação têm mostrado que a substituição aleatória oferece um desempenho 
apenas ligeiramente inferior a um algoritmo baseado no uso. 
 
2) 
 
a) O dado é escrito apenas no cache. Apenas quando o dado precisa ser sobrescrito é que 
será feita a cópia para o nível de hierarquia de memória inferior. 
 
● Memória principal somente é atualizada quando o bloco é substituído da cache; 
● Cache e memória momentaneamente inconsistentes; 
● Usa dirty bit para marcar linhas alteradas na cache; 
● Reduz quantidade de acessos à memória. 
 
b) O dado é escrito na cache e então é copiado para o nível de hierarquia de memória inferior. 
 
● Cache e memória são atualizadas simultaneamente; 
● Cache e memória sempre consistentes; 
● Penaliza desempenho. A CPU deve esperar acesso à memória. 
● Facilidade de implementação; 
 
c) Diz que um dado acessado recentemente têm mais chances de ser usado novamente do 
que um dado usado há mais tempo. Isso é verdade, pois as variáveis de um programa tendem 
a ser acessadas várias vezes durante a execução de um programa, e as instruções usam 
bastante comandos de repetição e sub-programas, o que faz as instruções serem acessadas 
repetidamente. Temos como exemplo instruções dentro de um loop. 
 
d) Diz que, numcenário em que o processador acesse um bloco, logo em seguida esse 
processador tentará acessar um bloco na memória logo abaixo do bloco anteriormente 
acessado. Se um bloco foi acessado recentemente, provavelmente o próximo acesso à 
memória principal se dará em busca de blocos diretamente abaixo. Temos como exemplo 
dados contidos num array. 
 
3) Vamos primeiro para as definições 
 
● Hit: dado encontrado no nível procurado; 
● Miss: dado não encontrado no nível procurado; 
● Hit-rate: percentual de hits no nível; 
● Hit time: tempo de acesso ao nível, incluindo tempo gasto ao analisar se o caso é hit 
ou miss; 
● Miss rate: percentual de misses no respectivo nível. Valor é complementar ao hit rate; 
 
De acordo com os nossos estudos e as definições acima, podemos afirmar que o grau de 
associatividade terá grande influência na mudança dos conceitos. Primeiro, o miss rate e o 
grau de associatividade possuem um comportamento inversamente proporcional: o miss rate 
diminui com o passar do aumento do grau de associatividade, ocasionado pela memória 
cache ser associada a menos blocos. Por outro lado, o custo de hardware já possui um 
comportamento de crescimento diretamente proporcional ao grau de associatividade, e 
aumentam de acordo. Em se tratando do hit time, existirá a necessidade de mais operações 
de comparação dentro do conjunto de blocos para encontrar o bloco desejado. Com isso, o 
hit time sofrerá um aumento considerável, também de acordo com o aumento da 
associatividade. 
 
4) Como expliquei abaixo na questão 5, o mapeamento direto e a associatividade por 
conjunto (nesse caso, grau 4) lidam de forma diferente com os cálculos de slot 
 
No caso do mapeamento direto, temos 2000 slots, que precisam ser representados por pelo 
menos 11 bits (11111010000). Pela questão, sabemos que cada slot tem 32 bytes = 32*8 bits 
= 256 bits. A tag será de 16 bits, e 32-(16+11) = 5, que será o valor do offset (32 = 100000). 
O validate é apenas 1 bit 
 
Sendo assim, teremos 1 + 16 + 256 = 273 bits cada linha de cache 
 
O cálculo fica: 2000 𝑥 273 =
 
= 68250 𝑏𝑦𝑡𝑒𝑠 
 
Partindo para o mapeamento associativo de grau 4, teremos que dividir os 2000 slots por 4, 
fazendo 500, que consome pelo menos 9 bits (111110100). Offset permanece 5 bits e validate 
1 bit. 32 -(9+5) = 18, que é o valor da tag. 
 
Sendo assim, teremos 1 + 18 + 256 = 275 bits cada linha de cache 
 
O cálculo fica: 
 
= 68750 𝑏𝑦𝑡𝑒𝑠 
 
5) 
 
a) 
 
 
 
b) 
 
 
 
 
c) 
 
 
 
 
6) 
 
a) Considerando os dados que temos e considerando também que o hit time dos ciclos é 
calculado baseado no ciclo mais lento: 
 
ℎ𝑖𝑡 𝑡𝑖𝑚𝑒 = 
ℎ𝑖𝑡 𝑡𝑖𝑚𝑒
𝐹
=
50
2,5
= 20 𝑐𝑖𝑐𝑙𝑜𝑠 
𝑠𝑡𝑎𝑙𝑙 = 𝑚𝑖𝑠𝑠 𝑟𝑎𝑡𝑒 𝑥 𝑖 / 𝑥 ℎ𝑖𝑡 𝑡𝑖𝑚𝑒
= 0,07 𝑥 0,15 𝑥 20 = 0,21 𝑐𝑖𝑐𝑙𝑜𝑠 
𝑠𝑡𝑎𝑙𝑙 = 𝑚𝑖𝑠𝑠 𝑟𝑎𝑡𝑒 𝑥 𝑖 / 𝑥 ℎ𝑖𝑡 𝑡𝑖𝑚𝑒 
= 0,0165 𝑐𝑖𝑐𝑙𝑜𝑠 
𝐶𝑃𝐼 = 𝐶𝑃𝐼 + 𝑠𝑡𝑎𝑙𝑙 + 𝑠𝑡𝑎𝑙𝑙 = 1 + 0,21 + 0,0165 
𝐶𝑃𝐼 = 1,2265 
 
b) Apenas com L1, a memória é acessada diretamente, fazendo com que o tempo de acesso 
seja 200ns. 
 
𝑚𝑖𝑠𝑠 𝑝𝑒𝑛𝑎𝑙𝑡𝑦 = 
𝑡𝑒𝑚𝑝𝑜
𝐹𝑐
= 
200
2,5
= 80 𝑐𝑖𝑐𝑙𝑜𝑠 
𝑠𝑡𝑎𝑙𝑙 = 𝑚𝑖𝑠𝑠 𝑟𝑎𝑡𝑒 𝑥 𝑖 / 𝑥 𝑚𝑖𝑠𝑠 𝑝𝑒𝑛𝑎𝑙𝑡𝑦 
= 0,07 𝑥 0,15 𝑥 80 = 0,84 
𝐶𝑃𝐼 = 𝐶𝑃𝐼 + 𝑠𝑡𝑎𝑙𝑙 = 1 + 0,84 = 1,84 
 
c) Ao acrescentar níveis em uma cache, existe a intenção de melhoria de desempenho em 
relação ao acesso à memória. 
 
Temos como exemplificar mostrando o ganho entre a letra b e letra a: 
 
𝐺𝑎𝑛ℎ𝑜 =
1,84
1,2265
= 1,5 
 
Como podemos ver pela imagem abaixo, os níveis da cache tem objetivos diferentes: