Consider a 4 stage pipeline processor. The number of cycles needed by the four…
2009
Consider a 4 stage pipeline processor. The number of cycles needed by the four instructions I1, I2, I3, I4 in stages S1, S2, S3, S4 is shown below:
What is the number of cycles needed to execute the following loop? For (i=1 to 2) {I1; I2; I3; I4;}
- A.
16
- B.
23
- C.
28
- D.
30
Attempted by 130 students.
Show answer & explanation
Correct answer: B
Key idea: treat the pipeline as a 4-stage flow shop. For each instruction (job) j and stage (machine) k compute the completion time using C[j,k] = max(C[j-1,k], C[j,k-1]) + p[j,k].
Instruction I1 stage times: S1=2, S2=1, S3=1, S4=1 (total 5)
Instruction I2 stage times: S1=1, S2=3, S3=2, S4=2 (total 8)
Instruction I3 stage times: S1=2, S2=1, S3=1, S4=3 (total 7)
Instruction I4 stage times: S1=1, S2=2, S3=2, S4=2 (total 7)
We execute the sequence I1, I2, I3, I4 twice (8 jobs). Using the recurrence C[j,k] = max(C[j-1,k], C[j,k-1]) + p[j,k] we compute completion times stage by stage.
After first I1: completes stage 4 at time 5.
I2 completes stage 4 at time 10.
I3 completes stage 4 at time 13.
I4 completes stage 4 at time 15.
Second-iteration I1 completes stage 4 at time 16.
Second-iteration I2 completes stage 4 at time 18.
Second-iteration I3 completes stage 4 at time 21.
Second-iteration I4 completes stage 4 at time 23.
Final answer: 23 cycles. The pipeline schedule above shows the last instruction finishes at time 23.
Note: shorter answers (for example 16) come from undercounting stage conflicts; larger answers (for example 28 or 30) come from failing to exploit possible overlaps. The correct makespan after scheduling is 23 cycles.
A video solution is available for this question — log in and enroll to watch it.