CODEWITHSUNDEEP
assemblymipscpu-architecturecpu-hazard
user19336710
user19336710

Reputation: 1

Identifying all RAWs & inserting "nop"(s) in the MIPS code

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

Upvotes: 0

Views: 595

Answers (1)

Erik Eidt
Erik Eidt

Reputation: 26646

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.

Upvotes: 2

Related Questions