Patent ID: 8392660

Claim:
A cache system, comprising: a plurality of processing units operative to access a main memory device or lower-level cache; a plurality of caches coupled in one-to-one correspondence to the processing units; and a controller coupled to the caches to control data transfer between the caches and data transfer between the main memory or the lower-level cache and the caches, wherein the controller includes: a memory configured to store first information and second information separately for each of a corresponding index, the first information indicating a recently used order of entries in each one of the caches, and the second information indicating a recently used order of entries for the plurality of the caches, and a logic circuit configured to select an entry to be evicted, based on the first information and the second information, wherein when a first cache, corresponding to a first processing unit of the plurality of units which sends an address to the controller, does not include a first entry which is least recently used among the plurality of caches, the logic circuit transfers a second entry which is least recently used in the first cache to a second cache which includes an entry that is least recently used among the plurality of caches, the second cache corresponding to a second processing unit of the plurality of the processing units, and wherein the first information includes for each of the caches: information indicating which of at least two entries is an oldest entry by considering all combinations of the two entries selected from all entries belonging to one index of a given cache.