Browse Prior Art Database

Method for inverse pLRU update based on the request type

IP.com Disclosure Number: IPCOM000033801D
Publication Date: 2004-Dec-28
Document File: 3 page(s) / 275K

Publishing Venue

The IP.com Prior Art Database

Abstract

Disclosed is a method for inverse pseudo-least-recently-used (pLRU) update based on the request type. Benefits include improved functionality and improved performance.

This text was extracted from a Microsoft Word document.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 55% of the total text.

Method for inverse pLRU update based on the request type

Disclosed is a method for inverse pseudo-least-recently-used (pLRU) update based on the request type. Benefits include improved functionality and improved performance.

Background

              Conventional set-associative caches use least recently used (LRU) history mechanisms to track access patterns and select victims during capacity evictions. The LRU mechanism indicates the line that has not been accessed for the longest time. This line, based on the principle of temporal locality, is an appropriate selection for eviction. The LRU history is updated to indicate it is the not an appropriate candidate for eviction when a line is accessed.

              Set-associative caches require mechanisms for the selection of victim lines during capacity evictions. Typically, LRU algorithms are used to fulfill this requirement. They track access pattern history for each set of lines in the cache. Based on the request type and hit results, the LRU mechanism is updated to track the temporal access relationship between the lines of cache.

              The types of cache requests include the following:

•             Reads – Look up cache and return data if a line is present.

•             Allocations – Add a new line to the cache.

•             Updates – Look up the cache and update the data and state if a line is present.

•             Snoops – Look up the cache and update the state if a line is present and return data if the line is dirty.

              During an allocation request, the LRU history is accessed to select which way is to be used for the allocation of the new line. After allocation, the way is selected and the LRU is updated to indicate that the line is the most recently used. During read and update requests, the LRU history is accessed. If the line is present (a cache hit occurs), the LRU is updated to reflect that the line is the most recently used. During snoop requests, the LRU is not updated.

              A pLRU mechanism does not maintain a complete true historical ordering but rather a relative access history. A pLRU mechanism requires less logic and die area to implement,  fulfills the required functionality, and has similar performance as a true LRU mechanism.

General description

              The disclosed method is inverse pseudo-least-recently-used (pLRU) updating based on the request type. The method improves the effectiveness of victim selection.

Advantages

              The disclosed method provides advantages, including:

•             Improved functionality due to providing inverse pLRU update based on the request type

•             Improved performance due to increasing the cache hit rate

•             Improved performance due to effectively using cache by inferring future probable use fro...