CS 251, Winter 2020, Assignment 5.1.3 20% of course mark Due Friday, March 27th, 5:30PM Lates accepted until 5:30pm March 28th with a 15% penalty Note: In this assignment, unless otherwise stated, assume that no branch prediction is used, and that the instruction after the branch (B, CBZ, CBNZ) is loaded and flushed if the branch is taken. 1. (8 points) The code sequence below is executing on the pipelined datapath where branching is deter- mined in the ID stage. You must consider branch data hazards that might exist between the conditional branch instruction and an instruction immediately before the branch. A one clock cycle delay is needed if the instruction immediately before the branch is an R-format instruction or an ADDI/SUBI instruction and a data dependency exists. A two clock cycle delay is needed if the instruction immediately before the branch is a load word instruction and a load-use hazard exists. If such a branch data hazard exists, the datapath will still add the necessary number of clock cycles to correctly handle the branch data hazard. (a) (4 points) Assume the datapath implements data forwarding, load-use stalling, branch data stalling, and branch flushing. Indicate any instructions that cause a stall or are flushed because of the instruction before it by using (*) beside that instruction. Re- arrange the code to remove any load-use hazards or branch data hazards if they exist. * Original Rearranged Code 100 ADDI X1,XZR,#50 104 ADD X5,XZR,XZR 108 LDUR X3,[X4,#100] 112 STUR X3,[X4,#300] 116 LDUR X2,[X4,#200] 120 STUR X2, [X4,#400] 124 ADDI X4,X4,#8 128 ADD X5,X5,X2 132 SUBI X1,X1,#1 136 CBNZ X1,#-7 140 ADD X8,X5,XZR 1 (b) (4 points) i. What is the total number of instructions that are flushed? ii. State the total number of clock cycles required to run the original sequence of code including pipeline start-up time. 2 2. (6 points) Given the following execution times for individual components on the Pipelined datapath find the minimum time that can be assigned to the clock cycle length (i.e., in class we always used a 200ps clock cycle for the pipelined datapath). You may assume Branch is determined in the MEM Stage for this question. (Note: These are hypothetical times and do not necessarily reflect accurate execution times in the hardware). A datapath has been included on the next page. • Memory accesses take 120ps • Register File access is 65ps (read or write) • ALU computations 130ps, Adders: 130ps • Sign Extension 10ps, Shift Left by two: 10ps • MUXes: 5ps • Writing to Intermediate Pipeline Registers (IF/ID etc.) Negligible. • Reading data from any Pipeline registers is Negligible • Control Unit decode of instruction opcode bits: 10ps • ALU Control: 10ps • Assume all other components are negligible and many operations occur in parallel. Complete the following table giving the minimum time needed for the stage to execute correctly. Be careful with the ID stage. IF ID EX MEM WB Min Time State the shortest clock cycle time we could allow on the Pipelined Datapath : 3 © 2 0 1 6 E ls ev ie r, In c. A ll ri gh ts r es er ve d . 5 1 4 3. (7 points) The datapath on the next page shows the hardware needed to execute branch in the ID stage. When branching is determined in the ID stage, data hazards may exist between the branch instruction and an instruction that immediately precedes it. This is called a branch data hazard. If a branch data hazard exists, the instruction causing the hazard moves forward to the MEM stage, a NOP is inserted in-between the two instructions, and forwarding would send the correct data to the branch instruction in the ID stage (this insertion of a NOP is illustrated in the diagram on the next page, with the pre-stalling instructions in red and the instructions after the NOP is inserted in black). State the conditions necessary to detect a branch data hazard between a branch (CBZ) instruction in the ID stage and an I-format instruction such as ADDI in the MEM stage. You only need to state the necessary conditions to detect a data hazard between the Rt/Rd register of the CBZ in the ID stage and the Rd destination register in the MEM stage. Control bits generated in the ID stage may be referred to as ID.ControlBit such as ID.MemRead. A copy of the data forwarding conditions from class are provided at the end of this assignment. 5 Pipelined datapath with Forwarding, Branch in ID stage. This is the WRONG datapath to use for question 2! 6 4. (12 points) The following code executes on the pipelines computer with branch in the ID stage with data forwarding, load-use stalls, branch flushing, and branch data stalling. 100 ADDI X1,X31,#8 104 ADDI X4,X4,#24 108 STUR X2,[X4,#0] 112 ADDI X2,X2,X1 116 SUBI X1,X1,#1 120 CBNZ X1,#-4 124 ADD X1,X2,X3 (a) (4 points) Compute how many correct/incorrect branch “predictions” are made using various schemes for determining which instruction to branch to/flush. Assume that X4 contains a multiple of 8. For all branch prediction methods, assume that the branch destination table has already been built. Assume that the 1-bit branch prediction method initially will assume all branches are not taken. For your answers to 2-bit branch predictions, do parts (b) and (c) of this question first, then fill in the entries for 2-bit prediction in the table below. Branch Prediction Next branch instruction Number Correct Number Incorrect PC+4 Branch destination 1-bit Branch Prediction 2-bit start at 11 2-bit start at 01 7 (b) (4 points) Here is the FSM for the 2-bit branch predictor: Trace the state of the 2-bit branch predictor for line 120 CBNZ as the code above is executed. Assume that the FSM starts in state 11, and that it generates an output T that is high (1) when predicting that the branch should be taken. Note whether each branch prediction was correct (C) or incorrect (I). You should trace the code until it completes execution of line 124. Current State 11 T Correct/Incorrect Next State (c) (4 points) Retrace the state of the 2-bit branch predictor for line 120 CBNZ as the code above is executed, but now assume that the FSM starts in state 01, and that it generates an output T that is high when predicting that the branch should be taken. Note whether each branch prediction was correct (C) or incorrect (I). You should trace the code until it completes execution of line 124. Current State 01 T Correct/Incorrect Next State Be sure to use your answers to parts (b) and (c) to complete the 2-bit entries in the table in part (a). 8 Conditions checking for a data hazard between the instruction in the MEM stage and the instruction in the EX stage for the Rn source register: 1. IF (EX/MEM.RegWrite) 2. AND (EX/MEM.RegisterRd != 31) 3. AND (EX/MEM.RegisterRd = ID/EX.RegisterRn1)) Conditions checking for a data hazard between the instruction in the WB stage and the instruction in the EX stage for the Rn source register: 1. IF (MEM/WB.RegWrite) 2. AND (MEM/WB.RegisterRd != 31) 3. AND !( EX/MEM.RegWrite AND EX/MEM.Rd != 31 AND EX/MEM.RegisterRd = ID/EX.RegisterRn1 ) 4. AND (MEM/WB.RegisterRd = ID/EX.RegisterRn1)) 9
