These are all set to 0 when the cache is flushed, and are updated on every cache hit or replacement. Let there be three LRU bits, B0, B1, and B2. This scheme can be expanded to cope with four-way sets by dividing the four lines into three pairs 6. The bit thus indicates which line was most/least recently accessed. Then, when L0 is accessed, bit B is set to 1, else it is set to 0. We can store a single bit, B, in the set to indicate which line was last used. This is expensive to implement in hardware, so we look for an approximation to the LRU policy that is simpler to implement.Ĭonsider a two-way set-associative cache. Each line count thus indicates the age of the line since it was last referenced the line with the highest count is the oldest and is the one to be replaced. When a line is referenced, its counter is set to zero while the other three counters are incremented. A strict method for this policy is to have a counter for each line, four counters in our four-way set cache. This policy is the least recently used policy, LRU, and, in one form or another, is in wide use. However, we seek a more rational policy.Ī rational approach suggests that the least recently used (accessed) line is the least likely to be needed in the near future. This is simple to implement and surprisingly effective. The current count is used to select the line within the set. Since we need a random number between 0 and 3, the policy can be implemented by having a single 2-bit counter that is incremented whenever a particular operation occurs. The simplest policy is the random replacement policy a line within the selected set is chosen at random.
However, when the Valid bits indicate that all four of the lines are in use, a policy for the replacement of a line is needed. Clearly, if the Valid bit in a line indicates that the line is not in use, that line is the one to be replaced.
Direct mapped cache tag index offset software#
Assuming a four-way set, bits A10 to A4 of the address from the microprocessor indicate the cache location where the new line is to be stored, but which of the four lines in the set stored at that location is to be replaced? This decision must be made entirely by hardware because software will be much too slow. When a requested word is not in the cache, a new line of data is copied from main memory into the cache. Wilson, in Embedded Systems and Computer Architecture, 2002 15.3.1 Line replacement
0 kommentar(er)
