XYT-CPU: A 8 bit CPU built from scratch in Logisim

This is an old course project I did at McGill for COMP 273 – Computer System. The goal is to create a CPU in Logisim using none other than the primitive logic gates. Although the CPU project is old and other better designs certainly exist, I still feel that this project’s structure organisation and its bundled assembler have some educational merits. The CPU is called XYT-CPU, named after the initials of the project members.

Logisim is an educational tool for designing and simulating digital logic circuits, its development has ceased since October 2014, but it is quite feature complete and still usable in 2018.

logisim.2.7.0.screenshot

Overview

This CPU is 8-bit, it has 2 general purpose registers r0 and r1, a 8 bit Arithmetic logic unit (ALU) capable of doing XOR and ADD operations, an Instruction Register (IR), an Argument Register (AR) to store instruction arguments and a Control Unit (CU) to handle data flow.

The CPU executes 1-2 bytes instructions (the byte size depends on the instruction) in 4 phases and is capable of addressing $2^8$ bytes in the ram. It comes with a single-pass assembler for this CPU written in Python 2.

cpu overview

The full system has a NUMPAD that is used to input data to the CPU and a pair 7-segment display to depict the output.

The original project requirements forbids the use of Logisim’s builtin registers and memories. This was because implementing registers and RAM using logic circuits was part of the assignment. However, this made debugging any program written to the cpu unnecessarily painful – we need to manually flip $\log_2{N}$ many memory cells to input the program. As a result, the team mirrored the implementation of Registers and Memory to show that they indeed know how to build them, and proceed to use Logisim built-in components as direct replacement blackboxes.

The components of the CPUs are separated into the following blackboxes, with their respective function:

Component Description
RAM-Main 16 bytes of ram with AR input, DR input and DR output
RAM-byte Connect 8 flipflops to make a byte, RAM-Main has 16 of them
Generic-4bitRegister Implementation of Logisim’s builtin Register with databit set to 4
Generic-8bitRegister Implementation of Logisim’s builtin Register with databit set to 8
SYS-Main System board, contains 17 bits sysbus, numpad input, 7seg output, CPU and RAM
ALU-Module 8 bit ALU with Zero, Negative, Overflow indicator. Support ADD and XOR operations.
CU Control unit with sequential combinatorics logic
EXT-DisplayDriver ROM for 7seg display to display hexadecimal digit
CPU-Registers Blockbox containing 2 Genenral purpose registers and logics to read and write to them concurrently
EXT-Numpad2Bin ROM for converting numpad keypress to bin representation of the number
CPU CPU, containing MAR MBR, General purpose registers, CU, IR and PC. Has 8 bit bus

Execution Flow

In summary, XYT-CPU operates in 4 phases:

  1. Load RAM[PC] to IR and increment Program Counter (PC) counter.
  2. Load instructions argument, (from RAM, GP Register, Keypard) PC++ for two byte instructions
  3. Execute instruction (ALU operation, BEQ jump)
  4. Dump result(if any, to RAM, GP Register or display buffer register)

Specifically, when the address in Program Counter (PC) is being read, the data corresponding to that address is copied from MBR into the Instruction Register (IR) and PC is incremented by one. The op-code section of IR consists 4 bits, with each unique code guarding its respective data-path. The following two bits consist register destination (rd) and register source (rs), respectively, as shown on the figure below. Since there are only two general purpose registers in the CPU, 0 in either rd or rs field indicates register 0 (r0), and similarly, 1 would indicate register 1 (r1).

In the cases where there is address involved (based on the OP-code that is read), PC fetches the address that is involved in the instruction, in this case, PC is then incremented by 1. Depending on the instruction, either rd or rs is picked with respect to the address used. For example, in instruction which stores value (STR), the register used would be the source register. If there is an address involved, after it has been fetched, it will be stored to Memory Address Register (MAR). In the case where value is either required to be send from (after it has passed from system bus) or stored to (after the value has been send through CPU bus from its general register) RAM, the value will be store in Memory Buffer Register (MBR).

In the cases where all general registers are involved, for example, the ALU addition instruction, two registers are send to right ALU and left ALU registers through the CPU bus, respectively. And the values are added together. Depending on the destination register, the control unit (CU) would select a pathway that allows ALU-OUT to be stored in the respective destination register. In the case of branch equal, both address and entire two general registers are involved, the general registers are compared using XOR gate, which would give a value of 0 when two registers are equal. Then the address is fetched by traveling through the system bus and put into PC to be the next address to be executed if and only if two registers have equal values.

When without address, only one register is present, according to the OP-code, appropriate data-path will be selected and either the keypad buffer will be activated to store data present in the buffer to selected register; or digital display data-path will be activated for data in register to be stored.

