US 5,293,609 A · Hit-density-based replacement for data cache with prefetching

Abstract

A least recently used cache replacement system in which the data cache is logically partitioned into two separate sections, demand and prefetch. A cache directory table and a least recently used table are used to maintain the cache. When a new demand data page is added to the cache, a most recently used (MRU) pointer is updated and points to this new page. When a prefetch page is added to the cache, the least recently used pointer of the demand section is updated with its backward pointer pointing to this new page. A cache hit on a demand of prefetch page moves that page to the top of the least recently used table. When a free page is needed in the cache, it is selected from the demand or prefetch sections of the memory based on a comparison of the demand hit density and the prefetch hit density so to maintain a balance between these two hit densities.

Claims13

Dependent claims

A computer-implemented method for replacing data in a data cache store in which demand data is stored in a demand section of said data cache store and prefetch data is stored in a prefetch section of said data cache store, comprising in combination;

storing demand data in said demand section;
storing prefetch data in said prefetch section;
determining a prefetch hit probability for said prefetch section on the basis of a ratio of a number of hits in said prefetch section to a number of prefetch requests;
determining a demand hit probability for said demand section on the basis of a ratio of a number of hits in said demand section to a number of demand requests;
determining a prefetch hit density for said prefetch section on the basis of a ratio of prefetch hit probability to a number of data entries in said prefetch section;
determining a demand hit density for said demand section on the basis of a ratio of the demand hit probability to a number of data entries in said demand section;
and
replacing an entry in said demand section or an entry in said prefetch section on the basis of a comparison of the demand hit density and the prefetch hit density.

5 more elements

Dependencies are inferred from the claim text.

Hit-density-based replacement for data cache with prefetching

Life of this patent

Hit-density-based replacement for data cache with prefetching

Life of this patent

Abstract

Claims13