Tema 4-TEXTO para ESTUDO ANTES DA AULA

Prévia do material em texto

CURSO: CIÊNCIA DA COMPUTAÇÃO 
DISCIPLINA: TÓPICOS AVANÇADOS EM ARQUITETURA DE COMPUTADORES 
TEMA 4: Tópicos em Memória-Memória Cache: Organização e Mapeamento Endereços 
 
 
TEXTO PARA APOIO AO ESTUDO (estudo antes da atividade em sala) 
 
No texto anterior, mostrou-se que os sistemas de computação possuem quase sempre uma diversa 
quantidade e tipos e memórias, as quais funcionam, em conjunto, como um sistema com requisitos próximos de 
uma memória rápida (devido à cache, RAM e registradores), de grande capacidade (devido às memórias 
secundárias e um pouco da RAM) e de custo aceitável (se considerado o custo médio entre os diversos tipos). 
Trata-se do que se conhece como uma hierarquia de memórias. 
 
Dessa hierarquia, desponta a memória cache que, atualmente tem sido apresentada com algumas versões 
de desempenho diferente, mas sempre muito rápidas (conforme será mostrado adiante, estas versões 
caracterizam as modalidades Cache L1, L2, etc). 
 
A figura 1 relembra a hierarquia de memórias já descrita anteriormente. 
 
 
 
Figura 1- Uma hierarquia de memórias 
 
 
 Observa-se o posicionamento das Caches entre o processador e a MP, de modo a reduzir ao máximo 
possível o tempo de transferência. Atualmente (e desde muito tempo) as caches vem sendo incluídas no interior 
do chip do processador (tornam-se mais rápidas ainda). No entanto, para efeitos didáticos, facilitando o aspecto 
gráfico e as explicações, as figuras mostram a cache externa ao processador, o que em nada atrapalha as 
descrições. 
 
 Tendo situado a memória Cache no contexto de uma hierarquia de memórias, o assunto deste texto é 
descrever os principais aspectos, características e elementos de projeto das memórias cache; ele será 
completado no próximo texto, ainda com elementos de projeto (mapeamento de endereços associativo e por 
conjunto) e políticas utilizadas no projeto e implementação de memórias cache. 
 
 O sumário do assunto a ser desenvolvido compreende os seguintes itens: 
 
• Organização e funcionamento genérico das memórias cache 
• Elementos de projeto de caches 
 - Mapeamento de endereços – Direto e Associativo (completo e por conjuntos) 
 - Políticas de implementação 
 - Outras considerações sobre projeto de caches 
 
I – ORGANIZAÇÃO GENÉRICA 
 
 Para descrição do processo de funcionamento dos sistemas de computação com cache inclusa, será 
considerada uma estrutura genérica comum, embora encontre-se no mercado diversos modelos de estrutura de 
cache. No entanto, mesmo havendo diferenças de parâmetros, de desempenho e outros aspectos, a estrutura 
genérica está perfeitamente adequada para compreensão de seu funcionamento. 
 
 Conforme se observou anteriormente, as Caches devem ter uma organização que aproveite ao máximo 
o Princípio da Localidade, dai o seu uso em larga escala para tornar os sistemas mais rápidos. Recapitulando 
esta parte, lembre-se que os processadores tendem (não é sempre) a buscar dados na MP de forma sequencial 
(localidade espacial) e, assim, criar uma memória muito rápida para armazenar pequenos grupos de dados 
(blocos) permite que esta memória (Cache) não seja de custo elevado (porque é pequena) mas contenha, em 
grande parte dos acessos, o dado desejado pelo processador. 
 
 A figura 2 mostra um exemplo genérico de organização de memória Cache. 
 
 
Figura 2- Organização básica de uma memória Cache 
 
