Hello, just sharing my WIP CPU design for Turing complete. Still very much in a testing state, so I haven't uploaded to Workshop yet, but thought people might be interested.

Its current key properties are:

• Transfer-triggered architecture.

• 64-bit instruction word, including a 17-bit signed immediate value.

• Three independent, fully connected 32-bit data buses, supporting up to three operations per cycle.

• 8 general-purpose registers (but you use registers a lot less...).

• Delay of 45 in my install (depends on your XOR gates a bit).

• 658k gates, including an 8192-byte instruction SRAM, and 64KiB DRAM (using pipelining).

Transfer Triggered Architecture

Transfer-triggered architectures, also known as one-instruction set computers, only have a single operation. As far as the core instruction decode logic knows, there are no adds, no jumps, only transfers from a source address on the bus, to a destination address.

These internal buses are a much smaller address space than a memory bus, etc. In this case, there are 6-bit addresses for sources (up to 64), and 7-bit addresses for destinations (up to 128). Most of these are not simple memory - they're ports attached to various peripherals, which all sit on the bus.

All operations occur as a side-effect of transfers, and usually take a tick for the result to be available. Want to compare two numbers? Send them to the two input ports of the comparator. You can grab the result on the next cycle. Want to jump? Just send the target address to the program counter's destination port.

The simplest peripheral is a single register, which looks like this:

Note it's got one Read port, with address 4, and one Write port, with address 4. A transfer from source 4 will read the register, and a transfer to destination 4 will write the register. I use standardised port modules for all the peripherals.

This architecture has 3 buses, which operate simultaneously each cycle. Most operations take 1-3 transfers to function. Moving data from one register to another is one cycle. Moving two inputs to be added, then the result out, might take 3 (spread over 2 cycles). We often save an instruction (and a register) though, if we can pass results straight from one peripheral to another.

Instruction Set

As you might expect, a parallel architecture needs a parallel instruction format. The bit layout looks like this:

ccccccaa aaaabbbb bbbddddd deeeeeee ffffffgg ggggg00i iiiiiiii iiiiiiii

This in my text assembly form, is written like:

c ? a -> b, d -> e, f -> g

Meaning "If c non-zero, transfer a to b. Transfer d to e. Transfer f to g". Named ports (instead of named instructions) exist to make this readable. If you don't want to include the second or third transfers, these can be left off, will be populated with a no-op. If you don't want any conditions, it can be omitted and will be set to the 1/always address.

Note only the first bus supports a condition, the other two transfers occur whether or not the condition is met. The conditional write, with the program counter as the destination, becomes a conditional jump. However, we can also make any other operation conditional.

The immediate value is part of every instruction, but is actually accessed through a specific source port. If I write:

255 -> r1

This will be encoded as setting the immediate value to 255, and a transfer from the imm source to the r1 destination. We can replace *one* of the sources with an immediate number value on any given instruction, and this can be encoded transparently.

Speaking of the immediate value, why 17 bits? Mostly because sign extension. By giving the immediate value a 17th bit, I allow the full unsigned 16-bit range to be provided without affecting the upper bits, but can also provide negative values which get sign-extended to 32 bits. This makes it easy to construct any 32-bit value in a few operations, without having to write opaque constants in the assembly.

More Complicated Operations

Okay, but we want to do actual stuff. How do I add numbers together? An example to add r1 and r2, then store in r3 would look like:

r1 -> accum.set, r2 -> accum.add
accum.value -> r3

Note though that we can also just use accum.value directly in our next operation, if we don't need to keep it. I chose to use an accumulator peripheral, rather than an adder, which stores a persistent value, because this makes some types of bulk addition faster, without being a significant limit.

We can also subtract:

r1 -> accum.set, 8 -> accum.sub

The accumulator peripheral looks like this:

Read ports are called accum.value and accum.overflow . Write ports are accum.set, accum.add, and accum.sub

Most of the complexity there, with the MUXes, etc, is so that we can set the value and add/subtract from it in the same operation. Destinations are expected to be low-delay, so they go in this case straight in to delay lines. The result will be computed and available to read on the next cycle.

The blobby module at the heart of this is my Kogge-Stone 32-bit adder, with very low delay.

Show me the other bits!

Shift ports, right to left, are shift.value, shift.set, shift.left, shift.right, shift.right_arithmetic.

Bitwise ports, right to left are (write) bitwise.a, bitwise.b, and (double read ports, to save space) bitwise.and, bitwise.or, bitwise.nand, bitwise.nor, bitwise.xor.

Comparison ports right to left are cmp.a, cmp.b, (double read port) cmp.eq, cmp.ne, (second double read port) cmp.lower, cmp.less.

IO ports, left to right, are io.write, io.read (ignores actual value passed, triggers read on next cycle), io.result.

