Method for maintaining low-overhead and non-coherent cache refresh mechanism with valid status monitoring on time period basis

Claim 1

A method of operating a cache, comprising the steps of: (A) for each of data requests generated by a processor coupled to the cache, performing the following steps: (i) determining whether a copy of the requested data is stored in the cache; (ii) if a copy of the requested data is determined to be stored in the cache, performing the following steps: (a) retrieving a status flag associated with the stored copy of the requested data from the cache, the retrieved status flag indicating whether the stored copy of the requested data has an IDLE, VALID, DYING, or REFRESH status, the IDLE status indicating that the stored copy is non-usable for satisfying processor data requests, the VALID status indicating that the stored copy is usable for satisfying processor data requests for at least a first time period T 1 commencing when the stored copy first attains VALID status, the DYING status indicating that the stored copy is usable for satisfying processor data requests but will become non-usable after the passage of a second time period T 2 in the absence of access thereto by the processor, the second time period T 2 commencing when the stored copy first attains DYING status, and the REFRESH status indicating that the stored copy is usable for satisfying processor data requests but will shortly be replaced by a fresh copy of the requested data to be retrieved from a memory coupled to the cache; (b) if the stored copy is indicated by the retrieved status flag as having an IDLE status, performing the steps recited in (A)(iii) below for the case in which a copy of the requested data is determined not to be stored in the cache; (c) if the stored copy is indicated by the retrieved status flag as having either a VALID, DYING, or REFRESH status, retrieving the stored copy of the requested data and returning the retrieved copy to the processor in satisfaction of the processor's data request; and (d) if the stored copy is indicated by the retrieved status flag as having a DYING status, performing the following steps: (1) changing the stored status flag to indicate that the stored copy now has a REFRESH status; and (2) initiating an update of the stored copy from the memory; and (iii) if a copy of the requested data is determined not to be stored in the cache, performing the following steps: (a) retrieving a copy of the requested data from the memory; (b) storing the retrieved copy in the cache; (c) setting the status flag associated with the stored retrieved copy to VALID upon storing the retrieved copy in the cache; and (d) returning the retrieved data to the processor in satisfaction of the processor's data request; (B) for each of stored copies of requested data in the cache, periodically performing the following steps: (i) retrieving the status flag associated with the stored copy; (ii) if the retrieved status flag indicates that the stored copy has a VALID status, performing the following steps: (a) monitoring the passage of T 1 for the stored copy; and (b) setting the status flag for the stored copy to DYING if T 1 has passed; and (iii) if the retrieved status flag indicates that the stored copy has a DYING status, performing the following steps: (a) monitoring the passage of T 2 ; and (b) setting the status flag for the stored copy to IDLE if T 2 has passed; and (C) for each of the stored copies for which an update from the memory has been initiated, performing the following steps: (i) retrieving a fresh copy of the requested data from the memory; (ii) storing the retrieved fresh copy in the cache replacing the stored copy; and (iii) setting the status flag for the stored fresh copy to VALID upon storing the retrieved fresh copy in the cache.

Claim 2

A method of operating a cache, comprising the steps of: (A) for each of data requests generated by a processor coupled to the cache, performing the following steps: (i) determining whether a copy of the requested data is stored in the cache; (ii) if a copy of the requested data is determined to be stored in the cache, performing the following steps: (a) retrieving a status flag associated with the stored copy of the requested data from the cache, the retrieved status flag indicating whether the stored copy of the requested data has an IDLE, VALID, DYING, or REFRESH status, the IDLE status indicating that the stored copy is non-usable for satisfying processor data requests, the VALID status indicating that the stored copy is usable for satisfying processor data requests for at least a first time period T 1 commencing when the stored copy first attains VALID status, the DYING status indicating that the stored copy is usable for satisfying processor data requests but will become non-usable after the passage of a second time period T 2 in the absence of access thereto by the processor, the second time period T 2 commencing when the stored copy first attains DYING status, and the REFRESH status indicating that the stored copy is usable for satisfying processor data requests but will shortly be replaced by a fresh copy of the requested data to be retrieved from a memory coupled to the cache; (b) if the stored copy is indicated by the retrieved status flag as having an IDLE status, performing the steps recited in (A)(iii) below for the case in which a copy of the requested data is determined not to be stored in the cache; (c) if the stored copy is indicated by the retrieved status flag as having either a VALID, DYING, or REFRESH status, retrieving the stored copy of the requested data and returning the retrieved copy to the processor in satisfaction of the processor's data request; and (d) if the stored copy is indicated by the retrieved status flag as having a DYING status, performing the following steps: (1) changing the stored status flag to indicate that the stored copy now has a REFRESH status; and (2) initiating an update of the stored copy from the memory; and (iii) if a copy of the requested data is determined not to be stored in the cache, performing the following steps: (a) retrieving a copy of the requested data from the memory; (b) storing the retrieved copy in the cache; (c) setting the status flag associated with the stored retrieved copy to VALID upon storing the retrieved copy in the cache; and (d) returning the retrieved data to the processor in satisfaction of the processor's data request; (B) for each of stored copies of requested data in the cache, periodically performing the following steps: (i) retrieving the status flag associated with the stored copy; (ii) if the retrieved status flag indicates that the stored copy has a VALID status, performing the following steps: (a) monitoring the passage of T 1 for the stored copy; and (b) setting the status flag for the stored copy to DYING if T 1 has passed; and (iii) if the retrieved status flag indicates that the stored copy has a DYING status, performing the following steps: (a) monitoring the passage of T 2 ; and (b) setting the status flag for the stored copy to IDLE if T 2 has passed; and (C) for each of the stored copies for which an update from the memory has been initiated, performing the following steps: (i) retrieving a fresh copy of the requested data from the memory; (ii) storing the retrieved fresh copy in the cache replacing the stored copy; and (iii) setting the status flag for the stored fresh copy to VALID upon storing the retrieved fresh copy in the cache.