Substituição de Cache de Alto Desempenho Usando Previsão de Intervalo de Re-referência (RRIP)

JULIANO ROCHA BARBOSA

Resumo do trabalho sobre o artigo:

Substituição de Cache de Alto Desempenho Usando Previsão de Intervalo de Re-referência (RRIP)

No artigo, o autor trata do problema em prever quais blocos devem estar na memória cache nos próximos intervalos de tempo, ou seja, quais blocos serão “re-referenciados”, aumentando assim a taxa de cache hits, este estudo é importante no que concerne o desempenho do computador, pois a memória cache é uma parte altamente importante nos sistemas computacionais atuais. Também atualmente há uma carência de políticas de substituição resistentes a scans e a descartes, scans são explosões de referências a temporais que tendem a permanecer no cache e que não serão mais referenciadas, ocupando apenas espaço, e ser resistente a descartes é a capacidade de preservar os blocos de cache que serão usados nos próximos instantes.

Para estes problemas, o autor propõe a substituição de cache utilizando previsão de intervalo de re-referência (RRIP) que é uma forma de ter previsões sobre os próximos blocos que serão referenciados ordenando os blocos de acordo com sua previsão, indo de previsão de re-referencia quase imediata à previsão de re-referência distante, primeiro, o autor mostra como os métodos mais comumente usados, o LRU e LFU, se saem mal em determinadas circunstâncias. Aplicações cujas re-referências ocorrem apenas em um futuro distante se saem mal sob o LRU, geralmente estas aplicações tem um conjunto de trabalho maior que o cache disponível.

Foram propostos no artigo duas variações do RRIP: O RRIP Dinâmico (DRRIP) e o RRIP Estático (SRRIP), o SRRIP é similar à política de substituição NRU que usa um bit para indicar se o bloco de cache foi recentemente utilizado ou não, bit este chamado de bit-nru. A diferença inicial se dá que o RRIP utiliza não apenas 1, mas M bits (o trabalho mostra que o valor ideal para M é por volta de 3) para o bit de controle, gerando uma cadeia de previsões de re-referência, os blocos que tem um RRIPV (o valor do bit que representa a previsão) menor estão previstos para serem re-referenciados num intervalo quase imediato enquanto os que estão na ponta da cadeia tem uma previsão distante. Então, quando um cache miss ocorrer, os bits que tem uma prioridade menor por terem uma previsão de re-referencia distante deverão ser substituídos. Com uma maior granularidade nas previsões em comparação com o NEU, é possível evitar que blocos de cache com um intervalo de re-referência distante poluam a cache. Porém, o SRRIP utiliza ineficientemente a cache quando o intervalo de re-referência de todos os blocos é maior do que a cache disponível, por isso, no DRRIP, utiliza-se o RRIP Bimodal, que insere a maioria dois blocos de cache com uma previsão de intervalo de re-referência distante, isso ajuda a preservar alguns dos conjuntos de trabalho em cache. Temos também que o SRRIP é resistente apenas a scans, enquanto o DRRIP é resistente a scans e a descartes.