Not reported jump buffer

Details Not reported jump buffer Not reported jump buffer

2000-01-10

2003-04-15

Treat, William M. (Department: 2183)

Electrical computers and digital processing systems: processing

Dynamic instruction dependency checking, monitoring or...

Commitment control or register bypass

C712S234000

Reexamination Certificate

active

06550003

ABSTRACT:

TECHNICAL FIELD
The present invention relates to the field of processors and in particular to reorder buffers in superscalar processors using out-of-order execution.
TECHNICAL BACKGROUND
In order to increase the capability of modern processors, the development is directed to solutions, where the processors execute several tasks in parallel. A superscalar processor handles more than one instruction each cycle. The reason for this development is that the speed of accessing memories has not increased in the same rate as the increased processor speed. With parallelism, more accesses can be done and even if the delay of each access is the same, more accesses can still be done over the same period of time.
The handling of large number of concurrently executed instructions has large benefits. Some of the benefits are pronounced when also using out-of-order execution, which nowadays often is employed. If an instruction has to wait for its operands a long time other instructions behind, which already have its operands ready can be executed while the first instruction waits for operands. This reduces the impact of a slow memory and maintains a higher throughput of instructions.
When using out-of-order execution, different hazards may occur. In such cases, a reorder buffer is introduced to keep track on the instructions, their results, their internal dependencies and order them in a proper program sequence.
In a superscalar processor according to prior art, predicted jumps are often used. A jump instruction may be conditioned on a certain result of another instruction, and the definite jump will not be possible to perform if the result is not available. However, if the jump instructions have to wait for the previous result to be ready for a long time, the overall speed of the processor is reduced. In order to speed up the process, the processor makes a prediction of whether the jump is going to be taken or not, and the subsequent instructions may be executed based on this. If the predicted jump was found to be correct at a later occasion, when the real result upon which the jump decision has to be made is available, the process may be continued from the point it had reached in the meantime. If the predicted jump was mispredicted, the processor has to start all over from the jump instruction and take the other path after the mispredicted jump. This means that all the instructions that are stored in the reorder buffer and other modules following the mispredicted jump instruction, have to be flushed. The probability for a correct prediction is much larger than a misprediction, so that the gain in time and reduced complexity by letting the execution continue past a predicted jump is larger than the loss caused by a flush and related actions.
In reorder buffers according to the state of the art, the processor stores all instructions in a main buffer together with associated information, e.g. concerning reading and writing addresses, sequence number etc. The main reorder buffer is normally arranged as a first-in-first-out queue in order to keep the original sequence order. The instructions are executed, and the results are temporarily stored in the reorder buffer. When the instructions have reached the first position of the buffer, i.e. when all earlier instructions are removed, a check, that the instruction is executed and that all results are normal and can be written into intended storage, is performed, the results are subsequently written into appropriate positions and the instruction is removed from the reorder queue. This procedure is known as committing the instruction.
Since a mispredicted jump instruction may cause an extensive loss of executed instructions, the evaluation of predicted jumps is requested to be performed as quickly as possible. The information stored together with the first not reported predicted jump has to be extracted from the main buffer. This information is then evaluated by the jump result that is received from the Arithmetic Logic Unit (ALU) and reported. If the prediction was correct, a flag is set in the main buffer that the predicted jump is reported to be correct and the processor searches for the next “not reported jump”. On the contrary, if the prediction was wrong, a flush signal is sent to the processor. The processor favours the evaluation of the jumps but has the disadvantage of introducing a search procedure in the main buffer. When designing processors, the problem with this solution is that the extraction of information takes too long time, in particular with a large reorder buffer and when the processor runs at a high clock speed. This means that the mispredicted jumps are then followed by too many executed instructions before they are evaluated. Since the evolution of processors tends to increase the clock speed of the processor as well as the size of the reorder buffer, there is a general problem to reduce the time and efforts for predicted jump evaluation.
DESCRIPTION OF THE INVENTION
It is a general object of the present invention to reduce the time used for evaluation of predicted jumps in a reorder buffer. It is also an object of the present invention to achieve such time reductions with as limited additional hardware means as possible, preferably less.
The above objects have been achieved by a device and method according to the accompanying claims.
In general words, the present invention has solved the problem to achieve a fast handling of the predicted jumps by introducing a separate buffer for not reported predicted jump instructions in the reorder buffer. This buffer is separate from the main buffer and contains only instructions related to predicted jumps. A predicted jump instruction is preferably stored both in the main buffer and the additional buffer. This “not reported jump queue” operates in parallel with the main buffer and in designed as a linear first-in-first-out queue. The first not reported jump is then always easily available at the top of the queue and may be evaluated and reported very rapidly.


REFERENCES:
patent: 5121473 (1992-06-01), Hodges
patent: 5765016 (1998-06-01), Walker
patent: 5778245 (1998-07-01), Papworth et al.
patent: 5805853 (1998-09-01), White et al.
patent: 5918046 (1999-06-01), Hoyt et al.
patent: 6112019 (2000-08-01), Chamdani et al.
patent: 0 685 789 (1995-12-01), None
patent: 0 731 408 (1996-09-01), None
Pihlgren, O., International-Type Search Report, Search Request No. SE99/00016, Nov. 19, 1999, pp. 1-4.

Affiliated with

Also associated with

Rating

Not reported jump buffer does not yet have a rating. At this time, there are no reviews or comments for this patent.

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

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3072281