NiAiMa CPU

Introduction

Whilst watching Harry Porter's relay CPU we thought that designing our own CPU would be fun. A while later we found a program called Logisim that could simulate logic gates, with hierarchical logic blocks, allowing you to make your own building blocks and re-use them in increasingly complicated circuits. Over the next few weeks we used Logisim to design and simulate an 8-bit RISC CPU - that's what we do for fun!

All instructions have a single Fetch / Execute cycle. The ALU "A" input is always connected to a register called the Accumulator. The ALU outputs to the accumulator as well, for use in the next instruction cycle(s). A single carry/condition bit is similarly kept from each instruction for future instruction cycles. We have 10 general-purpose registers, any of which can be used as the "B" input to the ALU. Some instructions write. Some special-purpose registers can be treated as 16-bit address registers used to read/write memory, with auto post-increment and pre-decrement. One pair is used as a Program Counter (PC), the other is an indirect address register (AD) often used as a stack pointer. Most instructions have 4 bits of "Operation" and 4 bits used to select the register to be read/written. Some simpler instructions only work on the Accumulator and Carry.

We named our CPU after the first 2 letters of each of our names - Nick (dad), Aiden, and Mark (13-year old twins)

ALU

We started with an 8-bit ALU that could do any simple boolean instruction you like, add, subtract, and a few other ripple-carry operations

Our 1-bit "AnyLogic" gate takes 3 inputs, A, B, C, and an 8-bit control. It acts as any 3-input, 1-output logic gate, for example:

Here we are showing the logic operation "A and B and C". The output is 1 only if A and B and C are all 1. We can perform this in our AnyLogic gate with the Control input set to 10000000 - the values you see in the bottom row. Some other interesting operations are:

By combining 2 of our "AnyLogic" gates, we make a 1-bit ALU. We treat A and B as regular inputs, C as a carry input, one "AnyLogic" produces out output bit, another "AnyLogic" produces the carry output to be sent to the next stage.

8 of these 1-bit ALUs are arrange into an 8-bit ALU. The A and B inputs are now regular 8-bit inputs, combined to form an 8-bit output. The single-bit Carry input "CIn" is rippled from the lowest bit to the highest bit, and then output. When adding, C can be used as a Carry, obviously, but some other operations can use it as a flag, for example we use C to choose whether to output A or B - if C is set (1) we output A, if C is clear (0) we output B:

We have to keep the Carry (/condition) value all the way down the 8-bit ALU otherwise this would only work on the first (lowest) bit.

We can also perform a "Shift Left" operation, by using the Carry to pass each input bit 1 place left. We ignore B. We output the "carry in", and we set the next carry to be the A bit:

	A Input
	7	6	5	4	3	2	1	0
Cout									CIn
	6	5	4	3	2	1	0	C
	Output

We can't perform a "Shift Right", because our carry always goes left not right, but we are also shifting C in, and out to C, so could perform a right-shift by doing 8 left-shifts:

Registers

Logisim has a few types of registers built in, but we decided we wanted to do it ourselves from scratch. When Write is active, one of the 2 NOR gates gets powered, allowing the other to lock them in place. The loop of back-to-back NOR gates is either locked on/off, or off/on. We can read from this loop as a "Peek" (any time) or a real "Read" which pulls a tristate high or low. We can also reset ("RST").

The animated register here is demonstrating writing a zero, reading it, writing a 1, reading it, and repeating. Hover over it to reset (RST), which forces a 0 to be written.

We combine 8 of these to make an 8-bit register.

Accumulator, and Carry bit

Our registers have "active high" Write inputs, they are not edge-triggered, so we need two 8-bit registers for our Accumulator. One holds the current accumulator value, the other latches the next value on execute cycles. Our Carry logic is the same but only 1-bit.

General Purpose Register Bank

Our CPU has 16 addressable registers. 10 of them are General-purpose registers. We select a register using RS3/2/1/0 through the AND gates, then Read (Rd) onto the data bus (DOut) or Write (Wr) from the data bus (DIn). We named these registers E to N. The "Peek" outputs are output just to be displayed on LEDs (see later).

Multiplexors

Again we could have used Logisim built-in blocks but wanted to create our own: A 1-bit "Mux" is made from 3 logic gates. It uses a "Sel" input to choose between "False" and "True" inputs.

8 are combined for an 8-bit mux where an 8-bit output is Selected from one of the two 8-bit inputs.

