ALU Control

We will take a closer look at the ALU. The ALU itself is actually a combinational circuit that is capable of performing several arithmetic operations. Combinational circuit has no internal state, so the output is dependent purely on the inputs. In this case, we will have to include the ALUcontrol signal as part of the input to the ALU.

For now, simply remember that the current draft (i.e., v0.5) is as follows:

ALU

We will create the ALU one bit at a time. So we will consider an ALU that will perform operations on only 1-bit data.

1-Bit ALU

A simplified 1-bit MIPS ALU can be implemented as follows¹:

There are 4 control bits needed:

• Ainvert (1-bit)

  • 0: Do not invert input A
  • 1: Invert input A

• Binvert (1-bit)

  • 0: Do not invert input B
  • 1: Invert input B

• Operation (2-bits)

  • 00: Result of bitwise AND
  • 01: Result of bitwise OR
  • 10: Result of ADD

1
2
3

bool not(bool A) {
  return !A;
}

1
2
3

bool and(bool A, bool B) {
  return A & B;
}

1
2
3

bool or(bool A, bool B) {
  return A | B;
}

1
2
3

[bool,bool] add(bool A, bool B, bool Cin) { // Cin is carry bit
  return [(A + B + Cin)%2, (A + B + Cin)/2];
}

1
2
3
4
5
6
7

bool or(bool A, bool B, bool ctrl) {
  if(ctrl == false) { // ctrl == 0
    return A;
  } else {            // ctrl == 1
    return B;
  }
}

Now, we can see how the 4-bits ALUcontrol signal is created. Note that the implementation for slt is not shown.

Now we can start to design the ALUcontrol signal. This signal must depend on:

• opcode: Inst[26:31]
• funct: Inst[0:5]

There are multiple ways we can do this.

Brute Force

The most obvious way to do this is to brute force our way. This can be done by finding a function that takes in two inputs, the opcode and funct (e.g., ctrl_regdst(opcode, funct)). In principle, this will be like finding expressions with 12 variables (i.e., 6-bits opcode and 6-bits funct).

Multilevel Decoding

The second approach is to use some of the input to reduce the cases. We can then generate the full output from this reduced cases. This will simplify the design process, reduce the size of the main controller and potentially speedup the circuit. As such, this will be our preferred approach.

32-Bit ALU

A simplified 1-bit MIPS ALU can be abstracted further by ignoring the internals.

Given this, we can then connect Cout output from 1-bit to Cin input for another 1-bit. This lets us add any 32-bits number. By chaining all of the results, we can then get the following 32-bit ALU.

And voila! We have just created the 32-bit ALU. This assumes that we can generate the ALUcontrol, which we will do next.

Multilevel Decoding

Using multilevel decoding approach, we can try to generate an intermediate signal. This intermediate signal is again simply a convention but what is important is that it can only depend on opcode. In other words, we can always have other conventions and proceed from there. Our convention is a 2-bit ALUop signal which is as follows:

This ALUop signal can be generated fully from the opcode. Then, using this 2-bit ALUop signal and the 6-bit funct field for the R-format instructions, we will generate the 4-bit ALUcontrol signal.

Now we are ready to generate the ALUcontrol signal. We will discuss how to generate the ALUop signal later together with the rest of the other control signals. But we have achieved part of our objective to reduce the complexity of generating ALUcontrol.

Summary Table

We can first construct a summary table. From this, we can generate the truth table. Using the truth table, we can hopefully find a pattern. But first, let us put the ground rule and convention to be used.

1. We use 1 to indicate true and 0 to indicate false.
2. We use X to indicate that the value can be either 1 or 0
   • If X appears in the output, then it does not matter what the value is.
   • If X appears in the input, then we have to ensure that the operation works regardless of what the value is.
3. We can only use the following operations:
   1. Bitwise OR: Indicate by +.
   2. Bitwise AND: Indicate by ..
   3. Bitwise NOT: Indicate by ! or ~.

Truth Table

So now, we can construct the truth table. The inputs are the ALUop signal and funct field. Since the funct field are 6-bit wide, we can number them for easy identification. We will use the name F0 to F5 to mean the bit from funct field at index 0 to 5 respectively. Similarly, we will use ALUop0 and ALUop1 to mean the bit from ALUop signal at index 0 and 1 respectively. Finally, we will use ALUcontrol0 to ALUcontrol3 to mean the bit from ALUcontrol signal at index 0 to 3 respectively.

So, the idea of constructing the operations to solve for this is to find pattern. To do that, we can try to simplify the pattern. Sometimes, we may be able to ignore the input since they definitely cannot depend on that. In such cases, maybe it is simpler to just ignore it and replace with - because the output is guaranteed to work regardless of that value. Note that it is not X which is a don't care (i.e., can be either 0 or 1).

Simplfied Truth Table

So now we arrived at the simplified truth table below.

Using this simplified truth table, we are ready to deduce the operat-ons to generate ALUcontrol.

ALuControl3

First note that ALUcontrol3 is always 0.

ALUcontrol2

Second, note that for ALUcontrol2, the value where it is 1 lines up nicely with F1. But this is only true if the instruction is R-format instruction.

We can say that:

ALUcontrol2 is 1 if F1 is 1 AND ALUop1 is 1 (i.e., R-format)

This gives us one part of the solution: F1 . ALUop1.

Now, if the instruction is NOT R-format, then ALUcontrol2 is 1 if the operation is beq. We can identify if it is beq by ALUop0.

We can say that:

ALUcontrol2 is 1 if ALUop0 is 1 (i.e., beq).

This gives us the other part of the solution: ALUop0.

Combining the two, we can say that it is 1 if either one or both of the above is true.

ALUcontrol1

Using similar method as before, note that ALUcontrol1 is 0 if F2 is 1 and the instruction is R-format.

ALUcontrol1 = ALUop1 . !F2

On the other hand, for non R-format, we simply set it to 1.

ALUcontrol1 = !ALUop1

We can then combine as before to get:

You can try to simplify this, but we do not have the technique yet, that will only be available later. However, we can take a look at the overall pattern and note that:

ALUcontrol1 is 0 if ALUop1 is 1 and F2 is 1.

But since we are interested in the point where they are 1, we can negate this entire condition.

ALUcontrol1 = !(ALUop1 . F2)

But using De Morgan's Law, this is simply:

ALUcontrol1 = !ALUop1 + !F2

ALUcontrol0

Lastly, for ALUcontrol0, we simply note that the formula will be as follows. Can you figure out how to deduce that?

ALU Control Unit

Let us first summarise the formula for each ALUcontrol bit.

1
2
3
4

ALUcontrol3 = 0
ALUcontrol2 = (F1 . ALUop1) + (ALUop0)
ALUcontrol1 = !ALUop1 + !F2
ALUcontrol0 = (F0 + F3) . ALUop1

This gives us the following circuit.