I Designed A CPU (And So Can You)

okay I want to make sure that this is it's doing the wer microphone so I'm is it that one or is it a did you know that you can just come up with your own CPU instruction set and then implement it it's totally legal and the government can't stop you in August of 2023 just before I started my most recent job I got really into Minecraft Redstone computers I won't explain all the ins and outs of how cool Minecraft red Stone computers are but my biggest takeaway from that period was how easy it was to just design a CPU you don't even have to follow any of the big complicated standards that most CPUs use nowadays you can just come up with your own set of assembly instructions by picking and choosing arithmetic and memory operations assign them some unique op codes and then design the CPU it's just that simple my design which is named Gibb CPU no relation is an 8bit Von Newman CPU with an 8bit address bus here are a few notes about this interesting architecture One 8 Bits means that the CPU can only take in eight bits of instruction at a time or one bite two Von Newman architecture means that the data is stored alongside the program instructions this is counter to Harvard architecture which has separate buses for data and instructions number three 8bit address bus means that a single address in memory is 8 Bits wide meaning we can only fit 256 bytes worth of program instructions and data within a single program not only that but each assembly instruction may contain more than one bite which means we have less than 256 instructions in order to write a single program I had to write a lot of testing programs in order to make sure each instruction was working correctly but my goal from the very beginning was to write Conway's Game of Life as the proof of concept in assembly in under 256 lines of bite Cod it sounds tough but let's give it a [Music] shot this is the first iteration of my instruction set I didn't want to use up all the available op codes right away I wasn't sure what would be needed later down the line this gave me a great starting block with plenty of room to grow without getting too deep into the weeds let me explain how each instruction is broken down the first four bits of an instruction are the most important they describe the function itself and is binary zero add is binary 3 so on and so forth the last four bits of an instruction describe which registers are being used for that operation this is the fun thing about assembly there's something in between a function and a variable called a register there are four General use registers numbered 0 to 3 which can be connected to the operation registers A and B and the result of the operation is always placed back into register B the second to last two bits describe which register is register a and the last two bits describe which is register B during initial planning I thought I could get away with only using two registers one and two register 0 would always read back zero because we would always need a zero and register 3 would be the output register this didn't end up being the case because we needed those other registers for data I'll explain this more later on these instructions are broken up into two groups arithmatic operations and memory operations arithmetic operations are easy to compute just some math between values already in the registers and only take up one bite of program memory memory operations are more complicated and more expensive taking up two bytes of memory after each memory operation is another bite which describes the location of a variable in the program memory I call this next Val now let's see what a program looks like in this program we clear registers 1 and two by anding them with register zero load register one with variable one load register 2 with variable two subtract register two from register 1 place the result in register 2 write register 2 down in variable one and jump to the end of the the program if register 2 is zero otherwise jump back to the top of the program this program should only Loop once before it halts eagle-eyed viewers might notice that there are two types of variables here there are dollar signs and there are hashtags dollar signs represent data values and hashtags represent memory locations initially I planned on jumping straight into an fpga implementation so I lay out all the module schematics here we can see the register bank which stores the four registers the path Setter which connects lines A and B to the corresponding register lines the arithmatic logic unit which performs the arithmatic operations the program counter which dictates where we are in the program The Ram which contains the program and all its variables and the memory control unit which takes in data from the RAM and decides if it's command or data then the corresponding signals to the rest of the CPU due to some timing issues I decided to move away from hardware implementations for the time being instead I wrote an emulator in C that would ideally replicate the processes that the CPU would perform the emulator itself is the weirdest thing I've ever programmed in C because it's programmed in the style of a hardware descriptive language each module I've mentioned before takes the form of a function but none of the functions take in or return values every variable representing a register or a data set line is a global that can be accessed anywhere the entire program is Laden with switch statements representing the many multiplexers that would be present in a hardware implementation of this [Music] CPU when building the emulator I was using binary programs manually written in Excel as shown in chapter 3 Once I Was satisfied that the emulator was executing the programs correctly I wanted to automate the process of creating these programs so I formalized the Syntax for each assembly instruction and started work on an assembler this additional layer would convert a text file containing assembly into a text file containing the correct binary which would save me hours of manually writing binary in Excel now how does it work okay editor note I am cutting this segment for a few reasons explaining exactly how the assembler Works would actually be getting way too deep into the weeds and I am trying to keep this video as top level as possible and I have been trying to make animations for this section in manm but it turns out that tables in manm are very hard to work with which would make this video production go way over schedule if you are interested in checking out the assembler or any of the programs that I've mentioned the full release GitHub of the entire project is linked in the description below after some hard verification with a few more handwritten programs the assembler was complete I thought about making a compiler on top top of all this converting an even higher custom language into assembly I decided against this when I realized just how big the generated assembly programs would be far bigger than our 256 byte limit compilers are great for turning highlevel language code into assembly but they inevitably create inefficient mass produced assembly I had to be as efficient as possible if I was going to get Conway's Game of Life implemented in the available memory which meant assembly only from here on out from here I had to make a few more changes to the CPU and the instruction set to make Conway's Game of Life possible we're just going to rush through them I needed a way of programmatically changing the values in location variables so the load and write commands now support data variables and location variables registers 0 and three are now used as data registers we always knew this day would come the subtract operation has to switch its decrement and decrement registers before if you had number and you wanted to subtract one from it multiple times in a row which happens a lot in Conway's Game of Life the register holding the one was being overwritten with the result meaning you had to load back in the one every time by switching this so that the one stays behind we can prevent a lot of load operations and save a lot of memory lastly I added two more operations load L and right L these work the same as load and write but instead of reading or writing into a register using a variable which creates a costly next Val it uses an address stored in another register once again this saves a ton of space in certain scenarios we now have all the architecture in place that lets us run Conway's Game of Life all I have to do now is write [Music] it so how are we going to do this for those unaware Conway's Game of Life is a cellular automa game it consists of a grid with each cell being alive or dead after each time step each cell on the grid changes its state according to the following rules one living cells with less than two living neighbors dies two living cells with exactly two or three living neighbors survives three living cells with more than three neighbors dies four dead cells with three live Neighbors comes to life this is a classic computer science program and it even turns out to be Turing complete itself since I got rid of our output register the grid will just have to be a range of data variables for the sake of space let's call it a 5x5 grid which takes up 25 data variables if each cell is numbered 0 to 24 then each neighbor for any cell n can be described as follows n + -1 n + - 4 n + - 5 and n + - 6 technically this is only true for the middle cells each cell around the edges will be checking up to six memory addresses out of bounds in either direction unfortunately this means we need to add six buffer variables on either end of the grid costing us 12 more bytes of memory this does hurt me to implement but unless I can fit wraparound functionality in less than 12 lines this is the most memory efficient method during the first attempt I just started writing the program without much of a plan resulting in an unoptimized mess that was 304 bytes long for the second attempt I combined two existing Loops into one large loop eliminating many variables along with it this would save over 70 bytes of memory bringing the size of V2 to 230 bytes unfortunately this version was broken the living cells were just disappearing it was here that I realized just how difficult debugging and assembling would be I have no debugger I have to hand calculate the program in order to figure out what the register value should be at any given time I took a break from this project for a while coming back to it with fresh eyes I realized that I hadn't formalized what a for Loop would or should look like in assembly I hadn't even fully broken down what the top level State machine would be for the program or how each state would operate I took the time to write out the top level State machine even adding functionality for a finite number of time steps before the program halt itself then I broke down state machines for each of those States refining them when I saw inefficiencies it was here that I realized many of the bugs that plagued V2 the reason the living cells were disappearing was due to a bug in my neighbor counting function the neighbor count was unprotected from overflow to combat this I wrote a more meticulous counting method it was costly but necessary then I identified the different types of Loops that would be used for each step I reasoned out how they would be nested and chained together and after identifying all the loop types I wrote out formalized examples for each using this new far cleaner programming standard I built a V3 from the ground up being very careful to Nest each Loop correctly and paying close attention to which values were in each register at any given time as I wrote I found even more ways to optimize the state machines and kept track of any redundant lines that could be removed if I went over the memory limit when fully written V3 stood at a Hardy 229 bytes long I tested its main execution with a known repeating pattern the blinker yes finally some progress after so long now let's move on to the most famous pattern the glider ew this might just be the outer edge making the neighbor math weird living cells on the edges are going to think all sorts of unconnected cells are its neighbors I don't see a way of the glider showing its full repeating cycle without touching the edges I think I have to modify the code to make it a 6x6 grid that way we can see the full life cycle of the glider and besides I won't be satisfied with the blinker or Worse the block like come on okay what would it take to convert the grid to 6x6 turns out not a lot the program is already very modular and variable based using countdowns and jump Z for conditional jumping all I have to do is increase the size of the gitter Rays increase the countdowns to match update all the location variables and change the variable containing integer 5 to six so that the neighbor counting will stay consistent with the new grid size with these changes V4 is born it is 250 bytes long the closest we have ever been to the Limit without going over I am prepared to have my heart broken again let's try this one more time with the glider man what is happening memory reading and writing looks fine and it appears to be following some kind of rule set just not Conway's Game of Life let's look at the second state there's something very odd about this the cell in the top left just comes out of nowhere and the upper middle of the glider itself is alive when it should be dead why would that cell come to life wait hold on let me check something oh no it's bringing cells to life with three or more living neighbors H I accidentally optimized out some of the core functionality okay okay this is a quick change it's at the very end of some State logic which makes the fix very costly the program is now exactly 256 bytes long this is the limit here we go for all the marbles [Music] [Applause] [Music] that was a very long and very arduous project overall I estimate that this project took about 130 hours done in short bursts over the course of about 9 months that includes all the bug fixing all of the discarded Hardware design and all of the grueling line by line binary writing and verifying that I left out of this video so what did I learn what could I have done better for one I could have just made the memory bus 16 bits wide which would have given me 65,536 36 bytes of memory instead of the measley 256 the project has been fun and that limitation did force me to get very creative but my God God it was so close especially near the end during planning I actually thought that I couldn't because next Val could only be as big as an OP code I did some research after the fact and it turns out you could have just added another next vow and it would have been 16 bits so I could have trusted my tools more uh the assembler near the very end was fine it was just fine but I kept not trusting it which meant I kept handwriting all of the binary in the Excel sheets instead of just trusting that my tool was giving me the correct binary and it was in fact it was giving me better binary than I was writing it kept catching mistakes that I was making but I still didn't trust it yeah and I probably should have done all of the state machine planning before I started V1 I mean who knew that I wouldn't be able to do it first try off the top of my head all of Conway's Game of Life in assembly you know I thought I was him for my next project I'm kind of torn in between making a Gib CPU 16 and fully fleshing it out adding a ton of different features like a stack or dedicated peripherals for output so I can maybe make a screen it's either that or I try to implement uh Gib CPU 8 on an fpga that way I could potentially go and have it fabricated and you know have an integrated chip which is completely by my own design that would be really cool I have no idea how to do that but I can definitely go and figure that out after that who knows 32 bits make it fully risk five compliant make it run Doom that would be really cool everything is possible anyone can do it you can do it you just got to build [Music] [Music]

Channel: Owen Gibson

Views: 3,020

Keywords:

Id: 7w8IeXKstJY

Length: 19min 14sec (1154 seconds)

Published: Sun Jun 16 2024