Identification and correction of cyclically recurring errors in one or more branch predictors

#1. Field of the Invention

#This invention relates to the field of data processing systems. More particularly, this invention relates to the field of branch prediction within data processing systems.

#2. Description of the Prior Art

#FIG. 1 schematically illustrates a data processing apparatus including one or more branch predictors and a supervising predictor;

#FIG. 2 schematically illustrates the supervising predictor;

#FIG. 3 is a flow diagram schematically illustrating the process of error correction by the supervising predictor;

#FIG. 1 illustrates a data processing apparatus 2 in the form of an integrated circuit which performs data processing operations in response to a stream of program instructions. The program instructions are supplied to an instruction processing pipeline. Part of this instruction processing pipeline is illustrated in FIG. 1. The stages of the instruction processing pipeline schematically illustrated are a prefetch unit 4 (which includes one or more branch predictors such as a branch target address cache, a global history table operating in conjunction with a global history buffer and other branch prediction mechanisms), a decode unit 6 and an execute unit 8. It will be appreciated by those in this technical field that many further elements will typically be present within the data processing apparatus 2. These elements will include, for example, the data path elements such as adders, multipliers and logic units as well as register banks, load store units and many other different circuit elements which will be familiar to those in this technical field. The present technique is directed toward the branch prediction behaviour of the data processing apparatus 2 and accordingly it is these elements which are illustrated in FIG. 1 and discussed in more detail below.

#Shown in FIG. 1 is a branch monitor unit 10 which verifies the branch predictions against the execution results to provide feedback to the branch predictors. The different types of branch predictor that may be employed to achieve accurate branch prediction will be known to those in this technical field. The action of a prediction monitor 12 (which includes the supervising predictor) illustrated in FIG. 1 is substantially independent of the nature of the underlying one or more branch predictors. The branch predictors update their behaviour independently of the action of the supervising predictor and the form of the branch predictors can be unaltered from their conventional form.

#The prediction monitor 12 is responsive to the results of execution of program instructions by the execution unit 8 as well as any metapredictions made by the supervising predictor associated with the program instructions being executed in order to identify cyclically recurring errors in the one or more branch predictors. The supervising predictor is not seeking to be responsive to the program instruction stream itself to identify branch instructions and predict their behaviour, but is instead operating at a higher level focusing on identifying cyclically recurring errors in the behaviour of the underlying branch predictors. This is a relatively simpler task and yet yields a worthwhile improvement in performance. The branch predictors will often have a high degree of accuracy and the remaining errors in the operation of the prefetch unit 4 will be relatively small in number and in practice many of these will be cyclically recurring errors arising as a consequence of the large scale behaviour of the program instruction stream being executed. Thus, these cyclically recurring errors can be identified by the supervising predictor and corrected behaviour can be instructed to the prefetch unit 4.