7

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:

enter image description here

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.

enter image description here

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.


  • 4
    There is no unqualified "simple". You can design your CPU around 74xxx chips, and it will look different than a "simple" architecture designed for a silicon wafer. (And it will have more than one register, because there are "register file" 74xxx chips). The "simplest" well-known computing device in theoretical computer science is a Turing Machine. But this use tape storage, which is not easy to implement with 74xxx chips... – dirkt Jun 23 at 4:10
  • @dirkt, thanks for pointing out the register file again. I have it here and I had another look, it has a read port and a write port, so indeed, it can be very useful to achieve something quite useful. Although it will require more instructions to address the registers, except ... (continued in next comment). One problem with that register file is it needs a negated edge detection to clock in data, ... but that can be done. – Gunther Schadow Jun 23 at 5:04
  • But the register file could be used for both an address pointer and a data value where the value would be stored into memory at that address by splitting the cycle into two phases and multiplexing the bus, latching the memory address and then sending the data to go into memory at that address. with a split cycle, the ALU can be used for both address and data computation, this might be useful. That way it would not require more wires. – Gunther Schadow Jun 23 at 5:04
  • 2
    A one-bit word with a single instruction can be a universal computer. esolangs.org/wiki/BitBitJump – RETRAC Jun 23 at 6:16
  • 3
    "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" not really, as 4 bit CPUs are still in use and available as new. They never vanished. Also "The format doesn't allow for that." That's (beside the missing retro question) the main part why this question not fits. you're presenting a lt of musings but no clear question, but rather ask for a dialog. All of that burdened by many implied assumptions that are not really stated. Discussions in questions should not happen – Raffzahn Jul 3 at 5:37
11

I would tend to favour "conceptual simplicity" rather than trying to strictly minimise any physical parameter. Observe that some low-cost computers managed to get away with a 1-bit ALU while supporting reasonably wide data words, eg. the PDP-8/S and the LGP-30. They did this using a bit-serial architecture which was largely invisible to the programmer, except in the resulting performance of the machine (much slower than a parallel architecture). So processing a single machine word took several machine cycles.

This was a natural fit for the LGP-30's drum memory, less so for the PDP's core memory. Historically, memory was the most complex and expensive part of a computer, so a wise designer started with the memory and built the CPU around it. Observe that the PDP-8/S cost about a third of its faster cousins, but had only a tenth of the performance, due to the poor match between its cost-minimised CPU and its standard core memory module. Observe also that the LGP-30 could perform multiplication and division with single instructions, within a single rotation of the drum, despite its relative simplicity.

When your ALU and data accumulator are as small as 4 bits, you will need to use multiple such words to be able to address a usefully large memory. Usually an instruction word needs to be effectively 12 bits wide (including operands) to be useful too. But this is not historically unusual; observe that the humble 6502, a resolutely 8-bit machine, has 16-bit addresses and instructions that can be 1-3 bytes long; always an 8-bit opcode, sometimes followed by an operand. The larger and more complex instructions took more memory cycles to process than the smaller and simpler ones.

Now, for conceptual simplicity, consider the following 12-bit Transport Triggered Architecture. Instruction words have no opcode, and only specify two locations to transfer data from and to. The locations are 16 12-bit registers, or the memory addresses pointed to by them, or a set of 16 ports which trigger operations in the ALU or provide results from such an operation.

The 12-bit instruction word is nothing more than a pair of 6-bit specifiers, 4 of these bits indicating a register, and the remaining two choosing the register directly, the memory addressed by the register, the latter with post-increment of the register, or the port behind the register.

One register should be the Program Counter, which gives you an easy way to load immediate operands (source: memory addressed by PC register with post-increment) and to jump to a new location (destination: PC register). Combining the two gives you an effective JMP instruction.

You get to choose what each port does on read or write. Several of the read ports could simply be adds and subtractions of adjacent registers. Another might select between a pair of register values based on a flag internal to the ALU - such as a zero flag, a negative flag, or a carry flag. A write port might let you choose between these possibilities dynamically. This gives you the possibility of a conditional branch.

