Cache memory and method for cache entry replacement based on modified access order

Abstract

A cache memory and method for controlling the cache memory. The cache memory selects, from an access address, a unique set from among a plurality of sets, each access set including a plurality of cache entries. Each cache entry holds unit data for caching. The cache memory holds, for each of the cache entries, order data that indicates an access order of the cache entries in each set, and replaces a cache entry that is oldest in the access order. The cache memory modifies the order data regardless of an actual access order, and selects, based on the modified order data, a cache entry to be replaced.

1 . A cache memory which selects, from an access address, a unique set from among a plurality of sets, each set including a plurality of cache entries, each cache entry holding unit data for caching, said cache memory holding, for each of the cache entries, order data indicating an access order of the cache entries in each set, said cache memory replacing a cache entry that is oldest in the access order, said cache memory comprising:
 a modifier operable to modify the order data regardless of an actual access order; and   a selector operable to select, based on the modified order data, a cache entry to be replaced.   
     
     
         2 . The cache memory of  claim 1 , wherein said modifier comprises:
 a specifier operable to specify a cache entry that holds data which is within an address range specified by a processor; and   an oldest-orderer operable to cause the order data of the specified cache entry to become oldest in order, regardless of the actual order.   
     
     
         3 . The cache memory of  claim 2 , wherein said specifier comprises:
 a first converter operable to convert a starting address of the address range to a start line address that indicates a starting line within the address range, in a case where the starting address indicates a midpoint in line data;   a second converter operable to convert an ending address of the address range to an end line address that indicates an ending line within the address range, in a case where the ending address indicates the midpoint in the line data; and   a determiner operable to judge whether there is a cache entry that holds data corresponding to each line address from the start line address to the end line address.   
     
     
         4 . The cache memory of  claim 3 , wherein said oldest-orderer is operable to attach, to the order data, an oldest-order flag which indicates that the access order is oldest. 
     
     
         5 . The cache memory of  claim 4 , wherein when a cache miss occurs, in a case where a cache entry that has the oldest-order flag attached is present, said selector is operable to select the cache entry to be replaced, and in a case where a cache entry that has the oldest-order flag attached is not present, said selector is operable to select a cache entry to be replaced in accordance with the order data. 
     
     
         6 . The cache memory of  claim 5 , wherein the cache entry has, as the order data, a 1-bit order flag that indicates whether the access order is old or new, and said selector is operable to select, to replace, the cache entry in which the order flag indicates old, in the case where a cache entry that has the oldest-order flag attached is not present. 
     
     
         7 . The cache memory of  claim 1 , wherein said modifier is operable to modify the order data so that one cache entry shows Nth in the access order, where N is one of:
 a number indicating the oldest in the access order;   a number indicating a newest in the access order;   a number indicating Nth from the oldest in the access order; and   a number indicating Nth from the newest in the access order.   
     
     
         8 . The cache memory of  claim 1 , wherein said modifier comprises:
 an instruction detector operable to detect that a memory access instruction that includes a modification directive for the access order has been executed; and   a rewriter operable to rewrite the order data for a cache entry that is accessed due to the memory access instruction.   
     
     
         9 . The cache memory of  claim 1 , wherein said modifier comprises:
 a holder operable to hold an address range specified by a processor;   a searcher operable to search for a cache entry that holds data corresponding to the address range held in said holder; and   a rewriter operable to rewrite the order data so that the access order of the cache entry searched for by said searcher is Nth in order.   
     
     
         10 . A control method for controlling a cache memory which selects, from an access address, a unique set from among a plurality of sets, each set including a plurality of cache entries each of which holds unit data for caching, the cache memory holding, for each of the cache entries, order data indicating an access order of the cache entries included in each set, the cache memory replacing a cache entry that is oldest in the access order, the method comprising:
 modifying the order data regardless of an actual access order; and   selecting, based on the modified order data, a cache entry to be replaced.