HRM CPU is a personal project aimed at designing a soft core microprocessor in Verilog, synthetizable in an FPGA that behaves like the gameplay of Human Resource Machine by Tomorrow Corp.
Here's an extract of an article on HRM, posted on IEEE's Spectrum site:
In this game the player takes on the role of an office worker who must handle numbers and letters arriving on an “in” conveyor belt and put the desired results on an “out” conveyor belt.
[...]Those in the know will recognize the office worker as a register, the temporary workspace on the office floor as random access memory, and many of the challenges as classic introductory computer science problems.[...]
The HRM CPU is an 8-bit multi-cycle RISC miroprocessor based on the Harvard architecture with variable length instructions and one register (accumulator).
TL;DR: For the impatients, you can jump to these demos (with videos) at the end:
We can see how the game actually represents a CPU and its internal components:
HRM components | # | CPU components |
---|---|---|
Office Worker | 1 | Register (Accumulator) |
In/Out belts | 2, 3 | Input/Ouput (I/O) |
Floor Tiles | 4 | Memory (RAM) |
Program | 5 | Program Memory |
6 | Program Counter | |
7 | Instruction Register |
The instruction set is (almost) the same as in the HRM game, I have respected the limited original 11 instructions set, to which I have added three convinient instructions: SET, WAIT and HALT.
The latest version of the instruction set is described in this Google Spreadsheet.
The following picture shows the instruction set format, and corresponding machine language:
The current implementation status is represented by the color in the first column (Green: implemented in Logisim, white: pending).
I have added a couple of instructions that were not in the HRM game: WAIT, SET, and HALT.
I have also added support for some memory mapped IO, allowing to access additional modules via the memory commands, by setting the mmio bit in the opcode lower nibble.
The opcodes are encoded with 1 word (8 bit) or two nibbles. Some instructions have one operand which is also encoded with 8 bits. So the length of instructions is variable: some are 1 word wide, others are two words wide.
The HRM CPU is capable of addressing 256 bytes of block-ram, or 256 bytes of memory-mapped IO.
Addressing Mode | Example Instruction | Description |
---|---|---|
Direct Mode | COPYTO A | The operand A represents the address in Ram the instruction will operate on |
Indirect Mode | COPYTO [A] | The value stored in Ram at the address A will be used as the address in Ram the instruction will operate on |
Memory Mapped IO | COPYTO /A | Address A represents a memory mapped module and possibly a function (depending of the module). See Memory Mapped I/O |
HRM CPU support a limited set of Memory Mapped modules detailled below.
Access to memory mapped modules is achieved by asserting the "mmio bit" (lsb) in the opcode of the instruction. In assembler language, we prefix the ADDR with "/":
Action | Instruction format | Example |
---|---|---|
Write from R to memory mapped device at address ADDR | COPYTO /ADDR | COPYTO /LEDS |
Read from memory mapped device at address ADDR into R | COPYFROM /ADDR | COPYFROM /RAND |
Currently, there are 3 modules available via Memory Mapped IO:
COPYTO /16
. There's also a macro so we can use COPYTO /LEDS
.The table below details the modules, the addresses and the corresponding function, when written or read:
Instruction | Meaning |
---|---|
COPYTO /A0 | Copy R to register A0 in XALU |
COPYTO /A1 | Copy R to register A1 in XALU |
COPYFROM /4 | Place A0 AND A1 (bitwise) in R |
Instruction | Meaning |
---|---|
COPYFROM /RAND | Get a pseudo-random number and place it in R |
Instruction | Meaning |
---|---|
COPYTO /RAND | Use R as new seed for RAND |
Instruction | Meaning |
---|---|
COPYTO /LEDS | Power on/off the leds according to the 8 bits of R |
I have added a new instruction, WAIT: It takes one operand N, and will pause the execution for N x 50ms.
Instruction | Meaning |
---|---|
WAIT n | Pause the execution for n x 50ms |
The purpose of the hrmasm
assembler is to translates an HRM program (the assembly language) to the corresponding machine code so it can then be loaded into the Program ROM (PROG) and drive the CPU accordingly.
The assembler resides in /hrmasm
folder.
usage: hrmasm [-h] [-s SOURCE] [-o OUTPUT] [-p PRETTY] [-b BIN] [-l] [-d]
[-r RAM]
optional arguments:
-h, --help show this help message and exit
-s SOURCE, --source SOURCE
source file
-o OUTPUT, --output OUTPUT
output rom file (for FPGA)
-p PRETTY, --pretty PRETTY
output pretty printed file
-b BIN, --bin BIN, --binary BIN
output in binary format file
-l, --logisim binary rom/ram file in logisim format
-d, --debug print debug messages
-r RAM, --ram RAM output initial ram file (for FPGA)
If you provide a source file using the -s
flag, you can generate the corresponding machine code in any of these formats:
-o
flag). It's an ascii file, with each byte written in hexadecimal, separated by spaces. Padded to 256 bytes. If the -l
flag is specified, a header is added so the output file is compatible with Logisim Rom/Ram format.-b
flag): raw bytes written in binary format, padded to 256 bytes.Notes:
-r
flag can be used to generate a 256 ram file (filled with 0x00). If the -l
flag is also specified, a header is added so the output file is compatible with Logisim Rom/Ram format.Todo
The HRM CPU architecture is loosely inspired from MIPS architecture. This CPU is a multi-cycle CPU with a Harvard architecture (program is held in a different memory as general memory).
The following internal Architecture simplified block diagram shows all the CPU components, the Data Path and Control Path (in red dashed line):
This is the corresponding RTL Block Diagram generated by Yosys from the Verilog HDL code I have written:
The sections below detail each module individually.
The top module shows all the inner modules, the Data Path and Control Path:
TODO:
The Control Unit is a Finite State Machine. It takes as input the instruction, and some external signals, and generate control signals that will orchestrate the data flow along the data path.
The following chart shows all the steps (clock-cycles) and control signals involved in each instruction:
Below is the corresponding FSM:
Note:
I have added a debug mode (which can be enabled by asserting the cpu_debug signal). When in debug mode, the FSM will pause right before loading the next instruction into the Instruction Register (IR). It will then resume execution when the user press the "nxtInstr" button. This allows the user to run the program in an Instruction by Instruction fashion, and inspect the state of all the components after an instruction has run, and before we run the next.
The CPU have a Hold mode which can be triggered by asserting the cpu_hold signal. This will gate the clock input of the FSM, so the FSM (Control Unit) will be paused ("on hold"). All the other components of the CPU (fifos, memory, registers) will still receive the clock signal, allowing to dump their values for example to a VGA screen.
We load the Inbox with some elements. The first element of the inbox is expected to be the length of the inbox (that is the number of elements).
In an initial design, the length of the inbox was fixed (see the 04 at the input of the comparator?).
Then I designed a small FSM inside the Inbox module that reads the first element, and sets the length of the queue. It then position the cursor on the actual first element of the Inbox, ready for the program to consume it.
This is the resulting design:
The INBOX FSM is very simple. (for some reason, I was unable to create it in Logisim with 2-bit states encoding, that's probaby a bug. That's why it has 3 bit state encoding.)
Notes:
[Update] The Verilog implementation is based on a FIFO queue, and doesn't require anymore to indicate the number of elements as first element.
NOTE: the Logisim model doesn't support Memory Mapped IO.
In place of the "ram" module that was in the MEMORY module, we now have a memory wrapper that will handle the IO Memory Mapping:
The ALU can perform 6 different operations selectable via aluCtl[2:0]:
aluCtl[1:0] | Operation | Output |
---|---|---|
00 | R + M | aluOut |
01 | R - M | aluOut |
10 | M + 1 | aluOut |
11 | M - 1 | aluOut |
aluCtl[2] | Operation | Output |
---|---|---|
0 | R = 0 ? | flag |
1 | R < 0 ? | flag |
This is a simple example of the game, level 4: in this level, the worker has to take each pair of elements from Inbox, and put them on the Outbox in reverse order.
First let see the level in the game:
Now, we'll load the same program in our PROG memory, load the INBOX, clear the OUTBOX, and run the simulation in Logisim.
Program:
init:
00: 00 ; INBOX
01: 30 2 ; COPYTO 2
03: 00 ; INBOX
04: 10 ; OUTBOX
05: 20 2 ; COPYFROM 2
07: 10 ; OUTBOX
08: 80 00 ; JUMP init
(This is the output of my Assembler)
The corresponding Logisim memory dump (machine language) is:
v2.0 raw
00 30 2 00 10 20 2 10 80 00
We load the PROG in Logisim:
Inbox:
The first element of the INBOX memory is the length (number of elements) of the INBOX.
INBOX |
---|
0x06 |
0x03 |
0x09 |
0x5a |
0x48 |
0x02 |
0x07 |
In Logisim that is:
v2.0 raw
06 03 09 5a 48 02 07
We load the INBOX in Logisim:
We clear the OUTBOX:
And we run the simulation:
Once the CPU halts (after trying to run INBOX instruction on an empty INBOX), we can see the resulting OUTBOX memory:
Indeed, we can verify that the elements have been inverted two by two:
OUTBOX |
---|
0x09 |
0x03 |
0x48 |
0x5a |
0x07 |
0x02 |
This level is more complex. In level 32 there are 14 letters on the tiles, plus a 0. For each letters that comes into the Inbox, you have to compute how many tiles have the same letter, and send the total count to the Outbox.
This is how I did it in the real game:
Now let see how my HRM CPU behaves with the same program. First let's have a look at the program itself:
Here's my solution for Level 32. It involves direct (COPYFROM 14
) and indirect adressing mode (COPYFROM [19]
).
init:
00: 20 0e ; COPYFROM 14
02: 30 13 ; COPYTO 19
04: 30 10 ; COPYTO 16
06: 00 00 ; INBOX
07: 30 0f ; COPYTO 15
nexttile:
09: 28 13 ; COPYFROM [19]
0b: 90 19 ; JUMPZ outputcount
0d: 50 0f ; SUB 15
0f: 90 15 ; JUMPZ inccount
inctileaddr:
11: 60 13 ; BUMP+ 19
13: 80 09 ; JUMP nexttile
inccount:
15: 60 10 ; BUMP+ 16
17: 80 11 ; JUMP inctileaddr
outputcount:
19: 20 10 ; COPYFROM 16
1b: 10 00 ; OUTBOX
1c: 80 00 ; JUMP init
(This is the output of my Assembler)
The corresponding Logisim memory dump (machine languag, ready for loading into Logisim) is:
v2.0 raw
20 0e 30 13 30 10 00 30 0f 28 13 90 19 50 0f 90 15 60 13 80 09 60 10 80 11 20 10 10 80 00
Below we can see it is loaded into the program memory (PROG) of the CPU:
Now let's see the Inbox:
We'll load 5 elements: 1
, 2
, 5
, 3
and 4
into the INBOX. As we have to load first the number of elements, it is in total 6 items:
INBOX |
---|
0x05 |
0x01 |
0x02 |
0x05 |
0x03 |
0x04 |
In Logisim format that is:
v2.0 raw
05 01 02 05 03 04
We load the INBOX in Logisim:
In this level, we also have to pre-load the tiles in MEMORY. Here's the file:
v2.0 raw
02 01 04 02 03 04 01 02 01 04 03 02 01 02 00
Let's pause and count mentally how many of each item we have in the Tiles:
Item | Count |
---|---|
0x01 | 4 |
0x02 | 5 |
0x03 | 2 |
0x04 | 3 |
0x05 | 0 |
(That is what we expect to get in the OUTBOX)
Before running the program, let's clear the OUTBOX:
And finally we run the program:
The program will finish when the last item in the inbox is processed. Let's see the result we get in OUTBOX:
OUTBOX |
---|
0x05 |
0x04 |
0x00 |
0x02 |
0x03 |
Indeed, we can verify that this is the total count of each item (from the INBOX) in the tiles: 4 x 0x01, 5 x 0x02, 0 x 0x05, 2 x 0x03 and 3 x 0x04.
So it works!!!
[TODO]
From verilog/test
Run all tests:
$ make -s
BUMP+: Success, all tests passed
Echo: Test [test01] OK
Echo: Success, all tests passed
Year-01: Success, all tests passed
Year-03: Success, all tests passed
Year-04: Success, all tests passed
Year-32: Success, all tests passed
Run all tests of 1 level:
$ cd Year-04
$ make -s -f ../tester.mk
Year-04: Test [test02] OK
Year-04: Test [test01] OK
Year-04: Success, all tests passed
Run only 1 test of a particular level
$ cd Year-04
$ make -s -f ../tester.mk test02.check
Year-04: Test [test02] OK
Inspect a particular tests and traces: for that we need to run the test manually, so it will generate the trace for Gtkwave:
$ cd Year-32-NOP
$ make -f ../tester.mk clean
$ make -f ../tester.mk test01.test.out
In addition to test01.test_out (output of the simulation), this will generate the test01.lxt (interLaced eXtensible Trace file), suitable for Gtkwave inspection:
$ gtkwave test01.lxt
Clean all test files
$ make -s clean
Some levels have a test generator, so it's easy to generate new random tests (random input and the corresponding expected output). Inside the gen_test.sh
script you can see information about size of input, number of tests to run.
Generally, each test will feature:
Check in verilog/test/*/
for the gen_test.sh
script. Simply run the script in the corresponding level test folder.
Some tests also have a gen_prog.sh
script that allows to generate new random programs (usually it randomizes the memory addresses used in the program).
The top modules is the one that will connect the IO pins, the UART-RX to the CPU's Inbox, the CPU's Outbox to the UART-TX. I have also added a small controller that to only pop data out of the Outbox when it's not empty AND UART-TX is not busy.
From verilog
directory:
make LEVEL=Echo upload
From a clean folder, it will generate the bitstream and program it to the FPGA connected via USB.
The Makefile offers several handy targets to do different actions, per module:
If no module is specified with MODULE=<module>
, it will default to MODULE=top
.
Target | What it does | Comments |
---|---|---|
bin | Generates bitstream | Makes sense for top module |
upload | Upload bitstream to FPGA | Makes sense for top module |
svg | Generates a netlistsvg output in asset/ folder | |
dot | Generates a GraphViz DOT output in asset/ folder | |
sim | Runs a testbench simulation of a specific module, generates Variables dumps and open Gtkwave to inspect the waveform | Use with MODULE=<module> . Testbench must be called |
Additionally:
BOARD=<board>
, it will default to MODULE=alhambra
(board must be defined first in Board.mk)LEVEL=<level>
. Level files must exist in /test/. See examples.[TODO]: add more detail
make PROGRAM=test/Year-32/program ROMFILE=test/Year-32/ram upload
I have implemented a mechanism to run the tests against the FPGA.
To run the tests, from the verilog/test
directory:
make BOARD=alhambra hwtest
It will synthesize the bitstream for each test directory under verilog/test
, and then for each test inside it, it will program the FPGA, send the input (testXX.in) and check that the generated output is the same as the expected output (testXX.out).
NOTE:
This GUI sub-project is about showing the internal state of all the components of the HRMCPU.
The GUI is made in QT, and designed using QT Creator. Internally, it relies on the Verilator model which is directly derived from the HRMCPU Verilog design.
In other words:
Please note that while the HRMCPU project is about creating a synthesizable CPU, this GUI doesn't interact with the real hardware (synthesized in FPGA) but with the verilated Verilog design (which runs in software).
I made it for (my own) recreational purpose, but it could serve educational purpose, or as a base to create other GUIs for other verilator models (CPUs or anything else).
The UI layout is self explanatory: it shows the main elements of the HRMCPU and their internal states in real time.
See this video for a demo.
These are some of the features the GUI brings at the moment:
TODO:
At the moment, the GUI can only be built on Linux.
$ cd gui
$ make
Make will make the Verilator model, and the QT gui and link both, to generate the hrmcpu
binary in gui/.
From gui/ folder, run it with no argument:
$ ./hrmcpu
Or you can also rebuild and run in one make command:
$ make run
Tests: cd /verilog/, make test
Latest Travis CI build status: (click to get all details)
[TODO] Document this part
There's a lot of effort put into progressively crafting the Makefiles in this project in order to acomplish several features:
verilog/Makefile
features:
verilog/test/Makefile
:
root's Makefile
features:
I have re-used some files from external sources: