Cache (computação) - Cache (computing)

Diagrama de uma operação de cache de memória da CPU

Em computação , um cache de ( / k æ ʃ / ( escute ) Sobre este som kash , ou / k ʃ / kaysh no Australian Inglês ) é um componente de hardware ou software que armazena dados para que futuros pedidos de que os dados podem ser servidos mais rápido; os dados armazenados em um cache podem ser o resultado de um cálculo anterior ou uma cópia dos dados armazenados em outro lugar. Um acerto de cache ocorre quando os dados solicitados podem ser encontrados em um cache, enquanto uma falha de cache ocorre quando não pode. As ocorrências de cache são atendidas pela leitura de dados do cache, o que é mais rápido do que recomputar um resultado ou ler de um armazenamento de dados mais lento; portanto, quanto mais solicitações puderem ser atendidas do cache, mais rápido será o desempenho do sistema.

Para ter uma boa relação custo-benefício e permitir o uso eficiente de dados, os caches devem ser relativamente pequenos. No entanto, os caches têm se mostrado comprovados em muitas áreas da computação, pois os aplicativos de computador típicos acessam os dados com um alto grau de localidade de referência . Tais padrões de acesso exibem localidade temporal, onde são solicitados dados já solicitados recentemente, e localidade espacial , onde são solicitados dados armazenados fisicamente próximos aos dados já solicitados.

Motivação

Há uma compensação inerente entre tamanho e velocidade (dado que um recurso maior implica maiores distâncias físicas), mas também uma compensação entre tecnologias premium caras (como SRAM ) e commodities mais baratas e facilmente produzidas em massa (como DRAM ou disco rígido discos ).

O buffer fornecido por um cache beneficia um ou ambos de latência e taxa de transferência ( largura de banda ):

Latência

Um recurso maior incorre em uma latência significativa para o acesso - por exemplo, pode levar centenas de ciclos de clock para que um processador moderno de 4 GHz alcance a DRAM . Isso é atenuado pela leitura em grandes blocos, na esperança de que as leituras subsequentes sejam de locais próximos. A previsão ou a pré-busca explícita também podem adivinhar de onde virão as leituras futuras e fazer solicitações com antecedência; se feito corretamente, a latência é totalmente ignorada.

Taxa de transferência

O uso de um cache também permite maior rendimento do recurso subjacente, reunindo várias transferências de granulação fina em solicitações maiores e mais eficientes. No caso de circuitos DRAM , isso pode ser servido por um barramento de dados mais amplo. Por exemplo, considere um programa acessando bytes em um espaço de endereço de 32 bits , mas sendo servido por um barramento de dados fora do chip de 128 bits; acessos de bytes individuais não armazenados em cache permitiriam que apenas 1/16 da largura de banda total fosse usada, e 80% da movimentação de dados seriam endereços de memória em vez dos próprios dados. Ler pedaços maiores reduz a fração da largura de banda necessária para transmitir informações de endereço.

Operação

O hardware implementa o cache como um bloco de memória para armazenamento temporário de dados que provavelmente serão usados ​​novamente. As unidades de processamento central (CPUs) e as unidades de disco rígido (HDDs) freqüentemente usam um cache baseado em hardware, enquanto os navegadores e servidores da web geralmente dependem do cache de software.

Um cache é composto de um pool de entradas. Cada entrada possui dados associados , que são uma cópia dos mesmos dados em algum armazenamento de apoio . Cada entrada também possui uma tag , que especifica a identidade dos dados no armazenamento de apoio dos quais a entrada é uma cópia. A marcação permite que algoritmos orientados a cache simultâneos funcionem de maneira multicamadas sem interferência de relé diferencial.

Quando o cliente de cache (uma CPU, navegador da web, sistema operacional ) precisa acessar dados presumivelmente existentes no armazenamento de apoio, ele primeiro verifica o cache. Se uma entrada puder ser encontrada com uma tag que corresponda aos dados desejados, os dados da entrada serão usados. Essa situação é conhecida como acerto de cache. Por exemplo, um programa de navegador da web pode verificar seu cache local no disco para ver se ele possui uma cópia local do conteúdo de uma página da web em um URL específico . Neste exemplo, o URL é a tag e o conteúdo da página da web são os dados. A porcentagem de acessos que resultam em acertos do cache é conhecida como taxa de acertos ou taxa de acertos do cache.

