BGE Implementation in MIPS

Question

I need to implement BGE instruction in MIPS:

BGE $r1,$r2,despl (jump to PC + 4 + despl(<<) if regA >= reg B)

I need to modify the architecture but I do not know how

Answer 1

It is true that for signed arithmetic, the MSB coming out of the ALU indicates the sign of the answer — but it is only valid when there is no overflow.

Mathematically speaking, adding two 32-bit numbers produces a 33-bit answer with no overflow.  If that 33-bit answer is forced into 32 bits by truncation (truncation means loosing/discard the 33'rd high bit, and there's no other reasonable approach to such downsizing), then there is the possibility of overflow.  When there is overflow, the 32-bit answer will have the sign reversed from what it should be, so the 32-bit answer is just junk — and while predictable junk, it is not directly usable.

However, a bge instruction doesn't need to capture a 33-bit answer in 32 bits of storage, but only tell us if the first operand was >= the second operand.  This can be done in all cases without overflow: we never need to truncate a 33-bit answer to 32 bits, but only need one bit of answer as output (yes/no) so unlike subtraction, no truncation is ever needed.  So, this is the most appropriate way to implement bge.

If, instead, you implement bge by using subtraction in the ALU and then looking at the MSB of a 32-bit result, that won't detect overflow, so this instruction will give wrong answers when the inputs are out of range, such as comparing max signed int to min signed int.  If you choose to detect overflow (possible by comparing signs of the A & B ALU inputs with the sign of the ALU output), what you'd have to do is either cause an exception (like add and sub do), or correct the answer outside the ALU.

To see more clearly, let's look at some examples as if we were doing this in 8 bits: let's see about 1 and -1, where the answer is 1 - (-1) = 2 which is positive so we know that 1 is indeed >= -1.  Using a larger values 63 and -63: 63 - (-63) = 126, also positive so we know >= holds.  But if we do 127 and -127, we get 127 - (-127) which is 254, but truncated back to 8 bits we have -2 (which is overflow) and that would lead us to believe that -127 is larger than 127.

Because this instruction could and can be implemented so as to avoid all issues of overflow, well, it should be done that way!

If it was me, I would add an OPALU value for ge operation to the ALU, and when that, have the ALU simply output Z=1 if >= holds on the operands and Z=0 otherwise.  No overflow, just some custom circuitry in the ALU, and an extra OPALU value to feed the ALU.

However, it seems that maybe your professor is looking for a different answer possibly involving reuse of existing ALU subtraction (OPALU) instead.

For that you would have OPALU call for subtraction, and then pull the 32 bit, the MSB out of the ALU.  You can take that (inverted of course, since MSB=1 means less than and Z=1 usually means take the branch) and then mux that into the Z line on condition of bge, or feed a second line to the UNIDAD DE CONTROL, and let it figure out whether to use Z vs. your new line.  This solution would involve overflow problems, which ought to be mitigated in some way (but perhaps unnecessary for this assignment).

---

These two potential approaches are not that different.  Assuming you did the OPALU ge value fed to the ALU, the ALU could do either 33-bit arithmetic or 32-bit arithmetic with overflow detection & correction.  The subtraction approach could also do overflow detection & correction, with the main difference being it would occur outside the ALU vs. inside the ALU.

As far as the final hardware is concerned, there is no box boundary between the gates inside the ALU vs. outside the ALU, but at the level of this kind of block diagram, I would put this complexity inside the ALU.