Baixe o app para aproveitar ainda mais
Prévia do material em texto
2019.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 15 e 16 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. 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 quais são os bits que representam o campo “ Conjunto” do formato de endereço? Bloco Byte 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? 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 TAG CONJUNTO BYTE 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 oprocessador 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. Resp: TAG CONJUNTO BYTE 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 contadorpara 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.
Compartilhar