Problem 2. Instruction Flow and Branch Prediction [30 points] Write down all assumptions. If you need more space, attach additional pages to the back, and label accordingly. Please save your work for this problem after you submit your answers. We will build on this assignment as we go through the semester and see alternative processor designs. Introduction This problem investigates the effects of branches and control flow changes on program performance for a scalar pipeline (to keep the focus on branch prediction). Branch penalties increase as the number of pipeline stages increases between instruction fetch and branch resolution (or condition and target resolution). This effect of pipelined execution drives the need for branch prediction. This problem explores both static branch prediction in Part C (we will see dynamic branch prediction based on this design in a future assignment). For this problem the base machine is a 5-Stage pipeline. The 5-Stage Pipeline without Dynamic Branch Prediction Br. Corr. Address Fetch Addr. Instruction Cache Sequential Addr. Calc.Part A: Branch Penalties. [4 points] What are the branch penalties for unconditional and conditional branches? Unconditional ______________ Conditional _______________ Part B: No Branch Prediction. [12 points] This problem will use the bubble sort program. An execution trace, or a sequence of executed basic blocks, is provided for this problem. A basic block is a group of consecutive instructions that are always executed together in sequence. Example Code: Bubble Sort BB Line# Label Assembly_Instruction Comment 1 1 main: 2 3 4 2 loop1: 3 5 6 4 loop2: 5 7 r7, 8 9 addi r2, ro, ListArray r2 <-Execution Trace: Sequence of Basic Blocks Executed: 1 2 3 4 5 6 7 4 5 7 4 5 7 4 8 2 3 4 5 6 7 4 5 7 4 8 2 3 4 5 6 7 4 8 2 3 4 8 2 9 [Hint: An alternate way to represent the same execution trace above is to use the sequence of branch instructions, both conditional and unconditional (i.e. ba), executed.] 1. (6 points) Fill in the branch execution table with an N for not taken and a T for taken. This table is recording the execution pattern for each (static) branch instruction. Use the execution trace on Page 2. Branch Execution - Assume No Branch Prediction: Branch Instruction No.(i.e. Line#) Branch Instruction Execution (dynamic execUsing the branch execution table above to calculate the statistics requested in the following table. Branch Execution Statistics: Branch Instr. No. Times Executed Times Taken Times Not Taken % Taken %Not Taken 4 6 9 13 15 17 2. (3 points) How many cycles does the trace take to execute (include all pipeline fill and drain cycles)? [Hint: you dont need to physically simulate the execution trace, just compute the cycle count.] 3. (3 points) How many cycles are lost to control dependency stalls? Part C: Static Branch Prediction. [14 points] Static branch prediction is a compile-time technique of influencing branch execution in order to reduce control dependency stalls. Branch opcodes are supplemented with a static prediction bit that indicates a likely direction during execution of the branch. This is done based on profiling information, ala that in Part B. For this part of Problem 1, new branch opcodes are introduced: bget - branch greater than or equal with static predict taken bgen - branch greater than or equal with static predict not-taken blet - branch less than or equal with static predict taken blen - branch less than or equal with static predict not-taken Static branch prediction information is processed in the decode stage of the 5-stage pipeline. When a branch instruction with static predict taken (i.e. bget) is decoded the machine predicts taken. Conversely, when a branch instruction with static predict not-taken (i.e. bgen) is decoded the machine predicts not-taken. 1. [10 points] Pretend you are the compiler, rewrite each conditional branch instruction in the original code sequence using the new conditional branch instructions with static branch prediction encoded. 2. [4 points] Assuming the same execution trace, what is the new total cycle count of the modified code sequence incorporating static branch prediction instructions. Indicate the resultant IPC. I am looking for precise answer and please explaan each section comprehensively to help me to understand the concept. thanks