An Example Microcoded CPU

1 Introduction

Last week we looked at a CPU whose control logic was fully hardwired.
We saw that designing the control logic using gates and multiplexors was messy.
This week, we look at alternative, to write the control logic using microcode.

2 An Example Microcoded CPU

Mythsim is a simulation of a microcoded CPU, with nice graphical windows showing the datapath of the CPU, the microprogram table, the contents of memory etc.
I will probably use Mythsim in one of the questions in Assignment 2, so pay attention!
The CPU has an 8-bit data bus and an 8-bit address bus.
Each instruction is 16-bits long. Implication: two memory fetches are required to bring an instruction in from memory.
Instructions are stored in little-endian format: the low-end is fetched first, then the high-end.
There are four 8-bit registers (R0 - R3) visible to the user, and 4 8-bit registers (R4 - R7) hidden from the user. R7 is used as the PC.
The ALU can perform four logic and four maths operations. Two of the maths operations take 2 operands; two take just one operand: typically to increment or decrement a register.
There is also an instruction register split into two 8-bit sections: ir0 and ir1, and latches on the data and address busses known as the memory data register mdr and memory address register mar.
Here is the datapath diagram, which also shows the main control lines into and out from each sub-unit.

2.1 Instruction Formats

There are two formats for the 16-bit instructions:

ir_opcode ir_ri ir_rj ir_rk ir_const4

bits 15 to 10 bits 8,9 bits 6,7 bits 4,5 bits 3 to 0

ir_opcode ir_ri ir_const8

bits 15 to 10 bits 8,9 bits 7 to 0
The first format has a 6-bit opcode, 3 register operands and a 4-bit constant.
The second format has a 6-bit opcode, one register operand and an 8-bit constant.
As you can see from the datapath diagram, the IR decode logic brings out all of the six fields in parallel.

2.2 Microcode

As we saw in the hardwired CPU, we need to assert different control lines at different phases of the instruction.
In a microcoded CPU, what lines to assert and when are stored in a table.

2.3 Writing the Microcode

Internally, the microcode is stored as a pattern of bits in rows and columns in the microprogram table.
To write it, there is a microassembler!
Each microinstruction is labelled, not numbered.
Each microinstruction lists the control lines which will be enabled, i.e. not left at zero.
Each microinstruction can perform IF .. THEN .. ELSE and jump to a specified next microinstruction if some data or control value is a specific value or not.
As well, the microcode can switch based on the particular opcode in the instruction, i.e. jump to microcode number X if the opcode is N.
At the beginning of each CPU instruction, the next instruction's value has to be loaded into the IR. Remember, R7 is the PC.

Let's look at the microassembly instructions to do this:

fetch0: a_sel=7, b_sel=7, alu_sel=AND, r6_write, mar_sel=LOAD;

ALU's output is R7 AND R7, i.e R7. Write this into R6 for now, and also load it into the memory address register. No next microinstruction is specified, so the default is the next one.
```
fetch1: r7_write, a_sel=6, alu_sel=ADDA, c_in, read, ir0_sel=LOAD,
        if wait then goto fetch1 endif;
```
The ALU is instructed to ADD only R6 + c_in, which is set to 1, i.e. we are incrementing R7. This is written back into R7.
On the memory interface, the data bus is instructed to read, and the value is loaded into ir0 (bottom-half of the IR).
Now, memory is much slower than the CPU, so it may be signalling wait to indicate that the data bus does not yet have the value. If this is true, loop back and redo this microinstruction.
This is why we add R6 + 1, and not R7 + 1. If we did the latter, R7 would increment for every clock cycle we wait for the data bus.

We are halfway through the 2-byte instruction fetch, so the next two microinstructions should be similar.

fetch2: a_sel=7, b_sel=7, alu_sel=AND, r6_write, mar_sel=LOAD;

fetch3: r7_write, a_sel=6, alu_sel=ADDA, c_in, read, ir1_sel=LOAD,
        if wait then goto fetch3 endif;

At this point, the 16-bit instruction is fetched, R7 has been incremented by 2 so it points at the next instruction.
The next microinstruction is unlabelled (nobody goes to it):
```
goto opcode[IR_OPCODE];
```
Using the 6-bit opcode as a lookup value, go to the specific microinstruction which is the first one for the given opcode.

2.4 The ADD Instruction