Inc/Decrementors

Some of our special-purpose registers will need to self-increment or decrement without using the ALU. The circuits here perform a simple ripple-carry increment ("add one") or decrement ("subtract one")

Delay

Unlike our "active high" registers, Logisim's RAM is rising-edge triggered, so it sometimes reads (or worse, writes) errors whilst our logic is still settling, unless we deliberately delay "memory write" by about 10 gate-delays.

Special Purpose Register Bank

Our CPU also has some special-purpose registers. A pair of 8-bit registers acts as the Program Counter (PC) where our instructions are read, and they need to be used as a 16-bit address. After reading an instruction, our incrementor increments the values in the PC ready to read the next instruction. A similar pair acts as an ADdress register for stack and other memory operations. Before you write to the memory, they decrement. This will make stack operations possible, where we decrement and write to the stack pointer, or read and increment:

Each pair of registers consumes 3 "register select" values. One for the "high byte" (P in PC, or A in AD), one for the "low byte" (C in PC, or D in AD), and one for memory read/writes using PC or AD as the address, with post=increment or pre-decrement.

The PC is almost always used in the "read and increment" mode, either during the Fetch cycle, and/or during the Execute cycle if we are using the register "[PC++]" (1111) - sort of an "immediate" addressing mode. To do a JUMP instruction, we write to the PC, but because we can only write 8 bits at a time, if we started by writing to P, then we would jump to an unintended location. We have something called "P holding" that gets written to P when we write to C. Similarly because we can't read P and C at the same time, we arrange for "Read C" to also transfer P into "P holding", which is what we actually read when we "Read P". This allows us to act as though we can read/write PC in one single operation even though in practice it will take 4 (FETCH a location, STORE to P (actually P-holding), FETCH another location, STORE to C, at which point P-holding is also written to P and we JUMP).

AD also has an "A holding" that holds a value to go into A when we write to D, or holds the value of A when we read D.

Sequencing

Hover over the image to reset our sequencer. Our sequencer uses a 3-bit shift register to create non-overlapping "Fetch" and "Execute" cycles. The sequence operates like:

Instruction Decoding

We used to decode the top 4 bits (for 16 instructions), using the lower 4 bits as "source/target register", however we we noticed a number of instructions that don't use a register, they operate only on the Accumulator and Carry/Condition flag. We instead decided to decode the full 8 bits using a ROM, though for many instructions we now repeat them 16 times, for the same instruction, but operating on each of the 16 registers.

During the fetch cycle, we select (RS) register 1111 - [PC++], and Read it into our Instr Register. This is then used as the address into a 256-row ROM. The outputs of the ROM are 8 bits of ALU output control, 8 bits of ALU Carry control, 2 bits of "Write select", 4 bits of register select (often, but not always, equal to the lower 4 bits of the Instruction Register).

The "Write Select" bits allow us to READ (00) from a register, Write (01) to the register, conditionally write (10) if Carry/Condition is 1, or conditionally write (11) if Carry/Condition is 0 (not yet used)

Our instruction set is shown below. For example, 59 is the "ADD N" instruction. The microcode 096e89 is in the ROM at address 0x59, decoded as WOOCCR where W=0, OO=96, CC=e8, R=9:

• W=0 means "don't write, read from the register".
• OO=96 is the ADD output control for the ALU, 1001 0110 in binary, as seen in our AnyLogic example way above
• CC=e8 is the ADD carry control for the ALU, 1110 1000 in binary, again as seen in our AnyLogic example
• R=9 selects register 9, also known as the "N" register

• W=0 means "don't write, read from the register" -which is going to be ignored anyway because:
• OO=f0 ALU output control, 1111 0000 in binary, "keep Accumulator" will output the Accumulator back into itself
• CC=ff ALU carry control, 1111 1111 in binary, will always set C to 1 regardless of Accumulator/Register/C inputs
• R=0 selects register 0 ("D"), which the ALU is going to ignore anyway

• W=1 means "write, unconditionally" (regardless of C=0 or C=1)
• OO=f0 ALU output control, 1111 0000 in binary, "keep Accumulator" will output the Accumulator back into itself
• CC=aa ALU carry control, 1010 1010 in binary, will keep C unchanged
• R=e selects "register e", which is actually using the special-purpose AD register to write not to AD itself, but to memory at address AD, but first pre-decrementing AD, often written [--AD]