Main CPU Circuit

Main Cpu

CPU Registers

There are two registers, r0 and r1

Main Cpu

Control Unit

Control Unit manages the state of the execution.

Control Unit

ROM for converting numpad decimal input into binary

Decimal to binary conversion was rather easy and can be designed cleanly.

NUM2BIN

ROM for displaying binary data as hexdecimal number

There were nothing too tricky this driver, but I remember designing a circuit for converting a byte of data into 7-segment hexidecimal was so mundane and tedious.

Full Picture

Instructions

Some instructions are one byte, some are two bytes instructions. Two byte instructions are in bold.

Rxy indicates that it can be any of the two general purpose register. yyyyyyyy is a placeholder for an address.

Instruction Function Binary Representation
ADD Rxy, Rxy Add value of the first register to the second and store the result in the first. 0000 xy00
INP Rxy Read from keypad buffer and save value to Rxy 0100 x000
PRINT Rxy Display value in Rxy to the 2 digit display 0101 x000
STOP Stop the program 0110
LW Rxy, Address Load value in memory address to Rxy 1100 x000 yyyy yyyy
SW Rxy, Address Save the value of Rxy to the memory address 1101 x000 yyyy yyyy
BZ Rxy, Rxy, Address Jump to address if value of first Rxy equals the second 1001 xy00 yyyy yyyy

Since the CPU operates in four phases, not all instruction require execution in all of the phases, the table below details the execution phases of the instructions.

Instruction Execution
ADD Rxy, Rxy In phase 3, ALU does addition and in Phase 4, result is saved to the first register
INP Rxy In phase 2, CPU load keypad buffer to argument register, in phase 4 save value in argument register to Rxy
PRINT Rxy In phase 4, CPU save value of Rxy to display buffer
STOP CPU emit stop signal in all phase, this causes system clock signal to block, making system stop
LW Rxy, Address In phase 2, CPU sets MAR to address. CPU data in ram[address] is loaded to MBR, which is fetched to argument register. In phase 4, data in argument register gets copied to destination general purpose register Rxy
SW Rxy, Address In phase 2, CPU sets MAR to address. In phase 3, data in general purpose register is copied to MBR and RW bit is set to 1. Ram will take care of this to save data in MBR to that corresponding address.
BZ Rxy, Rxy, Address In phase 2, the two registers data gets loaded to ALU L and ALU R. In phase 3, ALU do XOR on L and R. argument register gets copied to destination general purpose register Rxy. If ALOUT is zero then PC gets updated to be address.

Example: Multiplication of two numbers

Before showing the multiplication program, we want to first introduce the grammar of the assembly.

A line in the assembly program can be in one of the following syntax:

  1. label:opcode argument1,argument2
  2. opcode argument1,argument2
  3. label:.word 2A where 2A can be replaced by any arbitrary two hexdecimals.

Multiplication program

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
inp $t0
sw $t0,operand1
multi:lw $t0,operand1
lw $t1,counter
bz $t0,$t1,answer
lw $t0,operand2
lw $t1,answer
add $t1,$t0
sw $t1,answer
lw $t1,counter
lw $t0,one
add $t1,$t0
sw $t1,counter
lw $t0,zero #do a jump since we don't have unconditional jump, make both
lw $t1,zero #registers zero, and then
bz $t0,$t1,multi #do a jump here
answer: lw $t0,answer
print $t0
stop
.data
operand1:.word 0
operand2:.word 2 # this is the second operand
counter:.word 0
answer:.word 0
one:.word 1
zero:.word 0

Assembler

Since part of the project requirement was to create a program on the designed CPU that performs the multiplication of two numbers entered in the numpad. For the ease of reproducibility and debugging, an assembler was created.

The assembler take input of the multiplication assembly program depicted above and outputs the corresponding machine code for the CPU as a Logisim compatible RAM-image:

1
2
3
4
5
6
7
8
9
10
11
v2.0 raw 
40 d0 21 c0
21 c8 23 94
1d c0 22 c8
24 08 d8 24
c8 23 c0 25
08 d8 23 c0
26 c8 26 94
03 c0 24 50
60 00 02 00
00 01 00

Being a course project and under pressured time constraint, the assembler has the following limitations:

  1. The parser in assembler cannot handle comment, so all comment has to be removed.
  2. Parser handles cannot generate correct machine code for blank lines, so they have to be removed.
  3. The assembler is a 1-pass assembler, it translates instruction and build symbol table at the same time.

Using the assembler

  1. In your favourite shell, run python2 assembler.py your_program.sm > out_put_ram.img
  2. In Logisim, after loading the CPU, go to SYS-MAIN, right-click on the RAM, then load image, select the out_put_ram.img.

Downloads