GABARITO-TOP-AV-ARQ-Questionário 5

Prévia do material em texto

2020.1 - TÓPICOS AVANÇADOS EM ARQUITETURA DE COMPUTADORS 
QUESTIONÁRIO 5 – Tópicos Avançados em Memórias – Cache: Mapeamento 
Associativo e por Conjunto. Políticas. Videos 16 e 17 
GABARITO 
1. Considere uma MP que possui 4K blocos de 128 células de 1 byte cada e a memória 
cache do tipo associativa por conjunto possui 64 linhas divididas em conjuntos de 4 
linhas. Qual deverá ser o formato do campo de endereçamento para acesso à MP e à 
memória cache? 
Resp: 
Tag Conjunto Byte 
 8 bits 4 bits 7 bits 
Total de blocos da MP = 4K ou 212 
Total de células por bloco = total de bytes por linha = 128 = 27 
Total de conjuntos da cache: 64 linhas / 4 linhas por conjunto = 16 conjuntos 
Se há 16 conjuntos, então, o campo “conjunto” do endereço tem 4 bits de largura (16 
=24) 
O campo byte tem 7 bits de largura, pois 128 = 27 
Cálculo do Tag (campo que contem endereço do bloco armazenado no conjunto) 
Se há 4K blocos na MP e 16 conjuntos, então a quantidade de blocos por conjunto é de 
4K / 16 conjuntos = 256 blocos por conjunto. A largura do campo Tag será de 8 bits, 
pois 256 = 28 
 
2. O que essencialmente diferencia o método de mapeamento Direto do método 
Associativo? 
Resp: Em ambos há uma conexão direta de um bloco da MP para um elemento da 
cache; no mapeamento direto este elemento é a própria linha da cache e, assim, cada 
bloco está diretamente associado a uma linha. No mapeamento associativo por 
conjunto, o elemento é o conjunto de X linhas e, nesse caso, o bloco está associado a 
um conjunto, podendo ser atribuído a uma das X linhas daquele conjunto. 
 
3. Por que é necessário se estabelecer uma política para substituição de linhas para os 
métodos de mapeamento associativo e não para o método direto, em memórias cache? 
 Resp: No método de mapeamento de endereços direto, cada linha da cache tem 
predeterminado quais blocos da MP serão nela armazenados, de modo que, se ocorrer a 
transferência de um bloco da MP para uma linha da cache, o sistema já sabe onde armazenar 
(em que linha) o referido bloco. No entanto, no caso do método associativo (seja simples seja 
por conjunto), não há uma linha pré-definida para armazenar o bloco a ser transferido. Nesses 
caso, o sistema precisa escolher em qual linha irá armazenar o bloco, substituindo pelo 
existente. Daí a necessidade de se definir uma política de escolha do bloco a ser retirado. 
 
 
 Associação Carioca de Ensino Superior 
 
Centro Universitário Carioca 
http://www.unicarioca.br/index.php
4. Considere uma memória principal (MP) com capacidade máxima de X bytes, sendo 
endereçada por byte e uma cache com 512KB, organizada em linhas de 32 bytes. Sabe-
se que o BE do sistema possui 28 bits de largura. Mostre o formato dos campos de 
endereço considerando os métodos de mapeamento de endereços da cache direto e 
associativo. 
:Resp: Cache de 512KB e linhas/blocos de 32 bytes. Como 32 = 25, então o campo Byte = 5 bits 
em ambos os formatos. 
Se BE = 28 bits, o campo bloco no mapeamento associativo tem 28 – 5 = 23 bits 
SE Cache tem 512KB e linhas de 32 B, então, haverá 512KB / 32B = 16K linhas e cada linha 
terá endereço de 14 bits, pois 16K = 214 
 
Mapeamento Direto 
Tag Linha Byte 
 9 14 5 
Mapeamento associativo 
 
 
 23 bits 5 bits 
5. Considere um computador que possui uma MP (endereçada byte a byte) e uma única 
Cache. O sistema emprega o método de mapeamento associativo, tendo o seguinte 
formato de endereços: 
 
 
 19 bits 5 bits 
 
a) Qual é a capacidade de armazenamento da MP? 
b) Qual é o tamanho de cada linha de cache? 
Resp: O endereço completo de cada célula de MP = 19 + 5 = 24 bits. 
a) A capacidade máxima de armazenamento dessa MP (N) = 224 = 24 x 220 = 16M endereços. 
b) Como o campo byte do endereço tem 5 bits de largura, cada linha da cache tem uma 
largura (tamanho) de 32 bytes, pois 25 = 32 
 