A situação alternativa, quando o cache é verificado e não contém nenhuma entrada com a tag desejada, é conhecida como perda de cache. Isso requer um acesso mais caro aos dados do armazenamento de apoio. Depois que os dados solicitados são recuperados, eles geralmente são copiados para o cache, prontos para o próximo acesso.

Durante uma falha de cache, alguma outra entrada de cache existente anteriormente é removida para liberar espaço para os dados recém-recuperados. A heurística usada para selecionar a entrada a ser substituída é conhecida como política de substituição . Uma política de substituição popular, "menos usada recentemente" (LRU), substitui a entrada mais antiga, a entrada que foi acessada menos recentemente do que qualquer outra entrada (consulte o algoritmo de cache ). Algoritmos de cache mais eficientes calculam a frequência de acertos de uso em relação ao tamanho do conteúdo armazenado, bem como as latências e taxas de transferência para o cache e o armazenamento de apoio. Isso funciona bem para grandes quantidades de dados, latências mais longas e taxas de transferência mais lentas, como o que ocorre com discos rígidos e redes, mas não é eficiente para uso em um cache de CPU.

Políticas de redação

Um cache de gravação sem alocação de não gravação
Um cache de write-back com alocação de gravação

Quando um sistema grava dados no cache, ele deve, em algum ponto, gravar esses dados também no armazenamento de apoio. O tempo dessa gravação é controlado pelo que é conhecido como política de gravação . Existem duas abordagens básicas de escrita:

  • Write-through : a gravação é feita de forma síncrona no cache e no armazenamento de apoio.
  • Write-back (também chamado de write-behind ): inicialmente, a escrita é feita apenas no cache. A gravação no armazenamento de apoio é adiada até que o conteúdo modificado esteja prestes a ser substituído por outro bloco de cache.

Um cache de write-back é mais complexo de implementar, pois ele precisa rastrear quais de seus locais foram sobrescritos e marcá-los como sujos para gravação posterior no armazenamento de apoio. Os dados nesses locais são gravados de volta no armazenamento de apoio apenas quando são removidos do cache, um efeito conhecido como gravação lenta . Por esse motivo, uma falha de leitura em um cache de write-back (que exige que um bloco seja substituído por outro) muitas vezes exigirá dois acessos de memória para o serviço: um para gravar os dados substituídos do cache de volta para o armazenamento e, em seguida, um para recuperar os dados necessários.

Outras políticas também podem acionar o write-back de dados. O cliente pode fazer muitas alterações nos dados do cache e, em seguida, notificar explicitamente o cache para gravar os dados de volta.

Como nenhum dado é retornado ao solicitante nas operações de gravação, é necessário tomar uma decisão sobre as perdas de gravação, se os dados serão carregados ou não no cache. Isso é definido por estas duas abordagens:

  • Alocação de gravação (também chamada de busca na gravação ): os dados no local de gravação perdida são carregados para o cache, seguido por uma operação de ocorrência de gravação. Nesta abordagem, erros de gravação são semelhantes aos erros de leitura.
  • Alocação sem gravação (também chamada de gravação sem alocação ou gravação ao redor ): os dados no local de gravação perdida não são carregados no cache e são gravados diretamente no armazenamento de apoio. Nessa abordagem, os dados são carregados no cache apenas em erros de leitura.

Ambas as políticas write-through e write-back podem usar qualquer uma dessas políticas write-miss, mas geralmente elas são pareadas desta forma:

  • Um cache de write-back usa alocação de gravação, esperando por gravações subsequentes (ou mesmo leituras) no mesmo local, que agora está armazenado em cache.
  • Um cache de gravação usa alocação sem gravação. Aqui, as gravações subsequentes não têm nenhuma vantagem, pois ainda precisam ser gravadas diretamente no armazenamento de apoio.

