Question

Problem Description:

Given Machine Instruction

1. LD R1, 50(R2)

2. ADD R3, R1, R4

3. LD R5, 100(R3)

4. MUL R6, R5, R7

5. ADD R1, R1, #100

6. SUB R2, R2, #8

Font type: Times New Roman and Size 12

Task to do:

a) Draw the four-stage pipeline for the above Instruction.

b) Calculate the total clock cycles for all the above-mentioned instructions need to be completed.

c) Explain how to handle structural hazards the pipeline instruction.

d) Explain the classification of data hazards

e) Draw the flow chart for four stage pipeline and explain.

Answer 1

in four stage piple-line each and every instruction must execute in foure stages. lae us assum the four stages are: Fetch(F),Decode(D), Execute(E), Write(W). during the execution every stage able to process only one instruction. in the above progem the first four instructions are dependent instructions i.e the result obtained in the one instruction is used as input in the next instruction. the next instruction need to wait for the previous instruction completion. for example the the first instruction is loading the value into register R1. In second instruction R1 is the input operand. in second instruction R3 is destination or result in third instruction it is used as input operand . between these instruction deta dependency is there. In second stage (Decode) the instruction is decoded and the required operands are feteched, if operands are not available it will wait untill operands are avaialable called data hazard ( pipeline stalled). the following chart will show the instrution execution with data hazard

Instruction/clock cycle

T1

T2

T3

T4

T5

T6

T7

T8

T9

T10

T11

T12

T13

T14

T15

1.LD R1, 50(R2)

F

D

E

W

2.ADD R3, R1, R4

F

F

F

D

E

W

3.LD R5, 100(R3)

F

F

F

D

E

W

4. MUL R6, R5, R7

F

F

F

D

E

W

5.ADD R1, R1, #100

F

D

E

W

6.SUB R2, R2, #8

F

D

E

W

it is clear that second instruction is waiting for first instruction, third instruction is waiting for secong instruction and fourt instruction is waiting for third instruction. last two instructions are independent instructions.

total number of clock cycles for the completion= 15

Structural hazard means resource conflict, when more than one instruction is trying to access the same resource in the same clock cycle structural hazard will occur.

for example : STR 50(R2),R1

INSTR2

INSTR3

  SUB R2, R2, #8

INstruction/Clock	T1	T2	T3	T4	T5	T6
STR 50(R2),R1	F	D	E	W
INSTR2		F	D	E	W
INSTR3			F	D	E	W
SUB R2, R2, #8				F

in the above sequence of execution at clock cyle T4, instruction 1 is writing data into memory and instruction 4 is feacting the instruction from memory both are accessing the memory.

to handle the structural hazard we may include stalls in pile lien execution means delays.

INstruction/Clock	T1	T2	T3	T4	T5	T6
STR 50(R2),R1	F	D	E	W
INSTR2		F	D	E	W
INSTR3			F	D	E	W
SUB R2, R2, #8				STALL	F

another way of solving these hazards is to add additional hardwares. one is for featching the data another is for writing.

Classification of data hazard:

there are three types of data hazards

1. Read After Write (RAW)
2. Write After Write (WAW)
3. Write After Rerad (WAR)

1. RAW hazard will occure when one instruction need to read the data after written by another instructions. in the above sequence of instructions instructions (1,2), (2,3), (3,4) are best examples.

2.this hazard is occured when the write operation of any instruction will take more than one clock cycle .

for example,

LD R1, 50(R2)

ADD R1, R3, R4

	T1	T2	T3	T4	T5	T6
LD R1, 50(R2)	F	D	MEM	MEM	E	W
ADD R1, R3, R4		F	D	E	W

at the end of this instruction sequence execution we will expect the r1 value which is written by second instruction but the memory operation involved in first instrution took more clock cyles. this type of hazard will ocuure when instruction involved in memory operation which are possibly take more than one clock cylcles.

3. this hazard occure if one instruction write the value after read operation of another instrtion.

in instruction decoding phase the processor will identify the operation and operand sinvolver in the instruction. if it is a branch instruction it will save the current progrma counter value as return address and discard hte instrructions which are currently in pipeline and fetch the instructions from branch target. after every instruction execution completion it will check for pending interrupts. if any interrupts is there again save the current Program counte rvalue as return address and fetch the instruction from interrupt service routine.