6. Supondo um sistema de computação que possua memória principal, cujo 
endereçamento é realizado a nível de byte e que possua uma cache única e que, em 
dado momento o processador coloca o seguinte valor no barramento de endereços (BE): 
 
 1111 1001 1100 1001 0001 0001 
 
Suponha ainda que o sistema usa método de mapeamento associativo por conjunto de 8 vias, 
que a MP é vista pelo controle da cache como um conjunto de blocos de 64 Bytes e que são 
previstos sempre uma quantidade de 128 blocos em cada conjunto da cache. Considerando 
que o formato de endereço para acesso pelo controle da cache é: 
 
 TAG - CONJUNTO - BYTE 
Bloco Byte 
 
quais são os bits que representam o campo “ Conjunto” do formato de endereço? 
 
Resp: O campo endereço completo tem 24 bits; o campo BYTE tem 6 bits de largura, porque os 
blocos tem 64 bytes de largura (64 = 26). O campo TAG tem 7 bits, pois há 128 blocos 
associados a cada conjunto e 128 = 27. 
Assim, o campo conjunto tem 24 – 7 – 6 = 11 bits e os bits do endereço acima, que 
representam o endereço do conjunto desejado são: 
 1111100 11100100100 010001 
 TAG CONJUNTO BYTE 
 
7. Como se denomina a política de escrita na memória cache na qual a MP é atualizada 
apenas nos blocos que tiveram escrita, e apenas quando há a volta do bloco para a MP? 
 Resp: É denominada política de escrita “write back” ou escrita somente no retorno. 
 
8. Considere uma memória cache organizada com mapeamento associativo por conjunto, 
sendo cada conjunto de 4 linhas. A MP tem uma capacidade de armazenar 64MB, 
sendo organizada byte a byte e o sistema transfere de cada vez (MP>cache) 32 
bytes. Considerando que a capacidade da cache é de 64KB, mostre como deve ser o 
formato dos campos de endereço para a memória cache. 
Resp: Se a MP tem 64MB e é organizada byte por byte, então tem 64 M endereços (N) e N = 
2E. Então, N = 64M e E = 26 bits (64M = 226) Estes 26 bits do endereço completo são 
distribuídos em 3 campos, da esquerda para direita: TAG – CONJUNTO – BYTE 
Campo BYTE tem 3 bits de largura, pois são blocos de 32 bytes e 32 = 25 
Como a cache tem 64KB e cada linha tem 32B, entãoa quantidade de linhas é 64KB / 32B = 2K 
linhas e se o mapeamento é 4 linhas por conjunto, então haverá: 2K / 4 = 512 conjuntos e 
o endereço de cada conjunto tem 9 bits, pois 512 -= 29. Campo CONJUNTO= 9 bits 
O campo TAG terá uma largura igual a diferença entre 26 – 9 – 5 = 12 bits 
 
 
 
 12 bits 9 bits 5 bits 
 
9. Conceitualmente, qual a parte do processo de mapeamento associativo por conjunto 
pode ser considerado igual ao mapeamento direto? 
Resp: Trata-se da parte inicial quando o sistema acessa um conjunto de X linhas. Esta parte é 
semelhante ao do mapeamento direto, pois cada bloco da MP tem associado um conjunto 
(como no direto), embora não se saiba ainda se o bloco desejado pelo processador estará 
armazenado na cache em uma das X linhas do conjunto especificado. 
 
10. Por que não é conveniente escolher valores muito grandes para o tamanho (a largura) 
de linhas de uma memória cache? E por que esta largura é sempre bem maior que a 
largura de uma célula de memória principal? 
TAG CONJUNTO BYTE 
Resp: O princípio da localidade estabelece que o processador costuma acessar endereços 
contíguos, já que esta é a lógica de criação de algoritmos. No entanto, ele define também, que 
esta sequência lógica NÃO É para sempre e sim por um grupo de endereços, cujo tamanho 
depende da lógica do algoritmo. Depois ele “salta” a sequência e passa a outro grupo. 
Por causa desse princípio, quando o processador precisa trazer um dado da MP para a cache e 
daí para ele, este dado vem em um bloco de endereços contíguos, pressupondo-se que o 
processador vai querer os bytes subsequentes.Como o processo gasta tempo (MP-Cache) é 
conveniente trazer o bloco do que um por um byte. 
Mas se a largura do bloco for grande, é provável que os últimos bytes não sejam utilizados, já 
que a sequencialidade não é para sempre (conforme mencionado acima). Nesse caso, 
consumiu-se desnecessariamente uma parte da memória cache. A largura não deve ser muito 
pequena nem muito grande. 
A segunda pergunta já foi respondida nesta explicação acima. 
 
