Cache miss prediction method and apparatus

Claim 2

In a data processing system incorporating a cache memory, a method for predicting cache miss addresses comprising the steps of: A) establishing a miss stack for storing a plurality of cache miss addresses; B) waiting for a cache miss; C) when a cache miss occurs, placing the address of the called information onto the top of the miss stack; D) examining the miss stack for an address pattern among the resident cache miss addresses; E) if a pattern is not sensed, returning to step B); and F) if a pattern is sensed: 1) using the sensed pattern and at least one of the addresses in the miss stack to calculate a predictive address; 2) prefetching into cache memory the signal group identified by the predictive address; and 3) returning to step B).

Claim 3

The method of Claim 1 in which, during step D), a repertoire of predetermined address patterns are searchable, and the examination continues from pattern to pattern until a first pattern match is sensed.

Claim 4

In a data processing system incorporating a cache memory, a method for predicting cache miss addresses comprising the steps of: A) establishing a miss stack for storing a plurality of cache miss addresses; B) waiting for a cache miss; C) when a cache miss occurs, placing the address of the called information onto the top of the miss stack; D) examining the cache miss addresses resident in the miss stack for a match with a selected address pattern in a current group of a plurality of groups of patterns; E) if the selected pattern is not sensed, determining if all the patterns in the current group have been examined; F) if all the patterns in the current group have not been examined, selecting another pattern in the current group and returning to step D); G) if all the patterns in all the groups in the pattern repertoire have been searched, returning to step B); H) if all the patterns in the current group have been examined, assigning another group as the current group, selecting a pattern from the new current group and returning to step D); and I) if the selected pattern is sensed: 1) using the sensed pattern and at least one of the addresses in the miss stack to calculate a predictive address; 2) prefetching into cache memory the signal group identified by the predictive address; and 3) assigning another group as the current group and returning to step D).

Claim 5

In a data processing system incorporating a cache memory, a method for predicting cache miss addresses comprising the steps of: A) establishing a miss stack for storing a plurality of cache miss addresses; B) waiting for a cache miss; C) when a cache miss occurs, placing the address of the called information onto the top of the miss stack; D) examining the cache miss addresses resident in the miss stack for a match with a selected address pattern in a current group of a plurality of groups of patterns; E) if the selected pattern is not sensed, determining if all the patterns in the current group have been examined; F) if all the patterns in the current group have not been examined, selecting another pattern in the current group and returning to step D); G) if all the patterns in all the groups in the pattern repertoire have been searched, returning to step B); H) if all the patterns in the current group have been examined, assigning another group as the current group, selecting a pattern from the new current group and returning to step D); and I) if the selected pattern is sensed: 1) using the sensed pattern and at least one of the addresses in the miss stack to calculate a predictive address; 2) prefetching into cache memory the signal group identified by the predictive address; and 3) assigning another group as the current group and returning to step D).

Claim 6

The method of Claim 3 in which, intermediate substeps I)1) and I)3), there is performed substep I)2)a) in which the predictive address is placed onto the miss stack.

Claim 7

Apparatus for developing a predictive address for prefetching information into a cache memory comprising: A) a first in, first out stack for storing a plurality of addresses representing cache misses; B) a plurality of electronic switch means each having a plurality of address inputs and a single address output; C) means coupling said addresses stored in said stack individually to said electronic switch means inputs in predetermined orders; D) means for switching said electronic switch means to transfer said addresses applied to said electronic switch means inputs to said electronic switch outputs to establish at said electronic switch outputs predetermined combinations of said addresses; E) at least two subtraction circuit means each coupled to receive a pair of different addresses from said electronic switch means outputs and to issue a value representing the displacement therebetween; F) at least one comparator circuit means coupled to receive a pair of outputs from a corresponding pair of said subtraction circuit means and responsive thereto for issuing an prefetch enable logic signal if there is a compare condition; and G) predictive address development means adapted to combine one of said addresses appearing at one of said electronic switch outputs and displacement information appearing at one of said subtraction circuit means to obtain a predictive address; whereby, the coordinated presence of said predictive address and said prefetch enable logic signal causes a signal group identified by said predictive address to be prefetched into said cache memory.

Claim 8

Apparatus for developing a predictive address for prefetching information into a cache memory comprising: A) a first in, first out stack for storing a plurality of addresses representing cache misses; B) a plurality of electronic switch means each having a plurality of address inputs and a single address output; C) means coupling said addresses stored in said stack individually to said electronic switch means inputs in predetermined orders; D) means for switching said electronic switch means to transfer said addresses applied to said electronic switch means inputs to said electronic switch outputs to establish at said electronic switch outputs predetermined combinations of said addresses; E) at least two subtraction circuit means each coupled to receive a pair of different addresses from said electronic switch means outputs and to issue a value representing the displacement therebetween; F) at least one comparator circuit means coupled to receive a pair of outputs from a corresponding pair of said subtraction circuit means and responsive thereto for issuing an prefetch enable logic signal if there is a compare condition; and G) predictive address development means adapted to combine one of said addresses appearing at one of said electronic switch outputs and displacement information appearing at one of said subtraction circuit means to obtain a predictive address; whereby, the coordinated presence of said predictive address and said prefetch enable logic signal causes a signal group identified by said predictive address to be prefetched into said cache memory.

Claim 9

The apparatus of Claim 5 which includes at least three of said subtraction circuit means and at least two of said comparator circuit means and which further comprises: A) AND-gate means having separate inputs respectively receiving outputs coupled from said at least two comparator circuit means, said AND-­gate selectively issuing said prefetch enable logic signal only when fully enabled.

Claim 10

The apparatus of Claim 6 which further includes: A) OR-gate means driving at least one input to said AND-gate means, said OR-gate means having inputs receiving: 1. outputs coupled from at least one of said comparator circuits; and 2. a selectively applied reduce lookahead logic signal; whereby, application of said reduce lookahead signal to said OR-gate means partially enables said AND-gate means driven thereby and thus eliminates said at least one of said comparator circuits from consideration in the issuance of said prefetch enable logic signal.