CS2200 - EXAM 2 Solution

Question 1. Pipeline Buffer 

List the minimum size and contents of each pipeline buffer needed to execute the SW instruction of the LC-2200 ISA. Remember that this is a 32-bit machine. If a certain field is not stored in a given buffer, leave that table entry empty.
Field FBuff DBuff EBuff MBuff
Instruction
Opcode
RX
RY
RZ
Decoded RX
Decoded RY
Decoded RZ
SEXT Offset
ALU output (RY + Offset)
MEM[address]
Question 2. Branch prediction (10 points) (5 minutes)
We have modified the LC-2200 ISA to contain a new conditional branch instruction, BNEQ. When this instruction is executed, we branch to a target location if the two register operands are not equal. Assume we have a classical five-stage pipeline with all possible data forwarding paths. The pipeline is not equipped with any form of branch prediction and the ISA does not support branch delay slots. Given the following code:
lea $t1, var addi $t0, $zero, 4
loop: addi $t0, $t0, -1 sw $t0,0($t1) bneq $t0, $zero, loop addi $v0, $zero, 0xf var: .fill 0
a. Calculate the Cycles Per Instruction (CPI) achieved by the pipeline without any branch prediction. Explain your answer for credit. (6 points)
b. Now assume we extend the pipeline’s hardware to always predict that the branch is not taken and calculate the CPI again. Explain your answer for credit. (4 points)
Question 3. Pipeline Depth (9 Points) (6 minutes)
a. The classical pipeline we studied in cs2200 has a total of five stages. Modern processors, however, can have many more (upwards of 15 stages!). What is the benefit of a deeper pipeline compared to a shorter one? (3 points)
b. Say that we modified the LC-2200 pipeline to look like the following figure. Assume the pipeline uses branch prediction and a branch that is not taken is mispredicted as taken.

How many bubbles would result in the pipeline? Explain your answer. (3 points)
c. Comment on a potential disadvantage of a longer pipeline on the performance of the currently executing program, other than an increased branch penalty. (3 points)
Question 4. Data Hazards (9 Points) (8 minutes)
Consider the following snippet of LC-2200 assembly code:
I1: ADD $t0, $t1, $t2
I2: ADD $t1, $t0, $t1 I3: LW $t2, 0($t2) I4: ADD $t0, $t2, $t1
a. For each instruction, identify any of the three types of data hazards (RAW, WAR, WAW) that exist between all instruction pairs (e.g., for I4, you need to consider potential hazards with instructions I1, I2, and I3). (3 points)
I1 I2 I3 I4
I1
I2
I3
I4
b. Assuming the classical five-stage pipeline without any data forwarding support, count the number of bubbles that will be present upon the execution of the program. Explain your answer for credit. (4 points)
c. Count the number of bubbles with full data forwarding support. Explain your answer for credit. (2 points)
Question 5. Branch Table Buffer (9 Points) (5 minutes)
Consider a 5-stage pipelined processor (same as the one in the textbook) equipped with a branch target buffer (BTB which has only 1 bit of branch history). Assume a 32-bit word-addressable architecture. Upon misprediction, there will be a 2-cycle penalty (i.e., two NOPs). A BEQ instruction is fetched from memory location 1000 by the “IF” stage. The BTB currently has an entry for this BEQ instruction:
PC=1000 | branch predicted TAKEN;
PC of BEQ target = 1200;
PC of next sequential instruction = 1001
a. What will be the action in IF stage in the next clock cycle? (2 points)
b. When BEQ is in the EX stage, the outcome of the branch turns out to be NOT TAKEN. What are the actions that will ensue as a result of this outcome? (7 points)
Question 6. Scheduling (12 Points) (8 minutes)
Shown below are the duration of the CPU burst and I/O burst times for the three processes.
P1 P2 P3
CPU 2 6 3
I/O 4 1 3
Assume processes P1, P2, and P3 are ready to run at the beginning of time.
Assume each process does:
● CPU burst; first CPU burst
● I/O burst; one I/O burst
● CPU burst; second CPU burst
● Done; process execution complete
Priorities:
● P3 highest priority
● P2 next higher priority
● P1 lowest priority Process arrival:
● P1, P2, P3 all arrive within milliseconds of each other in this order
● all are ready to be scheduled at time 0
Shown below are the timelines of activities on the CPU and I/O for the three processes with some scheduling discipline.

a. What scheduling algorithm is implemented here? Explain your choice. (3 points)
b. Why does the scheduler pick P3 to run on the processor at time 10? (3 points)
c. What is the wait time for P2? Explain your answer. (3 points)
d. What is the turnaround time for P3? Explain your answer. (3 points)
Question 7. Round Robin Scheduler (17 Points) (10 minutes)
We are writing a new scheduler that will implement a round robin algorithm in order to schedule processes on the processor. The ready queue contains three processes P1, P2, P3 in that order. The execution characteristics of the three processes are as shown in the table below.
Process ID CPU Burst I/O Burst CPU Burst
P1 10 2 15
P2 4 2 3
P3 3 2 3

a. Given the above timeline with a timeslice of ten (10) time units, and assuming no scheduling or context-switching overhead, compute the average waiting time for the three processes. Show your work for credit. (3 points)
b. Given the above timeline with a timeslice of five (5) time units, and assuming no scheduling or context-switching overhead, compute the average waiting time for the three processes. Show your work for credit. (3 points)
c. Now assume that the scheduling and context-switching overhead (i.e., the time to pick the next process to run and dispatch it on the processor) is two (2) time units and I/O completions do not introduce any additional overheads. Compute the average waiting time for the above processes, for each of the two timeslice values (5 and 10). Show your work for credit. (5 points)
d. Qualitatively, state your intuition on the effect of the choice of timeslice on the waiting time for processes with short CPU bursts. (3 points)
e. Qualitatively, state your intuition on the effect of the scheduling and context-switching overhead on the waiting time for processes with short CPU bursts. (3 points)
Question 8. Priority Scheduling (6 Points) (4 minutes)
a. Describe a scenario in which certain processes in our system could experience starvation. (3 points)
b. Describe a policy to prevent processes of type B from starving. (3 points)

Question 9. Hidden? (10 Points) (7 minutes)
Question 10. Hidden? (10 Points) (7 minutes)
Appendix A: Useful Formulas

Appendix B: LC-2200 ISA