US 5,694,572 A · Controllably operable method and apparatus for predicting addresses of future operand requests by examination of addresses of prior cache misses

Abstract

In a data processing system which employs a cache memory feature, a method and exemplary special purpose apparatus for practicing the method are disclosed to lower the cache miss ratio for called operands. Recent cache misses are stored in a first in, first out miss stack, and the stored addresses are searched for displacement patterns thereamong. Any detected pattern is then employed to predict a succeeding cache miss by prefetching from main memory the signal identified by the predictive address. The apparatus for performing this task is preferably hard wired for speed purposes and includes subtraction circuits for evaluating variously displaced addresses in the miss stack and comparator circuits for determining if the outputs from at least two subtraction circuits are the same indicating a pattern yielding information which can be combined with an address in the stack to develop a predictive address. The cache miss prediction mechanism is only selectively enabled during cache "in-rush" following a process change to increase the recovery rate; thereafter, it is disabled, based upon timing-out a timer or reaching a hit ratio threshold, in order that normal procedures allow the hit ratio to stabilize at a higher percentage than if the cache miss prediction mechanism were operated continuously.

Claims27

Dependent claims

An operand address prediction procedure for selectively predicting operand request addresses from historic cache miss addresses practiced in a data processing system incorporating a processor for running successive processes, a cache memory and a main memory, the procedure comprising the computer-implemented steps of:

during the system hardware, firmware and software design procedure, performing the preliminary step of:
A) establishing a first in, first out miss stack for storing a plurality of cache miss addresses by employing at least a selected one of hardware, firmware and software design and implementation techniques;
and, during system operation, performing the following steps within the system:
B) waiting for a cache miss resulting from the absence in the cache of called information requested of the cache;
C) when a cache miss occurs, placing the address of the called information onto the top of the miss stack;
D) selecting, from among a plurality of pattern groups comprising a pattern repertoire, a current pattern group;
E) examining the cache miss addresses resident in the miss stack for a match with a selected address pattern in the current pattern group;
F) if the selected pattern is not matched, determining if all the patterns in the current group have been examined;
G) if all the patterns in the current pattern group have not been examined, selecting, from the current pattern group, a different pattern than the pattern last examined and returning to step E);
H) if all the patterns in all the groups in the pattern repertoire have been searched, returning to step B);
I) if all the patterns in the current pattern group have been examined, assigning a new pattern group, different from the pattern group last examined, as the current group, selecting a pattern from the new current group and returning to step E);
and
J) if the selected pattern is matched:
1) using the matched pattern and at least one of the addresses in the miss stack to calculate a predictive address pointed to a signal group stored in the main memory;
2) prefetching into cache memory from the main memory the signal group identified by the predictive address;
and
3) assigning another group as the current group and returning to step E);
wherein said procedure of said steps B through J is performed only during intervals which commence immediately after a process change and terminate upon the first occurence of a succeeding predetermined event, which predetermined event occurs after the maximum rate of increase in the operative hit rate of said cache memory is reached following said process change.

15 more elements

In a data processing system including a processor for running successive processes, a cache memory, a main memory and an operand address prediction mechanism for developing a predictive address for prefetching operands, each identified by an address, from the main memory into the cache memory, which operand address prediction mechanism comprises a first mechanism including:

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 said subtraction circuit means being coupled to receive a unique pair of 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 a prefetch enable logic signal if there is a compare condition;
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 from said main memory into said cache memory;
and
a control circuit coupled to said first mechanism for enabling said first mechanism to operate only during intervals which commence immediately after a process change and terminate upon the first occurence of a succeeding predetermined event, which predetermined event occurs after the maximum rate of increase in the operative hit rate of the cache memory is reached following said process change.

7 more elements

The method for predicting operand addresses of operand requests in a data processing system in which a cache thereof is repeatedly interrogated to determine whether an address corresponding to a request operand address is stored therein, which stored operand address corresponds to an operand also stored in said cache;

wherein said data processing system includes a main memory and a stack for holding addresses;
said method being carried out by said data processing system in operating said cache, characterized by the computer-implemented steps of:
A) upon the occurence of a cache miss when an operand is requested from said cache, entering the request operand address into said stack;
B) examining the request operand addresses present in said stack to determine whether one of a plurality of predetermined operand address patterns is represented by said request operand addresses;
and
C) (1) if no one of said patterns is determined to be represented in step (B), returning to step (A), but
(2) (i) if one of said patterns is determined to be represented in step (B), generating an operand address of a predicted operand request,
(ii) using said generated operand address to obtain an operand from said main memory and write such operand into said cache, and
(iii) returning to step (A);
wherein said method of steps A-C is performed only during intervals which commence immediately after a process change and terminate upon the first occurence of a succeeding predetermined event, which predetermined event occurs after the maximum rate of increase in the operative hit rate of said cache is reached following said process change.

