Address queue

Details Address queue Address queue

1995-03-14

2001-04-10

Moore, David K. (Department: 2759)

Electrical computers and digital processing systems: memory

Storage accessing and control

C711S003000, C711S202000, C711S104000, C711S118000

Reexamination Certificate

active

06216200

ABSTRACT:

A preferred embodiment of the present invention is incorporated in a superscalar processor identified as “R10000,” which was developed by Silicon Graphics, Inc., of Mountain View, Calif. Copies of Chapters 11, 12 and 13 of the design notes describing the R10000 are included as an appendix to this application and are hereby incorporated by reference in their entirety for all purposes.
BACKGROUND OF THE INVENTION
This invention relates in general to computers capable of executing instructions out of order and, in particular, to a computer capable of tracking dependencies between out-of-order instructions that are used to access memory.
From the perspective of a programmer, instructions in a conventional processor are executed sequentially. When an instruction loads a new value into its destination register, that new value is immediately available for use by subsequent instructions. This is not true, however, for pipelined computer hardware because some results are not available for many clock cycles. Sequencing becomes more complicated in a superscalar processor, which has multiple execution pipelines running in parallel. But the hardware must behave as if each instruction were completed sequentially.
Each instruction depends on previous instructions which produced its operands, because it cannot begin execution until those operands become valid. These dependencies determine the order in which instructions can be executed. The actual execution order depends on the organization of the processor. In a typical pipelined processor, instructions are executed only in program order. The next sequential instruction may begin execution during the next cycle provided all its operands are valid. Otherwise, the pipeline stalls until the operands become valid. Because instructions execute in order, stalls usually delay all subsequent instructions. A sophisticated compiler can improve performance by re-arranging instructions to reduce the frequency of these stall cycles.
In an in-order superscalar processor, several consecutive instructions may begin execution simultaneously, if all their operands are valid, but the processor stalls at any instruction whose operands are still busy. In an out-of-order superscalar processor, each instruction is eligible to begin execution as soon as its operands become valid, independently of the original instruction sequence. In effect, the hardware re-arranges instructions to keep its execution units busy. This process is called “dynamic issuing.”
Dynamic issue and execution of pipelined instructions creates a special need to monitor and resolve data dependencies between instructions. A newly-issued instruction is dependent on a previous instruction if, for example, the newly-issued instruction must use an output of the previous instruction as an operand. Such dependency inserts a restriction on the order of instruction execution.
Similarly, when out-of-order instructions are used in memory-access operations, the execution order of such instructions is restricted, at least in part, by memory dependency (i.e., two instructions accessing and altering the same memory location). Accordingly, there is a need for tracking the memory-dependency of memory-access instructions which may be executed out of order to maintain data integrity.
SUMMARY OF THE INVENTION
The present invention offers a highly efficient apparatus for tracking memory dependencies of memory-access instructions that may be executed out of order. This apparatus also provides for special identification of portions of a memory cache set to prevent unnecessary cache thrashing.
In one embodiment, the present invention provides an address queue for holding a plurality of entries used to access a set-associative data cache. This queue includes a comparator circuit, first matrix of RAM cells and second matrix of RAM cells. The comparator circuit compares a newly calculated partial address derived from a new queue entry with a previously calculated partial address derived from one of a number of previous entries. The first matrix of RAM cells tracks all of the previous entries in the queue that use a cache set that is also used by the new queue entry, The second matrix of RAM cells tracks queue entries that are store instructions which store a portion of data in the data cache which is accessed by a subsequent load instruction. The address queue may also assign status bits to certain blocks stored in the cache to identify the type of access allowed; i.e., random or sequential.
A better understanding of the nature and advantages of the present invention may be had with reference to the detailed description and the drawings below.


REFERENCES:
patent: 4466061 (1984-08-01), DeSantis et al.
patent: 5134561 (1992-07-01), Liptay
patent: 5201057 (1993-04-01), Uht
patent: 5377336 (1994-12-01), Eicknemeyer et al.
patent: 5467473 (1995-11-01), Kahle et al.
patent: 5471593 (1995-11-01), Branigin
patent: 5488729 (1996-01-01), Vegesna et al.
patent: 5511175 (1996-04-01), Favor et al.
Cocke, et al., “The Evolution of RISC Technology at IBM,” IBM J. Res. Develop., vol. 34, No. 1 p. 4-36 (Jan. 1990).
Grohoski, “Machine Organization of the IBM RISC System/6000 Processor,” IBM J. Res. Develop., vol. 34, No. 1 p. 37-58 (Jan., 1990).

Affiliated with

Also associated with

Rating

Address queue does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Address queue, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Address queue will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2439598