Excache Replacement Policies

[sarsanaee]

Hello,

I'm wondering why you chose to have different policies for your replacement policies? I thought the default LRU which is just an approximation of LRU would suffice for your case. But you still have implemented the FIFO.

What surprised me is the fact that FIFO is actually performing better than LRU. And I don't quite understand why FIFO is better that the LRU (Figure 13).

Also, I was wondering why fully associative Excache would not work for this case and you decided to have the set-associative organization there.

I would be thankful if you could provide some insights into this issue.

Thanks,
Alireza

[lastweek]

Hi @sarsanaee.

Maintaining an LRU list for physical pages is not cheap. The only information hardware provides is the Accessed bit of PTE entries. Our approach is to use a background daemon thread to periodically scan the PTE entries, extract the Accessed bit, update the LRU list, clear the Accessed bit (in theory, we need to flush TLB as well). The whole operation not only increases the PTE lock contention, but also generates a lot more cache coherence traffic, both of them are heavy taxes.

In our experiments with our current implementation, the LRU scanning cost is just too high. There are lot parameters to tune. But FIFO always turns out to be the best performant one.

Maybe its just our implementation issue. Google has used the same mechanism to extract the same information, and they manage to keep the cost low, though they don't have too much impl details. https://dl.acm.org/citation.cfm?id=3304053