Loading previously dispatched slots in multiple instruction...

Details Loading previously dispatched slots in multiple instruction... Loading previously dispatched slots in multiple instruction...

2001-05-24

2004-02-10

Kim, Kenneth S. (Department: 2181)

Electrical computers and digital processing systems: processing

Instruction issuing

Simultaneous issuance of multiple instructions

C712S023000, C712S206000

Reexamination Certificate

active

06691221

ABSTRACT:

BACKGROUND OF THE INVENTION
This invention relates to computing systems and, more particularly, to an apparatus for processing instructions in a computing system.
In a typical computing system, instructions are fetched from an instruction memory, stored in a buffer, and then dispatched for execution by one or more central processing units (CPU's).
FIGS. 1A-1C
show a conventional system where up to four instructions may be executed at a time. Assume the instructions are alphabetically listed in program sequence. As shown in
FIG. 1A
, an instruction buffer
10
contains a plurality of lines
14
A-C of instructions, wherein each line contains four instructions. The instructions stored in buffer
10
are loaded into a dispatch register
18
, comprising four registers
22
A-D, before they are dispatched for execution. When four instructions are dispatched simultaneously from dispatch register
18
, then four new instructions may be loaded from buffer
10
into dispatch register
18
, and the process continues. However, sometimes four instructions cannot be dispatched simultaneously because of resource contention or other difficulties.
FIG. 1B
shows the situation where only two instructions (A,B) may be dispatched simultaneously. In known computing systems, the system must wait until dispatch register
18
is completely empty before any further instructions may be transferred from buffer
10
into dispatch register
18
to accommodate restrictions on code alignment and type of instructions that may be loaded at any given time. Consequently, for the present example, at most only two instructions (C,D) may be dispatched during the next cycle (FIG.
1
C), and then dispatch register
18
may be reloaded (with instructions E, F, G, and H). The restriction on the loading of new instructions into dispatch register
18
can significantly degrade the bandwidth of the system, especially when some of the new instructions (e.g., E and F) could have been dispatched at the same time as the instructions remaining in the dispatch register (C,D) had they been loaded immediately after the previous set of instructions (A,B) were dispatched.
Another limitation of known computing systems may be found in the manner of handling branch instructions where processing continues at an instruction other than the instruction which sequentially follows the branch instruction in the instruction memory. In the typical case, instructions are fetched and executed sequentially using a multistage pipeline. Thus, a branch instruction is usually followed in the pipeline by the instructions which sequentially follow it in the instruction memory. When the branch condition is resolved, typically at some late stage in the overall pipeline, instruction execution must be stopped, the instructions which follow the branch instruction must be flushed from the pipeline, and the correct instruction must be fetched from the instruction memory and processed from the beginning of the pipeline. Thus, much time is wasted from the time the branch condition is resolved until the proper instruction is executed.
SUMMARY OF THE INVENTION
The present invention is directed to an apparatus for processing instructions in a computing system wherein four instructions are always made available for dispatching regardless of how many instructions are previously dispatched, and without regard to code alignment or instruction type. In one embodiment of the invention, a computing system has first and second instruction storing circuits, each instruction storing circuit storing N instructions for parallel output. An instruction dispatch circuit, coupled to the first instruction storing circuit, dispatches L instructions stored in the first instruction storing circuit, wherein L is less than or equal to N. An instruction loading circuit, coupled to the instruction dispatch circuit and to the first and second instruction storing circuits, loads L instructions from the second instruction storing circuit into the first instruction storing circuit after the L instructions are dispatched from the first instruction storing circuit and before further instructions are dispatched from the first instruction storing circuit.
The present invention also is directed to an apparatus for processing instructions in a computing system wherein branches are predicted at the time of instruction fetch, and the predicted target instruction is fetched immediately so that the target instruction is available for execution immediately after the branch instruction is executed. In one embodiment of this aspect of the invention, an instruction memory stores a plurality of lines of a plurality of instructions, and a branch memory stores a plurality of branch prediction entries, each branch prediction entry containing information for predicting whether a branch designated by a branch instruction stored in the instruction memory will be taken when the branch instruction is executed. Each branch prediction entry includes a branch target field for indicating a target address of a line containing a target instruction to be executed if the branch is taken, a destination field indicating where the target instruction is located within the line indicated by the branch target address, and a source field indicating where the branch instruction is located within the line corresponding to the target address. A counter stores an address value used for addressing the instruction memory, and an incrementing circuit increments the address value in the counter for sequentially addressing the lines in the instruction memory during normal sequential operation. A counter loading circuit loads the target address into the counter when the branch prediction entry predicts the branch designated by the branch instruction stored in the instruction memory will be taken when the branch instruction is executed. That way the line containing the target instruction may be fetched and entered into the pipeline immediately after the line containing the branch instruction. An invalidate circuit invalidates any instructions following the branch instruction in the line containing the branch instruction and prior to the target instruction in the line containing the target instruction.


REFERENCES:
patent: 4580214 (1986-04-01), Kubo et al.
patent: 4635194 (1987-01-01), Burger et al.
patent: 4682284 (1987-07-01), Schrofer
patent: 4777587 (1988-10-01), Case et al.
patent: 4984154 (1991-01-01), Hanatani et al.
patent: 5043868 (1991-08-01), Kitamura et al.
patent: 5121502 (1992-06-01), Rau et al.
patent: 5133077 (1992-07-01), Karne et al.
patent: 5136697 (1992-08-01), Johnson
patent: 5185868 (1993-02-01), Tran
patent: 5233694 (1993-08-01), Hotta et al.
patent: 5247628 (1993-09-01), Grohoski
patent: 5267350 (1993-11-01), Matsubara et al.
patent: 5283873 (1994-02-01), Steely, Jr. et al.
patent: 5297281 (1994-03-01), Emma et al.
patent: 5299321 (1994-03-01), Iizuka
patent: 5317701 (1994-05-01), Reininger et al.
patent: 5333281 (1994-07-01), Nishikawa et al.
patent: 5367703 (1994-11-01), Levitan
patent: 5390355 (1995-02-01), Horst
patent: 5404552 (1995-04-01), Ikenaga
patent: 5414822 (1995-05-01), Saito et al.
patent: 5497496 (1996-03-01), Ando
patent: 5553254 (1996-09-01), Berstis et al.
patent: 5680564 (1997-10-01), Divivier et al.
patent: 5835746 (1998-11-01), Girardeau, Jr. et al.
patent: 5978896 (1999-11-01), Kahle et al.
patent: 6065110 (2000-05-01), Meltzer et al.
patent: 42 11 222 (1992-10-01), None
patent: 42 16 905 (1993-01-01), None
patent: 0 116 883 (1984-08-01), None
patent: 0 240 870 (1987-10-01), None
patent: 0 372 865 (1990-06-01), None
patent: 0 380 854 (1990-08-01), None
patent: 0 401 992 (1990-12-01), None
patent: 0 477 598 (1992-04-01), None
patent: 50-152629 (1975-12-01), None
patent: 57-29153 (1982-02-01), None
patent: 57-152046 (1982-09-01), None
patent: 59-91549 (1984-05-01), None
patent: 4-247522 (1992-09-01), None
patent: 4-328636 (1992-11-01), None
patent: 5-2484 (1993-01-01), None
Young, H.C. and Shekita, E.J., “An Intelligent I-Cache Prefetch Mechanism,”Proceedings—1993 IEEE International Con

Affiliated with

Also associated with

Rating

Loading previously dispatched slots in multiple instruction... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Loading previously dispatched slots in multiple instruction..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Loading previously dispatched slots in multiple instruction... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3342818