Como o bloco de cache foi substituído em cache totalmente associativo?

No conjunto de caches associativos e totalmente associativos, várias políticas de substituição são utilizadas para este fim. Algumas delas são FIFO, LRU, P-LRU, etc.

A mais popular é a estratégia LRU (menos utilizada recentemente). Neste esquema, são utilizados contadores iguais ao número de linhas de cache (um para cada linha de cache). A linha de cache menos utilizada recebe a contagem de '0′ e a mais recente recebe a contagem de 'n-1', onde n é o número de linhas de cache.

Quando um bloco é necessário e se ele's não está presente na cache, o bloco é lido a partir do dram e substituído pela linha de cache menos utilizada (count of '0′).

Então ele's viu claramente que em cada acesso, todos os contadores alteram o seu valor (se o mais recentemente utilizado não for acedido novamente). E, portanto, o consumo de energia é bastante elevado. Também será necessário um total de flops nlog(n), o que aumenta o consumo de espaço.

Para evitar estes problemas, uma estratégia diferente (pseudo LRU) é frequentemente empregada. Esta estratégia usa árvores binárias ao invés de contadores.