Electrical computers and digital processing systems: processing – Dynamic instruction dependency checking – monitoring or... – Scoreboarding – reservation station – or aliasing
Reexamination Certificate
2000-10-02
2003-12-30
Treat, William M. (Department: 2183)
Electrical computers and digital processing systems: processing
Dynamic instruction dependency checking, monitoring or...
Scoreboarding, reservation station, or aliasing
C712S216000
Reexamination Certificate
active
06671794
ABSTRACT:
FIELD OF THE INVENTION
This disclosure relates to a method and system for the detection of address generation interlock in a pipelined processor.
BACKGROUND
Virtually all high-performance processors today are “pipelined.” Most instructions have to go through the same basic sequence: first the instruction must be fetched, then it is decoded, then operands are fetched. Then the instruction must be executed and the results of the execution must be put away. Rather than wait for an instruction to progress through the entire sequence before starting the next instruction, most processor architectures are pipelined, whereby, once instruction m has been fetched and progresses to the decode stage, instruction m+1 is fetched. Then, instruction m progresses to the address generation stage, instruction m+1 advances to the decode stage and instruction m+2 is fetched. Thus, multiple instructions may be active at various stages of the pipeline at any one time. However, the flow of instructions into the pipeline may stall for many reasons. If, for example, instruction m modifies a register of which a subsequent instruction, say instruction m+2, needs to calculate the address of operands, instruction m+2 may proceed to the address generation stage, but must be held in there until instruction m finishes putting away its results (i.e., updating the register that instruction m+2 requires). Only then may instruction m+2 complete its address generation and continue in the pipeline. This stall in the flow of instructions into the pipeline is referred to as Address Generation Interlock (AGI).
If instructions are placed in a queue, between the Instruction-decode and execution stages and the I-decode stage is used to read general registers (GR's) in preparation for address generation (AGEN), AGI can be detected during the decode cycle by comparing the GR's required to pending GR update information from each and every appropriate instruction queue (I-queue) position. Instructions are removed from the I-queue following successful execution of the corresponding instruction.
Heretofore, this has been accomplished by saving, in each I-queue position, the first and last GR numbers defining a range of GR's to be updated by the corresponding instruction. As a new instruction is decoded, the GR's required for AGEN were compared to all pending GR update ranges within the I-queue. However, for each GR read, this required two N-bit comparators in a machine with 2
N
GR's plus some combinatorial logic to fully define pending range followed by an Z input logical OR function, where Z is the number of I-queue positions. However, as the I-queue increases in size and as the machine cycle time is reduced, it is increasingly more difficult to implement this solution.
SUMMARY OF THE INVENTION
A method and system for detecting address generation interlock in a data processor having a pipeline in the form of a plurality of serially connected processing stages including an instruction decode stage, an address calculation stage following the decode stage, and an instruction execution stage following the address calculation stage, with each stage for processing an instruction where the pipeline shifts a series of instructions from stage to stage to perform pipeline processing on the series of instructions, and with the data processor including a set of N general registers which may be written to as a result of processing an instruction at the instruction execution stage in the pipeline or may be read from during the processing of an instruction at the address calculation stage in the pipeline is disclosed. The method comprises accumulating a plurality of vectors over a predefined number of processor clock cycles, with subsequent vectors corresponding to subsequent clock cycles; accumulating the status of one or more general registers in the plurality of vectors with the same bit location in each vector of the plurality of vectors corresponding to a particular general register; generating a list of pending general register updates from a logical combination of the plurality of vectors; and determining the existence of address generation interlock from the list of pending general register updates.
REFERENCES:
patent: 4287561 (1981-09-01), Liptay
patent: 4907147 (1990-03-01), Saito et al.
patent: 4991080 (1991-02-01), Emma et al.
patent: 5127093 (1992-06-01), Moore, Jr.
patent: 5416911 (1995-05-01), Dinkjian et al.
patent: 5481683 (1996-01-01), Karim
patent: 5787303 (1998-07-01), Ishikawa
patent: 5790821 (1998-08-01), Pflum
patent: 6016540 (2000-01-01), Zaidi et al.
patent: 6212619 (2001-04-01), Dhong et al.
patent: 6266759 (2001-07-01), Birrittella
patent: 6308259 (2001-10-01), Witt
patent: 6405304 (2002-06-01), Farrell et al.
Check Mark A.
Giamei Bruce C.
Liptay John S.
Augspurger Lynn
Treat William M.
LandOfFree
Address generation interlock detection 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 generation interlock detection, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Address generation interlock detection will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3136182