That is simplicity, yet still with interesting possibilities for experimentation. Have fun!

| improve this answer | |
  • I've been toying with a design using a 64x2 shift register as the primary store. The basic design would be somewhat like a Turing machine, except with the tape always moving to the right and looping. I think it would actually be practical to mimic the behavior of some handheld games using such a system, with a reasonable sized control ROM, if one stored numbers in ternary format (use the bit pattern 11 as an end-of-field marker). – supercat Jun 23 at 15:22
4

You could theoretically create a system with 3-bit words for the Brainfuck programming language. That language is technically Turing-complete, although quite tedious to program. It is a popular language for the Code Golf StackExchange.

A processor for Brainfuck needs the following:

  • Memory to store data. Wikipedia suggests a minimum size of 30,000 bytes, but I see no reason to make it as small as you want.

  • A data pointer with enough bits to index into the data memory.

  • Memory to store code. Make it just large enough to hold your programs. There are only 8 opcodes, so it only needs to be 3 bits wide:

    >     increment the data pointer (to point to the next cell to the right).
    <     decrement the data pointer (to point to the next cell to the left).
    +     increment (increase by one) the byte at the data pointer.
    -     decrement (decrease by one) the byte at the data pointer.
    .     output the byte at the data pointer.
    ,     accept one byte of input, storing its value in the byte at the data pointer.
    [     if the byte at the data pointer is zero, then instead of moving the
          instruction pointer forward to the next command, jump it forward to
          the command after the matching ] command.
    ]     if the byte at the data pointer is nonzero, then instead of moving
          the instruction pointer forward to the next command, jump it back
          to the command after the matching [ command. 
    
  • An instruction pointer with enough bits to index into the code memory.

  • An input and an output device. They are supposed to be ASCII devices, but if you don't care, make them as few bits as you want.

It is not a pleasant system to program (hence the foul name), but it is a minimal system.

| improve this answer | |
  • 3
    Implementing the "find the matching [ or ]" algorithm in hardware is not trivial – user253751 Jun 23 at 11:40
4

Amusingly, I posted about my design for a processor that's as simple as possible while still being useful over on the anycpu forums just this morning...

Summarising: My design uses 14 standard chips (including a 16-bit wide ROM for the instruction data which may need to be replaced with 2x8-bit ones depending on availability). It's a very limited design, but was designed with a specific purpose in mind (running a front panel for an 8-bit system that uses a hex keypad to allow boot code entry) and is capable of that. It's somewhat simpler than your design:

  • No jump instruction - instead, all instructions are implicitly looped infinitely, and different sections are selected using conditional execution
  • Not using a general purpose ALU - a series of AND and XOR gates is used to add either zero or one. The value to add is selected with a mux to be either 0, 1, the carry flag, or a hardwired bit from one of the registers
  • No memory addressing at all (other than the program counter, which is just a standard 4- or 8-bit counter) - all data are stored directly in registers (2x8-bit registers to store an address, 1x8-bit register for entered value to be stored, 4-bit scratchpad register).
  • No instruction decoding: programs are implemented directly in a microcode-like encoding.

Now, this design is not something I claim as the minimal general purpose computer:

  • It isn't actually properly general purpose, as it is impossible to (eg) add two numbers with it. This could be rectified with a few simple additions:
    • Adding an extra set of XOR gates at the input to the ALU would allow negating numbers; a 4-input NOR gate could be used to add a zero flag. Then incrementing until a carry occurs would allow repitition of a given number of operations.
    • More flag bits, and a way to set or clear an arbitrary flag bit, would be necessary for more complex programs.

All in all, I expect making this a true general-purpose machine (ie turing-complete modulo small memory size) could be achieved by adding around 4 standard logic chips.

| improve this answer | |
  • 1
    Re, "no memory addressing at all." I.e., no "external" memory bus. But in a real sense, registers are memory. – Solomon Slow Jun 23 at 12:52
  • 1
    @SolomonSlow - true, but the complexity is reduced massively due to not needing to encode addresses... enable signals for read and write are directly embedded in the instruction bits. – occipita Jun 23 at 13:03
  • I've been toying with the idea of designing a CPU based around a CD4517 2x64 shift register and a couple of 8-bit shift register for I/O, along with a couple of addressable latches for addressing and shift-strobe control, and an 8-bit wide ROM. On each cycle, form a ROM address using two bits from the shift register chain plus the outputs of the addressable latches. Feed two bits back to the shift register, two to A0 of first and second latch, two to A2 and A3 of both latches, and two to the data input of the first and second latch. – supercat Jun 25 at 20:56
3

[preface: This question would need a heave rewrite to really qualify as RC.SE compatible, as so far it may mention some historic architectures, but its core questions are about generic system/CPU design, making it rather a fit for EE.SE]

Showing other examples won't be of much use, as the question is burdened with unnamed assumptions and restrictions - and a mixup of terminology when defining goals

Well, that and a very basic misconception:

Reduced word size does not reduce complexity. It only reduces data path width, thus components acting in parallel (*1). All control logic still needs to be the same. Or better at least the same, as shorter word sizes may mean added overhead for multi word operations.

there ought to be some law here somewhere, is there?

Law(*2): Shorter words do not simplify designs. They only shorten the width of components used.

You see what I mean?

No. 'Cause you missed to specify the requirements you're using, and there seams to be quite a lot you're implying:

(caveat: these are things I figured while reading without finding any explicite declaration - so they might be wrong)

  • Word size equals instruction size
  • Word size equals bus size
  • Instruction size equals data size
  • Data path size is related to system complexity
  • Implied assumption of Von-Neumanisch architecture
  • Single address space
  • Memory external to CPU
  • Means of complexity is never described

These are just the most obvious, many more might hide and need a deeper read. All of them restrict/blur view at design possibilities and many are

Law: Define all constrains first and in full.

This doesn't mean you need to write them down on paper (despite that being helpful) like in 7th grade, but to keep them in mind and reproduce them whenever talking about. But it means you got to sit down first and make clear what are implied assumption.

Law: Don't assume things 'are'.

This point is especially important when trying to create something new. We are all product of our history. There is a ton of implied assumptions about everything. It's very helpful, as it allows us to navigate the world by assuming defaults - like a bit being only 0 or 1 and a byte having 8 bits. Right? No. already this short example shows the mixing of 'natural' (*3) defaults and man made. A bit is either 0 or 1. There is no inbetween in logic (*4). But a byte doesn't have to be 8 bits. It only became to be the most common size nowadays - almost the only one.

Next there is a constant feature creep - again due unclear requirements.

Examples are:

  • Generic ability of dynamic addressing
  • Direct addressing from 'within' the CPU
  • Assumption of certain processes working in parallel
  • Many more...

Law: Don't make a wishlist what would be nice to have. Take what nature (well circuits) give free and plenty and be happy about.

(Hmm, maybe that should be a moral point, then again, laws have to follow moral, shouldn't they?)

When your goal is to create something simple, don't make up a complex instruction set. This is especially visible in your musings about adding and looping, were one featurehunts the next? Doesn't that feels like a thick porridge, swelling in your mouth?

Just look at this instruction:

STADZ     ; store AC at current DP and decrement DP and zero out the AC

Oops? That's quite a complex one. Asking for

  • a memory transaction,
  • regster decrement and
  • a register clear

All in once, in addition two operations on the same item (AC), not really a chip shaver. Instead thinking about bloaty instructions that look nice in a source, the goal must be simple hardware, with a target of none wherever possible.

Why having a pointer register at all? Wouldn't it be more simple to have a pointer in memory, so any operation can be done by the same used for all othere

So there's one more:

Law: Think like a hardware designer cutting chips, not a programmer wanting easy do-what-i-mean type instructions.

Just look at the way Woz' designed the Apple II. Chips can always be replaced by more code.

Verdict:

Law: Don't get lost in details about chips and workings before working out basic details.

It's like in any craft:

  1. Work out what your tools are and how they work.
  2. Work out what your material is and how it behaves.
  3. Work out what you want to do and what the result has to be
  4. Only then apply the tools to your material and complete the task.

While it may look like there are many short cuts, they are all taken at some cost. The reason why an experienced developer may take them is that he knows about the pitfalls and includes that knowledge.



[I said I won't go into details, but I'm a mere mortal Nerd, it's impossible to tell my inner voice, calling for schematics and ideas, to shut up, so lets try to give 'only' a sketch]

What about an instruction set only able to very simple operations, loading, adding and negating a constant or word from memory. There would be a single accumulator register which may as well be tested for zero in a jump like instruction.

Instructions can only access direct memory locations that can be accessed with one word, so 16 if it's 4 bit. So lets make groups of memory cells act as address pointer. Like three of them making a 12 bit address (if it's a 4 bit). Any operation using these pointers will be able to address the full 12 bit address range as these 3 words.

The first group could form a generic memory pointer. So whenever there is a memory access to be made, the address must be build in group 1. Since it's fixed at location 0..2, it can be accessed and manipulated with absolute addresses 0..2. This saves the need for a dedicated pointer register,while at the same time enabling it to be target of any legal operation. That's much more than just increment or decrement.

Since we design the CPU, we can have r/w word access to the memory cells and parallel output of them as address as well - for example by putting these first 16 location on chip. It's hard to imagine a system with less memory, so they are needed anyway.

The second group could add as a jump target. At that point it doesn't matter if the CPU presents memory and program store separate or unified. The content of group 2 gets simply loaded into PC after being loaded and/or manipulated in group 2. Now we can do arbitrary jumps.

On an abstract level this means simply unifying the various registers of a more complex design into a register file that is addressed like memory. Instead of instructions having implied registers, everything would be explicite and symmetric. There could be more groups as well. Like a second memory pointer...

The whole functionally mentioned/desired in the question could be implemented with a sert of different 5-11 instructions - so way within the 16 available in 4 bit opcodes. Of course, the program would be a bit longer. But who cares? The goal is to make a hardwarewise simple CPU.

Of course, adding some hardware could simplify programming a quite a lot. In fact, some additions could as well simplify the instruction set further. Like adding a B register, thus separating memory access from ALU operations. Now the instruction set may go down again, as everything ALU related is now a single instruction, not intervened with other operation. The instruction set becomes kind of a construction set for more complex ones.

ADD mem becomes LoadB with mem + ALU-OP ADD

and so on.

A potential instruction summary could be like:

  1. ALU-OP x
  2. Load A with B
  3. Load B with constant
  4. Load B short (Register File)
  5. Load B via Group0 (Memory Pointer)
  6. Store A short (Register file)
  7. Store A via Group0 (Memory Pointer)
  8. SKIP if A is zero
  9. SKIP if CARRY
  10. LOAD PC with Group1 (Jump)
  11. HALT

#2 can even be omitted if there's an ALU-OP that simply lets B thru, so #3;#1 will replace #2, thus simplifying the circuitry for A, as it now can be loaded from a single source only, the ALU.

Everything past that is pure luxury ... or can be used to improve upon.

Like accessing instruction store with double width, delivering all multi word instructions (#1/3/4/5/6/7) in a single cycle. This does, BTW, not automatic imply a separate store - just that it's as well word accessible and that the lowest bit of the PC is always assumed as zero (i.e. the PC is only 11 bits, 11..1)

Or using more than one memory pointer, thus making #5 and #7 (maybe even #10) having the pointer to be used in the second word - quite simple if the instruction access is 8 bit anyway. In general, going to a 4 bit (nibble) addressable 8 bit memory word would result in not only sped advantage, but the general option to use 8 bit for all instructions, like giving an offet to SKIP

If you wonder about the HALT instruction, beside its usefulness for debugging, it could as well serve as a return instruction for a kind of fixed single level subroutine mechanism. As of now we have 5 unused instructions (#12..16), so why not making them 5 subroutine calls with implied address? (*5)

Any instruction not defined will have the PC being suspended and a 'sub' PC set to the value of the instruction times 256. So for example a instruction of x'F' would lead to an implied subroutine call to address x'F00'. This may come in quite handy to do complex but often needed things like incrementing a memory group. HALT will now as well serve as return long operation if from the 'sup' PC and only stop the CPU when on the 'real' PC.

Then again if we already have the works for two word instructions why not treat all 'unknown' such, having x'F' with operand x'8' jump to x'F80'. Of course now there is only room for 16 instructions (including HALT) per 'extended' opcode, but nothing stops us from spilling over. If x'F8' needs 20 instructions, then there will be no x'F9' (*6).

Now we could add 64 subroutines or well, instructions after all, with a little shifted viewpoint this could be seen as the core for a semi-micro-program system. Semi because it's not really a separated, invisible layer beyond the instruction set, but rather a kind of mechanic to extend it.

Of course, nothing stops us from turning this upside down and have the main PC invoke routines like described. Now we really have a microcoded execution with the microcode being the set of these 12 primitive instructions and the macro instructions being whatever the code says. And with the fun part of microcode being fully loadable. Heck it can even be manipulated from macro code, as it lies within the same address region (*7,*8)

At that point extending (external) memory referrence to 16 or 20 bit might be a good idea.

And now I got to stop as I'm getting close to run upstairs and fire up my soldering iron.


To complete this, take a look at a few examples of minimalist design:

Motorolas 14500 is eventually if the most minimalist processor. It can't get less complex than that: one bit data word and arbitrary instruction word size. PC as well as other glue logic not included.

Intel's 8008 and 8080 are direct implementations of the Datapoint logic, presented with exactly your problem: building a somewhat capable CPU out of as least TTL IC as possible. It's well worth to take a look.

Atmels AVR is not only one of the most successful new architectures, it's also made with a focus on minimalist design. There are no 'visible' registers, but memory, with a register file at the start. Certain memory cells act as pointers (a bit like IBM's 7030 or way later a DEC PDP-8). Programm store is separate and 16 bit wide (while data is 8). And so on.


*1 - Let's skip serial internal structures, as they only bring real advantage when build from single gates/transistors, not complex 74xx devices.

*2 - From Raffzahn's book of ad hoc laws - ought to be extended at any moment ;)

*3 - Yes, one may argue the 0/1 thing is as well man made, but within binary it's undisputable, as not only everything beside doesn't exist, it would also simply blow all logic.

*4 - No, tehre is no inbetween, what you're thinking of are signals which may be weak and mess up results. Logic doesn't care about that, TTL does :)

*5 - If this sounds like the 68k's Line-A, tuned for 4 bit, then you're straight on :))

