Electrical computers and digital processing systems: memory – Storage accessing and control – Hierarchical memories
Reexamination Certificate
1999-12-14
2003-07-08
Hudspeth, David (Department: 2651)
Electrical computers and digital processing systems: memory
Storage accessing and control
Hierarchical memories
C711S169000
Reexamination Certificate
active
06591342
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to processors having large instruction windows, and more specifically to memory disambiguation in processors having large instruction windows.
BACKGROUND OF THE INVENTION
With every new generation of microprocessors, instruction window sizes are increasing. The term “instruction window” describes the set of processor instructions in various stages of execution at any given time. As newer generations of processors continue to increase the number of parallel execution units and the depth of pipelines, the number of processor instructions in the instruction window at any given time continues to increase.
Some processors with parallel execution units can execute many processor instructions in parallel. This improves program execution speed. Instructions enter the instruction window when they are read from the software program in “program order.” “Program order” is the sequential order of the processor instructions in the program. When in the instruction window, different instructions can be scheduled to be executed by different execution units. This can lead to instructions being executed out of program order, or “out-of-order.”
The execution order of some processor instructions can be important. Examples include “load” instructions that read the contents of memory locations, and “store” instructions that update the contents of memory locations. For example, if a load instruction and a store instruction that specify the same memory location exist in a program with the store instruction preceding the load instruction in program order, the load instruction is said to be “dependent” on the store instruction. If the dependent load instruction accesses the memory location before the store instruction, the load instruction will read the memory location contents prior to the update by the store instruction, and an error will result. When a load instruction is dependent on a store instruction, the program order of these two instructions should be respected by the processor executing them.
FIG. 1
shows a prior art store queue. Store queue
100
is a fully associative queue that includes information from every store instruction that is in the instruction window. When a store instruction is read from the program, information from the store instruction is deposited in store queue
100
, where it stays for as long as the store instruction is in the instruction window. Store queue
100
includes entries
130
, each of which including a store address (STA) field
110
and store data (STD) field
120
. When a store instruction is encountered in a program, an entry in store queue
100
is allocated, and to the extent that information is available to fill in STA field
110
and STD field
120
, they are filled in. When a store instruction is completed, or “retired,” the corresponding entry is removed from store queue
100
.
When a load instruction is encountered in a program, store queue
100
is searched to see if store queue
100
includes a store instruction upon which the load instruction depends. If one of entries
130
has an STA field
110
that matches the address corresponding to the load instruction, then the load instruction is dependent. If no such store instruction is found in store queue
100
, the load instruction can be executed immediately without causing an erroneous out-of-order condition. This is called “memory disambiguation.” If a store instruction upon which the load instruction depends is found, then execution of the load instruction can be delayed, or the load instruction can be satisfied by reading the data value from store queue
100
rather than from the memory location. This is called “store data forwarding.” Store queue
100
is a fully associative queue that is completely searched each time a load instruction is encountered in a program. The search of store queue
100
takes time. For each load instruction encountered in a program, time is spent in a sequential search of store queue
100
to find any store instructions upon which the load instruction depends, and to find data to satisfy the load instruction with a store data forwarding operation. As instruction windows increase in size, store queue
100
and the associated search time also increase in size. When store queue
100
is very large, the search time can become so large as to cause performance problems.
For the reasons stated above, and for other reasons stated below which will become apparent to those skilled in the art upon reading and understanding the present specification, there is a need in the art for an alternate method and apparatus for providing memory disambiguation.
SUMMARY OF THE INVENTION
In one embodiment, a method of executing instructions in an out-of-order processor includes receiving a decoded instruction such as a store instruction that is configured to store a data value to a memory address. The instruction is inserted in a queue, and the instruction is also assigned to an entry in a set-associative buffer.
In another embodiment, a method of executing instructions includes issuing and removing a store instruction from a queue to a memory such that a data value associated with the store instruction is stored at a memory location specified by a memory address associated with the store instruction. The method also includes searching a set-associative buffer for an entry corresponding to the store instruction, and when the entry corresponding to the store instruction is found, removing the entry from the set-associative buffer.
In another embodiment, a method of executing instructions in an out-of-order processor includes receiving a first decoded instruction that is configured to load a data value from a memory address, and allocating an entry in a queue for the instruction. The method also includes searching a set of a set-associative buffer for a second instruction upon which the first instruction depends.
In another embodiment, a memory disambiguation apparatus includes a queue configured to hold all of the store instructions that are in an instruction window, and a set-associative buffer configured to hold a subset of the store instructions that are in the instruction window. In this embodiment, the set-associative buffer is organized in multiple sets, and each of the store instructions in the set-associative buffer has resolved memory addresses. Each of the multiple sets is configured to be searched for store instructions upon which a load instruction depends.
In another embodiment, a memory disambiguation apparatus includes a set-associative buffer arranged in sets, where each set includes buffer entries, and each of the buffer entries includes a tag field and a data field. In this embodiment, each of the buffer entries corresponds to a separate store instruction in an instruction window. Also included in this embodiment are overflow indicators, where each overflow indicator has a one-to-many relationship with the buffer entries in the set-associative buffer.
REFERENCES:
patent: 5420991 (1995-05-01), Konigsfeld et al.
patent: 5434987 (1995-07-01), Abramson et al.
patent: 5564034 (1996-10-01), Miyake
patent: 5564111 (1996-10-01), Glew et al.
patent: 5577200 (1996-11-01), Abramson et al.
patent: 5588126 (1996-12-01), Abramson et al.
patent: 5606670 (1997-02-01), Abramson et al.
patent: 5613083 (1997-03-01), Glew et al.
patent: 5625835 (1997-04-01), Ebcioglu et al.
patent: 5664137 (1997-09-01), Abramson et al.
patent: 5694574 (1997-12-01), Abramson et al.
patent: 5694577 (1997-12-01), Kiyohara et al.
patent: 5717882 (1998-02-01), Abramson et al.
patent: 5724536 (1998-03-01), Abramson et al.
patent: 5748937 (1998-05-01), Abramson et al.
patent: 5751983 (1998-05-01), Abramson et al.
patent: 5767856 (1998-06-01), Peterson et al.
patent: 5826109 (1998-10-01), Abramson et al.
patent: 5838943 (1998-11-01), Ramagopal et al.
patent: 5860154 (1999-01-01), Abramson et al.
patent: 5881262 (1999-03-01), Abramson et al.
patent: 5897666 (1999-04-01), Mallick et al.
patent: 5948100 (1999-09-01), Hsu et al.
patent: 5956753 (1999-09-01),
Akkary Haitham
Hily Sebastien
Hudspeth David
Schwegman Lundberg Woessner & Kluth P.A.
Tzeng Fred F.
LandOfFree
Memory disambiguation for large instruction windows does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Memory disambiguation for large instruction windows, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Memory disambiguation for large instruction windows will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3004147