Outras entidades além do cache podem alterar os dados no armazenamento de apoio, caso em que a cópia no cache pode ficar desatualizada ou obsoleta . Como alternativa, quando o cliente atualiza os dados no cache, as cópias desses dados em outros caches se tornam obsoletas. Os protocolos de comunicação entre os gerenciadores de cache que mantêm os dados consistentes são conhecidos como protocolos de coerência .

Pré-busca

Em uma falha de leitura de cache, os caches com uma política de paginação por demanda lêem a quantidade mínima do armazenamento de apoio. Por exemplo, a memória virtual de paginação por demanda lê uma página de memória virtual (geralmente 4 kBytes) do disco para o cache de disco na RAM. Por exemplo, uma CPU típica lê uma única linha de cache L2 de 128 bytes da DRAM para o cache L2 e uma única linha de cache L1 de 64 bytes do cache L2 para o cache L1.

Caches com uma fila de entrada de pré - busca ou política de paginação antecipatória mais geral vão além - eles não apenas leem o trecho solicitado, mas supõem que o próximo trecho ou dois serão necessários em breve e, portanto, pré-busca esses dados no cache com antecedência. A paginação antecipada é especialmente útil quando o armazenamento de apoio tem uma longa latência para ler o primeiro fragmento e tempos muito mais curtos para ler sequencialmente os próximos fragmentos, como armazenamento em disco e DRAM .

Alguns sistemas operacionais vão além com um carregador (computação) que sempre pré-carrega todo o executável na RAM.

Alguns caches vão ainda mais longe, não apenas pré-carregando um arquivo inteiro, mas também começando a carregar outros arquivos relacionados que podem ser solicitados em breve, como o cache de página associado a um pré - buscador ou o cache da web associado à pré-busca de link .

Exemplos de caches de hardware

Cache de CPU

Memórias pequenas na CPU ou próximas a ela podem operar mais rápido do que a memória principal, muito maior . A maioria das CPUs, desde a década de 1980, usou um ou mais caches, às vezes em níveis em cascata ; modernos microprocessadores embarcados , de desktop e de servidor de última geração podem ter até seis tipos de cache (entre níveis e funções). Exemplos de caches com uma função específica são o D-cache e o I-cache e o buffer lookaside de tradução para o MMU .

Cache GPU

As unidades de processamento gráfico (GPUs) anteriores geralmente tinham caches de textura somente leitura limitados e introduziam texturas swizzled de ordem de Morton para melhorar a coerência do cache 2D . Perdas de cache afetariam drasticamente o desempenho, por exemplo, se o mapeamento mip não fosse usado. O armazenamento em cache era importante para alavancar transferências de 32 bits (e mais amplas) para dados de textura que geralmente eram tão pequenos quanto 4 bits por pixel, indexados em padrões complexos por coordenadas UV arbitrárias e transformações de perspectiva no mapeamento de textura inversa .

À medida que as GPUs avançavam (especialmente com sombreadores de computação GPGPU ), elas desenvolveram caches progressivamente maiores e cada vez mais gerais, incluindo caches de instrução para sombreadores , exibindo funcionalidade cada vez mais comum com caches de CPU. Por exemplo, as GPUs de arquitetura GT200 não apresentavam cache L2, enquanto a GPU Fermi tem 768 KB de cache de último nível, a GPU Kepler tem 1536 KB de cache de último nível e a GPU Maxwell tem 2048 KB de cache de último nível . Esses caches cresceram para lidar com primitivos de sincronização entre threads e operações atômicas e fazer interface com um MMU de estilo CPU .

DSPs

Os processadores de sinais digitais generalizaram-se de maneira semelhante ao longo dos anos. Projetos anteriores usavam memória de rascunho alimentada por DMA , mas DSPs modernos como Qualcomm Hexagon geralmente incluem um conjunto muito semelhante de caches para uma CPU (por exemplo, arquitetura Harvard modificada com L2 compartilhado, I-cache L1 dividido e D-cache).

Buffer lookaside de tradução

Uma unidade de gerenciamento de memória (MMU) que busca as entradas da tabela de páginas da memória principal tem um cache especializado, usado para registrar os resultados de endereços virtuais em traduções de endereços físicos . Esse cache especializado é chamado de buffer lookaside de tradução (TLB).

Cache na rede

Rede centrada na informação

