CPU cache

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

CPU Cache é uma memoria de acesso rápido. É usada pela Unidade central de processamento(CPU) com o objetivo de reduzir o tempo médio de acesso aos dados armazenado na memoria. A cache é uma memoria de pouco espaço, porem muito mais rápida e armazena as informações que são usadas com mais frequência pela CPU.

Quando a CPU precisa buscar uma informação na memoria, ela busca primeiro pela cache. Se não encontrado, busca-se na memoria Principal, então devolve a informação para a CPU e armazena esta informação na cache.

Com os avanços tecnológicos, vários tipos de cache foram desenvolvidos. Atualmente há cache em processadores, discos rígidos, sistemas, servidores, nas placas-mãe, clusters de bancos de dados, entre outros. Qualquer dispositivo que requeira do usuário uma solicitação/requisição a algum outro recurso, seja de rede ou local, interno ou externo a essa rede, pode requerer ou possuir de fábrica o recurso de cache.

Por ser mais caro, o recurso mais rápido não pode ser usado para armazenar todas as informações. Sendo assim, usa-se o cache para armazenar apenas as informações mais frequentemente usadas. Nas unidades de disco também conhecidas como disco rígido ou Hard Drive (HD), também existem chips de cache nas placas eletrônicas que os acompanham.


Como funciona/CACHE HIT/CACHE MISS[editar | editar código-fonte]

Diagrama de uma memória de cache da CPU.

Um cache é um bloco de memória para o armazenamento temporário de dados que possuem uma grande probabilidade de serem utilizados novamente.

Uma definição mais simples de cache poderia ser: uma área de armazenamento temporária onde os dados frequentemente acedidos são armazenados para acesso rápido.

Quando a CPU necessita de um conteúdo que esta armazenado na memoria, o primeiro lugar a procurar esta informação é na memoria cache. Se o conteúdo está na cache, ocorre o acerto na cache,chamado de CACHE HIT(quando o conteúdo requisitado pelo CPU é encontrado na cache), fazendo a informação volta pra CPU. Se o conteúdo não está na cache, ocorre erro de cache, chamado de CACHE MISS(quando o conteúdo requisitado pela CPU não esta presente na cache), oque leva a CPU a buscar essa informação na memoria principal.Como provavelmente essa informação será requisitada novamente (localidade temporal) o dado que foi buscado na RAM é copiado no cache.

Se o cache possuir capacidade de armazenamento limitada (algo comum de acontecer devido ao seu custo), e não houver mais espaço para armazenar o novo dado, algum outro elemento deve ser retirado dela para que liberte espaço para o novo elemento. A forma (heurística) utilizada para seleccionar o elemento a ser retirado é conhecida como política de troca (replacement policy). Uma política de troca muito popular é a LRU (least recently used), que significa algo como “elemento recentemente menos usado”.

Quando um dado é escrito no cache, ele deve ser gravado no local de armazenamento em algum momento. O momento da escrita é controlado pela política de escrita (write policy). Existem diferentes políticas. A política de write-through (algo como “escrita através”) funciona da seguinte forma: a cada vez que um elemento é colocado no cache, ele também é gravado no local de armazenamento original. Alternativamente, pode ser utilizada a política de write-back (escrever de volta), onde as escritas não são directamente espelhadas no armazenamento. Ao invés, o mecanismo de cache identifica quais de seus elementos foram sobrepostos (marcados como sujos) e somente essas posições são colocadas de volta nos locais de armazenamento quando o elemento for retirado do cache. Por essa razão, quando ocorre um cache miss (erro de acesso ao cache pelo fato de um elemento não existir nele) em um cache com a política write-back, são necessários dois acessos à memória: um para recuperar o dado necessário e outro para gravar o dado que foi modificado no cache.

O mecanismo de write-back pode ser accionado por outras políticas também. O cliente pode primeiro realizar diversas mudanças nos dados do cache e depois solicitar ao cache para gravar os dados no dispositivo de uma única vez.

Os dados disponíveis nos locais de armazenamento original podem ser modificados por outras entidades diferentes, além do próprio cache. Nesse caso, a cópia existente no cache pode se tornar inválida. Da mesma forma, quando um cliente atualiza os dados no cache, as cópias do dado que estejam presentes em outros caches se tornarão inválidas. Protocolos de comunicação entre gerentes de cache são responsáveis por manter os dados consistentes e são conhecidos por protocolos de coerência.

