Decode Stage

Requirements

The decode stage is combined with the operand fetch stage due to the simplicity of the pure decode stage.

Since the decode stage is done after the fetch stage, it takes as its input, the output of the fetch stage. Additionally, the output of the decode stage will be passed to the ALU stage.

1. Read the opcode to determine the instruction type and field lengths.

2. Read data from all necessary registers.

   • Can be two registers (e.g., add, sub, beq, etc).
   • Can be one register (e.g., addi, lw, etc).
   • Can be zero register (e.g., j but our processor do not support this).

3. The data read is given as output to the next stage (i.e., ALU stage).

Block Diagram

Given the requirements above, we can have the following initial design:

As usual, let us take a look at the three steps more closely. We will later note that this initial design will not satisfy certain operations. This will be replaced with a more correct design later.

Examples

In these examples, we will use the notation Inst[Y:X] to mean the bits from the instruction Inst from bit X to bit Y.

Elements

Register File

The Register File is simply a collection of 32 registers. Each of the register is 32-bit wide. Reading and writing into the register is done by specifying the register number. We can only read at most 2 registers per instruction (i.e., based on $rs and $rt) and can only write at most 1 register per instruction (i.e., based on $rd or $rt according to instruction).

But what data are we writing? The Register File we have shown above is incomplete. We will need to 2 more inputs:

1. Write Data: The 32-bit data to be written to the register specified by Write Register.
2. RegWrite: A control signal to indicate whether we want to write into the register or not.
   • Write: 1 or true
   • No Write: 0 or false

Now, for the functional view of a Register File, it is easier to represent it as 2 functions: 1 function to generate the two output and 1 function to write into the register. Additionally, we can represent the 32 registers as a single-dimensional array similar to Instruction Memory but a much smaller size is needed. We are going to abuse the function notation to allow returning two values using a notation [val1, val2] with a type of [type1, type2]. These may be extended into more values.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

/* Note:
    RR1: Read Register 1
    RR2: Read Register 2
    WR : Write Register
    WD : Write Data
*/
Word Regs[32]; // 32 registers
[Word, Word] read_data(int RR1, int RR2) {
  return [Regs[RR1], Regs[RR2]]; // output: [Read Data 1, Read Data 2]
}
void write_reg(int WR, Word WD) {
  Regs[WR] = WD;
}

Multiplexer

Note that we currently do not have a multiplexer (usually abbreviated as mux) in our diagram, but it is needed to create the correct diagram for the processor. A multiplexer is another combinational logic but now it is used to select which input is passed to the output.

The block diagram is shown on the right. Again, we can view it conceptually as a function instead. Now, instead of just an input and output, we add another line called the control line¹.

1. Inputs

   • n inputs in₀ to in_n-1 shown by an arrow going in to the multiplexer.
   • Each input should be the same width.

2. Outputs

   • One output out shown by an arrow going out of the multiplexer.
   • The result is one of the inputs.

3. Control

   • One control with a width of log₂ n shown by the control line at the top (sometimes at the bottom).
   • This controls which input is selected to the output.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

/* Note:
    There is no internal state (no global variable).
    We assume uint input, but can be changed to suit our needs.
    The n inputs are represented as an array.
*/
uint mux(uint IN[n], uint CTRL) {
  return IN[CTRL];
}
// Special case for 2 inputs
uint mux2(uint in0, uint in1, uint CTRL) {
  if(CTRL == 0) {
    return in0;
  } else {
    return in1;
  }
}

Sign Extend

This is the most straightforward combinational logic. It will simply duplicate the MSB of the input until the output is 32 bits wide.

1
2
3
4
5
6
7
8
9

/* Note:
    Assume we can retrieve and set the bit via indexing.
*/
uint sign_extend(uint IN) {
  for(i=16; i<32; i++) {
    IN[i] = IN[i-1]; // extend the MSB
  }
  return IN;
}

Modified Block Diagram

Using multiplexer, we can modify the block diagram to correct the behaviour for I-format.

There are now two additional multiplexers and one additional sign extend. Furthermore, there are 3 control signals:

1. RegDst: Select which input goes into Write Register.

   • Inst[20:16]: 0
   • Inst[15:11]: 1

2. RegWrite: Write WriteData into register specified by WriteRegister or not.

   • No Write: 0
   • Write: 1

3. RegDst: Select which input goes into output result.

   • Read Data 2: 0
   • Inst[15:11]: 1

Using this modified block diagram, the previous problem with I-format instruction no longer pose any problem.