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 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 Part A: Branch Penalties. Instruction Decode E xecut e Memory Access Write Back Instruc tion Cache Inst ructi ons 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. Br. Corr. Addre ss Fetch Sequent ial Addr. Addr. Calc. Instruction Fetch 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# 1 1 2 3 2 4 3 5 4 6 5 7 8 9 6 10 11 7 12 13 8 14 15 9 16 17 Label Assembly_Instruction Comment ListArray r2 <- ListArray ListLength r3 <- ListLength r0 i=0; main: loop1: loop2: skip: cont: end: addi r2, r0, addi r3, r0, add r4, r0, bge r4, r3, end while (i < Length) Execution Trace: Sequence of Basic Blocks Executed: addi r5, r4, 1 bge r5, r3, cont lw r6, r4(r2) lw r7, r5(r2) ble r6, r7, skip sw r7, r4(r2) sw r6, r5(r2) addi r5, r5, 1 ba loop2 addi r4, r4, 1 ba loop1 lw r1, (sp) ba r1 { { 1 2 3 4567 457 457 4823 4567 457 4823 4567 4823 4829 [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.] 4 j = i + 1; while (j < Length) temp = ListArray[i]; temp2 = ListArray[j]; if (temp > temp2) { ListArray[i] <- temp; ListArray[j] <- temp2; } j++; } i++; } r1 <- Return Pointer How many cycles are lost to control dependency stalls? Part C: Static Branch Prediction. 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. 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. 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. 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 Branch Instruction Execution (dynamic executions of each branch) No.(i.e.Line#) 1 2 3 4 5 6 7 8 9 10 4 6 9 13 15 17 Using the branch execution table above to calculate the statistics requested in the following table. Branch Execution Statistics: BranchInstr.No. TimesExecuted 4 6 9 13 15 17 TimesTaken TimesNotTaken %Taken %NotTaken 2. How many cycles does the trace take to execute (include all pipeline fill and drain cycles)? [Hint: you don't need to physically simulate the execution trace, just compute the cycle count.]

Tag the questionStep-by-stepFinal answer

Subject

Computer Science

Sub-subject159 results available.Skip questionExit I need only type solution

Don't give diagram and handwritten solution

It's urgent