Pipelining
Question 1 |
Consider a 6-stage instruction pipeline, where all stages are perfectly balanced. Assume that there is no cycle-time overhead of pipelining. When an application is executing on this 6-stage pipeline, the speedup achieved with respect to non-pipelined execution if 25% of the instructions incur 2 pipeline stall cycles is _________.
4 | |
5 | |
6 | |
7 |
There were 2 stall cycles for pipelining for 25% of the instructions.
So pipeline time =(1+(25/100)*2)=3/2=1.5
Speed up =Non-pipeline time / Pipeline time=6/1.5=4
Question 2 |
Register renaming is done in pipelined processors
as an alternative to register allocation at compile time | |
for efficient access to function parameters and local variables | |
to handle certain kinds of hazards | |
as part of address translation |
Question 3 |
The instruction pipeline of a RISC processor has the following stages: Instruction Fetch (IF), Instruction Decode (ID), Operand Fetch (OF), Perform Operation (PO) and Writeback (WB). The IF, ID, OF and WB stages take 1 clock cycle each for every instruction. Consider a sequence of 100 instructions. In the PO stage, 40 instructions take 3 clock cycles each, 35 instructions take 2 clock cycles each, and the remaining 25 instructions take 1 clock cycle each. Assume that there are no data hazards and no control hazards.
The number of clock cycles required for completion of execution of the sequence of instructions is ___________.
219 | |
220 | |
221 | |
222 |
Number of stages = 5
We know in a normal pipeline with k-stages time taken for n-instructions = k + n - 1 clock cycles.
So, in normal case total cycles = 100 + 5 - 1 = 104 cycles
But in this question it is given that PO stage of 40 instructions takes 3 cycles, 35 instructions takes 2 cycles and 25 instructions takes 1 cycle.
It is also given that all other stages take one clock cycle in all the 100 instructions.
PO stage of 40 instructions takes 3 cycles so these instructions will cause 2 stall cycle each, PO stage of 35 instructions takes 2 cycles so these instructions will cause 1 stall cycle each, But the 25 instruction whose PO stage takes 1 cycle, there are no stall cycles for these.
So, extra stall cycles = 40*2 + 35*1 = 80+35 = 115 cycles. So, total clock cycles = 104 + 115 = 219
Question 4 |
1.51 | |
1.52 | |
1.53 | |
1.54 |
The stage delays are 5, 4, 20, 10 and 3. And buffer delay = 2ns
So clock cycle time = max of stage delays + buffer delay
= max(5, 4, 20, 10,3)+2
= 20+2
= 22ns
Execution time for n-instructions in a pipeline with k-stages = (k+n-1) clock cycles
= (k+n-1)* clock cycle time
In this case execution time for 20 instructions in the pipeline with 5-stages
= (5+20-1)*22ns
= 24*22
= 528ns
Efficient Pipeline implementation:
OF phase is split into two stages OF1, OF2 with execution times of 12ns, 8ns
New stage delays in this case = 5, 4, 12, 8, 10, 3
Buffer delay is the same 2ns.
So clock cycle time = max of stage delays + buffer delay
= max(5, 4, 12, 8, 10,3) + 2
= 12+2
= 14ns
Execution time = (k+n-1) clock cycles
= (k+n-1)* clock cycle time
In this case no. of pipeline stages, k = 6
No. of instructions = 20
Execution time = (6+20-1)*14 = 25*14 = 350ns
Speed up of Efficient pipeline over native pipeline
= Naive pipeline execution time / efficient pipeline execution time
= 528 / 350
≌ 1.51
Question 5 |
The stage delays in a 4-stage pipeline are 800, 500, 400 and 300 picoseconds. The first stage (with delay 800 picoseconds) is replaced with a functionally equivalent design involving two stages with respective delays 600 and 350 picoseconds. The throughput increase of the pipeline is ________ percent.
33.33% | |
33.34% | |
33.35% | |
33.36% |
Cycle time = max of all stage delays.
In the first case max stage delay = 800.
So throughput = 1/800 initially.
After replacing this stage with two stages of delays 600, 350... the cycle time = maximum stage delay = 600.
So the new throughput = 1/600.
The new throughput > old throughput.
And the increase in throughput = 1/600 - 1/800.
We calculate the percentage increase in throughput w.r.t initial throughput, so the % increase in throughput
= (1/600 - 1/800) / (1/800) * 100
= ((800 / 600) - 1) * 100
= ((8/6) -1) * 100
= 33.33%
Question 6 |
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;} 16 | |
23 | |
28 | |
30 |