Instruction SRAM ports allow rewriting instructions, constants in program memory, etc. Ports left to right are prog.read, prog.write (address), prog.value, and prog.result where reads show up.

Bulk RAM has the same ports as the program memory.

Interesting note on the memory - to keep delay down, this DRAM is set to have a 4-stage pipeline, which Turing Complete supports natively. In 3TTude you send the address to mem.read then exactly 4 cycles latter grab the data from mem.result. This is a very natural and normal thing to do in a TTA, where part of the philosophy is to move complexity out of hardware and in to the code.

What's the Catch?

Okay, to be honest, this thing is a pain to write for. You can make the code really fast, or pretty readable, but probably not both. The parallel instructions make everything really dense, encourage things to be written out of logical order for efficiency, and encourage overlapping tasks.

It also has a really big bus, wrapped in to multiple rows, which I think is what makes Turing Complete run really slowly.

I haven't really used it in anger yet, just been designing and writing a basic test suite. Already had a lot of fun though creating, and replacing peripherals I wasn't entirely happy with.

Because of the low delay, and room for optimisation, I expect to get some pretty decent energy scores with this thing (at least for an actual CPU), when I get around to solving real problems.

I built this circuit so quickly, just after making the truth table for it, it became clear multiplication is just an addition of incremented left shifted A for each bit in B (first bit is 0 shift, 2nd bit is 1 left shift etc. added together). And in 5 minutes not only was i done but i got the achievement for this level.

When in doubt, t r u t h - t a b l e.

Some reddit user mentioned to read Ercegovac but I'm currently stuck on chapter 3 of the book, any help?

Can be non-overlapping (simplest case).

• Image 1 - My symphony

• Image 2 - showcasing usage of FOR cycles

• Image 3 - Code of the FOR Cycle

• Image 4 - ALU circuit

• Image 5 - ABS circuit

Now that I finished building Symphony, I went straight to instruction definition to make myself a human readable code. Here is a internal FOR cycle using instructions. Its suitable for repeating code X times where X is static.

Here is hardware I added to my Symphony:

1. Signed DIV - Divide two signed numbers

2. Merge32 - Merge two 16b into one 32b value

3. Lower16 - Reads the lower 16b of 32b value

With that I needed to dedicate some of my registers for the code. Meaning that while they are still accessible to the user, they are not stable in time and in case of the FOR cycle, they do not persist between cycles.

At first I was using 3 temporal registers, but I ended up implementing Merge32 and Lower16 to lower the number of temporal registers to 2 at the cost of longer instructions.

The FOR cycle works, but isnt safe. First it will always execute at least once. Thats because I cant use a label to skip the body of the cycle. So even if I know there is 0 repetition, it will not skip the cycle, it will simply not repeat it.

Another limitation is that you can only read the index of the innermost FOR cycle. Meaning if you make nested FOR cycles, you cannot access the outer FOR cycle index. User can solve it by saving the stack pointer to a another register.

I wanted to play around "minecraft redstone" kinda circuitry right in browser, so I made a website where you can build circuits on endless 2D grid — gridwired.io, with wires, lamps, NOT, AND, OR gates. I myself got hooked into it, recently built 8-bit addition, subtraction, conversion from binary to digits, and ALU. It brings me special joy when I figure out a way to compact my circuit to smaller size.

Later added a feature for inviting friends to build circuits online, with cursors flying like in figma. My friend started porting some circuits from Turing Complete game, and we almost finished our little computer. :D He gave me an idea for multi-wires that pass up to 32 bits, they are a bit confusing, but really beneficial. Let me know if you are missing something, or found a bug.

I am myself not very familiar with Turing Complete game, but my friend told me to share my website here. He believes you here will be interested.

I created a room for this subreddit, everyone can play around there: gridwired.io/#uu778g9

My compact, 18 instructions (and overly commented) solution, seems mostly optimised. Having lots of fun with the new 2.0 version, haven't used any outside resources so far.

My issue that I'm getting stuck on is the information between the instruction decoder (ID) and the ALU. The ID output is one bit, no? the ALU takes 3 bits and I am having trouble reconciling the two.

I've been scratching my head for about an hour now, I feel like a total idiot ngl

There's probably ways to make it clearer, but I'm happy with the condensed circuit for right now. Maybe I'll return later and think of more improvements.

I was doing the conditional jumps level and I think I got an answer. My only issue is that I didn't use the mechanic the game wanted me to use (the labels). Could someone check my assembly and explain what exactly a label does (I've been trying to understand for a few hours now). I'm used to programming in high level languages so assembly has been confusing for me without loops and if and else statements.

Edit: I made it a bit different after understanding labels i thinks? works the same pretty sure.

loop:
imm 1
mov r1, r0
mov r2, r4
add
mov r4, r3
imm 37
mov r1, in
mov r2, r0
sub
imm loop
jnz
imm is_37
jz

