Structural, data and control hazards

Which one of the following dependencies among
the register operands of different instructions can
cause a data hazard in a pipelined processor?

• (a)Read-after-read
• (b)Read-after-write
• (c)Write-after-read
• (d)Write-after-write

The EX stage of a pipelined processor performs
the memory read operations for LOAD
instructions, and the operations for the arithmetic
and logic instructions. Let tEX denote the time
taken by the EX stage to perform the operation for
an instruction. For each instruction type, the
values of tEX and M (the number of instructions of
that type in a sequence of 100 instructions for a
program P), are given in the table below. The
duration of the pipeline clock cycle is 1
nanosecond. Assume that the latch time for the
interstage buffers in the pipeline is negligible.

When program P is executed, the number of clock
cycles for which the pipeline is stalled due to
structural hazards in the EX-stage is
.
(answer in integer).

An instruction format has the following structure:
Instruction Number: Opcode destination reg,
source reg-1, source reg-2
Consider the following sequence of instructions to
be executed in a pipelined processor:
I1 : DIVR3,R1,R2
I2 : SUB R5,R3,R4
I3 : ADDR3,R5,R6
I4: MUL R7,R3,R8
Which of the following statements is/are TRUE?

• (a)There is a RAW dependency on R3 between I1 and I2
• (b)There is a WAR dependency on R3 between I1 and I3
• (c)There is a RAW dependency on R3 between I2 and I3
• (d)There is a WAW dependency on R3 between I3 and I4

A
non-pipelined
instruction
execution
unit
operating at 2 GHz takes an average of 6 cycles to
execute an instruction of a program P. The unit is
then redesigned to operate on a 5-stage pipeline at
2 GHz. Assume that the ideal throughput of the
pipelined unit is 1 instruction per cycle. In the
execution of program P, 20% instructions incur an
average of 2 cycles stall due to data hazards and 20%
instructions incur an average of 3 cycles stall due to
control hazards. The speedup (rounded off to one
decimal place) obtained by the pipelined design over
the non-pipelined design is

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 a non-pipelined processor operating at
2.5 GHz. It takes 5 clock cycles to complete an
instruction. You are going to make a 5-stage
pipeline out of this processor. Overheads
associated with pipelining force you to operate the
pipelined processor at 2 GHz. In a given program,
assume that 30% are memory instructions, 60%
are ALU instructions and the rest are branch
instructions. 5% of the memory instructions cause
stalls of 50 clock cycles each due to cache misses

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
.

Consider the following code sequence having five
instructions from 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
MUL
R5, R0, R1
DIV
R6, R2, R3
ADD
R7, R5, R6
SUB
R8, R7, R4
Computer Organization and Architecture

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 the above statements is/are
correct?

• (a)Only S1 is true
• (b)Only S2 is true
• (c)Only S1 and S3 are true
• (d)Only S2 and S3 are true

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 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 is 25% if the instructions incur 2 pipeline
stall cycles is
.

Register renaming is done in pipelined processors

• (a)as an alternative to register allocation at compile time
• (b)for efficient access to function parameters and local variables
• (c)to handle certain kinds of hazards
• (d)as part of address translation

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

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 Read-
After-Write (RAW) dependencies, Write-After-
Read( WAR) dependencies, and Write After-Write
(WAW) dependencies in the sequence of instructions
are, respectively,

• (a)2,2,4
• (b)3,2,3
• (c)4,2,2
• (d)3,3,2

Following table indicates the latencies of
operations between the instruction producing the
result and instruction using the result.

Instruction producing
the result
Instruction using the
result
Latency
ALU Operation
ALU Operation
2
ALU Operation
Store
2
Load
ALU Operation
1
Load
Store
0

Consider the following code segment:
Load R1, Loc 1; Load R1 from memory location Loc1
Load R2, Loc 2; Load R2 from memory location Loc 2
Add R1, R2, R1; Add R1 and R2 and save result in R1
Dec R2; Decrement R2
Dec R1; Decrement R1
Mpy R1, R2, R3; Multiply R1 and R2 and save
result in R3
Store R3, Loc 3; Store R3 in memory location Loc 3

What is the number of cycles needed to execute
the above code segment assuming each instruction
takes one cycle to execute?

• (a)7
• (b)10
• (c)13
• (d)14