Question 7 |
Delayed branching can help in the handling of control hazards
For all delayed conditional branch instructions, irrespective of whether the condition evaluates to true or false
The instruction following the conditional branch instruction in memory is executed. | |
The first instruction in the fall through path is executed. | |
The first instruction in the taken path is executed.
| |
The branch takes longer to execute than any other instruction. |
Question 8 |
A 4-stage pipeline has the stage delays as 150, 120, 160 and 140 nanoseconds respectively. Registers that are used between the stages have a delay of 5 nanoseconds each. Assuming constant clocking rate, the total time taken to process 1000 data items on this pipeline will be
120.4 microseconds
| |
160.5 microseconds | |
165.5 microseconds
| |
590.0 microseconds |
1st instruction × 4 × clock time + 999 instruction × 1 × clock time
1 × 4 × 165ns + 999 × 1 × 165ns
= 1654.95ns
= 165.5μs
Question 9 |
Consider a 3 GHz (gigahertz) processor with a three-stage pipeline and stage latencies τ1, τ2, τ3 and such that τ1 = 3τ2/4 = 2τ3. If the longest pipeline stage is split into two pipeline stages of equal latency, the new frequency is _________ GHz, ignoring delays in the pipeline registers.
4 | |
5 | |
6 | |
7 |
Given, τ1 = 3 τ2/4 = 2 τ3
Put τ1 = 6t, we get τ2 = 8t, τ3 = 3t
Now largest stage time is 8t.
So, frequency is 1/8t
⇒ 1/8t = 3 GHz
⇒ 1/t = 24 GHz
From the given 3 stages, τ 1 = 6t, τ 2 = 8t and τ 3 = 3t
So, τ 2 > τ1 > τ3.
The longest stage is τ2 = 8t and we will split that into two stages of 4t & 4t.
New processor has 4 stages - 6t, 4t, 4t, 3t.
Now largest stage time is 6t.
So, new frequency is = 1/6t
We can substitute 24 in place of 1/t, which gives the new frequency as 24/6 = 4 GHz
Question 10 |
Consider a non-pipelined processor with a clock rate of 2.5 gigahertz and average cycles per instruction of four. The same processor is upgraded to a pipelined processor with five stages; but due to the internal pipeline delay, the clock speed is reduced to 2 gigahertz. Assume that there are no stalls in the pipeline. The speed up achieved in this pipelined processor is __________.
3.2 | |
3.3 | |
3.4 | |
3.5 |
Time taken to complete one cycle = (1 / 2.5 G) seconds
Since it is given that average number of cycles per instruction = 4, the time taken for completing one instruction = (4 / 2.5 G) = 1.6 ns
In the pipelined case we know in the ideal case CPI = 1, and the clock speed = 2 GHz.
Time taken for one instruction in the pipelined case = (1 / 2 G) = 0.5 ns
Speedup = 1.6/0.5 = 3.2
Question 11 |
Consider the sequence of machine instructions given below:
MUL R5, R0, R1 DIV R6, R2, R3 ADD R7, R5, R6 SUB R8, R7, R4
In the above sequence, R0 to R8 are general purpose registers. In the instructions shown, the first register stores the result of the operation performed on the second and the third registers. This sequence of instructions is to be executed in a pipelined instruction processor with the following 4 stages: (1) Instruction Fetch and Decode (IF), (2) Operand Fetch (OF), (3) Perform Operation (PO) and (4) Write back the Result (WB). The IF, OF and WB stages take 1 clock cycle each for any instruction. The PO stage takes 1 clock cycle for ADD or SUB instruction, 3 clock cycles for MUL instruction and 5 clock cycles for DIV instruction. The pipelined processor uses operand forwarding from the PO stage to the OF stage. The number of clock cycles taken for the execution of the above sequence of instructions is
11 | |
12 | |
13 | |
14 |
O ⇒ Operand Fetch
P ⇒ Perform the operation
W ⇒ write back the result

