I am trying to build the most simple CPU possible. And doing it on bread boards. There is a popular movement, one of the biggest protagonists of that being a certain Ben Eater, who is a good teacher, and has a YouTube channel.
UPDATE: I realize that my original question was meandering and lengthy and not really targeted well. Also that there is a question if it should be in scope of the Retrocomputing stack exchange. The question had received some very interesting variety of answers, when it was shut down, but then, based on popular interest, it was re-opened again.
First to get this out of the way: this is clearly in scope of the RC stack exchange because 4 bit computing is as retro as it gets. While my angle is to create my own computer using TTL chips -- which too is as retro as it gets -- one may say hat it's not about any one commercial retro computers. While it isn't about any one, it is in a way about all of them. I am looking at 6502 block diagrams, at PDP-8 ISA and schematics, as the 4004 and TMS-1000.
What I am finding is the understanding why the designers of old had built the systems the way they did. And I more and more reach a hypothesis that what the designers of old did was not by accident but because they pretty much mapped the space of what is possible. That's why I keep asking if there isn't some fundamental law here?
I have digested many of the answers, and continued thinking through and wiring up the design of a 4 bit CPU, I can try to target my question better. But I won't just change it as I do not want to invalidate the excellent answers that have already been given.
The issue with many of the answers is this: they are theoretical and way out of the box. However, they raise the question: why didn't the designers of old choose these approaches? That isn't to say that none of the suggested answers are something nobody had ever done successfully, but the more esoteric ideas just didn't make it in practice, and this is probably for a reason.
So, for example, the Turing machine was known for a very long time, when tape was en vogue, yet nobody had marketed a Turing machine. Because it is just not practically useful! Likewise, this Brainfuck language is cool but it actually isn't practical.
So let me be more clear as what we're trying to do here:
- von Neumann machine
- a "traditional" machine language
- imperative programming, not some other FSA or event transducer approach
I find it really interesting to think a completely different approach but it's not in scope for my question here. One commenter had pointed to a fascinating forum thread at "anycpu", but the specific example is simply an FSA where each state plus new event leads to another state. It's interesting but out of scope and doing the trade-off on the side of memory, since now your instruction step has to carry the address of the next instruction step in it, every instruction becomes a jump, that's cool, but not really efficient on the memory.
Sure, I can see that this works nicely for a calculator program, as I can write a YACC parser to essentially implement the standard calculator in the state automaton: reactive state -> event (key press) -> action+next state model. I can put that in hardware, yet, so could the designers of old. And still they ended up with a traditional von Neumann machine to program their calculator with.
It's probably not because they didn't know any better. I guess that's my point.
I will add some updates below too to sharpen more what I have found while further pulling my hair out trying to get something off the ground.
Anyway, I want to build something simpler. Less wiring. So I thought I scale the word width down to 4 bit 74LS173 and the '283 adder and the legendary ALU '181, they are all 4-bit wide. I understand that the VAX 11/780 was using 8 of those 74S181 chips for the 32 bit ALU.
I want everything as simple as possible but not simpler. And I am looking at the legendary TMS-1000 and Intel 4004 architectures to see how they did this, but it seems to me that then should also be simplified. By trying to simplify it all I am hitting my head against a wall and I wonder if there isn't some kind of principle law of computer architecture that blocks my way no matter what I do?
Since I want everything as simple as possible:
- minimum number of registers
- minimum word width
- minimum number of wires and connections
- minimum number of chips
Therefore I want the data path to be as simple as possible, the smallest number of busses. So I decided to use the PDP-8 style accumulator machine, only simpler. Only one register the accummulator AC. No "B" register. You have a loop from AC register into ALU and sourcing the other side from the one single bus. Then the result is clocked right back into the AC register. A single register. Minimize everything. The ALU out is a tiny little "bus" which does nothing other than feed back into the AC.
Now the memory address is a major squeeze, it has to be wider, has to at least use 2 word addresses (not unlike most 8 bit CPUs use 16 bit addresses). Otherwise you'd just have 16 words of memory. And if your words are 4-bit wide then 16 words is really uselessly little.
You might argue "but a 4 bit computer is already useless, why worry if you have only 16 memory locations?" Not so fast! A CPU is not useless if it can turn all longer word operations into sequential executions. And the TMS 1000 and Intel 4004 has one principle standard application: to build a calculator. You may say I can do a Turing machine with a single bit perhaps, but I would say the minimal CPU is one on which you can at least program a simple calculator that would allow an arbitrary-digit number addition and subtraction (and then be programmable to do multiplication). Floating point or big decimal doesn't matter. It's all in software.
And to me it looks like there is an "as simple as possible but not simpler" threshold.
For example, if I have to use BCD (doesn't matter, let's use full hex) I will have to process the addition of two user entered numbers with a loop. Everything needs to be looped. So now I need to have some way to make loops. How do you make a loop with a single accumulator? You have your result of the addition, now how do you decide where to store it? How do you select the next digit for your addition?
Many of these simple CPU designs I have seen discussed use a Memory Address Register (MAR). This is an implicit register that is only available to microcode, you can't actually manipulate it like a register. But then I look at the Instruction Pointer (IP) and that you do address with the usual instructions like JMP.
So, I figured why not make that memory address register explicit and call it a "Data Pointer" (DP). Now instead of an "store accumulator to absolute address" x I would have two instructions: "load data pointer" (LDP) with immediate value x and then "store accumulator at data pointer". This works for absolute addresses, but not for the loops that are required to do anything useful with a 4 bit machine!
So, I thought let's use a counter, even and up/down counter for this data pointer register. I use a pre-settable up-counter (74LS161) already for the instruction pointer.
So if I found a changing number of values in my accumulator, then I could make a loop like this for a routine that adds a fixed single digit in AC to a variable length number in memory and does that in place:
LDP lsd ; load data pointer (DP) from immediate value lst (the least significant digit) BC loop ; branch on carry to loop, a no-op, with a side effect of clear carry loop: ADC ; add with carry the current value in AC STADZ ; store AC at current DP and decrement DP and zero out the AC BZ end ; branch on zero JMP loop ; jump to loop end: HLT ; end
UPDATE: one commented pointed out that this "STADZ" is a weird composite instruction, but it's not unheard of at all, even the PDP-8 had such combined instructions, and it was easy for the PDP-8 since it had 12 bit wide instructions. With 4 bit op codes, we need to squeeze all features in 16 op codes, maybe have one extension code which pulls a second op-code.
This could work if you imagine the numbers stored most significant digit first, no more than 16 digits, and somehow we would know the least significant digit. But there are obvious limitations with this: I cannot set an end of a loop, I can only count backwards from a starting value to zero.
Even that could work, but what if I have a more realistic scenario where I add two numbers from least significant digit onward and store the result in a third location? Maybe I could invent a second data pointer, EP, then I could at least do a copy operation from DP to EP. But if I wanted to add two numbers and store them at a result I would need 3 data pointers, DP, EP, and FP.
But I still can't compare these index registers for an end value, I have to count down to zero or up to overflow only.
You see where I'm getting at? There seems to be a minimum complexity that cannot be simpler!
The TMS-1000 used something like my DP, called it Y register, and then an X register as a high address word. And then you have a complicated data path:
We can still see the AC -> ALU -> AC loop here, but there is also a fork to that Y register. So at a minimum now I would need another register on the ALU output bus. This seems like a hard "cannot do simpler" rule?
The Intel 4004 is more complicated, it has a register at the other ALU input because the ALU result goes back on the bus.
And it has like a scratch pad register file, way more than the simplest possible machine.
Is there any hard theoretical limit that someone has established?
UPDATE: Don't get hung up on my ramblings. Look at the TMS-1000, isn't it odd that its instruction size is 8 bit wide? Why is that in a 4 bit architecture? Not because PROMS were standard 8 bit wide. I myself came up with a very easy way of using a 28C16 2 kByte EEPROM to be a 4 kWord simply by hooking the A0 address line to a 74LS257 quad 2-to-1 line selector chip, with three-state output.
The reason why they ended up using the 8-bits straight is that it's a royal pain and useless to squeeze an insufficient set of 4-bit instructions and their immediate operands over the data bus if you have only 4 bits. You are working so constrained that you end up with some basic instructions like a subroutine call requiring a dozen micro-instructions just to squeeze addresses of the stack pointer to the memory and then the instruction pointer through the bus.
It falls apart on every level. Everything becomes such a battle of the trade-offs. Compare that with a 32 bit wide modern RISC ISA, it's so much simpler because you have broken through these initial bottlenecks of bus width, word width, address range, to something that actually starts to work.
Notice, when I increase word size it immediately relaxes the tense situation. Suddenly your instruction words get longer with 8 bit words you can have a large number of instructions already, not just 16. That way you can have more complex addressing modes. Each word if data also has more information already. You have more addresses, at least 256 words addressable with on word.
Next step up would be the PDP-8 12 bit where you can begin having single-word instructions. You could not possibly do single-word instructions in 4-bit. You could fudge in 8 bit, but really only practically start in 12 bit.
Now if you do 16 bit consistent word size you can almost start with a RISC like instruction set. You can put operation, source registers and destination register all in the same word (if you have only 8 registers you can do 7 bit op code, and 3 bit address each for operand 1, 2 and destination.
When you reach 32 bit you can do full RISC-V architecture. Everything is relaxed then.
You see what I mean? I think there is something of a theoretical threshold, a minimum word size at which you just cannot even do a Turing complete machine. Like for Turing you need to at least have a forward, backward, and a single conditional branch instruction, so you probably have to have at least a 2 bit word, don't you?
This would sound like something computer scientists would have figured out: what is the absolute simplest functional instruction set architecture?
UPDATE: I may not have done a good job at updating and explaining and targeting my question. The format doesn't allow for that. But I do think that if you challenge our esoteric solutions that may seem simpler, and consider if they are practical, you may find that they are not practical. And that instead these trade-off battles over word size, bus lines, number of busses, memory width vs. data width, number of registers vs. the cost of addressing registers in small opcodes, these are real struggles, that have no perfect solution, but also some sort of optimal answer which we can glean from the old architectures and finding out where they worked well and where they didn't. Where they didn't scale. I think there is a reason that we ended up with RISC-V today.