A programmable backward jump instruction prediction mechanism includes a backward
branch prediction queues (BBQ) for assisting an embedded processor to overcome an inevitable control
hazard caused in a pipeline execution for a
conditional branch instruction. A large percentage of nested loops exists in an application program executed by the embedded processor, and thus when the backward
branch encounters a nested loop, the behavior of
branch of a nested loop is similar to a
queue that will automatically restore its original status; the whole nested loop iterates at a center and repeats the execution of innermost loops (
Queue Front) and leaves the prediction miss to the next backward branch (an outer loop,
Queue Next); once if an outer loop hits a branchy, the
inner loop will repeat the branch ( and returns to the
innermost loop Queue Front). Since the
program counter (PC) and the branch address of the
queue can be used for determining whether or not the program execution is still in a nested loop or whether or not a jump is from a backward branch by the target address of the branch instruction. It is only necessary to predict an execution and compare a specific branch address in the
queue for each time, and thus the queue structure needs not to store too many instructions or quickly compare a large number of data by the associative memory technique. The hardware is very simple, but the effect is excellent. According to the
simulation analysis of the application program, it is discovered that the average prediction accuracy is up to 82% and some applications may even have an accuracy of 99%. The hardware mechansim of the invention features a low cost and a low level of complexity, and thus fully satifying the requirements for low cost, low
power consumption, and high performance / cost ratio of an embedded processor.