System and method for time weighted access frequency based caching for memory controllers

Abstract

A system and method for replacing cached data for a computer system utilizing one or more storage devices is disclosed. The storage devices are divided into a plurality of areas or bins. Each bin is preferably the same size. A Bin Access Table (BAT) is an array stored in memory that contains a frequency value for each bin corresponding to the number of times that the bin has been accessed during a predetermined time period. The BAT also contains a time stamp for each bin corresponding to the time that the bin was last accessed. A hot spot algorithm is used to calculate a hot spot factor or value hsf(x) for each bin based on its associated frequency value listed in the BAT. The frequency values may be weighted based on the time the bin was last accessed. Each line in cache will therefore correspond to a specific bin for which a time weighted hotspot factor hsf(x) has been calculated. These time weighted hot spot values are be stored in a hot spot table. When data is retrieved from a storage in response to a cache miss, a memory controller, such as a processor or RAID controller, will compare the hotspot factor hsf(a) of the bin associated with the new data to the lowest time weighted hotspot factor hsf(z) in the hot spot table. If the time weighted hsf(z) is greater than hsf(a), then this indicates that bin (z), the bin with the lowest time weighted hotspot factor, is accessed more frequently than bin (a), the bin containing the retrieved data. Thus if the time weighted hsf(z) is greater than hsf(a), then the cache line containing data from bin (z) will not be replaced. If hsf(a) is greater than the time weighted hsf(z) then the new data will replace the cached data from bin (z). The BAT table is updated after the I/O access.