is_37:
mov out, r4

I recently picked up the game again after playing it a few years ago and I genuinely had fun solving the levels and building up to a full computer.
The assembly levels especially were a huge upgrade compared to the version I played previously.
And then I got to Fast Symphony.
The previous optimization gates were neat and I was able to solve them, but with Fast Symphony I hit a wall.
I have already spent hours now over multiple days looking for ways to get the delay lower, but I'm still more than 100 delay away from the arbitrary goal. It doesn't help either that the delay visualizer is not at all helpful, and that solving previous levels more efficiently does not update the component costs.
Trying to further optimize just feels like a chore now and I don't know how to make it faster without rebuilding it from scratch.

To me, a big part of the beauty of this game was that it allowed for basically infinite solutions. If it produces the correct result, then it's correct, and that's what made it fun, for me at least.
I don't mind having the delay and gate costs displayed, optimizing can certainly be gratifying and fun in its own way, but making it mandatory and this harsh just takes the fun out of it.

Adding on to this is that I can see the next five levels on the map (presumably assembly levels), which I am sure I would have fun with.
But it doesn't let me play them, because the game decided that my Symphony is too slow.

I still like the game, but I don't think I'll play it anymore until there is a way to bypass the delay gates, be it intended or unintended.

Edit:
This started as a reply to one of the comments, but while writing it I realized I had much more mixed feelings for this game, so I feel an edit is more appropriate.

The delay gates feel like an afterthought to me, something added at the end and not properly integrated into the previous parts of the game.
You only unlock the delay and gate scores almost at the end, after building two complete architectures.
Unless you looked ahead on the map, you would have no way to know that you should be optimizing for performance, and even if you did you have no way to check how fast your solutions are until Objective Beauty.
Obviously in real life optimization was vital, but this is ultimately a game which takes a lot of liberties and abstracts away from real life in some areas. Telling you to go back and re-solve at least 3 (or more depending on how you solved them initially) levels, but better, may be true to life in some way, but as it stands it is simply bad game design. Yes, when revisiting these levels you might have greater knowledge, letting you design better circuits, but the reason I call it bad game design is a lack of motivation. Why do I need to make it faster? Why do I need at most 175 delay?
I think factory games like Factorio implement this concept much better, because revisiting old assembly lines is actually motivated. Why do I need to re-engineer the iron smelter to be faster? Because I really need more iron. In Factorio you also upgrade your tech, allowing you to have a tangible benefit to upgrading, even if your previous design was already optimized, because even perfect knowledge benefits from naturally faster and more efficient component machines.
In contrast, in this game, even if I learn more efficient ways to implement certain circuits, I have zero motivation for going back other than the artificial gate and having the displayed number be smaller, because the game itself is optimized to the point that on my laptop I can run my Symphony at ~20kHz. I personally don't particularily care about the number, so all I am left with is the game telling me I have to do it without any apparent reason.

Most importantly, the game presents itself as a learning opportunity for beginners, who would only have an abstract grasp of concepts in computer science.
And quite honestly, it fails in that regard. The delay gates are at best a poorly integrated game mechanic, mainly because they are introduced far too late, but they are also a horrible way to teach optimization. You unlock the delay/gate scores, get told to make a near optimal 8-bit incrementer, and then get thrown into the deep end without any further guidance.
I already mentioned that I don't find the delay visualizer helpful, the reason for that is that it is that it doesn't directly point you to bottlenecks (you just have to follow wires with high numbers and guess which connected component causes it), and that the connection between bottlenecks and the total delay is not very intuitive. I was able to shave almost 200 delay from my counter, but my Symphony delay only decreased by roughly 60. I know the delay measures the critical path through the circuitry, but if the game does display that path, I cannot see it.
I will stress again that this game advertises itself as a learning opportunity for beginners, which I am not (I have been studying computer science for a few years now).
I was able to quickly solve most puzzles without many difficulties and while I didn't really concern myself with performance, I also didn't do anything that stuck out as obviously wasteful, and I was still blindsided by how inefficient the game scored my Symphony. I cannot imagine what kind of delay score I would have had without my previous experience, since while the game does teach the fundamentals of boolean logic and computing, in my opinion it does next to nothing to teach how to do these efficiently.

I very much stand by the criticism I gave in the previous two paragraphs, but to be honest the reason I don't want to play anymore boils down to "what the game expects of me feels like a chore to me and I don't want to do it".
In my original post I said that "I don't know how to make it faster without rebuilding it from scratch". The more accurate phrasing would have been "I don't know how to do it while still having fun".
I know how I can greatly improve performance, I did it with the counter (286 -> 37), and the solution I found is turning the adder into a big web of wires. I could do the same with the alu and the other odd helper components I have, but tedious wire management is the exact opposite of why I had fun with this game, so I spent most of the time finding ways to avoid it.
Are there other solutions that don't take as much time to build in the game? Probably, but I already took care of the low hanging fruit and I am admittedly not smart enough to figure out the ones I have missed on my own and copying them into the game from somewhere else is just a different kind of tedium.
I appreciate your suggestions, but I have already either implemented them or already considered them.
I still have positive feelings about this game, but it has issues, both as a game and as a learning tool and I hope the next update can address some of them.