11. Qual é a diferença entre cache unificada e cache dividida? Em sistemas multicache, 
que categoria(s) de memória(s) cache utiliza um e outro métodos? 
Resp: Todas as memórias armazenam instruções-I (o código de programa) e dados-D. 
Aquelas memórias que armazenam junto esses elementos (I e D) chamam-se 
unificadas (emboar este termo não seja praticado para MP e MS e apenas para as 
caches, pois, nesse caso, há uma outra possibilidade e assim é preciso distinguir um 
modo de outro. 
Na cache L1 (apenas nessa cache), que é diretamente ligada ao processo de execução 
de uma instrução, atualmente costuma-se separar o armazenamento de instruções e 
dados e assim, ter Cache L1 para Instruções (cache Li-I) e Cache L1 para dados (cache 
L1-D). 
Isso acontece para otimizar os acesso e tornar mais rápida a s transferências, em 
virtude de instruções e dados seguirem caminhos diferentes na ocasião de execução. 
 
12. Suponha um sistema de memória constituído de memória principal e uma única cache, 
a qual utiliza mapeamento associativo por conjunto de 4. O formato de endereço para 
análise pelo sistema de controle da cache é: 
 
 
 
 8 bits 8 bits 4 bits 
Calcule: 
a) Capacidade de armazenamento da MP, em bytes. 
b) Quantidade de linhas da memória cache. 
c) Quantidade de conjuntos da memória cache. 
d) Largura de cada bloco/linha. 
e) Quantidade de blocos atribuídos a cada conjunto da cache. 
TAG CONJUNTO BYTE 
Resp: 
a) A soma dos campos é 20 bits (8 + 8 + 4) e, nesse caso, 220 = 1 M endereços (assumindo 
que cada endereço armazena um byte, então a capacidade de armazenamento da 
memória principal- MP é 1 MB 
b) Como o campo Byte tem 4 bits, então cada bloco/linha possui 16B (24 =16)- resposta 
da letra d) 
c) Como o campo conjunto tem 8 bits de endereço, então haverá 256 conjuntos (28 = 
256) – resposta da letra c) 
d) Como o campo TAG tem 8 bits, então, deve haver 256 blocos atribuídos a cada 
conjunto da cache. (28 = 256) – resposta da letra e) 
e) A quantidade de linhas da cache será 1024 ou 1K linhas, pois há 256 conjuntos com 4 
linhas em cada um e 256 x 4 = 1024 (o método é associativo por conjunto de 4 vias) – 
resposta da letra b) 
 
