This problem investigates the effects of branches and control flow changes on program performance for a scalar pipeline. Branch penalties increase as the number of pipeline stages increases between...

This problem investigates the effects of branches and control flow changes on program performance for a scalar pipeline. 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 static branch prediction. For this problem the base machine is a 5-stage pipeline. Branches predicted taken or untaken are handled as described in Exercise 3.7. Unconditional branches are executed in the ID stage. This exercise will use the all too familiar bubble sort program. In bubble sort the elements to sort are repeatedly scanned. Each element is compared with the next element, and if the next element is lower the two elements are swapped. This procedure ends when no elements are swapped in a scan. Assume register R0 is always zero. The execution trace of basic block numbers are provided below the code segment. Assume the execution trace provided represents the actual execution of the program.

(a) Explain how each basic block (1–9) was obtained.

(b) Branch behavior and statistics. Fill in the branch execution table with an N for not taken and a T for taken. This table records the execution pattern for each branch instruction. Use the execution trace shown above to fill the table.