Princípio da localidade de referência[editar | editar código-fonte]

Podemos definir resumidamente localidade de referencia como o método em que os dados são escritos/levados ate a memoria cache consequentemente até a CPU. Existem dois tipos de localidade de Referencia:[1]

Localidade Temporal[editar | editar código-fonte]

O processador, ao longo de sua execução poderá requisitar uma informação que não esteja na cache. Isso faz com que está informação seja buscada na Memoria Principal. Como a há uma grande probabilidade de essa informação ser executada novamente em um tempo próximo, ela é guardada(uma cópia) na memoria cache. Desta maneira essa informação não precisará mais ser buscada na MP por um tempo.[1]

Localidade Espacial[editar | editar código-fonte]

Quando uma informação é buscada na MP, a localidade temporal faz com que esta informação seja copiada para a cache, porém, também haverá uma grande possibilidade de suas informações vizinhas serem requisitadas em um futuro próximo. Deste modo, junto com a informação requisitada, os vizinhos também serão copiados para a cache.[1] As duas localidades temporal e espacial ocorrem juntas quando a informação é requisitada da MP.

Tipos de memória cache[editar | editar código-fonte]

mapeamento direto[editar | editar código-fonte]

No mapeamento direto, cada bloco da memória principal é mapeado para uma linha do cache, cada linha da cache possui 3 campos, índice(ou linha), tag e o endereço da palavra. O tag é usado para para validar se a linha procurada é a mesma que esta na cache. O índice serve como um endereço da cache, apontado aonde pode estar a linha procurada. O endereço da palavra são os bits menos significativos que identificam uma palavra dentro de um bloco da memoria Principal. No inicio do mapeamento,cada bloco da memoria principal tem sua linha exclusiva mapeada na cache. Este mapeamento é facilmente implementado. Tudo começa com o endereço da Memoria Principal. Através deste endereço, para o acesso a cache, deve se identificar os três campos citados acima. Para achar o End. da palavra, é necessário fazer uma simples conta de logaritmo, tendo em base a quantidade de bytes por linha da cache. LOG2 Nr bytes. Para achar o índice, deve levar em conta o numero de linhas que possui a cache , fazendo o mesmo calculo de logaritmo: LOG2 Nr Linhas O restante será designado a tag.[2]

tag Indice endereço

Suponhamos, em um exemplo que o endereço da linha seja de 32 bits, e a cache possui 1024 linhas com 64 Bytes cada linha. Log2 64 = 6 bits para End. Log2 1024 = 10 bits para índice. 32-(10+6)=16 bits para tag.


Na operação de leitura, a CPU envia um endereço de 32 bits para o circuito de controle da cache que já identifica os campos para começar a pesquisa nas linhas. Inicialmente começando pelo indice, onde a busca ocorre para tentar achar a linha desejada. Após, o próximo passo é comparar os valores da tag do endereço com o valor da tag da linha. Se forem iguais, em seguida, a palavra que esta na linha(6 ultimos bits) é transferida pra CPU.[3] Caso os valores das tags não forem iguais, isso significa que a linha desejada pela CPU não esta na cache, portanto é buscada na MP e transferida para a mesma linha, substituindo-a....

totalmente associativa[editar | editar código-fonte]

No mapeamenteo direto, cada linha da memoria principal tinha um lugar exclusivo na memoria cache. Ja No mapeamento associativo não, aqui, cada linha da MP pode ser carregada em qualquer lugar da cache. Neste modo haverá apenas dois campos. A tag e o end. da palavra. Estes dois campos têm as mesmas funções dos dois campos do mapeamento direto. Porem o campo tag terá uma quantidade de bits maior. No mapeamento associativo, para verificar se a linha esta na cache, é comparado a tag de cada linha na cache com a tag do endereço apresentado pela CPU. Se achou, então os bytes da palavra são transferidos para a CPU, caso contrario, busca-se o endereço na MP e guarda na cache.[3]

Associativa por conjunto (N-Way)[editar | editar código-fonte]