13. Suponha um sistema de computação que tenha uma memória principal (MP) com 
capacidade máxima de 2GB, sendo endereçado byte a byte. E também possui uma 
memória cache, organizada com mapeamento associativo, tendo linhas de 32 bytes. 
Considerando que a cache tem 256KB, quantos registradores de comparação devem 
existir nesse sistema para que ele funcione com a máxima rapidez possível na parte de 
mapeamento de endereços? 
Resp: Para que a cache funcione com máxima rapidez na parte do mapeamento de endereço 
em um sistema associativo, é necessário que a verificação se o bloco acessado se encontra na 
cache seja feita por comparação simultânea entre o bloco desejado e todos os blocos 
armazenados um em cada linha. Ou seja, deverão existir tantos registradores de comparação 
quantas linhas da cache. 
Por exemplo, suponha uma cache que tem 512 linhas, cada uma tem um campo TAG indicando 
o bloco que está atualmente armazenada naquela linha. E o processador, em um acesso, 
deseja um dado que faz parte do bloco X. O sistema de controle da cache coloca X em TODOS 
os 512 registradores de comparação (uma parte do registrador terá X e outra parte o end do 
bloco armazenado e simultaneamente eles passam por um circuito lógico XOR. Se houver 
igualdade (só poderá ser em um registrador) – saída 0 do XOR – então este bloco é o desejado 
e o sistema localiza a célula (byte) pelo campo endereço de byte. Caso contrário – saída 1 do 
XOR – haverá uma FALTA (“Miss”). 
No problema em questão, como a cache possui 256KB e cada linha tem 32B, a quantidade de 
linhas será: 256K / 32 = 8K linhas ou 8 x 1024 = 8.192 linhas. 
Haverá necessidade, então, de 8192 registradores de comparação. 
14. Considere um sistema de computação que possui uma memória principal, organizada 
em células de 1 byte cada, tendo apenas uma memória cache externa, organizada para 
utilizar o método de mapeamento associativo, com as linhas tendo uma largura de 64 
bytes. Em um dado instante, o processador inicia um acesso, colocando no BE 
(barramento de endereços) comum o endereço hexadecimal: 3C7F9C. 
Pergunta-se: 
a. qual deverá ser a largura do BE do sistema? 
b. qual é o valor total de endereços da memória principal? 
c. qual foi o bloco desejado pelo processador (valor expresso em binário), 
d. quantos registradores de comparação devem existir para que o acesso seja o 
mais rápido possível, sabendo-se que a cache tem 256KB? 
Resp: Mapeamento associativo. O formato de endereço é: BLOCO (endereço do bloco) – BYTE 
(endereço da célula). 
Largura de linha (cache)/bloco(MP) = 64 bytes = 26. Logo, campo BYTE tem largura de 6 bits. 
Endereço acesso MP (BE) = 3C7F9C16 Como cada algarismo hexadecimal tem valor equivalente 
a um número binário de 4 algarismos, então, a largura do BE = 6 x4 = 24 bits, pois são 6 
algarismos em base 16, cada um de 4 bits. 
a) BE = 24 bits 
b) Total de endereços da MP(N) = 2BE ou 224 =16M endereços (24 =16 x 220 =1M) 
c) 3C79FC16 = 0011110001111111100111002, sendo 6 bits mais à direita o endereço de 
cada byte e o restante (24 -6=18 bits) de endereço do bloco (001111000111111110). 
d) Se cache = 256KB e cada linha tem 64B então há 256KB / 64B = 2K linhas = 2048 linhas. 
Então, haverá 2048 registradores de comparação para determinar se o bloco desejado 
está em uma das 2049 linhas. 
 
15. Como é conhecida a política de escrita da cache pela qual a MP somente é atualizada 
quando há retorno do bloco para ela (MP)? Por que nem sempre há retorno do bloco 
para a MP? 
Resp: política de “escrita no retorno” ou “write back”). Por que nem sempre um bloco é 
atualizado por resultado de processamento. Se um determinado bloco foi escolhido pelo 
algoritmo de substituição de linha para ser substituído e nenhum dos seus bytes sofreu alguma 
alteração de valor, não há necessidade de se perder tempo retornando-o para a MP. Somente 
se houve alteração em algum de seus bytes é que precisa retornar, para ser mais tarde 
transferido para o HD, de forma permanente. 
16. O que significa o termo “mapeamento associativo por conjunto com 8 caminhos” ou 
set asociative 8 way? 
 Resp: o método associativo por conjunto procura usar as vantagens dos métodos associativo 
e direto, minimizando suas desvantagens. Assim, ele organiza a cache em grupos de linhas 
chamadas conjuntos, tendo cada grupo uma quantidade de X linhas. Este valor X é conhecido 
como vias (em inglês: “way”). Assim, set associative 8 way significa associativo por conjunto e 
cada conjunto possui 8 linhas. 
17. Explique brevemente o funcionamento de dois algoritmos de substituição de linhas em 
sistemas de computação que possuam memórias cache. 
Resp: Algoritmo LRU (least recently used) ou do tipo: a linha não é usada há mais tempo. 
Por este algoritmo, quando uma linha precisa sair para entrar um novo bloco que contém o 
dado desejado pelo processador, o sistema escolhe a linha que não é usada há mais tempo, 
supondo-se que, assim, ela provavelmente não será mais usada. Para isso, há um contador 
para cada linha que vai sendo incrementado a cada acesso ou de forma mais simples (quando 
é conjunto de 2 linhas) por um bit, setado com acesso e resetado sem acesso. 
Algoritmo LFU (least frequently used) ou tipo: que tem menos referências 
Nesse caso, o contadoré incrementado a cada acesso a uma linha, de modo que a linha cijo 
contador tem menor valor, é a que tem menos referências.