A rede centrada em informações (ICN) é uma abordagem para evoluir a infraestrutura da Internet de um paradigma centrado no host, com base na conectividade perpétua e no princípio de ponta a ponta , para uma arquitetura de rede na qual o ponto focal é a informação identificada (ou conteúdo ou dados). Devido à capacidade de armazenamento em cache inerente dos nós em um ICN, ele pode ser visto como uma rede de caches fracamente conectada, que possui requisitos exclusivos de políticas de armazenamento em cache. No entanto, o cache de conteúdo onipresente apresenta o desafio da proteção de conteúdo contra acesso não autorizado, o que requer cuidado e soluções extras. Ao contrário dos servidores proxy, no ICN o cache é uma solução em nível de rede. Portanto, ele tem estados de cache que mudam rapidamente e taxas de chegada de solicitação mais altas; além disso, tamanhos de cache menores impõem ainda um tipo diferente de requisitos nas políticas de despejo de conteúdo. Em particular, as políticas de despejo do ICN devem ser rápidas e leves. Vários esquemas de replicação e remoção de cache para diferentes arquiteturas e aplicativos ICN foram propostos.

Políticas

Tempo ciente de uso menos recente (TLRU)

O TLRU (Time ciente de uso menos recente) é uma variante do LRU projetada para a situação em que o conteúdo armazenado no cache tem um tempo de vida válido. O algoritmo é adequado em aplicativos de cache de rede, como redes centradas em informações (ICN), redes de distribuição de conteúdo (CDNs) e redes distribuídas em geral. TLRU apresenta um novo termo: TTU (Tempo de Uso). TTU é um carimbo de data / hora de um conteúdo / página que estipula o tempo de usabilidade para o conteúdo com base na localidade do conteúdo e no anúncio do editor de conteúdo. Devido a esse carimbo de data / hora com base na localidade, o TTU fornece mais controle ao administrador local para regular o armazenamento da rede. No algoritmo TLRU, quando uma parte do conteúdo chega, um nó de cache calcula o valor TTU local com base no valor TTU atribuído pelo editor de conteúdo. O valor TTU local é calculado usando uma função definida localmente. Depois que o valor TTU local é calculado, a substituição do conteúdo é realizada em um subconjunto do conteúdo total armazenado no nó de cache. O TLRU garante que o conteúdo menos popular e pequeno seja substituído pelo conteúdo de entrada.

Menos usado recentemente (LFRU)

O esquema de substituição de cache menos frequente recentemente usado (LFRU) combina os benefícios dos esquemas LFU e LRU. O LFRU é adequado para aplicativos de cache 'em rede', como redes centradas em informações (ICN), redes de distribuição de conteúdo (CDNs) e redes distribuídas em geral. No LFRU, o cache é dividido em duas partições chamadas partições privilegiadas e não privilegiadas. A partição privilegiada pode ser definida como uma partição protegida. Se o conteúdo for muito popular, ele será enviado para a partição privilegiada. A substituição da partição privilegiada é feita da seguinte forma: LFRU remove o conteúdo da partição não privilegiada, envia o conteúdo da partição privilegiada para a partição não privilegiada e, finalmente, insere novo conteúdo na partição privilegiada. No procedimento acima, o LRU é usado para a partição privilegiada e um esquema LFU aproximado (ALFU) é usado para a partição não privilegiada, daí a abreviatura LFRU. A ideia básica é filtrar o conteúdo popular localmente com o esquema ALFU e enviar o conteúdo popular para uma das partições privilegiadas.

Previsão do tempo

Em 2010, o New York Times sugeriu "Digite 'clima' seguido do seu código postal." Em 2011, o uso de smartphones com opções de previsão do tempo estava sobrecarregando os servidores AccuWeather ; duas solicitações dentro do mesmo parque gerariam solicitações separadas. Uma otimização por servidores de borda para truncar as coordenadas GPS para menos casas decimais significava que os resultados em cache da consulta anterior seriam usados. O número de pesquisas para o servidor por dia caiu pela metade.

Caches de software

Cache de disco

Embora os caches da CPU sejam geralmente gerenciados inteiramente por hardware, uma variedade de softwares gerencia outros caches. O cache de página na memória principal, que é um exemplo de cache de disco, é gerenciado pelo kernel do sistema operacional .

