Cache é um conceito utilizado na Computação que se refere ao mecanismo de acessar de forma mais rápida informações consideradas importantes levando em conta algum critério. Este conceito é utilizado pelos navegadores Web, nas Redes de Computadores, nos Bancos de Dados, nos Servidores Web e etc.
Para fins desse micro artigo, cache se
refere à memória de alta velocidade utilizada pelo processador a fim de evitar
(ou reduzir) o acesso a “lenta” memória principal. Especificamente, abordaremos
a forma (política) como as informações contidas na cache são substituídas por
outras consideradas mais relevantes em um determinado momento.
A política de substituição das informações
da memória cachê influencia consideravelmente o desempenho do processamento das
informações em uma CPU. De acordo com Zebchuk
et. al. (2008), as políticas
de substituição comumente usadas em processadores modernos são em média 57%
pior que uma “política de substituição ótima”. Abaixo citamos as políticas de
substituição mais comuns.
Políticas de Substituição Não-Adaptativas:
LRU (Least-Recently Used): Este método utiliza uma pilha para
acompanhar a ordem dos acessos mais recentes ao conjunto de linhas da cache.
Quando uma linha é acessada, esta é movida para o topo da pilha. Ao escolher
uma linha para ser substituída por uma informação vinda da memória principal a
linha que estiver no fundo da pilha (a linha menos recentemente usada - Least-Recently Used) será
substituída. Tradicionalmente, a nova linha é colocada no topo da pilha.
LFU (Least-Frequently Used): A política LFU mantém um
contador de acesso para cada linha da memória. Ao escolher uma
linha para a substituição, a linha com a contagem mais baixa (a linha
menos freqüentemente usada - Least-frequently
Used) é descartada. Políticas LFU devem implementar um
mecanismo de envelhecimento que decrementa automaticamente o valor
do contador de acessos de cada linha ao longo do tempo para
evitar a poluição da cache com linhas obsoleto.
Políticas Aleatórias: Outras políticas não-adaptativas muito
utilizadas são as políticas N-MRU e Aleatória. A Política Aleatória escolhe
aleatoriamente uma linha para ser substituída. A vantagem deste método é que
ele não necessita de nenhum metadado (como pilhas e filas) para o seu
funcionamento. A Política N-MRU (Not Most Recently Used) é uma variação
da Política Aleatória e escolhe aleatoriamente a linha a ser substituída com
exceção da linha mais recentemente usada.
Políticas com Inserção Adaptativa:
Nestas políticas novas linhas da cache são
inseridas (e não necessariamente substituídas) na pilha. Estes métodos devem
tratar o esgotamento da memória cachê (quando o working set for maior que tamanho disponível pela
cache).
LIP (LRU Insertion Policy): É um método baseado em LRU onde novas
linhas são inseridas abaixo da pilha (posição LRU) e só as promove para o topo
da pilha (posição MRU) após um novo acesso a memória principal.
BIP (Bimodal Insertion Policy): É uma variação do LIP que utiliza um
“parâmetro bimodal” que pode alterar o comportamento LIP inserindo a nova linha
diretamente na posição MRU ou não.
Shepherd Cache:
Este método propõe uma divisão lógica de
uma cache em dois componentes. Um Shepherd
Cache com política de substituição
utilizando a filosofia FIFO (primeiro a entrar é o primeiro a
sair), e um Main Cache que emula uma política de substituição
ótima.
Pode-se encontrar na Literatura várias
outras propostas de políticas de substituição das linhas da memória cache.
Zebchuk et. al. (2008)
propõem duas novas políticas de substituição (Lightweight Shepherd Cache e Extra-Lightweight
Shepherd Cache) baseadas no método Shepherd
Cache.
Principais Referências:
- Zebchuk et. al. Re-Examining Cache Replacement Policies. Systems Technology Lab. Intel Corporation. IEEE. 2008.
- Zadnik,Martin & Canini, Marco. Evolution of Cache Replacement Policies to Track Heavy-hitter Flows. IEEE. 2011.
- Scoton, Filipe M. Power Laws na Modelagem de Caches de Microprocessadores. Universidade de São Paulo. São Paulo. 2011.
show
ResponderExcluir