How are various functions (eg. add, subtract, and, etc) implemented in ALU?

Question

I am wondering since there are so many functions an ALU need to do, how might I start implementing one (a homework where I am supposed to implement a MIPS system with Logisim, using basic Gates, Flip-flops etc).

The part I am confused about is how can I implement an ALU which can do different functions like Add/Subtract/AND/OR/etc. Do I need to more control logic (see top right in "prev assignment" below).

In a previous assignment, I implemented an ALU that can do Add/Subtract/Negate. Now I think an ALU should be able to do functions like

My prev assignment

Answer 1

While internally computing all the answers, and then using a mux to select among them will work, it certainly is not a minimal design.

Consider that you can bit-slice the problem; instead of a single block of logic with two 8 bit inputs, you could partition this as two 4-bit sections, as long as you can link them to get a correct overall result. Fortunately, linking the slices is no worse than a single bit, which in the case of addition represents the carry bit. So each 4-bit slice has a carry-in bit and a carry-out bit. (Note that logicals like AND and NOR won't even need this, though if later on you implement left/right shifts, this bit is easily re-purposed).

Carried to an extreme you could use 8 slices of 1-bit each. It's useful to think about the 1-bit slices, because it makes it easier to think about an approach that scales back up to larger slices. So with a 1-bit slice, you have just 7 inputs: the 4 bit function code, a bit from input A, a bit from input B, and a carry-in bit. You also have just two outputs: function out, and carry out. So now you can write the two output functions in terms of just 7 inputs, which is within the realm of human ability to reasonably reduce. You'll end up with a handful of gates that won't necessarily always compute all the functions, but it doesn't matter what happens within the slice, only that it produces the correct result when viewed from outside.

Now you can go a couple of ways. One way is to simply use 8 of these 1-bit slices and you're done. Another way is to make larger slices and then use those. Going from 1-bit to 2-bits, the equations go from 7 inputs to 9, and 4-bits will require functions of 13 inputs. It's not necessarily easy, but will give more compact results than the compute-everything-then-mux approach. Besides, if you look at the internals of a 74181 4-bit ALU slice, you won't see a mux in there.

Answer 2

Yes, you need more control logic.

Your previous assignment was purely arithmetical (is that a word?), so you could use a single adder and massage the inputs using the control signals to create the functions you want

Your new functions are logical, so you need another block to perform logical operations. The control signals will change the functionality of this block.

Then at the bottom of your diagram you'll need a multiplexer (sometimes called a 'mux') driven by the control signals to choose which of the answers you are going to output (the one from the adder and it's "input massaging" circuit or the one from the logic operator).

If you can choose new encodings for your ALU control lines, I might be tempted to use the MSB as a "arithmetic/logic" select, and the others to select the "subfunction" if that makes sense, as it simplifies the decode for the final mux.

Answer 3

One nice approach to handling logical operations is to have the bits of the two operands serve as selector inputs to a 4-input multiplexer, and feed the "data" inputs of the multiplexer a four-bit pattern corresponding to the desired operation (typically in an 8-bit ALU, there would be eight multiplexers--one for each bit--and the "data" inputs of all 8 multiplexers would be tied together).