Question

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 intermediate storage buffers after each stage and the delay of each buffer is 1 ns. A program consisting of 12 instructions I₁, I₂, I₃, …, I₁₂ is executed in this pipelined processor.

Instruction I₄ is the only branch instruction and its branch target is I₉. If the branch is taken during the execution of this program, the time (in ns) needed to complete the program is

1. 132
2. 165
3. 176
4. 328

Answer 1

"Correct Answer - Option 2 : 165

The correct answer is ""option 2"".

CONCEPT:

A pipeline is a process where multiple instructions get overlapped during execution.

The pipeline is divided into stages and these stages are connected with one another to improve the execution process

The pipeline allows storing and executing instructions in an orderly process.

In the instruction pipeline, a stream of instructions is executed by overlapping phases of the instruction cycle like fetch, decode, execute, etc.

It reads an instruction from memory while previous instruction being executed in others segments of the pipeline.

EXPLANATION:

T1

T2

T3

T4

T5

T6

T7

T8

T9

T10

T11

T12

T13

T14

T15

I1

FI

DI

FO

EI

WO

I2

FI

DI

FO

EI

WO

I3

FI

DI

FO

EI

WO

I4

FI

DI

FO

EI

WO

I5

Stall

I6

stall

I7

stall

I9

FI

DI

FO

EI

WO

I10

FI

DI

FO

EI

WO

I11

FI

DI

FO

EI

WO

I12

FI

DI

FO

EI

WO

 

Cycle time = max of all stages delay + buffer delay

= max (5ns,7ns,10ns,8ns,6ns) + 1ns

= 10ns + 1ns

= 11ns

Out of all the instructions from I1 to I12, I4 is the only branch instruction.

When I4 takes branch, the control will jump to the target instruction I9.

There will be 3 stalls in stages DI, FO & EI.

So after 3 stalls, I9 will start its execution as it is a branch target.

So, total number of clock cycles = 15

Since 1 clock cycle time = 11ns

So, total time to complete the program = 15 × 11ns = 165 ns

Hence, the correct answer is ""option 2"".   

"