US 5,418,922 AGranted

History table for set prediction for accessing a set associative cache

AssigneeInternational Business Machines Corporation

InventorLishing Liu

Life of this patent

Estimating the term…

Loading patent…

Abstract

A cache control maintains a history table SETLAT for the prediction of line entry (i.e., set member) within a congruence class for cache accessing. For a given cache access, a SETLAT entry can be selected based on the requesting logical address bits directly. The selection of a SETLAT entry may also be based on the hashing of such logical address bits together with other information in order to achieve sufficient randomization. A similar hashing history table may be devised to predict virtual address translation information with high accuracy. Such prediction mechanisms not only allow efficient implementation of the cache access path but also offer the opportunity of achieving multiple accesses per cycle. The proposed prediction method also provides a generic approach to efficient implementations for various directory based table accesses.

Claims8

Dependent claims

In a set-associative cache memory system of the type wherein data lines are stored in a two-dimensional logical array of rows (called sets) and columns (called congruence classes) of storage cells and a main memory (real) address corresponds to each of the stored data lines and is stored in an associated directory, apparatus for predicting a set position in the logical array for access to a desired data line from a virtual address of the desired data line before determination of a real address corresponding thereto, comprising:

a history table for storing set positions of past successful accesses to data lines in said set-associative cache, at least some of said stored set positions being stored each at an address in said history table determined by a virtual address of the data line corresponding thereto;
and
means for accessing said history table at an access address determined by a virtual address of a desired data line and retrieving a stored set position at said access address,
said predicted set position being said retrieved set position.

1 more element

Dependencies are inferred from the claim text.