Forwarding, stalls and branch prediction

Consider a 5-stage pipelined processor with
Instruction Fetch (IF), Instruction Decode (ID),
Execute (EX), Memory Access (MEM), and
Register Writeback (WB) stages. Which of the
following statements about forwarding is/are
CORRECT?

• (a)In a pipelined execution, forwarding means the result from a source stage of an earlier instruction is passed on to the destination stage of a later instruction.
• (b)In forwarding, data from the output of the MEM stage can be passed on to the input of the EX-stage of the next instruction.
• (c)Forwarding cannot prevent all pipeline stalls.
• (d)Forwarding does not require any extra hardware to retrieve the data from the pipeline stages.

A processor X1 operating at 2 GHz has a standard 5-
stage RISC instruction pipeline having a base CPI
(cycles per instruction) of one without any pipeline
hazards. For a given program P that has 30% branch
instructions, control hazards incur 2 cycles stall for
every branch. A new version of the processor X2
operating at the same clock frequency has an
additional
branch
predictor
unit
(BPU)
that
completely eliminates stalls for correctly predicted
branches. There is neither any savings nor any
additional stalls for wrong predictions. There are no
structural hazards and data hazards for X1 and X2. If
the BPU has a prediction accuracy of 80%, the speed
up (rounded off to two decimal places) obtained by
X2 over X1 in executing P is
.
Computer Organization and Architecture

Consider a pipelined processor with 5 stages,
Instruction Fetch (IF), Instruction Decode (ID),
Execute (EX), Memory Access (MEM), and Write
Back (WB). Each stage of the pipeline, except the
EX-stage, takes one cycle. Assume that the ID stage
merely decodes the instruction and the register read
is performed in the EX-stage. The EX-stage takes
one cycle for ADD instruction and two cycles for
MUL instruction. Ignore pipeline register latencies.
Consider the following sequence of 8 instructions:
ADD, MUL, ADD, MUL, ADD, MUL, ADD,
MUL
Assume that every MUL instruction is data-
dependent on the ADD instruction just before it and
every ADD instruction (except the first ADD) is
data-dependent on the MUL instruction just before
it. The speedup is defined as follows:

Speedup = Execution time without operand forwarding
Execution time with operand forwarding

The Speedup achieved in executing the given
instruction sequence on the pipelined processor
(rounded to 2 decimal places) is
.
and 50% of the branch instructions cause stalls of 2
cycles each. Assume that there are no stalls
associated with the execution of ALU instructions.
For this program, the speedup achieved by the
pipelined processor over the non-pipelined processor
(round off to 2 decimal places) is
.

Consider the sequence of machine instructions
given below

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
.

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 performance, 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 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
.

Consider an instruction pipeline with five stages
without any branch prediction: Fetch Instruction (FI),
Decode Instruction (DI), Fetch Operand (FO),
Execute Instruction (EI) and Write Operand (WO).
The stage delays for FI, DI, FO, EI and WO are 5 ns,
7 ns, 10 ns, 8 ns and 6 ns, respectively. There are
Computer Organization and Architecture

intermediate storage buffers after each stage and
the delay of each buffer is 1 ns. A program
consisting of 12 instructions I1, I2, I3, .... I12 is
executed in this pipelined processor. Instruction I4
is the only branch instruction and its branch target
is I9. If the branch is taken during the execution of
this program, the time (in ns) needed to complete
the program is

• (a)132
• (b)165
• (c)176
• (d)328

A 5-stage pipelined processor has Instruction Fetch
(IF), Instruction Decode (ID), Operand Fetch (OF),
Perform Operation (PO) and Write Operand (WO)
stages. The IF, ID, OF and WO stage take 1 clock
cycle each for any instruction. The PO stage takes 1
clock cycle for ADD and SUB instructions ,3 clock
cycles for MUL instruction, and 6 clock cycles for
DIV instruction respectively. Operand forwarding is
used in the pipeline. What is the number of clock
cycles needed to execute the following sequence of
instructions?

• (a)13
• (b)15
• (c)17
• (d)19

Delayed branching can help in the handling of
control hazards
The following code is to run on a pipelined
processor with one branch delay slot:
I1: ADD R2 ← R7 + R8
I2: SUB R4 ← R5 - R6
I3: ADD R1 ← R2 + R3
I4: STORE Memory [R4] ← R1
BRANCH to Label if R1 == 0
Which of the instructions I1, I2, I3 or I4 can
legitimately occupy the delay slot without any other
program modification?