Na figura 2 a Cache é estruturada em L linhas (este termo para cada endereço de cache não é consenso, mas 
a maioria dos textos sobre cache o usa e neste texto também será). Cada Linha é identificada por um endereço, de 
endereço 0 até endereço L -1 (quando o mapeamento de endereços Cache - MP for descrito, será verificado que os 
bits do endereço de linha são parte do endereço de célula que o processador gera). Cada linha é constituída de 
diversos bytes (porque as MP são organizadas em bytes também, possuindo um grupo (ou bloco) com X bytes, sendo 
X o mesmo valor do tamanho do bloco da MP; além disso, há um grupo de bits (coluna mais à esquerda), chamado 
TAG (rótulo) que indica o endereço do bloco da MP que está armazenado no momento naquela linha e à direita (não 
mostrado na figura) há um ou mais bits, com fins específicos no processo de transferência de dados, a serem 
identificados mais adiante. 
OBS: conforme mencionado antes, a quantidade real de bytes da linha da cache é maior que a da MP; o que é igual 
é a quantidade de dados armazenado em cada bloco da MP e da linha da Cache. O restante dos bytes da linha 
refere-se ao conteúdo do campo TAG e bits de controle. 
 A figura 3 mostra de forma mais completa a organização do conjunto Cache e MP, os quais se juntam ao 
processador para funcionamento do processo de leitura e escrita de dados 
 
 
 
 
Figura 3 – Estrutura Cache-MP para utilização em operações de transferência de dados 
 
 
 Pode-se observar que a MP é organizada de três formas diferentes, conforme o sistema que a esteja 
visualizando no momento: 
1. Fisicamente ela é fabricada com N células (ou palavras), cada uma com um endereço e largura de 
M bits (quase todas M = 8 bits ou 1 Byte). O processador acessa este endereço de byte. 
OBS: É importante relembrar que um dos aspectos da antiga arquitetura von Newmann permanecem válidos 
até os dias atuais e refere-se ao endereço de acesso ao dado desejado por um processador, quando executando uma instrução. 
Assim, sempre que realiza uma busca a um dado ou instrução, o processador gera o endereço de MP onde está localizada uma 
cópia desse dado ou instrução, como se não existisse nenhuma outra memória (no passado era assim e continua assim). 
 Na realidade , o processador gera o endereço virtual do dado ou instrução (uso da memória virtual) e uma unidade no 
interior do processador converte o endereço virtual em endereço real (da MP) , se houver cópia deste dado/instrução na 
MP. Trata-se de processo de funcionamento do SO. 
 
2. Logicamente, para o funcionamento do controle da Cache, a MP é organizada como uma conjunto 
de B Blocos, cada um com X bytes ou X células de largura. Este bloco é que é transferido da MP para 
a Cache, quando requerido. 
3. Logicamente, para funcionamento de transferência entre Memória Virtual (MV) e MP, o Sistema 
Operacional (SO) visualiza a MP como um conjunto de quadros (páginas na MV), com Q Bytes em 
cada um). Este modo é analisado quando se estuda SO. Não é assunto deste texto. 
A organização lógica descrita no item 2, baseia-se conforme já mencionado, no Princípio da Localidade. Ou 
seja, os processadores tendem a buscar um valor em endereços contíguos, em vez de buscar um por um na 
MP (bem lenta), eles buscam um bloco com diversos dados (endereços contíguos) e os transfere de uma vez 
para a cache. Deste modo, de pois da vinda de uma bloco para a aCache, durante algum tempo o processador 
recebe os dados da cache e não da MP. 
 Então, a relação entre memórias é: 
▪ Processador-Memória Cache – transfere-se dado por dado 
▪ Cache – Memória Principal – transfere-se bloco por bloco 
 
 O processo de colocar os dados de um bloco da MP em uma determinada Linha da Cache é chamado de 
Mapeamento 
 
II – FUNCIONAMENTO BÁSICO DE ACESSO AOS DAODS PELO PROCESSADOR 
 
 Para simplificar a explicação, suponha-se que um sistema seja constituído de Processador-Cache – MP. 