Este tipo de mapeamento intercala as vantagens dos outros dois mapeamentos citados acima, acabando com a comparação exaustiva dos campos tag(causado no mapeamento totalmente associativo)e o problema de conflito de endereços por uma mesma linha na cache(causado no mapeamento direto). Neste caso, a cache nada mais é do que uma serie de conjuntos, constituídos por uma serie de linhas em cada conjunto. A sigla N-Way significa quantos conjuntos tem a cache, onde N é a quantidade de conjuntos.

Cada linha da memoria principal pode ser armazenada em qualquer linha de um conjunto especifico. O conjunto é determinado pelo endereço, que é dividido em 3 campos: TAG, Nr do conjunto e o End da palavra. Dado um endereço a cache para leitura, ela separa os endereço nesses três campos. O primeiro campo a ser analisado é o Nr do conjunto, que define em qual conjunto a linha vai ser pesquisada. Apos, o campo TAG é comparado com todas as linhas deste conjunto para achar a linha desejada.

Algoritmos de substituição de dados[editar | editar código-fonte]

Ai podemos se perguntar. Mas e quando a cache encher? É aqui que entra o papel dos algoritmos de substituição. Eles tem a função de definir quais linhas com informações atualmente armazenadas vão ser retiradas para dar lugar a uma novas linhas com informações.

Alguns algoritmos sao citados  abaixo:

LRU- least recently used: Este algoritmo escolhe escolhe a linha que esta a mais tempo sem uso pela CPU e substitui pela nova linha.

FIFO-First Input, first output: FIFO se resume a uma fila qualquer. Um exemplo pratico seria uma fila de banco, o primeiro a entrar sera o primeiro a ser atendido. No caso da cache, a linha que a mais tempos esta armazenada na cache sera substituída, independentemente se a CPU estiver usando ou não.

LFU- least frequently used: O algoritmo escolhe a linha de acordo com a sua referencia, ou seja, a linha que tiver menos acessos por parte da CPU vai ser a escolhida para substituição.

Modelos De Cache[editar | editar código-fonte]

Estes modelos consideram uma hierarquia de memoria que possua cache de dados L1 com mapeamento direto.[4]

Cache de Vítimas[editar | editar código-fonte]

A cache vítima ou CV é uma pequena cache, localizada entre a L1 e os níveis inferiores da cache, usado para armazenar blocos/linhas que foram "expulsos" da cache principal durante a substituição. O cache de vítima geralmente é totalmente associativo e destina-se a reduzir o número de erros de conflito. Na verdade, apenas uma pequena fração dos acessos memória do programa exigem alta associatividade. O cache de vítima explora essa propriedade fornecendo alta associatividade para apenas esses acessos. A politica de troca de blocos na CV é LRU. Foi introduzida por Norman Jouppi na década de 90.[5]

Stream Buffer[editar | editar código-fonte]

Stream Buffer(SB) é uma simples estrutura dentro da cache, que faz buscas para a cache antecipadamente. Esta estrutura reduz o numero de faltas compulsórias. Esta falta ocorre quando um bloco foi pela primeira vez referenciado pela CPU. Isso porque quando ocorre esta falta, o SB pega o endereço desta referencia e busca os blocos subsequentes e armazena em uma fila, enquanto a fila não encher, a busca continua. Em uma requisição da CPU, a referencia requisitada é buscada tanto na cache como na SB. Caso ocorra um acerto na fila da SB, o bloco/linha é entregue pra CPU e armazenado na cache. Se ocorrer uma falta na fila e na cache também, os blocos que estão na fila são "expulsos" e o processo de busca retorna a partir do endereço da referencia que ocorreu a falta.[6]

Cache em níveis[editar | editar código-fonte]

Com a evolução na velocidade dos dispositivos, em particular nos processadores, o cache foi dividido em níveis, já que a demanda de velocidade a memória é tão grande que são necessários caches grandes com velocidades altíssimas de transferência e baixas latências. Sendo muito difícil e caro construir memórias caches com essas características, elas são construídas em níveis que se diferem na relação tamanho X desempenho.

Cache L1 