Embora o buffer de disco , que é uma parte integrada da unidade de disco rígido, às vezes seja erroneamente referido como "cache de disco", suas funções principais são sequenciamento de gravação e pré-busca de leitura. As ocorrências repetidas de cache são relativamente raras, devido ao pequeno tamanho do buffer em comparação com a capacidade da unidade. No entanto, os controladores de disco de última geração geralmente têm seu próprio cache on-board dos blocos de dados da unidade de disco rígido .

Finalmente, uma unidade de disco rígido local rápida também pode armazenar em cache informações mantidas em dispositivos de armazenamento de dados ainda mais lentos, como servidores remotos ( cache da web ) ou unidades de fita locais ou jukeboxes óticas ; tal esquema é o conceito principal de gerenciamento de armazenamento hierárquico . Além disso, drives de estado sólido (SSDs) baseados em flash rápido podem ser usados ​​como caches para drives de disco rígido de mídia rotacional mais lenta, trabalhando juntos como drives híbridos ou drives híbridos de estado sólido (SSHDs).

Cache da web

Navegadores da web e servidores proxy da web utilizam caches da web para armazenar respostas anteriores de servidores da web , como páginas da web e imagens . Os caches da Web reduzem a quantidade de informações que precisam ser transmitidas pela rede, já que as informações anteriormente armazenadas no cache podem frequentemente ser reutilizadas. Isso reduz a largura de banda e os requisitos de processamento do servidor da web e ajuda a melhorar a capacidade de resposta para os usuários da web.

Os navegadores da Web empregam um cache da Web integrado, mas alguns provedores de serviços de Internet (ISPs) ou organizações também usam um servidor proxy de cache, que é um cache da Web compartilhado entre todos os usuários dessa rede.

Outra forma de cache é o cache P2P , onde os arquivos mais procurados por aplicativos ponto a ponto são armazenados em um cache de ISP para acelerar as transferências P2P. Da mesma forma, existem equivalentes descentralizados, que permitem às comunidades realizar a mesma tarefa para o tráfego P2P, por exemplo, Corelli.

Memoização

Um cache pode armazenar dados que são calculados sob demanda, em vez de recuperados de um armazenamento de apoio. Memoização é uma técnica de otimização que armazena os resultados de chamadas de funções que consomem recursos em uma tabela de pesquisa, permitindo que chamadas subsequentes reutilizem os resultados armazenados e evitem cálculos repetidos. Está relacionado com a metodologia de design de algoritmos de programação dinâmica , que também pode ser pensada como um meio de armazenamento em cache.

Outros caches

O daemon DNS BIND armazena em cache um mapeamento de nomes de domínio para endereços IP , assim como uma biblioteca de resolução.

A operação de write-through é comum ao operar em redes não confiáveis ​​(como uma LAN Ethernet), devido à enorme complexidade do protocolo de coerência exigido entre vários caches de write-back quando a comunicação não é confiável. Por exemplo, caches de página da web e caches de sistema de arquivos de rede do lado do cliente (como aqueles em NFS ou SMB ) são normalmente somente leitura ou gravação, especificamente para manter o protocolo de rede simples e confiável.

Freqüentemente, os mecanismos de pesquisa também disponibilizam páginas da Web que indexaram em seu cache. Por exemplo, o Google fornece um link "Em cache" ao lado de cada resultado da pesquisa. Isso pode ser útil quando as páginas da web de um servidor da web estão temporariamente ou permanentemente inacessíveis.

Outro tipo de cache é o armazenamento de resultados computados que provavelmente serão necessários novamente, ou memoização . Por exemplo, ccache é um programa que armazena em cache a saída da compilação, a fim de acelerar as execuções de compilação posteriores.

O armazenamento em cache do banco de dados pode melhorar substancialmente o rendimento dos aplicativos de banco de dados , por exemplo, no processamento de índices , dicionários de dados e subconjuntos de dados usados ​​com frequência.

Um cache distribuído usa hosts em rede para fornecer escalabilidade, confiabilidade e desempenho ao aplicativo. Os hosts podem ser co-localizados ou espalhados por diferentes regiões geográficas.