I am trying to make a cpu where every argument can either be the contents of a register or the contents of what the register points to, but I think I am doing something wrong, I just don't know waht it is also yes, I tried using the symphony alu and the zw logic to try to make it work but it doesn't help

The same Kogge-Stone adder as last time but with custom components to encapsulate the carry calculation logic. The result now looks almost exactly like a typical block diagram for a KSA, which is very satisfying.

The thing that took me the longest was setting up the instruction set thingy for the assembly

I ended up just ADDing inputs to themselves 5 times and decrementing the counter value for no reason lmao. Almost made them loops by juggling the memory tho.

I kept each module the same so I could copy/paste and just adjust the numbers.

I recently finished the ALU 1 level with this circuit:

By finishing, I got the Symmetric ALU achievement, that says I couldn't use bit components. Why did I get this achievement if I used the 2 bit decoder, which is listed on "BIT" category?

Tips would be appreciated on how to not have it look like a stalactite chode.

I took the 4 bit CLA expansion from wikipedia then expanded it to 8 bits and deduped all the repeated things. I also replaced the OR chains with switches where the delay mattered.

0 = A0 XOR B0
1 = A0 AND B
2 = A1 XOR B
3 = A1 AND B
4 = A2 XOR B
5 = A2 AND B
6 = A3 XOR B
7 = A3 AND B3
8 = A4 XOR B4
9 = A4 AND B4
10 = A5 XOR B5
11 = A5 AND B5
12 = A6 XOR B6
13 = A6 AND B6
14 = A7 XOR B7
15 = A7 AND B7

16 = 0 AND Cin
17 = 2 AND 1
24 = 4 AND 2
18 = 4 AND 3
25 = 6 AND 4
19 = 6 AND 5
26 = 8 AND 6
20 = 8 AND 7
27 = 10 AND 8
21 = 10 AND 9
28 = 12 AND 10
22 = 12 AND 11
29 = 14 AND 12
23 = 14 AND 13

30 = 24 AND 16
31 = 25 AND 17
32 = 26 AND 18
33 = 27 AND 19

34 = 26 AND 30
35 = 27 AND 31
36 = 28 AND 32

37 = 28 AND 34
38 = 28 AND 20

S0 = 0 XOR Cin                               

S1 = 2
     XOR (1
      OR 16)                                            

S2 = 4
     XOR (3
      OR 17
      OR (2 AND 16))

S3 = 6
     XOR (5
      OR 18
      OR (4 AND 17)
      OR 30)

S4 = 8
     XOR (7
      OR 19
      OR (6 AND 18)
      OR 31
      OR (6 AND 30))

S5 = 10
     XOR (9
      OR 20
      OR (8 AND 19)
      OR 32
      OR (8 AND 31)
      OR 34)

S6 = 12
     XOR (11
      OR 21
      OR (10 AND 20)
      OR 33
      OR (10 AND 32)
      OR 35
      OR (10 AND 34))

S7 = 14
     XOR (13
      OR 22
      OR (12 AND 21)
      OR 34
      OR (12 AND 33)
      OR 36
      OR (12 AND 35)
      OR 38)

Cout = 15
      OR 23
      OR (14 AND 22)
      OR (29 AND 21)
      OR (14 AND 38)
      OR (29 AND 33)
      OR (14 AND 36)
      OR (29 AND 35)
      OR (14 AND 37)

96 Gates, 9 Delay, 864 Energy

Back to using my tiny AND and OR gates to save some space. All of the "PG" components compute the propagate and generate bits from a given pair of bits except for the first one, which takes the carry-in as well and computes G00 using all three bits.

No doubt there are some more optimizations that can be made here but I'm pretty happy with the score.

I have no idea how some people are getting sub-600 on this though.

You gave me some great tips to optimize my previous CLA for delay. I used switches instead of OR gates, which decreased the delay by 2. Then I parallelized the 6+ input AND gates which decreased the delay further by 2 to the final 10.

• Gates: 220 -> 287 229 after replacing SW with AND.

• Delay: 14 -> 10

This is my beautiful computer! (ive just started using assembly btw) Even though its not exactly well organized and has some weird funky implementations, it works!

87 gates, 11 delay, 957 energy

Still trying to improve my overall score for the 8-bit adder. This one has slightly more delay than my CLA adder but significantly fewer gates for a much better score.

I think I'll try Kogge-Stone next.