CODEWITHSUNDEEP
assemblymipscpu-architecturemips32
user5496677
user5496677

Reputation: 21

Trying to understand creating a MIPS pipeline diagram

I have to create a pipeline diagram executing the following MIPS code. It's a 5-stage pipeline. Both the mul and div instructions use 4 execute instructions. To quote the assignment for the mul instruction

This means that a multiply instruction runs through the pipeline as follows: F-D-X0-X1-X2-X3-M-W and up to four multiply instructions maybe in-flight at a time. All other instruction types are blocked from the execute stage while any of the multiply stages are being used.

and for div

This means that a divide instruction runs through the pipeline as follows: F-D-X0-X0-X0-X0-M-W. All other instructions are blocked from the execute stage while a division is being done.

Here is the MIPS code.

xor   $r0, $r0, $r0
addiu $r1, $r0, 10
j L1
loop: 
    lw    $r3, 0($r2)
    mul   $r4, $r3, $r3
    mul   $r3, $r3, $r1
    addiu $r0, $r0, 1
    div   $r3, $r4, $r3
    sw    $r3, 0($r2)
    addiu $r2, $r2, 4
L1: 
bne $r0, $r1, -8

The full question I have to answer for this is:

Q: Draw a pipeline diagram (table) showing the execution of the MIPS code through the first iteration of the loop, without bypassing. Assume data hazards and structural hazards are resolved using only stalling. Assume the processor assumes branches are not taken, until they are resolved. What is the CPI of the entire program?

Here is what I got:

MIPS Pipeline Diagram

My biggest snag came from trying to understand what to do when it came to the jump instruction. As you can see I just kind of went about business as usual but I know that is most likely completely wrong. I'm fairly confident I handled the instructions after mul and div properly, it's just the j L1 instruction I'm not confident with regards since I have no examples to refer to. CPI as an after thought though I'm assuming I just take the total cycles and divide it by the number of instructions? So in this case it would be (32 cycles)/(11 instructions) so CPI = 2.91?

Thank you for your time.

Upvotes: 2

Views: 2602

Answers (1)

mewais
mewais

Reputation: 1337

Before answering your question, you should first know about branch prediction. Branches can cause you to either fetch from a new location or continue fetching sequentially as normal. Waiting for the branch condition to resolve which address you should fetch from often causes stalling and wastes some cycles. To overcome that processors use branch prediction or speculation, they assume a branch is taken or non-taken and continue fetching and execution based on this assumption. Once the branch condition is resolved, the processor knows whether its assumption was right or wrong, if it is right you continue execution as normal and you have saved a couple of precious cycles instead of stalling. if the assumption turns out to be wrong you flush the wrongly executed instructions out of your pipeline and the penalty is usually the same as if you stalled waiting for the branch to resolve. Better branch prediction algorithms have a higher probability of correctly guessing whether to branch or not.

As you stated in your question

Assume the processor assumes branches are not taken, until they are resolved.

Your processor uses a static branch prediction. It always assumes the branch is not taken. if the assumption is found to be wrong the instructions are flushed from the pipeline.

This applies to branches but not jumps because only branches are dependent on a condition. jumps execute unconditionally and do not prediction. so after executing that jump instruction you should have continued directly from L1.

Upvotes: 1

Related Questions