Unlike inclusive cache, it is harder to implement an exclusive policy on cache. This post introduces two schemes for exclusive cache.

Reuse distance calculation is a problem related to cache design and evaluation. With a sequence of address references, reuse distance is defined as the number of unique addresses between two references to the same address. For example, in “A B C A C B”, the first B has an infinite reuse distance since it has never been rereferenced, while the second B has a reuse distance of 2.

Several algorithms were discovered long time ago. The following three are included in this post:

• Stack approach - Mattson et al. in 1970;
• Bit Vector approach - Bennett & Kruskal in 1975;
• AVL Tree approach - Olken in 1981;

David Black-Schaffer from Uppsala Univerity made an impressing presentation about their TLC (Tag-Less Cache) work.

TLC is a novel cache hierarchy without tag array. Instead, it stores metadata separately to avoid unnecessary cache access.