Uma pequena porção de memória estática.Ela pode estar dentro do chip da CPU ou fora dele, existe um ganho de velocidade mais desejável com a cache dentro do chip,pois a comunicação ocorre melhor dentro do chip do que entre chips, o que vem fazendo, atualmente, os chips conterem essa pequena parte da cache (L1) dentro do chip. Mas não termina por ai, para intercalar essas duas partes(dentro e fora), ela foi dividida em 2 níveis: a parte dentro do chip(L1) e a parte de fora do chip(L2).[7]

Em alguns tipos de processador, como o Pentium 2, o L1 é dividido em dois níveis: dados e instruções (que "dizem" o que fazer com os dados).O primeiro processador da Intel a ter o cache L1 foi o i486 com 8KB. Geralmente tem entre 16KB e 128KB; hoje já encontramos processadores com até 16MB de cache. 

Cache L2 

Possuindo o Cache L1 um tamanho reduzido e não apresentando uma solução ideal, foi desenvolvido o cache L2, que contém muito mais memória que o cache L1. Ela é mais um caminho para que a informação requisitada não tenha que ser procurada na lenta memória principal. Alguns processadores colocam esse cache fora do processador, por questões econômicas, pois um cache grande implica num custo grande, mas há exceções, como no Pentium II, por exemplo, cujas caches L1 e L2 estão no mesmo cartucho que está o processador. A memória cache L2 é, sobretudo, um dos elementos essenciais para um bom rendimento do processador mesmo que tenha um clock baixo. Um exemplo prático é o caso do Intel Itanium 9152M (para servidores) que tem apenas 1.6 GHz de clock interno e ganha de longe do atual Intel Extreme, pelo fato de possuir uma memória cache de 24MB. Quanto mais alto é o clock do processador, mais este aquece e mais instável se torna. Os processadores Intel Celeron tem um fraco desempenho por possuir menos memória cache L2. Um Pentium M 730 de 1.6 GHz de clock interno, 533 MHz FSB e 2 MB de cache L2, tem rendimento semelhante a um Intel Pentium 4 2.4 GHz, aquece muito menos e torna-se muito mais estável e bem mais rentável do que o Intel Celeron M 440 de 1.86 GHz de clock interno, 533 MHz FSB e 1 MB de cache L2.

Cache L3 

Terceiro nível de cache de memória. Inicialmente utilizado pelo AMD K6-III (por apresentar o cache L2 integrado ao seu núcleo) utilizava o cache externo presente na placa-mãe como uma memória de cache adicional. Ainda é um tipo de cache raro devido a complexidade dos processadores atuais, com suas áreas chegando a milhões de transístores por micrómetros ou nanómetros de área. Ela será muito útil, é possível a necessidade futura de níveis ainda mais elevados de cache, como L4 e assim por diante.

Caches Unificadas/Caches Separadas[editar | editar código-fonte]

Quando o nivel L1 da cache começou a aparecer dentro do chip da CPU, apenas uma cache inteira era usada para armazenar dados e instruções,porem tornou-se comum separar a cache em duas partes,1 dedicada a armazenar dados e a outra dedicada a instruções. Assim, quando o processador busca um dado, ele busca na cache de dados, e quando busca uma instrução, ele busca na cache de instrução.

Ate um certo tamanho, a vantagem fica com a cache unificada, pois a cache tende a equilibrar as buscas por instruções dados, ou seja, se o processador tende a buscar mais instruções, a cache vai armazenar mais instruções. A mesma coisa acontece se o processador busca mais dados. Alem disso, somente uma cache precisa ser projetada e implementada.

Mas o futuro tende a continuar com a cache separada, principalmente em computadores superescalares por ex. o PowerPC. Pois esses processadores escalares, executam instruções paralelas e fazem a pré-busca de instruções futuras previstas. Na cache separada o processador busca antecipadamente as instruções e guarda em um buffer com instruções a serem armazenadas. A cache separada ainda nao precisa de politicas de escrita, e tem barramentos independentes, onde cada cache se liga ao CPU.[8]


Caches inclusivos e exclusivos[editar | editar código-fonte]

