
222
8.4.5
Pseudo-LRU and Cache Replacement
When a cache miss occurs during a read, the data of the missed address is read from 1 line (16
bytes) of memory and replaced. This makes it important to decide which of the ways to replace. It
is likely that the way least recently used has the highest probability of being the next to be
accessed. This algorithm for replacing ways is called the least recently used replacement
algorithm, or LRU. The hardware to implement it, however, is complex. For that reason, this
cache uses a pseudo-LRU replacement algorithm that keeps track of the order of way access and
replaces the oldest way.
Six bits of data are used as the LRU information. The bits indicate the access order for 2 ways, as
shown in figure 8.8. When the value is 1, access occurred in the direction of the appropriate arrow
in the figure. The direction of the arrow can be determined by reading the bit. All the arrows show
the oldest access toward that way, which becomes the object of replacement. The access order is
recorded in the LRU information bits, so the LRU information is rewritten when a cache hit occurs
during a read, when a cache hit occurs during a write, and when replacement occurs after a cache
miss. Table 8.3 shows the rewrite values; table 8.4 shows how ways are selected for replacement.
After a cache purge by CCR’s CP bit, the LRU information is completely zeroized, so the initial
order used is way 3
→
way 2
→
way 1
→
way 0. Thereafter the way is selected according to the
order of access set by the program. Since the replacement will not be correct if the LRU gets an
inappropriate value, the address array write function can be used to rewrite. When this is done, be
sure not to write a value other than 0 as the LRU information.
When CCR’s OD bit or ID bit is 1, neither will replace the cache even if a cache miss occurs
during data read or instruction fetch. Instead of replacing, the missed address data is read and
directly transferred to the CPU.
The two-way mode of the cache set by CCR’s TW bit can only be implemented by replacing ways
2 and 3. Comparisons of tag addresses of address arrays are carried out on all four ways even in
two-way mode, so the valid bit of ways 1 and 0 must be zeroized prior to operation in the two-way
mode.
Writing for the tag address and valid bit for cache replacement does not wait for the read from
memory to be completed. When the memory access is aborted by a reset during replacement or the
like, the cache contents and memory contents may be out of sync, so always perform a purge.