This invention relates generally to computer systems and more particularly to a prediction of branches which a computer instruction may take in pipelined processors.
As it is known in the art, computer systems have become ubiquitous. In particularly, one type of computer system widely employed is the so-called pipelined processor. In a pipelined processor instructions are decomposed into assembly like stages. Illustratively, a pipeline stage includes an instruction fetch stage in which instructions are fetched in one or several cycles from a cache memory and an instruction decode stage in which an instructions op code, that is the portion of the code which determines the function of the instruction is examined to ascertain the function of the instruction and thus the resources needed by the instruction. Illustrative resources may include general purpose registers within the CPU access to internal buses as well as external buses and functional units such as I/O units and arithmetic logic units and so forth. A third stage is typically the instruction issue stage in which resource availability is checked for each instruction and resources are reserved for particular instructions. The fourth stage of a typical pipelined processor is the execution stage in which instructions are executed in one or several execution stages writing results into the general purpose registers during the last execution stage.
In an ideal pipelined processor, time is measured in CPU clock periods. In theory, the clock period for a P-stage pipeline would be 1/P the clock period for a non-pipelined equivalent since the non-pipelined equivalent would have P-1 less stages of execution for the instruction. Thus, with the pipelined approach there is the potential for a P times improvement in throughput or performance over a conventional non-pipelined architecture.
There are several practical limitations on pipeline performance however which prevents a pipelined processor from achieving the P times throughput improvement. One particular limitation on practical performance is instruction dependencies. Instruction dependencies may be viewed as instructions which depend on the results of previous instructions and may therefore have to wait for the previous instructions to complete before they can proceed through the pipeline. Two types of instruction dependencies may be identified. The first one is the so-called data dependency which occurs when instructions use the same input and or output operands as for example when an instruction uses the result of a preceeding instruction as an input operand. A data dependency may cause an instruction to wait in the pipeline for a preceeding instruction to complete. A control dependency on the other hand, occurs when a control decision such as for example a conditional branch decision must be made before subsequent instructions can be executed.
When an instruction dependency occurs, all instructions following the instruction being executed are blocked from executing and typically the instruction in the pipeline is stalled in a pipeline stage and does not proceed further until the instruction ahead of it proceeds or until all resources and data dependencies for the particular instruction are satisfied. When a large number of instruction dependencies occur in a program executed by a pipeline processor, the performance improvement implicit in a pipeline processor are reduced accordingly.
One technique known in the art to overcome the occurrence of instruction dependencies is so-called instruction scheduling. An important characteristic of pipeline processors is that by using equivalent but reordered code sequences, the pipeline processor can provide an improved performance by eliminating many of the so-called instruction dependencies. This is often done in an instruction scheduler in which the instructions are reordered by some algorithm to eliminate register conflicts that appear to the hardware as dependencies and to reduce the occurrence of data dependencies by executing instructions in a rescheduled order.
When a processor is fed a branch type of instruction, the processor waits until a target address is calculated if the instruction is an unconditional branch such as a GO TO type of instruction, or if a conditional branch such as an IF type statement the processor waits until some branch prediction is resolved.
To improve performance of instruction scheduling and in general pipelined processor performance, branch prediction techniques have been developed.
A known technique is so called static branch prediction. In static branch prediction apparatus is provided to predict that all encountered branches are always assumed to be taken or not taken. Generally, "not taken" branches are usually assumed and the prediction is correct more often than not.
However, when there is a branch mispredict, the instruction pipeline of the processor has to be flushed of the instructions currently under execution, thus execution of the instructions is terminated and the instruction pipeline must be loaded with a new set of instructions corresponding to the correct branch address. Branch mispredicts waste processor time, particularly for very long pipelined processors.
For a large number of branch mispredicts which is implicit in a static approach the advantages obtained from a pipelined processor are reduced. This problem of branch mispredicts degrades performance concomitantly with the length of the pipeline. Thus, advantages of a long pipelined processor are also reduced with a poor branch prediction scheme.