Electrical computers and digital processing systems: processing – Processing control – Branching
Reexamination Certificate
1999-03-18
2001-05-15
Chan, Eddie (Department: 2183)
Electrical computers and digital processing systems: processing
Processing control
Branching
C712S234000, C712S238000, C712S239000
Reexamination Certificate
active
06233676
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates in general to the field of instruction execution in computers, and more particularly to an apparatus and method for executing a forward branch instruction in a pipeline microprocessor.
2. Description of the Related Art
An application program for execution on a microprocessor consists of a structured series of macro instructions that are stored in sequential locations in memory. A current instruction pointer within the microprocessor points to the address of the instruction currently being executed and a next instruction pointer within the microprocessor points to the address of the next instruction for execution. During each clock cycle, the length of the current instruction is added to the contents of the current instruction pointer to form a pointer to a next sequential instruction in memory. The pointer to the next sequential instruction is provided to logic that updates the next instruction pointer. If the logic determines that the next sequential instruction is indeed required for execution, then the next instruction pointer is updated with the pointer to the next sequential instruction in memory. Thus, macro instructions are fetched from memory in sequence for execution by the microprocessor.
Obviously, because a microprocessor is designed to execute instructions from memory in the sequence that they are stored, it follows that a program configured to execute macro instructions sequentially from memory is one which will run efficiently on the microprocessor. For this reason, most application programs are designed to minimize the number of instances where macro instructions are executed out of sequence. These out-of-sequence instances are known as jumps, or branches.
A program branch presents a problem because most conventional microprocessors do not simply execute one instruction at a time. Rather, a present day microprocessor consists of a number of pipeline stages, each stage performing a specific function. Instructions, inputs, and results from one stage to the next are passed in synchronization with a pipeline clock. Hence, several instructions may be executing in different stages of the microprocessor pipeline within the same clock cycle. As a result, when logic within a given stage determines that a program branch is to occur, then previous stages of the pipeline, that is, stages that are executing instructions following in sequence, must be cast out to begin execution of sequential macro instructions beginning with the instruction directed by the branch, or the branch target instruction. This casting out of previous pipeline stages is known as flushing and refilling the pipeline.
Additionally, a microprocessor maintains a number of sequential macro instructions queued up for decode in an instruction buffer, so that a macro instruction is provided each clock cycle for execution. When a program branch is encountered, the contents of the instruction buffer must also be flushed and refilled.
A conditional branch is a branch that may or may not occur, depending upon the evaluation of some specified condition. And, this evaluation is typically performed in later stages of the microprocessor pipeline. To preclude wasting many clock cycles associated with flushing and refilling the pipeline, present day microprocessors also provide logic in an early pipeline stage that predicts whether a conditional branch will occur or not. If it is predicted that a conditional branch will occur, then only those instructions prior to the early pipeline stage must be flushed, including those in the instruction buffer. Even so, this is a drastic improvement; correctly predicted branches are executed in roughly two clock cycles rather than many more.
Yet, present day branch prediction techniques do not consider the contents of the instruction buffer, because the branch prediction typically occurs in a pipeline stage that follows the instruction buffer. In fact, even if the target instruction for the branch is already present in the instruction buffer, the instruction buffer is still flushed and refilled. Thus, the target instruction is fetched again and placed in the buffer.
It has been observed that a notable percentage of conditional branch instructions in application programs branch forward in sequence by only a few instructions. Consequently, when these programs execute on a conventional microprocessor, a significant number of clock cycles are wasted flushing and refilling the instruction buffer with virtually the same contents. When branch prediction logic declares that a conditional branch will be taken, it is very likely that the branch target instruction is already in the instruction buffer.
Therefore, what is needed is a microprocessor that executes a forward branch much faster than has heretofore been provided.
In addition, what is needed is an apparatus in a microprocessor that determines if a branch target instruction is already within its instruction buffer when a branch is declared.
Furthermore, what is needed is a microprocessor that shifts a branch target instruction to the front of the instruction buffer when a conditional branch is declared rather than flushing the buffer and fetching the branch target instruction again.
Moreover, what is needed is a method for executing a forward branch in a microprocessor that determines if a branch target instruction is present in an instruction buffer and, if so, shifts it to the front of the buffer.
SUMMARY
To address the above-detailed deficiencies, it is an object of the present invention to provide a microprocessor that executes a forward branch without incurring undue delays associated with flushing and refetching a target instruction for the branch from the microprocessor's instruction buffer.
Accordingly, in the attainment of the aforementioned object, it is a feature of the present invention to provide a microprocessor for executing a forward branch. The microprocessor includes translation logic and instruction fetch logic. The translation logic receives a branch instruction from a front position of an instruction buffer, and directs the microprocessor to provide a branch target instruction in said front position. The instruction fetch logic is coupled to the translation logic and provides the branch target instruction in the front position. If the branch target instruction is already within the instruction buffer, then the instruction fetch logic shifts the branch target instruction directly to the front position.
Another object of the present invention is to provide an apparatus in a microprocessor that determines if a branch target instruction is already within its instruction buffer when a branch is declared.
In another aspect, it is a feature of the present invention to provide an apparatus in a microprocessor for providing a branch target instruction for translation. The apparatus has an instruction decoder, branch prediction logic, and instruction fetch logic. The instruction decoder receives a branch instruction from a front position in an instruction buffer and translates the branch instruction into associated micro instructions for execution by the microprocessor. The branch prediction logic is coupled to the instruction decoder and predicts that execution of the associated micro instructions will result in a branch to a branch target instruction. The branch prediction logic also directs the microprocessor to provide the branch target instruction in the front position. The instruction fetch logic is coupled to the branch prediction logic and determines if the branch target instruction is already within the instruction buffer. If the branch target instruction is already within the instruction buffer, the instruction fetch logic shifts the branch target instruction directly to the front position.
Another advantage of the present invention is that clock cycles are not wasted performing unnecessary flushes of the microprocessor's instruction buffer.
A further object of the invention is to provide a microprocessor that shifts a branch t
Henry G. Glenn
Parks Terry
Chan Eddie
Huffman James W.
Huffman Richard K.
IP-First L.L.C.
Nguyen Dzung C.
LandOfFree
Apparatus and method for fast forward branch does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Apparatus and method for fast forward branch, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apparatus and method for fast forward branch will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2438161