Given the following sequence of instructions to be executed on a 5-stage pipelin

Question

Given the following sequence of instructions to be executed on a 5-stage pipelined data path as descripted in our textbook: a. List true dependencies in the given sequence in the format of (register _involved. Producer _instruction, consumer_ instruction). Use labels to indicate instructions. For example: ($0, I10, I11) means a true dependence between instruction I10 and I11: value of register $0 is generated by I10 and used by I11. Do NOT list output or anti-dependences. b. If there is no forwarding or hazard detection, no reordering allowed, insert nops to ensure correct execution. c. Repeat b. but allow instruction reordering -- nops should be inserted only when a hazard cannot be avoided by reordering instructions. d. If there is full forwarding support, draw multiple-cycled pipeline diagram to show the execution of the original sequence (NOT the reordered version). Use arrows to mark forwarding's clearly in your diagram. Each arrow should point from instruction/stage that generates the data rightarrow instruction/stage that consumes the data. Also mark the necessary pipeline stalls.

Explanation / Answer

1)
True Dependency 1: ($8,I1,I2)
True Dependency 2: ($9,I2,I3)
True Dependency 3: ($8,I3,I4)
True Dependency 4: ($9,I2,I5)

2)
Since the MIPS is a load-store architecture, all instructions take 1 clock cycle except those instructions which get there operands from memory.
These instructions which get their operands from memory will take 3 clock cycles.

I1       - add instruction, takes 1 cycle
I2       - Store to memory, takes 3 cycles
NOP
NOP
I3       - Load word takes 3 clock cycles.
NOP
NOP
I4       - and instruction, takes 1 cycle
I5       - NOP after this instruction, does not matter.

3)
Instruction reordering can be done as below. Only I5 instruction can be included earlier.

I1
I2
NOP
NOP
I3
I5
NOP
I4

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.