Caches Multi-level introduzem novos aspectos na sua implementação. Por exemplo, em alguns processadores, todos os dados no cache L1 devem também estar em algum lugar no cache L2. Estes caches são estritamente chamados de inclusivos. Outros processadores (como o AMD Athlon) têm caches exclusivos - os dados podem estar no cache L1 ou L2, nunca em ambos. Ainda outros processadores (como o Pentium II, III, e 4 de Intel), não requerem que os dados no cache L1 residam também no cache L2, embora possam frequentemente fazê-lo. Não há nenhum nome universal aceitado para esta política intermediária, embora o termo inclusivo seja usado.

A vantagem de caches exclusivos é que são capazes de armazenarem mais dados. Esta vantagem é maior quando o cache L1 exclusivo é de tamanho próximo ao cache L2, e diminui se o cache L2 for muitas vezes maior do que o cache L1. Quando o L1 falha e o L2 acerta acesso, a linha correta do cache L2 é trocada com uma linha no L1. Esta troca é um problema, uma vez que a quantidade de tempo para tal troca ser realizada é relativamente alta.

Uma das vantagens de caches estritamente inclusivos é que quando os dispositivos externos ou outros processadores em um sistema multiprocessado desejam remover uma linha do cache do processador, necessitam somente mandar o processador verificar o cache L2. Nas hierarquias de cache exclusiva, o cache L1 deve ser verificado também.

Uma outra vantagem de caches inclusivos é que um cache maior pode usar linhas maiores do cache, que reduz o tamanho das Tags do cache L2. (Os caches exclusivos requerem ambos os caches teres linhas do mesmo tamanho, de modo que as linhas do cache possam ser trocadas em uma falha no L1 e um acerto no L2).

Técnicas de escrita de dados do cache


Política de Escrita[editar | editar código-fonte]

Quando a CPu necessita fazer uma operação de escrita na Memoria, esta ocorre diretamente na cache. Mas como a cache não é uma memoria principal, em algum momento a MP precisa ser atualizada, para manter a integridade.Isso deve acontecer pois quando uma linha vai ser substituída na cache, antes de isso acontecer , é preciso verificar se essa linha não foi alterada na cache e também não foi alterada na MP. Caso ela tenha sido alterada em algum dos dois casos, isto significa que a linha da cache esta diferente da linha da MP. Isto não pode acontecer, pois a MP precisa estar tão mantida corretamente quanto a cache.[9]

Hoje são encontradas algumas politicas de escritas que resolvem este problema, cada uma com suas vantagens e desvantagens.


Write-Back Cache[editar | editar código-fonte]

Usando esta técnica a CPU escreve dados diretamente no cache, cabendo ao sistema a escrita posterior da informação na memória principal. Como resultado, o CPU fica livre mais rapidamente para executar outras operações. Em contrapartida, a latência do controlador pode induzir problemas de consistência de dados na memória principal, em sistemas multiprocessados com memória compartilhada. Esses problemas são tratados por protocolos de consistência do cache.

Exemplo:

A escrita de um endereço é feita inicialmente numa linha do cache, e somente no cache. Quando mais tarde algum novo endereço precisar desta linha do cache, estando esta já ocupada, então o endereço inicial é guardado na memoria e o novo endereço ocupa-lhe o lugar na respectiva linha do cache.

Para reduzir a frequência de escrita de blocos de endereços na memória aquando da substituição é usado um "dirty bit", este é um bit de estado(atualização), ou seja, quando o endereço é instanciado inicialmente numa linha do cache, estando essa linha vazia, o valor inicial é implicitamente '0', quando o bloco do endereço é modificado (quando ocorre uma substituição) o valor inicial passa a '1' e diz-se que o bloco do endereço está "dirty".[9] [10]

Vantagens

a escrita ocorre à velocidade do cache;

escritas múltiplas de um endereço requerem apenas uma escrita na memória;

consome menos largura de banda.

Desvantagens

difícil de implementar;

nem sempre existe consistência entre os dados existentes no cache e na memória;

leituras de blocos de endereços no cache podem resultar em escritas de blocos de endereços "dirty" na memória.

Write-Through Cache[editar | editar código-fonte]

