0

This is the MIPS code :

(1)    Loop : lw $2, 0($1)
(2)           lw $3, 0($2)       # $2
(3)           add $4, $3, $2     # $3, $2
(4)           sw $4, 4($2)       # $4
(5)           beq $4, $5, Loop   # $4

  1. For identifying all the RAW dependencies in the code, I think that $2 in instruction 2 and 3 have RAW dependency to $2 in instruction 1. And $3 in instruction 3 has RAW dependency to $3 in instruction 2. Lastly, $4 in instruction 4 and 5 have RAW dependency to $4 in instruction 3. I don't know if this is right or not.

  2. Question : Assume the pipelined processor provides full forwarding but no hazard detection logic. Assume branch target address calculation and resolution is done in ID and the last beq instruction is taken. Please insert "nop" between instructions and after beq if needed to avoid the hazards. [hint : you can insert two nops if you need two stall cycles]

First, I'm not sure If I checked all the RAWs right or not. and Second, I have no idea where to put nop(s) in the code, I only inserted nop in the codes that are not in loop. please help me with this. Thank you

  • I edited again thanks to the comment. I'm not used to stackoverflow
Peter Cordes
  • 328,167
  • 45
  • 605
  • 847
user19336710
  • 1
  • 1
  • [Please do not post images of text because they are hard to use.](https://meta.stackoverflow.com/questions/285551/why-not-upload-images-of-code-errors-when-asking-a-question) Text should be posted directly **as text** in your question. – MikeCAT Jun 14 '22 at 11:07
  • Sorry. I was not used to the format. I corrected my post. thanks – user19336710 Jun 14 '22 at 11:22
  • *Assume branch target address calculation and resolution is done in ID and the last beq instruction is taken* FYI, that's not how commercial MIPS CPUs did it: [How does MIPS I handle branching on the previous ALU instruction without stalling?](https://stackoverflow.com/q/56586551) - it's actually done in the first half-cycle of EX, so you can `slt` / `bne` without any stalls, because real MIPS also have bypass forwarding. (But forwarding backwards in time is still impossible, so EX can't forward to ID for the next instruction.) Anyway, you have a hypothetical slow MIPS, to see how slow it is – Peter Cordes Jun 15 '22 at 00:07

1 Answers1

1

Your assessment of the RAW hazards look good.

For the nop insertion on the hypothetical pipelined processor with no hazard mitagation, probably best to work with a pipeline table.

It is a two-dimensional table, with time/cycle# on one axis and the 5 pipeline stages on the other.  (Which axis is which doesn't really matter.)  Then in the cells of the table, put the instruction number — the table effectively tells us which instruction is in which pipeline stage at what cycle#.

We can use the table to detect RAW hazards: check all the true data dependencies and look at where the ID stage (Instruction Decode) of the reading instruction is relative to the WB stage (Write Back) of the writing instruction.

Whenever there is a data dependency where the ID stage of the reader is earlier in time than the WB stage of the writer, that is a data dependency that is also a RAW hazard.  This is the definition of RAW hazard.

(Let's note that the data dependence on $2 of instruction (4) as reader and instruction (1) as writer line up: so that (4)'s ID stage is in the same cycle as (1)'s WB stage.  This is a data dependency that is not a RAW hazard.)

For each RAW hazard some nop(s) must be inserted to accommodate the hypothetical processor.  Each such insertion changes the timing so that minimally the ID stage lines up with the WB stage for a given hazard — however, let's note that nop's inserted to mitigate one RAW hazard will also change timings of the other data dependencies, such that they may no longer be RAW hazards.

So, the approach then is to insert one or two nops (one or two as needed) into the instruction stream, to mitigate the first occurring RAW hazard, then using the new code sequence, redo the list of RAW hazards (and redo the table), such that you only work on the RAW hazards that remain in the newly modified code.  Repeat until no hazards.

Erik Eidt
  • 23,049
  • 2
  • 29
  • 53