• (a)I1
• (b)I2
• (c)I3
• (d)I4

Which of the following are NOT true in a pipelined
processor?
1. Bypassing can handle all RAW hazards.
2. Register renaming can eliminate all register
carried WAR hazards.
3. Control hazard penalties can be eliminated by
dynamic branch prediction.

• (a)1 and 2 only
• (b)1 and 3 only
• (c)2 and 3 only
• (d)1, 2 and 3

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.

• (a)The instruction following the conditional branch instruction in memory is executed
• (b). The first instruction in the fall through path is executed
• (c). The first instruction in the taken path is executed
• (d). The branch takes longer to execute than any other instruction

Consider a pipelined processor with the following
four stages:
IF: Instruction Fetch
ID: Instruction Decode and Operand Fetch
EX: Execute
WB: Write Back
The IF, ID, and WB stages take one clock cycle each
to complete the operation.
The number of clock cycles for the EX stage depends
on the instruction. The ADD and SUB instructions
need 1 clock cycle, and the MUL instruction needs 3
clock cycles in the EX stage.
Operand forwarding is used in the pipelined
processor.
What is the number of clock cycles taken to complete
the following sequence of instructions?

• (a)7
• (b)8
• (c)10
• (d)14 Computer Organization and Architecture

A CPU has a five-stage pipeline and runs at a 1
GHz frequency. Instruction fetch happens in the
first stage of the pipeline. A conditional branch
instruction computes the target address and
evaluates the condition in the third stage of the
pipeline.
The processor stops fetching new instructions
following a conditional branch until the branch
outcome is known.
A program executes 109 instructions out of which
20% are conditional branches.
If each instruction takes one cycle to complete on
average, then the total execution time of the
program is:

• (a)1.0 second
• (b)1.2 Seconds
• (c)1.4 Seconds
• (d)1.6 Seconds

A pipelined processor uses a 4-stage instruction
pipeline with the following stages: Instruction fetch
(IF), Instruction decode (ID), Execute (EX) and
Writeback (WB). The arithmetic operations as well as
the load and store operations are carried out in the EX
stage. The sequence of instructions corresponding to
the statement X=(S-R*(P+Q))/T is given below. The
values of variables P,Q,R,S and T are available in the
registers R0,R1,R2,R3 and R4 respectively, before the
execution of the instruction sequence.
ADD R5,R0,R1 ;R5←R0 + R1
MUL R6,R2,R5 ;R6←R2 * R5
SUB R5,R3,R6 ;R5←R3 -R6
DIV R6,R5,R4 ;R6←R5/R4
STORE R6,X ;X←R6
The IF, ID and WB stages take 1 clock cycle each.
The EX stage takes 1 clock cycle each for the ADD,
SUB and STORE operations, and 3 clock cycles each
for MUL
and DIV operations. Operand forwarding from the
EX
stage to the ID stage is used. The number of clock
cycles
required to complete the sequence of instructions i

• (a)10
• (b)12
• (c)14
• (d)16 Computer Organization and Architecture

A 5 stage pipelined CPU has the following
sequence of stages:
IF – Instruction fetch from instruction memory
RD – Instruction decode and register read
EX – Execute: ALU operation for data and
address computation
MA – Data memory access - for write access, the
register read at RD state is used.
WB – Register write back
Consider the following sequence of instructions:
I1: L R0, Loc1;
R0 ← M[Loc1]
I2: A R0, R0;
R0 ← R0 + R0
I3: A R2, R0;
R2 ← R2 - R0
Let each stage takes one clock cycle.
What is the number of clock cycles taken to
complete the above sequence of instructions
starting from the fetch of I1?

• (a)8
• (b)10
• (c)12
• (d)15

Data forwarding techniques can be used to speed up
the operation in the presence of data dependencies.
Consider the following replacements of LHS with
RHS:
(i)
R1 → Loc,
Loc → R2 ≡ R1 → R2,R1→Loc
(ii)
R1 → Loc,
Loc → R2 ≡ R1 → R2
(iii) R1 → Loc,
R2 → Loc ≡ R1 → Loc
(iv) R1 → Loc,
R2 → Loc ≡ R2 → Loc
In which of the following options will the result of
executing the RHS be the same as executing the
LHS irrespective of the instruction that follow ?
Computer Organization and Architecture

• (a)(i) and (iii)
• (b)(i) and (iv)
• (c)(ii) and (iii)
• (d)(ii) and (iv)