*6 - Uhhhh... illegal opcodes ... what may they do?

*7 - Not always a good idea :)

*8 - Some mainframes of the 70s had a similar construct - except the microcode storage was protected and hidden even in real mode, Only accessible under certain conditions with dedicated instructions.

| improve this answer | |
  • 1
    "like a PDP" should specify PDP-8? Unless other models had it too? (Not all did, PDP-10 did not.) I think you're thinking of the addresses that auto-increment when you load/store indirect through them? or something else? – davidbak Jun 23 at 17:23
  • I like how you got from your initial "question does not qualify" rant to being fully carried away by your thoughts and excitement. This is reflective of what happened to this entire question, going from being killed by the usual suspects who have nothing better to do than shutting down questions to being re-opened apparently due to popular interest. I never get the zealous urge to shut down topics which are intended to get the mind boggled. – Gunther Schadow Jun 27 at 17:27
  • @GuntherSchadow :)) well, for one that initial cursive paragraph isn't a rant but rather a stating a fact, as I'm still convinced that this question is not fit for RC.SE. The issue is tat a question can be a good and tempting one and still being off-topic for RC.SE. Exactly like this, as the question doesn't ask for any historical/retro information, but general observations, taught at school/university (at still I hope so), as they are about basics. – Raffzahn Jun 27 at 17:40
