Branch Prediction | Computer Architecture
Budget: ₹1,500 – ₹12,500 INR
Branch Predictor Parameters
The experiments must be run with the following three different sizes for the Pattern History Tables (PHTs): 128, 1024, and 4096 entries. Note that you must assess all three PHT sizes for each of the different branch predictors.
Each PHT entry is logically comprised of 2-bit saturating counters as explained in the lecture slides. Remember that you are writing a simulator in a high-level language; you are not designing actual circuits. As such, you may use any data types for the counters (and other program variables). Regardless of the data type you use, it must behave like a saturating 2-bit counter.
Local Branch predictor
• The Local Branch predictor uses per-branch history (i.e. history of each branch considered independently) to make a prediction. The Predictor consists of two structures:
1) An array of 128 distinct Local History Registers (LHRs), that store the branch history of different branches;
2) The PHT.
The 7 Least Significant Bits (LSBs) of the Program Counter (PC) of the branch instruction are used to index into the array with the LHRs and select the relevant LHR to be used for the prediction. Each LHR is composed of as many bits as necessary to index the PHT. For example, if the PHT contains 1024 entries, then each LHR should be 10 bits long. Each n-bit LHR contains the n last outcomes of all branches that map to that LHR (i.e. all branch PCs whose 7 LSBs are identical), with 0 denoting not taken and 1 denoting taken. All LHRs should be initialized to 0. The number of LHRs must be 128 and must stay constant across all experiments(i.e. 128 LHRs is a fixed parameter, independent of PHT size).
• The selected LHR is used to index into the PHT, which yields the prediction. All PHT entries must be initialized to “11” (i.e. 3).
• To train the predictor after each prediction, the relevant LHR must be updated such that it reflects the new history and the used PHT entry must be strengthened in case of a correct prediction and weakened in case of misprediction.
- To strengthen a saturating counter means to increment it if its prediction bit is ‘1’, and decrement it if the prediction bit is ‘0’.
- To weaken a saturating counter means to decrement it if its prediction bit is ‘1’, and increment it if the prediction bit is ‘0’.
• Figure 1 shows a pictorial view of the Local Branch Predictor, with 128 distinct LHRs, each of which consists of 12 bits of branch history, that is used to index into a 4096-entry PHT of 2-bit saturating counters. Students are referred to [1] (Section 4) for more information.
4
PC
7 LSBs 0
127
Local History Registers
PHT
4095
12-bit Local History
Figure 1: A Local Branch predictor with 128 Local History Registers and a PHT with 4096 2-bit saturating counters
Gshare Branch Predictor
• The Gshare Branch predictor combines a Global History Register (GHR) and the LSBs of the branch’s PC to index into the PHT. The PC and the GHR are XORed in order to create the index to the PHT.
• The Global History Register is composed of as many bits as necessary to index the PHT. For example, if the PHT contains 1024 entries, then the GHR should be 10 bits long. These 10 bits contain the outcomes of the last 10 branches, with 0 denoting not taken and 1 denoting taken. GHR should be initialized to 0. All PHT entries must be initialized to “11” (i.e. 3).
• To train the predictor after each prediction, the GHR must be updated such that it reflects the new global history and the used PHT entry must be strengthened in case of a correct prediction and weakened in case of misprediction.
• Figure 2 shows a pictorial view of the Gshare Branch Predictor with a GHR of 10 bits that gets XORed with the 10 least-significant bits of the PC of the branch in order to index into the PHT that contains 1024 entries of 2-bit saturating counters. Students are referred to [1] (Section 7) for more information. For the purpose of this assignment, the number of LSBs used from the branch PC should be equal to the number of bits of the GHR.
PC
10 LSBs
XOR
PHT 0
1023
Predict Not Taken
01
0
10
Predict Taken
10-bit Global History Global History Register
Figure 2: Gshare Branch predictor with a 10-bit GHR and a 1024-entry PHT
5
Tournament Branch Predictor
• The Tournament predictor is composed of three different predictors: the Local predictor, the Gshare predictor, and a meta-predictor that selects between the Local or the Gshare predictor to provide the actual prediction of the branch outcome.
• The PHT of the meta-predictor is indexed with the LSBs of the Program Counter (PC) of the branch instruction.
• In the meta-predictor, when the prediction bit (i.e. the MSB) of the saturating counter is 0, the Local predictor is selected to supply the prediction. When the MSB is 1, the Gshare predictor is selected. All PHT entries must be initialized to “11” (i.e. 3).
• The Tournament predictor will follow a total update policy. Both the Local and the Gshare predictors will be trained after each branch is resolved. After a correct prediction the relevant meta-predictor entry must be strengthened. After a mis- prediction, the relevant meta-predictor entry (the counter) must be weakened only if the predictor that was not chosen was correct. If both the Local and the Gshare predictors were incorrect, there is no update to the meta-predictor.
• Since the underlying behavior of the Local and Gshare predictors is unmodified in the Tournament scheme, you may choose to use your existing implementations of Local and Gshare predictors to implement the Tournament predictor.
• Figure 3 shows a pictorial view of the Tournament Branch Predictor with a PHT that contains 1024 entries of 2-bit saturating counters. The 2-bit saturating counter indicates which predictor should be used (Local or Gshare) for the branch given its PC.
• As before, the experiments must be run with PHTs of 3 different sizes (128, 1024 and 4096 entries). In each experiment the PHTs of the Local Predictor and the Gshare Predictor must all have the same size. I.e. when the meta-predictor PHT is 1024 entries, then the Gshare PHT is also 1024 entries and the Local Predictor PHT is also 1024 entries.
PHT 0
1023
PC
10 LSBs
01
Figure 3: Tournament Branch predictor with a a 1024-entry PHT
6
Use Local Predictor
Local Predictor
Final prediction
Gshare Predictor
1.3 Simulator infrastructure
The three requested predictors must all be implemented inside the branch predictor example.cpp file. Inside the file, you must create a class with an appropriate name for each predictor. The file branch predictor example.cpp includes comments and guidelines on how you must create your classes and the appropriate member functions. To help you get started, an implementation of the Always Taken predictor is supplied. You should start with the same code as the one for the Always Taken predictor and
modify it to implement new functionality for each specific predictor type.
For the purpose of this assignment you can ignore the Branch Target Buffer (BTB) (i.e. the implementation of a BTB is not needed): the simulated predictors must only generate a prediction without specifying the target address of the branch. Additionally the predictors do not need to identify whether an instruction is a conditional branch; the predictors can assume that every instruction is a conditional branch, because the given
code feeds only conditional branches into the prediction functions.
The contents of the file branch predictor example.cpp should be modified only as the above guidelines specify, and not in any other way.
The experiments must be run with the following three different sizes for the Pattern History Tables (PHTs): 128, 1024, and 4096 entries. Note that you must assess all three PHT sizes for each of the different branch predictors.
Each PHT entry is logically comprised of 2-bit saturating counters as explained in the lecture slides. Remember that you are writing a simulator in a high-level language; you are not designing actual circuits. As such, you may use any data types for the counters (and other program variables). Regardless of the data type you use, it must behave like a saturating 2-bit counter.
Local Branch predictor
• The Local Branch predictor uses per-branch history (i.e. history of each branch considered independently) to make a prediction. The Predictor consists of two structures:
1) An array of 128 distinct Local History Registers (LHRs), that store the branch history of different branches;
2) The PHT.
The 7 Least Significant Bits (LSBs) of the Program Counter (PC) of the branch instruction are used to index into the array with the LHRs and select the relevant LHR to be used for the prediction. Each LHR is composed of as many bits as necessary to index the PHT. For example, if the PHT contains 1024 entries, then each LHR should be 10 bits long. Each n-bit LHR contains the n last outcomes of all branches that map to that LHR (i.e. all branch PCs whose 7 LSBs are identical), with 0 denoting not taken and 1 denoting taken. All LHRs should be initialized to 0. The number of LHRs must be 128 and must stay constant across all experiments(i.e. 128 LHRs is a fixed parameter, independent of PHT size).
• The selected LHR is used to index into the PHT, which yields the prediction. All PHT entries must be initialized to “11” (i.e. 3).
• To train the predictor after each prediction, the relevant LHR must be updated such that it reflects the new history and the used PHT entry must be strengthened in case of a correct prediction and weakened in case of misprediction.
- To strengthen a saturating counter means to increment it if its prediction bit is ‘1’, and decrement it if the prediction bit is ‘0’.
- To weaken a saturating counter means to decrement it if its prediction bit is ‘1’, and increment it if the prediction bit is ‘0’.
• Figure 1 shows a pictorial view of the Local Branch Predictor, with 128 distinct LHRs, each of which consists of 12 bits of branch history, that is used to index into a 4096-entry PHT of 2-bit saturating counters. Students are referred to [1] (Section 4) for more information.
4
PC
7 LSBs 0
127
Local History Registers
PHT
4095
12-bit Local History
Figure 1: A Local Branch predictor with 128 Local History Registers and a PHT with 4096 2-bit saturating counters
Gshare Branch Predictor
• The Gshare Branch predictor combines a Global History Register (GHR) and the LSBs of the branch’s PC to index into the PHT. The PC and the GHR are XORed in order to create the index to the PHT.
• The Global History Register is composed of as many bits as necessary to index the PHT. For example, if the PHT contains 1024 entries, then the GHR should be 10 bits long. These 10 bits contain the outcomes of the last 10 branches, with 0 denoting not taken and 1 denoting taken. GHR should be initialized to 0. All PHT entries must be initialized to “11” (i.e. 3).
• To train the predictor after each prediction, the GHR must be updated such that it reflects the new global history and the used PHT entry must be strengthened in case of a correct prediction and weakened in case of misprediction.
• Figure 2 shows a pictorial view of the Gshare Branch Predictor with a GHR of 10 bits that gets XORed with the 10 least-significant bits of the PC of the branch in order to index into the PHT that contains 1024 entries of 2-bit saturating counters. Students are referred to [1] (Section 7) for more information. For the purpose of this assignment, the number of LSBs used from the branch PC should be equal to the number of bits of the GHR.
PC
10 LSBs
XOR
PHT 0
1023
Predict Not Taken
01
0
10
Predict Taken
10-bit Global History Global History Register
Figure 2: Gshare Branch predictor with a 10-bit GHR and a 1024-entry PHT
5
Tournament Branch Predictor
• The Tournament predictor is composed of three different predictors: the Local predictor, the Gshare predictor, and a meta-predictor that selects between the Local or the Gshare predictor to provide the actual prediction of the branch outcome.
• The PHT of the meta-predictor is indexed with the LSBs of the Program Counter (PC) of the branch instruction.
• In the meta-predictor, when the prediction bit (i.e. the MSB) of the saturating counter is 0, the Local predictor is selected to supply the prediction. When the MSB is 1, the Gshare predictor is selected. All PHT entries must be initialized to “11” (i.e. 3).
• The Tournament predictor will follow a total update policy. Both the Local and the Gshare predictors will be trained after each branch is resolved. After a correct prediction the relevant meta-predictor entry must be strengthened. After a mis- prediction, the relevant meta-predictor entry (the counter) must be weakened only if the predictor that was not chosen was correct. If both the Local and the Gshare predictors were incorrect, there is no update to the meta-predictor.
• Since the underlying behavior of the Local and Gshare predictors is unmodified in the Tournament scheme, you may choose to use your existing implementations of Local and Gshare predictors to implement the Tournament predictor.
• Figure 3 shows a pictorial view of the Tournament Branch Predictor with a PHT that contains 1024 entries of 2-bit saturating counters. The 2-bit saturating counter indicates which predictor should be used (Local or Gshare) for the branch given its PC.
• As before, the experiments must be run with PHTs of 3 different sizes (128, 1024 and 4096 entries). In each experiment the PHTs of the Local Predictor and the Gshare Predictor must all have the same size. I.e. when the meta-predictor PHT is 1024 entries, then the Gshare PHT is also 1024 entries and the Local Predictor PHT is also 1024 entries.
PHT 0
1023
PC
10 LSBs
01
Figure 3: Tournament Branch predictor with a a 1024-entry PHT
6
Use Local Predictor
Local Predictor
Final prediction
Gshare Predictor
1.3 Simulator infrastructure
The three requested predictors must all be implemented inside the branch predictor example.cpp file. Inside the file, you must create a class with an appropriate name for each predictor. The file branch predictor example.cpp includes comments and guidelines on how you must create your classes and the appropriate member functions. To help you get started, an implementation of the Always Taken predictor is supplied. You should start with the same code as the one for the Always Taken predictor and
modify it to implement new functionality for each specific predictor type.
For the purpose of this assignment you can ignore the Branch Target Buffer (BTB) (i.e. the implementation of a BTB is not needed): the simulated predictors must only generate a prediction without specifying the target address of the branch. Additionally the predictors do not need to identify whether an instruction is a conditional branch; the predictors can assume that every instruction is a conditional branch, because the given
code feeds only conditional branches into the prediction functions.
The contents of the file branch predictor example.cpp should be modified only as the above guidelines specify, and not in any other way.