Let's say that we want ADD Ri, Rj, Rk, i.e. Ri = Rj + Rk. How do we achieve this in microcode? Let's make it opcode 1.
```
opcode[1]: ri_sel, rj_sel, rk_sel, alu_sel=ADD, goto fetch0;
```
rj_sel and rk_sel control the register file, and send Rj's and Rk's value out along the a_bus and b_bus to the ALU.
The ri_sel selects in which register to write the result of the ALU.
Note that the final command is to go back to the fetch0 microinstruction. At the end of every sequence which performs one CPU instruction, the micro counter has to return back to microinstruction 0.

2.5 The Branch if R3 is Zero Instruction

Let's write an instruction that, if R3 is zero, adds the ir_const8 to the value in the PC, i.e. R7. Let's make it opcode 3.

opcode[3]: a_sel=3, b_sel=3, alu_sel=SUBA, 
           r6_write, result_sel=IR_CONST8,
           if c_out then goto fetch0 else goto branch endif;

branch: r7_write, a_sel=7, b_sel=6, alu_sel=ADD, goto fetch0;

This needs a bit of explanation. The SUBA ALU operation does this: adds the value on the a_bus to the constant -1. Now, watch what happens when the a_bus holds the number 0:
```
     0000 0000 +
     1111 1111       (i.e. twos-complement -1)
    -----------
     1111 1111
```
and note that there was no carry. However, for any other bit pattern on the top, there would be a 1 bit which would cause a carry, which would ripple out on the left-hand side.
The ALU in Mythsim doesn't have an "is zero" status output, just a carry output. So, we load R3 into the ALU on the a_bus and subtract 1 from it using the SUBA operation. If c_out is off, R3 was zero; if c_out is on, R3 was not zero.
In parallel, we also use the Result multiplexor to select the 8-bit constant from the IR and write it across the result_bus into R6.
If c_out is on, i.e. R3 is not zero, we simply do the next CPU instruction, i.e. go back to fetch0. Otherwise, we take the branch.
The branch microinstruction sends R7 (the PC) and R6 (the branch amount) on the a_bus and b_bus to the ALU, which ADDs them, and writes the result across the result_bus back into R7, and then goes to fetch0 to do the next CPU instruction.

2.6 Simulation of an Example Assembly Program

Given a series of 8-bit numbers at memory address 32 onwards, add them together until the first zero number is found, then store the result into memory address 30.

After designing some CPU instructions with our microcode, and giving each one an opcode number, we should be able to write this hypothetical assembly language program:

      LOADI R0, 0       # R0 <- 0
      LOADI R1, 1       # R1 <- 1
      LOADI R2, 32      # R2 <- 32
loop: NOP               # Do nothing
      LOAD R3, (R2)     # R3 <- memory[R2]
      BEQ R3, end       # Stop looping if R3 == 0
      ADD R0, R0, R3    # Add number to the running sum in R0
      ADD R2, R2, R1    # Move R2 up to the next number
      JUMP loop         # Loop backwards for the next number
end:  LOADI R1, 30      # R1 <- 30
      STORE R0 (R1)     # memory[R1] = R0, i.e write result in location 30
      HALT              # Halt the CPU

It's time to run the simulator and see this in action.

3 Inspirational Reading

If you find the idea of designing a CPU at all interesting, then you should read these books.
The first book is The Soul of a New Machine by Tracy Kidder, which describes the huge effort that a team puts in to design a new 32-bit CPU.
The book is in no way a dry, technical read. Instead, it talks about the people, what motivates them, the journey that the team takes to get it working, the frustration and the elation. One reviewer writes: "This is not only a history of a major moment in computer history, it is a superb picture of the dynamics of people in technical development teams and the challenges of achieving a technical goal".
The second book is The Elements of Computing Systems by Noam Nisan and Shimon Schocken. In this self-study book, you get to build a fully-working (simulated) hardwired CPU from the simplest logic gates up, including the ALU, the registers and RAM chips, and the control logic. If you want to get your hands dirty building a CPU, this is the book to read!

File translated from T_EX by T_TH, version 3.85.
On 17 Dec 2010, 10:38.

ir_opcode	ir_ri	ir_rj	ir_rk	ir_const4
bits 15 to 10	bits 8,9	bits 6,7	bits 4,5	bits 3 to 0

ir_opcode	ir_ri	ir_const8
bits 15 to 10	bits 8,9	bits 7 to 0