7 more elements

Apparatus for controllably generating a predicted operand address of an operand request in a data processing system in which a cache thereof is repeatedly interrogated to determine whether an address corresponding to a request operand address is stored therein, which stored operand address corresponds to an operand also stored in said cache;

wherein said data processing system includes a store for holding a plurality of said addresses in respective cells thereof;
said apparatus being characterized by:
a controllable operand address prediction mechanism comprising:
a plurality of switches, each of said switches having a plurality of input terminals, an output terminal and a control terminal, whereby a control signal applied to said control terminal causes said switch to couple one of said input terminals to said output terminal;
said control signal being delivered to said control terminals to cause the input terminals of said switches to be successively coupled to said output terminals;
a circuit coupling each of said input terminals of said switches to one of said cells;
a plurality of first arithmetic circuits, each of said first arithmetic circuits having a pair of input terminals and an output terminal, the input terminals of each of said first arithmetic circuits being coupled to the respective output terminals of two of said switches, each of said first arithmetic circuits performing an arithmetic operation on the two addresses received by its input terminals from the two cells of said store coupled to said input terminals by said two switches and delivering a signal at its output terminal which represents the result of said arithmetic operation;
a plurality of comparators, each of said comparators having a pair of input terminals and an output terminal, the input terminals of each of said comparators being coupled to the respective output terminals of two of said first arithmetic circuits, each of said comparators comparing the two arithmetic result signals received thereby and delivering a signal at its output terminal denoting whether said result signals are alike;
a second arithmetic circuit having a pair of input terminals and an output terminal, a first input terminal of said second arithmetic circuit being coupled to the output terminal of one of said switches and the second input terminal of said second arithmetic circuit being coupled to the output terminal of one of said first arithmetic circuits, said second arithmetic circuit performing an arithmetic operation on the address received by said first input terminal and the arithmetic result represented by the signal received by said second input terminal and delivering an output signal at its output terminal which represents the result of said arithmetic operation performed by said second arithmetic circuit;
whereby when the signals delivered at the output terminals of all of said comparators denote that the compared arithmetic results are alike, the arithmetic result represented by the concurrent output signal of said second arithmetic circuit represents said predicted operand request address;
and
a control circuit coupled to said prediction mechanism for enabling said prediction mechanism to operate only during intervals which commence immediately after a process change and terminate upon the first occurence of a succeeding predetermined event, which predetermined event occurs after the maximum rate of increase in the operative hit rate of said cache is reached following said process change.

9 more elements

The method for predicting operand addresses of operand requests in a data processing system in which a cache thereof is repeatedly interrogated to determine whether an operand address corresponding to a requested operand is stored therein, said cache storing operands and their corresponding operand addresses;

wherein said data processing system includes a main memory;
said method being carried out by said data processing system in operating said cache, characterized by the computer-implemented steps of:
A) upon the generation of and interrogation of said cache by a request operand address,
B) determining whether a plurality of earlier-generated request operand addresses correspond to one of a plurality of predetermined operand address patterns, and
C) (1) if no one of said patterns is determined to correspond to said plurality of request operand addresses in step (B), returning to step (A), but
(2) (i) if one of said patterns is determined to correspond to said plurality of request operand addresses, generating an operand address of a predicted operand request using said one pattern,
(ii) obtaining the operand from the main memory location represented by said predicted operand address and writing said operand into said cache, and
(iii) returning to step (A),
wherein said method of steps A-C is performed only during intervals which commence immediately after a process change and terminate upon the first occurence of a succeeding predetermined event, which predetermined event occurs after the maximum rate of increase in the operative hit rate of said cache is reached following said process change.

6 more elements

Dependencies are inferred from the claim text.

Controllably operable method and apparatus for predicting addresses of future operand requests by examination of addresses of prior cache misses

Life of this patent

Controllably operable method and apparatus for predicting addresses of future operand requests by examination of addresses of prior cache misses

Life of this patent

Abstract

Claims27