Homework 02 (45 Points)
1. Identify the data dependencies in the following instructions when processed in a five-stage pipeline. (5 points)
LDR R2,[R1,#60]
LDR R1,[R2,#40]
ADD R1,R1, R2
STR R1,[R2,#20]
2. Draw a pipeline diagram for the following instructions when processed in a five-stage pipeline. Identify the data dependencies and show forwarding if it can reduce the data hazards. (5 points)
LDR R1,[R4,#0]
ADD R2,R1,#8
MUL R3,R1,R1
STR R3,[R2,#4]
3. Consider the following loop.
Loop
add R2,R5,R6
sub R1,R2,#8
CBZ R1,Loop
Assume that perfect branch prediction is used (no stalls due to control hazards), that there are no delay slots, that the pipeline has full forwarding support. Draw a pipeline execution diagram with forwarding (if any) for the first two iterations of this loop. Give how many clock cycles it takes to iterate twice? (10 points)
4. Pipeline performance. Suppose processor X executes instructions in the following 4 stages (no pipeline), where each stage could run this fast. Compare the performance of a pipelined vs. unpipelined implementation of processor X. (10 points)
IF&ID 25ns
EX 20ns
Mem 40ns
WB 15ns
Draw the pipeline diagram to show clock cycles with time. Compare the performance of a pipelined vs. unpipelined implementation of processor X.
5. Consider an instruction pipeline with five stages without any branch prediction. The stage delays for each stage are 5 n sec, 6 n sec, 10 n sec, 8 n sec and 6 n sec, respectively. There are intermediate storage buffers after each stage and the delay of each buffer is 1 n sec. A program consisting of 12 instructions 1, 2, …, 12 is executed in the pipelined processor. Instruction 3 is the only branch instruction and its branch target is 8. If the branch is taken during the execution of this program, what is the time needed to complete the program. Draw the pipeline diagram to show clock cycles with time. (10 points)
6. Consider a loop branch that branches nine times in a row, then is not taken once. What is the prediction accuracy for this branch, assuming the initial prediction is Not Taken in the Branch History Table? Show how many correct predictions and how many mispredictions. (5 Points)