É a técnica mais simples usada. As operações de escrita são feitas tanto na Memoria Principal como na cache, garantindo que a memoria principal esteja sempre valida. Este tipo de politica providencia pior desempenho do que Write-Back Cache, pois ela gera um grande trafego na memoria principal, podendo formar gargalos, mas é mais simples de implementar e tem a vantagem da consistência interna, porque o cache nunca está dessincronizada com a memória como acontece com a técnica Write-Back Cache.[9] [10]

Vantagens

fácil de implementar;

um "cache-miss" nunca resulta em escritas na memória;

a memória tem sempre a informação mais recente.

Desvantagens

a escrita é lenta;

cada escrita necessita de um acesso à memória;

consequentemente usa mais largura de banda da memória;

alto uso do barramento da memoria.

Técnicas de "Write Miss":

Write Allocate[editar | editar código-fonte]

O bloco de endereço é carregado na ocorrência seguindo-se uma acção de "write hit". O "Write Allocate" é usado com frequência em caches de "Write Back".

No Write Allocate[editar | editar código-fonte]

O bloco de endereço é diretamente modificado na memória, não é carregado no cache. O "No Write Allocate" é usado frequentemente em caches de "Write Through".


Ícone de esboço Este artigo sobre hardware é um esboço. Você pode ajudar a Wikipédia expandindo-o.

Referencias[editar | editar código-fonte]

  1. a b c MONTEIRO,M. MEMÓRIA CACHE:Conceito de Localidade. In:______ (Org). INTRODUÇÃO À ORGANIZAÇÃO DE COMPUTADORES. Rio de Janeiro: LTC-Livros Técnicos e Científicos Editora S.A, 1996. p.112-114.. [S.l.: s.n.].
  2. STALLING,W. MEMÓRIA CACHE:Elementos do projeto da memoria cache. In:______ (Org). ARQUITETURA E ORGANIZAÇÃO DE COMPUTADORES. São Paulo: Pearson Practice Hall, 2010. p.98-113.. [S.l.: s.n.].
  3. a b MONTEIRO,M. MEMÓRIA CACHE:Mapeamento de Dados MP/Cache. In:______ (Org). INTRODUÇÃO À ORGANIZAÇÃO DE COMPUTADORES. Rio de Janeiro: LTC-Livros Técnicos e Científicos Editora S.A, 1996. p.116-121.. [S.l.: s.n.].
  4. SOUZA R. (2009). [http://www.inf.ufpr.br/roberto/tgRichard.pdf Avaliação de Caches Especializadas para Sistemas Embarcados]. Visitado em 2014/11/29.
  5. N.P.Jouppi. "Improving direct-mapped cache performance by the addition of a small fully-associative cache and prefetch buffers." - 17th Annual International Symposium on Computer Architecture, 1990. Proceedings., doi:10.1109/ISCA.1990.134547
  6. SOUZA R. (2009). [http://www.inf.ufpr.br/roberto/tgRichard.pdf Avaliação de Caches Especializadas para Sistemas Embarcados]. Visitado em 2014/11/29.
  7. STALLING,W. MEMÓRIA CACHE:Elementos do projeto da memoria cache. In:______ (Org). ARQUITETURA E ORGANIZAÇÃO DE COMPUTADORES. São Paulo: Pearson Practice Hall, 2010. p.98-113.. [S.l.: s.n.].
  8. STALLING,W. MEMÓRIA CACHE:Elementos do projeto da memoria cache. In:______ (Org). ARQUITETURA E ORGANIZAÇÃO DE COMPUTADORES. São Paulo: Pearson Practice Hall, 2010. p.98-113.. [S.l.: s.n.].
  9. a b c MONTEIRO,M. MEMÓRIA CACHE:Elementos de projeto de uma Memoria Cache:Politica de Escrita pela Memoria Cache MP/Cache. In:______ (Org). INTRODUÇÃO À ORGANIZAÇÃO DE COMPUTADORES. Rio de Janeiro: LTC-Livros Técnicos e Científicos Editora S.A, 1996. p.122-123.. [S.l.: s.n.].
  10. a b STALLING,W. MEMÓRIA CACHE:Elementos do projeto da memoria cache. In:______ (Org). ARQUITETURA E ORGANIZAÇÃO DE COMPUTADORES. São Paulo: Pearson Practice Hall, 2010. p.98-113.. [S.l.: s.n.].