Pipelining 379
4-State Branch Prediction Algorithm
This 2-state branch prediction algorithm may be extended to a 4-state branch prediction algorithm by
assigning one more bit with each branch instruction of the software. With two bits assigned, four differ-
ent states may be represented. These four states of branch prediction may be something like as follows:
R 00: No branching (absolutely sure) [NB]
R 01: Possibly no branching (but not so sure) [PNB]
R 10: May branch (but again not so sure) [MB]
R 11: De nitely would branch (absolutely sure) [DWB]
Just like the previous case, the bit conditions are checked as a prediction of the outcome of the
forthcoming branch instruction and instructions are fetched accordingly. In this case, if BPB is 00 or 01
then it is assumed that branching would not take place and in case of BPB being 10 or 11 the assump-
tion would be for an expected branching. The content of BPB is updated after every execution of the
concerned branch instruction in the following manner ( Figure 12.9 ).
In Figure 12.9 , the reader should note that there are two unstable and two stable states. If BPB is either
10 or 01 then the resulting state is unstable. Irrespective of the next type of branching instruction (whether
branching really takes place or not), these unstable states would either be changed to 11 or to 00. On the
other hand, the states indicated by BPB as either 00 or 11 are stable if there is no change in the next branch-
ing operation (branching or no branching) with respect to the previous branching performance.
The reader should also note that the states indicated by either BPB = 01 or BPB = 10 are not identical,
although apparently they seem to be in that state. In one case (BPB = 01), it indicates no branching (with lesser
certainty), while in the other case (BPB = 10), it indicates branching (with lesser certainty) although both are
located somewhat mid-way between absolutely sure for no-branching and absolutely sure for branching .
12.6 STRUCTURAL HAZARDS
As indicated before, structural hazard occurs when two separate instructions need to share the same hard-
ware resource at the same time. As an example, we may take up the case of the opcode fetch of one instruc-
tion and result write of the previous instruction. If in both cases, the processor needs to access the external
Figure 12.9 State-diagram for 4-state algorithm for branch-prediction
00
M12_GHOS1557_01_SE_C12.indd 379M12_GHOS1557_01_SE_C12.indd 379 4/29/11 5:24 PM4/29/11 5:24 PM
380
Figure 12.10 An example of structural hazard in a 5-stage pipeline
M12_GHOS1557_01_SE_C12.indd 380M12_GHOS1557_01_SE_C12.indd 380 4/29/11 5:24 PM4/29/11 5:24 PM
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.