Computer Architecture MIPS assembler with predictors

Question

This MIPS code is given:

loopA: lw $t0, 0($s1)          # $ array element
       addu $t0, $t0, $s3      # add scalar in s3    
       sw $t0, 0($s1)          # store result
       addi $s1, $-4           # decrement pointer
       bne $s1, $zero, loopA   # branch if s1!=0       

loopB: lw $t0, 0($s2)          # $ array element
       addu $t0, $t0, $s3      # add scalar in s3 
       sw $t0, 0($s2)          # store result
       addi $s2, $-4           # decrement pointer
       bne $s2, $zero, loopB   # branch if s2!=0       

The code is going from top to bottom, passing first trough loopA, and the loopB accordingly. After every passing a constant in $s3 is added to each element(which value is not important).

• The address of the last element of field A is given in the register $s1 and it is equal to 80;

• The address of the last element of field B is given in the register $s2 and it is equal to 100;

We need to use static predictor for branching with strategy that predicts that there will NOT be branching. How many times will there not be stop because of control conflict, in other words how many times the predictions will be right?

The other two question are the same, but:

1. What if we use dynamic predictor with 1 bit, initially set to 0(there will not be branching)?
2. What if we use dynamic predictor with 2 bits, initially set to 11(there will be branching)?

Answer 1

I found an answer to this question and want to answer it, in case someone else needs it.

First we find from the question that $s1 and $s2 are the last element from their fields, and they are equal to 80 and 100.

First we see that the code goes trough the loopA and then the loopB, we see that

addi $s1, $-4   #in loopA


addi $s2, $-4   #in loopB

are the same but with the different registers.

After that we see that the program substracts each of them with 4(four) every time the loop goes trough the fields.

So if we find how many 4(fours) are in:

• first: 80
• second: 100

We should be able to find how many iterations are there.

By dividing 80 with four, and 100 with four we get

loopA: 80/4 = 20

loopB: 100/4 = 25

together = 20+25 = 45 iterations in total.

Now we first focus on the static predictor: The static predictor predicts static, which means it will not change no matter what. It is initially set to 0.

1. We see that from the 45 in total iterations the static predictor will be right only 2 times, when it will exit loopA, and when it will exit loopB. So the answer to the first question is 2 times.

2. Second we use dynamic predictor with 1 bit initially set to 0(there will not be branching). This dynamic predictor changes every time when it gets wrong or right value. from 0 to 1 if right, and from 1 to 0 if wrong. From the 45 total iterations, only 4 times the predictor will be wrong. We see that first the predictor is set to 0, so it will mistake one time entering loopA. Then it will change to 1. When exiting loopA it will miss again setting the bit to 0. When entering loopB it will be set to 0, but we find out that there will be branching, so it goes wrong one more time, while it gets the value 1. After that we see that it will be wrong one last time while exiting loopB. So from the total it will miss 4 times. We need the amount of iterations when the predictor is right, so we substract 45 - 4 = 41 times it will be right. The bit will be 0 at the end. 0->1->0->1->0

3. Lastly with the dynamic predictor we have the same thing, so I will make a smaller explanation. Firstly the bits are set to: 11->10->11->10 (changing of bits) 1 miss when exiting loopA and 1 miss when exiting loopB. 45 - 2 = 43 times it will be right with two bits set to 10 at the end.