• Sempre que o processador quer buscar um dado ,ele coloca seu endereço (da MP) no BE. 
• O controle da memória cache intercepta o endereço e verifica se há uma cópia do dado na cache. 
• Se houver a cópia, chama-se de ACERTO (A) ou HIT (H). 
• Se não houver cópia do dado na cache, chama-se de FALTA (F) ou MISS (M). 
• Nesse caso (de Falta), o sistema busca um bloco de dados contíguos na MP (que contém o dado desejado 
mais os dados que deverão ser buscados nos próximos acessos, devido ao princípio da localidade) e traz 
para a memória cache . E leva o dado desejado para o processador 
▪ A Falta (Miss) acarretauma perda de tempo, mas espera-se que seja pouco frequente. 
▪ A Eficiência do sistema (E) é medida pela relação entre Acertos (A) e Total de Acessos (T). 
 
 A eficiência é usualmente medida em percentagem 
 Pode-se exemplificar em um sistema que obtenha 75 Acertos (Hits), isto é, A = 75 em cada 100 acessos (T), 
que a eficiência do uso da Cache é de 75% ou E = 75 / 100 = 0,75 ou 75 % 
 
Exercício 1 
Considere um sistema de memória onde a MP tem um máximo de 2 GB, sendo endereçada por byte, 
interligada a uma memória Cache, organizada em 128K linhas, cada uma com capacidade de armazenar 16 Bytes. 
Qual é a quantidade de blocos na MP? Qual é a largura do endereço de cada linha e de cada Byte da MP? 
Exercício 2 
Um computador tem uma cache de dois níveis. Suponha que 60% das referências à memória obtêm presença 
na cache nível 1, 35% na cache nível 2 e os 5% restantes não estão em cache (estão, consequentemente, em MP). Se 
os tempos de acesso são de 5 ns, 15 ns e 60 ns, respectivamente, qual é o tempo médio de acesso? 
 
 Para concluir este assunto de funcionamento genérico da memória cache, observe um exemplo de 
processamento, mostrado com os elementos das figuras 4, 5 e 6. 
 
Na figura 4 mostra-se um sistema constituído de Processador, interligado à Memória Cache (única e que 
pode estar no interior ou exterior do processador) e essa interligada à Memória Principal. No exemplo da figura, a 
MP é organizada fisicamente em células (posições), cada uma com seu endereço indicado ao lado (30, 31, 32, etc) e 
tendo em seu interior armazenado um dado (D1, D2, etc). Todos os valores estão representados em decimal para 
facilidade de compreensão. 
Logicamente a MP é organizada em blocos de 4; na figura é visto o bloco 0, com as células de endereço 30 a 
33 e o bloco 1, com as células de endereço 34 a 37. 
E = A / T 
 