Question 12 |
Consider the following reservation table for a pipeline having three stages S1, S2 and S3.
Time -->
-----------------------------
1 2 3 4 5
-----------------------------
S1 | X | | | | X |
S2 | | X | | X | |
S3 | | | X | | |
The minimum average latency (MAL) is ________.
3 | |
5 | |
6 | |
7 |
S1 is needed at time 1 and 5, so its forbidden latency is 5-1 = 4.
S2 is needed at time 2 and 4, so its forbidden latency is 4-2 = 2.
So, forbidden latency = (2,4,0) (0 by default is forbidden)
Allowed latency = (1,3,5) (any value more than 5 also).
Collision vector (4,3,2,1,0) = 10101 which is the initial state as well.
From initial state we can have a transition after "1" or "3" cycles and we reach new states with collision vectors
(10101 >> 1 + 10101 = 11111) and (10101 >> 3 + 10101 = 10111) respectively.
These 2 becomes states 2 and 3 respectively.
For "5" cycles we come back to state 1 itself.
From state 2 (11111), the new collision vector is 11111.
We can have a transition only when we see first 0 from right.
So, here it happens on 5th cycle only which goes to initial state. (Any transition after 5 or more cycles goes to initial state as we have 5 time slices).
From state 3 (10111), the new collision vector is 10111.
So, we can have a transition on 3, which will give (10111 >> 3 + 10101 = 10111) third state itself. For 5, we get the initial state.
Thus all the transitions are complete. State\Time 1 3 5 1 (10101) 2 3 1 2 (11111) - - 1 3 (10111) - 3 1 So, minimum length cycle is of length 3 either from 3-3 or from 1-3. So the minimum average latency is also 3.
Question 13 |
For a pipelined CPU with a single ALU, consider the following situations
I. The j + 1-st instruction uses the result of the j-th instruction as an operand II. The execution of a conditional jump instruction III. The j-th and j + 1-st instructions require the ALU at the same time
Which of the above can cause a hazard?
I and II only | |
II and III only | |
III only | |
All the three |
II is belongs to the Control hazard.
III is belongs to the Structural hazard.
→ Hazards are the problems with the instruction pipeline in CPU micro architectures.
Question 14 |
The performance of a pipelined processor suffers if
the pipeline stages have different delays | |
consecutive instructions are dependent on each other | |
the pipeline stages share hardware resources | |
All of the above |
If pipeline stages can’t have different delays, no dependency among consecutive instructions and sharing of hardware resources should not be there.
Question 15 |
An instruction pipeline consists of 4 stages: Fetch(F), Decode operand field (D), Execute (E), and Result-Write (W). The five instructions in a certain instruction sequence need these stages for the different number of clock cycles as shown by the table below.
Find the number of clock cycles needed to perform the 5 instructions.
Theory Explanation. |
Question 16 |
Consider the following code sequence having five instructions I1 to I5. Each of these instructions has the following format.
OP Ri, Rj, Rk
where operation OP is performed on contents of registers Rj and Rk and the result is stored in register Ri.
I1 : ADD R1, R2, R3
I2 : MUL R7, R1, R3
I3 : SUB R4, R1, R5
I4 : ADD R3, R2, R4
I5 : MUL R7, R8, R9
Consider the following three statements:
S1: There is an anti-dependence between instructions I2 and I5.
S2: There is an anti-dependence between instructions I2 and I4.
S3: Within an instruction pipeline an anti-dependence always creates one or more stalls.
Which one of above statements is/are correct?
Only S1 is true | |
Only S2 is true | |
Only S1 and S3 are true | |
Only S2 and S3 are true |
S2: True. There is WAR dependency between I2 and I4.
S3: False. Because WAR or antidependency can be resolved by register renaming.
Question 17 |
Consider the following processors (ns stands for nanoseconds). Assume that the pipeline registers have zero latency.
-
P1: Four-stage pipeline with stage latencies 1 ns, 2 ns, 2 ns, 1 ns.
P2: Four-stage pipeline with stage latencies 1 ns, 1.5 ns, 1.5 ns, 1.5 ns.
P3: Five-stage pipeline with stage latencies 0.5 ns, 1 ns, 1 ns, 0.6 ns, 1 ns.
P4: Five-stage pipeline with stage latencies 0.5 ns, 0.5 ns, 1 ns, 1 ns, 1.1 ns.
Which processor has the highest peak clock frequency?
P1 | |
P2 | |
P3 | |
P4 |
So CPP1 = Max(1,2,2,1) = 2ns
CPP2 = Max(1,1.5,1.5,1.5) = 1.5ns
CPP3 = Max(0.5,1,1,0.6,1) = 1ns
CPP4 = Max(0.5,0.5,1,1,1.1)=1.1ns
As frequency ∝ 1/C.P, so least clock period will give the highest peak clock frequency.
So, fP3 = 1/1ns = 1GHz
Question 18 |
An instruction pipeline has five stages, namely, instruction fetch (IF), instruction decode and register fetch (ID/RF), instruction execution (EX), memory access (MEM), and register writeback (WB) with stage latencies 1 ns, 2.2 ns, 2 ns, 1 ns, and 0.75 ns, respectively (ns stands for nanoseconds). To gain in terms of frequency, the designers have decided to split the ID/RF stage into three stages (ID, RF1, RF2) each of latency 2.2/3 ns. Also, the EX stage is split into two stages (EX1, EX2) each of latency 1 ns. The new design has a total of eight pipeline stages. A program has 20% branch instructions which execute in the EX stage and produce the next instruction pointer at the end of the EX stage in the old design and at the end of the EX2 stage in the new design. The IF stage stalls after fetching a branch instruction until the next instruction pointer is computed. All instructions other than the branch instruction have an average CPI of one in both the designs. The execution times of this program on the old and the new design are P and Q nanoseconds, respectively. The value of P/Q is __________.
1.54 | |
1.55 | |
1.56 | |
1.57 |
Instruction Fetch (IF),
instruction decode and register fetch (ID/RF),
Instruction execution (EX),
Memory access (MEM),
and register writeback (WB)
P old design:
With stage latencies 1 ns, 2.2 ns, 2 ns, 1 ns, and 0.75 ns
Cycle time = MAX(1 ns, 2.2 ns, 2 ns, 1 ns, and 0.75 ns) = 2.2nsec
Branch penalty = 3-1 = 2 because the next instruction pointer at the end of the EX stage(which is 3rd stage) in the old design
AVG instruction execution time is
P = Tavg = (1+no. of stalls*branch penalty)*cycle time
= (1+0.20*2)2.2
P = 3.08 nsec
Q new design:
ID/RF stage is split into three stages (ID, RF1, RF2) each of latency (2.2)/3 ns = 0.73ns.
The EX stage is split into two stages (EX1, EX2) each of latency 1 ns.
The new design has a total of eight pipeline stages.
Time of stages in new design = {1ns, 0.73ns, 0.73ns, 0.73ns , 1ns, 1ns, 1ns, and 0.75ns}
Cycle time = MAX(1ns, 0.73ns, 0.73ns, 0.73ns , 1ns, 1ns, 1ns, and 0.75ns) = 1nsec
Branch penalty = 6-1 = 5 because the next instruction pointer at the end of the EX2 stage(which is 6th stage) in the new design.
AVG instruction execution time is
Q = Tavg = (1+no. of stalls*branch penality)*cycle time
= (1+0.20*5)1
Q = 2 nsec
Therefore, P/Q = 3.08/2 = 1.54
Question 19 |
A non pipelined single cycle processor operating at 100 MHz is converted into a synchronous pipelined processor with five stages requiring 2.5 nsec, 1.5 nsec, 2 nsec, 1.5 nsec and 2.5 nsec, respectively. The delay of the latches is 0.5 nsec. The speedup of the pipeline processor for a large number of instructions is
4.5 | |
4.0 | |
3.33 | |
3.0 |
For pipelined system = Max(stage delay) + Max(latch delay) = 2.5 + 0.5 = 3.0
Speedup = Time in non-pipelined system/Time in pipelined system = 10/3 = 3.33