2

Answer to update on top:

While my angle is to create my own computer using TTL chips

I am looking at 6502 block diagrams, at PDP-8 ISA and schematics, as the 4004 and TMS-1000.

Then you are looking in the wrong place. You should be looking at bit-slice computers that made use of those 74xxx TTL chips, like the Alto, the PDP-11, the Data General Nova, or many more.

Internal IC designs are restricted by very different rules compared to designs using 74xxx chips.

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.

Of course they did.

That's why I keep asking if there isn't some fundamental law here?

There's no "general law", but bit-slice designs using the 74181 ALU all follow a similar pattern: A bunch of ALU chips, a MUX in front of the ALU inputs, a bunch of register chips, a ROM for microcode, some counter chips as microcode PC, some control unit to execute the microcode.

And they don't aim to be "minimal", or "4 bit". If you want 16 bits, just use 4 ALUs. Which many of those designs did. Or a single ALU, and serial processing (which may actually be more complicated).

The issue with many of the answers is this: they are theoretical and way out of the box.

Because "what is the simplest CPU" is the wrong question. The only answer you'll get to that are "theoretical" CPUs that are very simple, but impractical, and don't fit the 74xxx approach.

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!

Exactly. It's a theoretical answer to "what is the simplest computing model". The question you were originally asking.

