the 2 last digit of my id is odd
COMPUTER ARCHITECTURE BRANCH TARGET BUFFER PROJECT Objective: To write a program that simulates a branch target buffer (BTB) that performs dynamic branch prediction. Input: A long set of PC addresses from program traces. Programming language: Use any programming language (C++, Phyton, Java, …). Figure 1 below shows the basic structure of the BTB which was introduced in class. It has four fields with an entry: Entry number, Current PC, Target PC, and Prediction. In this project the BTB number of entries is 1024; thus, only 10 bits are needed to address the entire BTB. Entry Num. Current PC Target PC Prediction 0: 1: PC 10 1023: Figure 1. 1024-entry Branch Target Buffer. In order to determine the BTB entry, 10 bits (from bit 2 to bit 11) from the PC address are used as shown in Figure 2. The least significant bits (0 and 1) are always 0; thus, they are not needed. 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 PC Figure 2. 10-bit BTB address obtained from the 32-bit PC. Here is an example how the BTB index is determined. Let us assume the current PC address is: 0x4001c4 (this is an hexadecimal number). 31 29 28 27 25 24 23 21 20 19 17 16 15 13 12 11 9 8 7 6 5 4 3 2 1 0 c 4 We need only the last 3 hexadecimal numbers: 11 9 8 7 6 5 4 3 2 1 0 c 1 0 0 0 1 1 1 0 0 0 0 0 The binary number are shown as well. Using the binary number we can obtained the BTB entry. 0001 1100 01 = 26 + 25 + 24 + 20 = 113 We can obtain the address using the hexadecimal numbers (this might be a bit easier). 1c4 = 1*162 + 12*16 + 4 = 452 Now, we need to remove the 2 least significant bits (we divide by 4): 452/4 = 113 Trace . 400190 To compute index, 10 bits are need (for 1024-entry BTB). 400194 We used the 3 least significant bytes (in red); 400198 40019c the 2 least significat bits are not considered (they are always 00) 4001a0 4001c4 1*162 + 12*16 + 4 452 / 4 =113 4001a4 0001 1100 0100 = 26 + 25 + 24 + 20 = 113 4001a8 ↑↑↑↑ ↑↑↑↑ ↑↑ 4001ac 4001b0 2n → 9876 5432 10 4001b4 4001b8 Current PC Target PC Prediction 4202d4 4202d8 4202dc 4202dc 2*162 + 13*16 + 12 732 / 4 =183 42ac30 42ac34 42ac38 42ac3c 42ac40 42ac44 0010 1101 1100 = 27 + 25 + 24 + 22 + 21 + 20 = 183 42ac48 42ac5c 42ac60 42ac64 42ac68 42ac6c 42ac70 42ac74 42ac78 42ac7c 42ac80 42ac84 42ac88 42ac8c 42ac90 42ac94 42ac98 42ac9c 42ac48 12*162 + 4*16 + 8 3144/4 =786 4001bc 4001c4 10 : : : : 113 4001c4 4202b0 Taken (00) 183 4202 dc 42 ac 30 Taken (00) 786 48 ac 42 ac5c 42 Taken (00) entries 1024 4001c0 4202b0 4202b4 index 4202b8 4202bc 4202c0 4202c4 4202c8 4202cc 4202d0 Specifications: · BTB size: 1024 Entries · Two Benchmarks. Use the least significant digit in your ID*: · Even (0, 2, 4, 6 or 8): Li_int and Doduc_FP · Odd (1, 3, 5, 7 or 9): Espresso_int and Spice_FP · Two prediction state machines. Use second least significant digit of ID*: - Even: Class state machine (Figure 3) and State Machines A (Figure 4) · Odd: Class state machine (Figure 3) and State Machines B (Figure 5) Total number of instructions executed: instruction count (IC). · Number of hits (Hit): number of times a branch is found in BTB. · Number of misses (Miss): number of times a branch is not found in BTB. · Number of right predictions (Right): number of times the prediction is right. · Number of wrong predictions (Wrong) ): number of times the prediction is wrong. · Number of taken branches/jumps (B_Taken) · Number of collisions (Collisions): number of times a branch displaces a branch in BTB. · Number of wrong address predictions (Wrong_addr): A wrong addres is when a branch is predicted (as taken) but the address is not right. · Hit rate: This is defined as follows ?????? ?? ℎ??? ??? ???? (%) = (?????? ?? ℎ???) + (?????? ?? ??????) · Prediction accuracy: ?????? ?? ??????? (???ℎ?) ??????????? ???????? (%) = (?????? ?? ℎ???) · Incorrect address (%) ?????_???? ???????_????? (%) = (?????? ?? ????? ???????????) 00 Predicted Taken Taken Not taken 01 Predicted Taken Taken Not taken 10 Predicted not Taken Not taken Not taken 11 Predicted not Taken Taken Taken Initial state Figure 3. Class Prediction State Machine Figure . Prediction State Machine A 4 . T 00 T 01 NT 11 NT 10 Initial state Prediction T: Taken NT: Not taken Actual Branch Taken Not taken Figure 5 . Prediction State Machine B. T 00 T 01 NT 11 NT 10 Initial state Prediction T: Taken NT: Not taken Actual Branch Taken Not taken Deadlines Deadline Items Grade April 12 (11:59 pm) BTB w/ branches A list of branches (PC and Target) and their entry number in BTB. (See Appendix A, below). Program code needs be included as a file. The trace sample is used (11,154 addresses). 10 points April 19 (11:59 pm) BTB w/ predictions Mid-project report using sample trace. This will include the status of BTB with prediction at the end of the run. (See Appendix B, below) 10 points Monday, May 1 Project Report Project report with all the results (11:59 pm). An outline of the report will be provided at a later time. (Final exam 11am - 12noon.) 80 points Appendix A. BTB entries with PC and Target PC. Please include only entries with content. Entry PC Target 0 423000 425E40 7 8 11 42E01C 42E028 423020 4230A8 42E02C 42B30C 14 : : 423038 425E40 : : : : 1018 422FE8 4230A8 Appendix B. BTB entries with PC, Target PC, and Prediction. Entry PC Target Pred. 0 423000 425E40 00 7 42E01C 42E028 00 8 11 14 : 423020 4230A8 00 42E02C 42B30C 00 423038 425E40 00 : : : : : : : 1018 422FE8 4230A8 00 Branch prediction Variables to Keep Track (& initial values) Hit = 0 Miss = 0 Right = 0 Wrong = 0 Wrong_addr = 0 Collision = 0 ‹#› EE334 Computer Architecture Step 1 (IF stage) Example Trace 4001c4 4202b0 4202b4 PC_current = 4001c4 PC_next = 4202b0 Is PC_current in BTB ? No Yes Use PC_current address to determine BTB location. BTB_Address: 113 Next slide BTB (113) has either: No prediction at all PC in BTB is not equal to PC_current ‹#› EE334 Computer Architecture Step 2 (ID stage –No found side) Is instruction a taken branch? No Yes Normal Instruction Execution Miss=Miss+1 Taken=Taken+1 Is PC_next not equal to PC_current + 4 PC_current= 4001c4 PC_next = 4202b0 ‹#› EE334 Computer Architecture Step 2 (ID stage –No found side) Is instruction a taken branch? No Yes Normal Instruction Execution Miss=Miss+1 Taken=Taken+1 Is PC_next not equal to PC_current + 4 PC_current= 4001c4 PC_next = 4202b0 Step 3 (EX stage) If BTB entry is used by other branch address: Collision = Collision + 1 Enter branch address and next PC into BTB EntryPCTargetPrediction 113:4001c44202b0 Taken (strong) ‹#› EE334 Computer Architecture Back to Step 1 (IF stage) Example Trace 4001c4 4202b0 4202b4 PC_current = 4001c4 PC_next = 4202b0 Is PC_current in BTB ? No Yes Hit = Hit + 1 Use PC_current address to determine BTB location. BTB_Address: 113 Next slide B T B EntryPCTargetPrediction 113:4001c44202b0 Taken (00) ‹#› EE334 Computer Architecture Step 2, 3 (ID,EX) Right prediction? No Yes If prediction is Taken: If (PC_next = BTB target) // {PC_next = BTB Target= 4202b0} Then Right = Right + 1; Taken = Taken + 1; updateBTB (predictor: Br T) Else Wrong = Wrong + 1 If (PC_next = PC_Current+4) Then updateBTB (predictor: Br NT)