Give an implementation of LRU algorithm for a 2-way set-associative cache. Solut

Question

Give an implementation of LRU algorithm for a 2-way set-associative cache.

Explanation / Answer

In the case of two-way set-associative caches with LRU, the preferred location algorithm has one big drawback: the LRU information has to be maintained in a separate table, and this table has to be updated on every probe. It is somewhat more efficient to simply keep the LRU member of a set in location 0; i.e. to use the MRU algorithm. This has the additional advantage that the position of the entry encodes the LRU information - location 1 always contains the LRU entry. The following code is an implementation of 2-way set-associative caches based on this approach: int probe_cache( unsigned address ) { unsigned tag = address >> OFFSET_BITS; unsigned set = tag & 2WAY_SET_MASK; if( cache[ set ] == tag ) { return 1; } if( cache[ set + SET_SIZE ] == tag ) { cache[ set + SET_SIZE ] = cache[ set ]; cache[ set ] = tag; return 1; } cache[ set + SET_SIZE ] = cache[ set ]; cache[ set ] = tag; return 0; } With this algorithm, hits in location 0 have exactly the same performance as a hit in a direct-mapped cache. As can be from Table 3, most of the time the probe does hit in location 0. Also, the preferred location algorithm does not do too much better than the MRU approach - on the average, preferred location generates only 5% more first location hits than MRU

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.