Problem 2. Instruction Flow and Branch Prediction 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! Sequential Addr. Addr. Calc. Instruction Fetch Instruction Cache Instructions Execution Assumptions: unconditional branches execute in the decode stage conditional branches execute in the execute stage Effective address cal- culation is performed in the execute stage All memory access is performed in the mem- ory access stage All necessary forwarding paths exist The register file is read after write Instruction Decode Execute The fetch address is a choice between the sequential address generation logic and the branch correction logic. If a mispredicted branch is being corrected the correction address is chosen over the sequential address for the next fetch address. Memory Access Write Back Part A: Branch Penalties. What are the branch penalties for unconditional and conditional branches? Unconditional Conditional Part B: No Branch Prediction. 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 2 3 4 N 3 4 5 6 5 7 8 9 main: addi r2, ro, ListArray r2 temp2) { sw r7, r4(r2) ListArray[i] temp2) { sw r7, r4(r2) ListArray[i]