A cache is commonly provided in a system having a processor to store items of information for access by the processor at a lower “cost” than if the cache were not present. For example, a system may be structured such that the processor can obtain data or program instructions stored in one memory faster than other memories. This memory may be used as a cache so that frequently-accessed information contained in the other memories may be copied into and accessed from the cache instead. In addition, the use of a cache may help to reduce internal data traffic between the processor and internal system elements such as a memory or input-output interface when the information items are available locally, as well as reduce external data traffic between the system and a remote system when the information is not available locally.
Caches are often too small to store all of the information a processor may need. Accordingly, cache-based systems typically need to be selective when it comes to determining which information will be stored in the cache. For example, a processor may repeatedly and frequently access ten different items of information, but the cache may only be able to store five.
Various algorithms have been used to determine when an item should be stored in the cache. For example, some existing systems automatically store the most-recently used information in the cache. If the processor recently processed ten items and the cache can store five, the last five discrete items are stored in the cache regardless of how often the items are used.