Buffer vs. cache

A semântica de um "buffer" e de um "cache" não é totalmente diferente; mesmo assim, existem diferenças fundamentais de intenção entre o processo de armazenamento em cache e o processo de armazenamento em buffer.

Fundamentalmente, o armazenamento em cache realiza um aumento de desempenho para transferências de dados que estão sendo transferidos repetidamente. Embora um sistema de armazenamento em cache possa perceber um aumento de desempenho na transferência inicial (normalmente de gravação) de um item de dados, esse aumento de desempenho é devido ao armazenamento em buffer que ocorre dentro do sistema de armazenamento em cache.

Com caches de leitura, um item de dados deve ter sido buscado de seu local de residência pelo menos uma vez para que as leituras subsequentes do item de dados percebam um aumento de desempenho em virtude de poder ser buscado no armazenamento intermediário (mais rápido) do cache em vez de o local de residência dos dados. Com caches de gravação, um aumento de desempenho de gravação de um item de dados pode ser realizado após a primeira gravação do item de dados em virtude do item de dados sendo imediatamente armazenado no armazenamento intermediário do cache, adiando a transferência do item de dados para seu armazenamento residente em um estágio posterior ou então ocorrendo como um processo em segundo plano. Ao contrário do buffer estrito, um processo de cache deve aderir a um protocolo de coerência de cache (potencialmente distribuído) para manter a consistência entre o armazenamento intermediário do cache e o local onde os dados residem. Buffer, por outro lado,

  • reduz o número de transferências para dados de outra forma novos entre os processos de comunicação, o que amortiza a sobrecarga envolvida por várias pequenas transferências em menos transferências maiores,
  • fornece um intermediário para a comunicação de processos que são incapazes de transferências diretas entre si, ou
  • garante um tamanho mínimo de dados ou representação exigida por pelo menos um dos processos de comunicação envolvidos em uma transferência.

Com implementações de cache típicas, um item de dados que é lido ou escrito pela primeira vez está efetivamente sendo armazenado em buffer; e no caso de uma gravação, principalmente percebendo um aumento de desempenho para o aplicativo de onde a gravação se originou. Além disso, a parte de um protocolo de cache em que as gravações individuais são adiadas para um lote de gravações é uma forma de armazenamento em buffer. A parte de um protocolo de cache em que leituras individuais são adiadas para um lote de leituras também é uma forma de armazenamento em buffer, embora esta forma possa impactar negativamente o desempenho de pelo menos as leituras iniciais (mesmo que possa impactar positivamente o desempenho da soma de o indivíduo lê). Na prática, o armazenamento em cache quase sempre envolve alguma forma de armazenamento em buffer, enquanto o armazenamento em buffer estrito não envolve armazenamento em cache.

Um buffer é um local de memória temporário tradicionalmente usado porque as instruções da CPU não podem endereçar diretamente os dados armazenados em dispositivos periféricos. Assim, a memória endereçável é usada como um estágio intermediário. Além disso, tal buffer pode ser viável quando um grande bloco de dados é montado ou desmontado (conforme exigido por um dispositivo de armazenamento), ou quando os dados podem ser entregues em uma ordem diferente daquela em que são produzidos. Além disso, um buffer inteiro de dados geralmente é transferido sequencialmente (por exemplo, para o disco rígido), então o próprio buffer às vezes aumenta o desempenho da transferência ou reduz a variação ou jitter da latência da transferência, em oposição ao cache, onde a intenção é reduzir a latência. Esses benefícios estão presentes mesmo se os dados do buffer forem gravados no buffer uma vez e lidos do buffer uma vez.

Um cache também aumenta o desempenho de transferência. Uma parte do aumento também vem da possibilidade de que várias pequenas transferências se combinem em um grande bloco. Mas o principal ganho de desempenho ocorre porque há uma boa chance de que os mesmos dados sejam lidos do cache várias vezes ou que os dados gravados sejam lidos em breve. O único propósito de um cache é reduzir o acesso ao armazenamento subjacente mais lento. O cache também é geralmente uma camada de abstração projetada para ser invisível da perspectiva das camadas vizinhas.

Veja também

Referências

Leitura adicional