"I want to design a CPU with 74xxx chips" is a very different question. And it's not hard to do such a design. Just play around and do it. Simulators for 74xxx chips exist, you don't even have to wire it up, or try to find a source for 74xxx chips.

And if you drop your artificial "but I want it to be minimal, and I want a general law for it" requirement, start out with something that works, and then think about ways to reduce chip count, and may even end up with a fairly minimal system.

The only way to gain experience about how to design such a system is to design one. Or two. Or three.

Edit

And to add two examples for fairly minimal systems (which still use quite a few TTL chips):

  • The PISC ("Pathetic Instruction Set Computer") uses 22 TTL chips. 4x 74181 for a 16-bit ALU, 8x 74172 for eight 16-bit dual-port registers, and a programmable status latch and a 4-way multiplexer for the carry input, plus RAM and ROM. Very simple microcode of only 16 bits.

  • Homemade Apollo 181 CPU, with one accumulator, 16 4-bit registers (or, if you want, data storage), 256 8-bit words of program storage, and a reduced microcode decoder by using several opcodes for what would be normally different microcode stages for a single opcode. Still needs a few dozen TLL chips, looking at the board. About the level of complexity of an Intel 4004 system (you could probably implement a pocket calculator with that).

| improve this answer | |
  • This is a good point. Minimal isn't a useful target. Aiming for the smallest design that can be used for some specified application is. Thus my design referenced above was the simplest solution I could think of for putting data into memory via a keypad, while the datapoint 2200 was the simplest system its designers could think of for the more complex task of running a full-screen terminal. Different requirements lead to different designs. The question assumes, but does not specify, some particular set of requirements, and specifying these could help the author come up with his design. – occipita Jul 3 at 5:56
  • @occipita Exactly. There's a continuum between "simple, but useless" and "more complex, but useful". In particular you must state "useful for what?". Then you can try to find a minimal-ish design that this useful for this particular purpose. – dirkt Jul 3 at 6:59
  • Love the PISC and Apollo181 references. Lots to learn from. – Gunther Schadow Jul 5 at 6:29
  • If you want another nice design around the 74181 ALU, have a look at the Dietz 621X (German required). Not minimal in any way. Microcoded, 16 levels, 128 macrocode registers per level. Very clever use of 74194 shift registers and 74161 counters as microcode registers. Very clever way to do multi-byte operations. – dirkt Jul 5 at 9:52

Not the answer you're looking for? Browse other questions tagged or ask your own question.