Figura 4- Funcionamento da Cache-parte 1 
A Cache é organizada em Linhas de 4 células cada uma, mesmo largura do bloco da MP, de modo que se um 
bloco precisar ser transferido para a cache, será inserido exatamente em um determinada Linha, isto é, o 1º byte do 
bloco entra no 1º byte da linha e assim por diante. O processamento é iniciado com a Cache vazia (sem dados) e o 
processador colocando o endereço 30 no BE (ele deseja acessar o D1, armazenado no endereço 30 da MP. 
Observe o desenvolvimento do funcionamento do sistema por meio das figuras 5 e 6. 
1. O processador transfere o endereço 30 para BE e dai ele é interceptado pelo sistema de controle da cache 
2. O controle da cache sinaliza uma Falta (porque assumimos um início de processamento e a cache vazia 
(figura 4) ela estava vazia). 
3. Figura 5 - O controle interrompe processo para trazer o bloco 0 (que contém o byte – D1 de endereço 30 
e mais os dados D2, D3 e D4); isto consome 50 ns, e em seguida, o dado D1 desejado é transferido para o 
processador (mais 5 ns). Tempo Total deste acesso= 55 ns 
 
Figura 5-Exemplo de funcionamento da Cache-parte 2 
 
4. O processamento prossegue e, conforme o princípio da localidade o processador requer o dado no 
endereço 31-D2. Neste caso tem-se um Acerto, pois o dado veio com o bloco no momento anterior. 
Tempo Total deste acesso= 5 ns 
5. E no instante seguinte de processamento, para endereço 32 (ainda de acordo com o princípio da 
localidade supõe-se que os acessos estão se sucedendo em sequência) repete-se o Acerto e o dado D3 é 
transferido no menor tempo (pois o dado já estava na Cache). Tempo Total = 5 ns 
6. E no instante seguinte de processamento, para endereço 33 repete-se o Acerto para o dado D4 e o Tempo 
Total = 5 ns 
7. No instante seguinte, no entanto, o dado armazenado no endereço 34 não tem cópia na Cache. Houve, 
então, outra Falta. O controle interrompe processo para trazer o bloco 1 (que contém o dado D5 de 
endereço 34. Trará junto os dados D6, D7 e D8, de forma idêntica ao acesso do bloco 0); isto consome 50 
ns, e em seguida, o dado desejado é transferido para o processador (mais 5 ns). Tempo Total do acesso= 
55 ns---Ver Figura 6 
 
Figura 6-Exemplo de funcionamento da Cache-parte 3 
8. E assim por diante, a não ser que haja uma mudança de sequência, pois a sequencialidade de uma 
execução nunca é para sempre. Pode ocorrer um desvio da ordem de execução por conta de um 
comando (tipo IF-THEN-ELSE ou FOR) ou até mesmo desvio (realizado pelo SO) para execução de outro 
programa. Neste caso, provavelmente ocorre uma Falta e o processo se repete com o novo bloco. 
Observe que em cada 4 acessos 3 foram de Acertos (D2-D3-D4) e 1 era Falta-D1 (isso neste exemplo) o que 
acarreta uma Eficiência de 75% , ou E = A / T = 3 /4 e o TM será de 17,5 ns (bem menor que os 50 ns se somente 
existisse a MP). 
 
III – ELEMENTOS DE PROJETO DE MEMÓRIAS CACHE 
 O estudo e análise de projetos e funcionamento das memórias cache contempla diversos aspectos. Entre 
eles, vai-se neste texto analisar alguns: 
✓ Mapeamento de Endereços MP-Cache 
✓ Políticas de projeto 
✓ Quantidade de caches 
✓ Tamanho de Linhas 
 
Neste texto serão abordados aspectos do mapeamento de endereços na modalidade Direto e o restante do 
material estará discutido no texto seguinte. 
 
 
III.1 – Mapeamento de Endereços 
 
 Considere, então, que há sempre uma enorme diferença de capacidade entre a MP e a Cache, ou seja, há 
sempre muito mais blocos lógicos na organização da MP que Linhas (blocos) da Cache. Como, então, se saber 
onde inserir na Cache m bloco da MP a ser transferido em um acesso (por Falta)? 
 Conforme mencionado anteriormente, o processo de colocar os dados de um bloco da MP em uma 
determinada Linha da Cache é chamado de Mapeamento. 
 Há duas modalidades básicas de mapeamento: 
• Direto 
• Associativo, sendo que este método tem duas variantes: 
 - Associativo completo e 
 - Associativo por conjuntos 
 
Mapeamento Direto 
 
 Neste método, o fabricante estabele, de forma permanente, a relação entre endereço de bloco da MP 
com o local na Cache, isto é, coma Linha pré-determinada. 
 Primeiramente, como em qualquer método, o tamanho (largura) de um bloco da MP (quantidade de 
células ou bytes) é igual a largura de dados de cada Linha da Cache. Ou seja, se um bloco da MP consiste de 8 
bytes (usualmente 8 endereços físicos da MP), também cada Linha da Cache possui 8 bytes de largura, mais o 
tamanho do TAG e dos bits de controle, conforme já mencionado anteriormente. 
 
 Neste método, o bloco 0 da MP é alocado á Linha 0 da Cache, O bloco 1 da MP é alocado fisicamente à 
Linha 1 e assim sucessivamente até o bloco de nr igual a à ultima linha da Cache (L-1); o bloco seguinte da MP é 
alocado para o bloco 0, o bloco seguinte à linha 1 e assim até o final. 
 De modo que sempre haverá diversos blocos da MP alocados a uma mesma linha da cache (naturalmente 
somente um estará armazenado na Linha em cada momento. Seu nr fica registrado no campo TAG para ao sistema 
verificar na ocasião de um acesso. 
 A figura 7 mostra um exemplo deste método. 
 
 
Figura 7 – Exemplo do método direto 
 
 No exemplo descrito a seguir, a MP possui 32 células (ou palavras) de 1 Byte cada, de modo que cada 
endereço físico de célula (ou byte) é um número com 5 bits, pois 25 = 32 
A Cache, por outro lado, é organizada em 4 linhas de 2 bytes cada. Total = 8 Bytes mais o campo TAG e bits de 
controle (não mostrados) 
 
• MP é logicamente organizada em blocos de 2 bytes cada (são 16 blocos). A Cache é organizada em “linhas” 
(blocos) de 2 bytes também, havendo 4 linhas. 
• A relação entre cada bloco e cada linha é DIRETA e permanente. 
• Nesse caso, cada linha tem atribuídos 4 blocos, um de cada vez (16 / 4, ou 16 blocos para 4 linhas) 
• Os blocos 0, 4, 8 e 12 são sempre alocados à mesma linha 0 (um em cada instante). 
• Os blocos 1, 5, 9 e 13 são sempre alocados à mesma linha 1 
• Os blocos 2, 6, 10 e 14 são sempre alocados à mesma linha 2 
• Os blocos 3,7, 11 e 15 são sempre alocados à mesma linha 3 
 
 Pode ocorrer do processador realizar um acesso ao byte 5 (célula de endereço físico 5) da MP. Este byte 
(decimal 5 e binário 00101) faz parte do bloco 2 (0010 em binário). O endereço físico 510 = 001012 
 Conforme se observa na figura 7, o bloco 2 está alocado para a Linha 2 (mas também estão alocados os 
blocos 6 -10 -14). É preciso saber qual desses blocos está armazenado na linha no momento do acesso ao byte 5 
(campo TAG indica isso). Se o bloco desejado (2) estiver armazenado na Linha ocorrerá um ACERTO e, em seguida, 
o endereço do byte (0 ou 1) é acessado e ocorre a transferência do dado para o processado, no tempo da Cache. 
Caso contrário (se estiver armazenado o bloco 6 ou 10 ou 14), haverá uma FALTA e o sistema precisa transferir o 
bloco 2, retirando o bloco que lá estava armazenado. 
 
 Mapeamento Direto é simples de projetar e funcionar, já que as ligações são permanentes. No entanto, 
esta vantagem é também uma desvantagem, porque pode gerar uma série de conflitos de endereçamento, 
com aumento da quantidade de faltas (“misses”.) 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
AS INFORMAÇÕES CONTIDAS NESTE MATERIAL DE APOIO AO ESTUDO FORAM EXTRAÍDAS DAS SEGUINTES 
PUBLICAÇÕES: 
MONTEIRO, M. Introdução à organização de computadores. 5. ed. Rio de Janeiro: LTC, 2007. 
STALLINGS, W. Arquitetura e organização de computadores. 8. ed. São Paulo: Pearson Prentice Hall, 2010. 
TANENBAUM, A. S. Organização estruturada de computadores. 5. ed. Rio de Janeiro: LTC, 2007. 
Null, Linda - Computer Organization and Architecture 
PATTERSON, D e Hennesy, J. Computer Organization and Design, The Hardware/Software Interface.