The full contents of our Instruction Decoding ROM, including comments discussing the details of each command, register names, and possible (bits of) future commands, can all be downloaded. Most of the file is comments, only the "0f0aa0" hex strings without #s will be loaded into the Instruction Decoding ROM.

Overview

Now that we have everything described, we can build the entire CPU. The Accumulator and Carry/Condition sits just above the ALU so that there is less wiring. Below it is the Instruction Decoding, to control the ALU. The Sequencer, next to the Instruction Decoding, clocks throough the Fetch / Execute cycle. The General Purpose Registers sit below the Instruction Decoding, which selects a register and controls the Read / Write lines. Below that we placed the PC and AD Special-Purpose registers. PC (usually, AD occasionally) is output onto the address bus at the bottom, to control the RAM in the bottom-left. The Data bus sits to the left of the ALU, Instr Dec, GP Reg, and PC/AD. In the top right is the reset switch. Most of the rest on the right-hand side are blinky LED displays showing the values of all the registers and some control lines.

The entire Logisim circuit file NiAiMa.circ can be downloaded.

The image here shows the CPU after it has finished the multiplication of 42 * 100 to get 4200. multiply.hex can also be downloaded. This was our first real program for the NiAiMa CPU unless you count a few simple tests.

Our ALU can't multiply directly, so we made a program about 50 bytes long which does binary long-multiplication. 42 is stored in E. 100 is stored in F. G and H will store the 16-bit result. We do the long-multiplication by looping I=8 times for the 8 bits in E. We shift GH left (the "result so far"). We shift E left, setting Carry if it overflowed. If it did, we add F to GH, then we decerement our loop counter (I) and loop back. E is destroyed in the process by left-shifting it out, F is still 100, GH contains 1068 hex, which is 4200 decimal. M and N were used to store the "loop start" which can be (conditionally) written back to PC to jump back there.

Endianness

[See Endianness on Wikipedia]. At this stage, our CPU is neither big-endian nor little-endian. Everything is 8-bit. There are no 16-bit or 32-bit instructions. 16-bit or 32-bit maths requires multiple commands, it usually makes sense to start at the 1s (Least Significant Byte - LSB) so you can carry into the next byte(s), but in memory we could store them in any order we like.

Some exceptions...

• When we are JUMPing, the instructions might be:
  FETCH [MSB], STORE in P (actually P' - P-holding),
  FETCH [LSB], STORE in C (and P' → P = JUMP)
  You could say this is big-endian (MSB first) but it's also broken up between multiple commands
• When we are writing PC onto the stack to use as a return address for a CALL, the obvious, quickest, easiest way to do so would be:
  FETCH C, (which also holds P → P'),
  PUSH it onto the stack (STORE [--AD]),
  FETCH P', PUSH it onto the stack (STORE [--AD]).
  When RETURNing to a previously stacked return address, the obvious way would be:
  POP P (FETCH [AD++]), STORE it to P (actually P')
  POP C, STORE it to C (and P' → P, completing the return JUMP
  Because our stack starts at the end of memory and works backwards, this ends up stored in the order P (at [AD]), C (at [AD+1]), which is also big-endian.
• If we wanted to store little-endian, we could do so, but we'd need to deliberately write in a different order, EG:
  FETCH C (holding P → P'), STORE in some spare register,
  FETCH P', PUSH it, FETCH the spare above, PUSH it.
  This uses more instructions and requires an extra register.

Stack

The examples above are very simple, just storing return addresses. Real stacks have areas for local variables, function parameters, and return values, often of different sizes. Rather than just having one Stack Pointer, there is sometimes a pointer called a Frame Pointer which only moves during calls/returns. The Frame Pointer points at the start of the frame for this current function. All local variables, arguments, temporary variables, return values are stored at known offsets from the Frame Pointer.

Because our AD register is also used for reading/writing any other part of memory, we can't always use it as a stack pointer. Instead we will use the MN registers as a Frame Pointer except during real stack operations (at some known offset of the Frame Pointer)

Example

Ignore the terrible type errors, that's not the point. Also assume int=short=16bit for this example

// An example C program:
int main(int argc, char **argv) {
  byte X = foo(1,2,3);
  return 42 + X;
}

byte foo (int A, int B, int C) {
  byte D = bar(A, B);
  D     += bar(D,C);
  return D;
}

int bar(int X, int Y) {
  return X + Y;
}

When inside bar(), our stack might look like:

This stuff is maintained by Nick Waterman - Email Me