Electrical Engineering Stack Exchange is a question and answer site for electronics and electrical engineering professionals, students, and enthusiasts. It only takes a minute to sign up.
Sign up to join this community
I don't understand how MIPS would implement the sll (shift left logical) instruction using the hardware present in its ALU as shown in the diagrams below. Would anyone be able to clarify what would be happening in it when it's executing an sll command? I originally posted this question on Stack Overflow but I was told that I should probably post it here as well. Thanks
Source: MIPS ALU
A commercial MIPS CPU will have a barrel shifter, which takes more / different gates than shown here, letting it shift by any amount in constant time.
As @devnull pointed out, those slides are showing a toy ALU for teaching purposes, supporting only add/sub/compare and some bitwise ops, not left or right shifts. Also not including other MIPS instructions, like xor or sltu (unsigned compare).
A chain of full-adders like that can do left shift by 1 as addu dst, same,same. In a toy CPU (or old real-world CPUs like 8086) you could do that iteratively, shifting 1 count per clock cycle. You could hypothetically do that for a toy MIPS implementation, too, if you're prepared to have the rest of a multi-cycle design pause its sequence while the ALU iterates. But only for left shifts, unless you also have a separate 1-bit right shifter.
But for counts other than 0 or 1, iterative shifting is incompatible with a real MIPS pipeline which requires single-cycle latency for any shift count, so the instruction can leave the EX stage after 1 cycle. The MIPS instruction set has sll $rd, $rt, shamt (funct=0) and sllv $rd, $rt, $rs (funct=04), as well as right shifts (both logical and arithmetic). So counts other than 1 are encodeable, as are variable counts from a register.
The very name of the ISA is Microprocessor without Interlocked Pipeline Stages. Taking multiple cycles for shift counts other than x << 1 = x+x would require a way to stall previous instructions, but a design goal for MIPS I was to avoid needing that. (Except for mul/div, and cache misses.)
(That's why it has load delay slots. Although in MIPS II they added HW detection and stall for that hazard, so those slots didn't have to be filled by NOPs or independent work. They couldn't change the branch-delay slot, though, since existing binaries depended on executing the instruction there. So in MIPS II and later, the name didn't really fit anymore. :P)
I think the normal way to build a barrel shifter into the ALU would be to mux its output with the output of the configurable full-adder chain that you've shown. It handles everything else, where carry propagates from low to high (or not at all for bitwise). You'd still have that chain of full adders, but only use the outputs for funct codes that aren't shifts.
The answer seems to be in the next slide after the one posted in the question:
This is not the MIPS ALU. It is a step by step approach taken in this class material to show the implementation of the operations above.
shift doesn't appear in the whole document).
\$\endgroup\$
add r, r?
\$\endgroup\$
1 would require a way to stall previous instructions.
\$\endgroup\$
May 26 at 18:01
sll rd, rs, 1 could be encoded as addu rd, rs, rs, but not any other immediate count, and not variable-count. See my previous comment; real-world pipelined MIPS needs fixed-latency shifts, therefore a barrel shifter.
\$\endgroup\$
May 26 at 18:03