combinator computer MK2

[piriform]

It's probably a godsend for somebody making a full-blown CPU.

Or a train scheduler Thanks for the tip

[Gertibrumm]

Not sure I understand, do you store more than one signal per memory cell?

well I store all of them that way I can store huge lists and even instructions! I was using each>0 deciders until now, that way I can filter unwanted signals and remove the need for one extra decider
well I probably havnt thought about this problem well enough to give any meaningfull opinions.
though you have a point with the clear=0 memory as it might be good for storing negative values.
also I was just thinking about double bus, well instructor is fast enough, memory cant keep up.
but until I havnt drawn a out all the signals on paper, no more views from my side, my cpu is lacking good timing
until then

[piriform]

For the past couple of months, I've been working on/off on a new version of CPU (i.e. MK4). Even though it's not ready for general release as it needs more testing, I'd thought to show what I have for comments (good or bad).

MK4markup.GIF (370.58 KiB) Viewed 8038 times

Description
Boxes outline different functional areas
white- PC (ish)
brown- X,S,Y,Z registers (X on a top)
blue – read/write assists
green –pipeline ahem. spine
red - arithmetic unit (i.e. +,-,*,/)
teal - accumulator and buffer
yellow- branch logic
the two stacks peeking from the bottom are ROM and RAM

more description and discussion

From a high level architectural perspective, MK4 is a single accumulator CPU with a simple 4 function arithmetic unit and several assist registers (X,S,Y,Z) All registers have full transfer/load functionality (i.e can receive or send data: to accumulator,memory and other registers) and can be used as scratchpad memory. Their main purpose however, is generation of different addressing modes. To that end contents of the registers can be used to generate read or write (RAM) addresses.
X and S have additional functionality. S is used for (quick) stack addressing, whereas X has special assist for REPEAT instruction which is useful in dealing with arrays,block moves,strings,etc. Y,Z registers are intended to be used as base registers ( i.e. they hold address offsets) allowing a certain degree of indirection.
Instruction and data buses are fully separated (physically and logically),so the CPU is a full Harvard. Call and Return "instructions" OTOH require a 'bridge' between the two and have therefore been provided with instruction.address<->data translator primitives. These could be used to construct computed GOTOs or some really strange multiple entry routines.

Basic instruction cycle is 2 ticks, thus enabling peak execution rate of 30 IPS. However, certain instructions degrade execution speed by a considerable amount.
RETURN instruction takes 4 ticks, and BRANCH a whopping 7. Average execution rate will be highly dependent on the nature of the program.
Assuming 14.3% branches and 5% returns, the average time will be 2.81 ticks or 21.3 IPS.

MK4's most significant difference from its predecessors is the lack of instruction decoder. Instruction primitives are stored directly in the instruction memory. This of course, significantly complicates instruction assembly, and makes certain forms of memory (e.g. multi-signal storage) much more difficult,but has the positive side effects of speeding up execution, reducing the combinator count, and the not so obvious -instruction merging/combining.
Obviously, instruction merge is very situational and should be approached with caution (or at least some testing:-),but can accomplish significant speedups, as several instruction equivalents can be executed in one cycle.
In general, the issue of code “density” (or how much work each instruction can/should do) has been hotly debated for years (decades actually) with consensus that the RISC side won (kinda...sorta... if you squint really hard and ignore the 800 lb gorilla called Intel).
OTOH consider the following (contrived) example
-We need a code segment that moves n words from address a to address b while adding 5 to each moved word .
In this (hypothetical) CPU the code might look like this:
R1=n // this will be our counter
R2=5 // number to be added to each word
R3=a // R3 will generate read address
R4=b // R4 write address
again: R5=[R3]
R5=R5+R2
[R4]=R5
R3 +=1
R4 +=1
R1 -=1
if (R1>0) again

So we have a 4 instruction setup + 7 instruction loop, executed n times. This CPU runs at 1 tick/instruction (although if you can get a branch to run in 1 tick, please tell me how) .
Total time = 7n +4.

MK4 code would look something like this:
X= n
Y= a
Z= b
repeat 0 [Z+X]=[Y+X]+5

Total time = 2n +6.
So the bottom line is that raw IPS is not that helpful.

Speedup potential
Two approaches come to mind when considering speedup.
1.move to a single tick execution cycle
In essence this would entail driving the instruction addresses via free running counter and letting the control instructions (jump,branch,call,return) override it. Basic instructions would then execute in 1 tick,however ALL the control instructions would take 1 tick longer. Assuming these comprise 30-40% of running code,the net speedup would be .2-.4 ticks (23-25 IPS).
2.The other approach is to tackle the root cause (I.e. BRANCH).
In order to reduce the branch time, some form of branch prediction is necessary. The simplest (continue and rollback if fail) could reduce BRANCH instruction time to 4 ticks average,but would require storing of 'old' values of all registers (5), a write cache and flush/restore circuitry. The net impact of this would be to speedup average execution by 3/7 tick to 25.2 IPS.

Possible enhancements,tweaks
-Second SP might be nice in order to separate parameter,return stacks.
-Second index register ? or adding 'stride' to y enabling 2d arrays or tables (I.e. addr=y*stride+ x)
-ALU enhancements: %,bits,logic (v0.14?)
-Compiler – Na-aah! Don't need no stinking NIST compiler

EDIT
----------------------------------------------------------------------------------------

A video going over MK4 architecture and showing MK4 it in action is available on youtube
https://youtu.be/X2DETxFWTMc

A google sheet containing more detailed description (signals, architecture etc) and a program listing can be found here. I realize that I'm not the nearly the best programmer, so any 'constructive' comments would be more than welcome.
https://docs.google.com/spreadsheets/d/ ... sp=sharing
------------------------------------------------------------------------------------------------------
EDIT 2

Here's the blueprint string (thanks to Foreman)

mk4.txt

(13.78 KiB) Downloaded 225 times

And here's a close up of the start/stop controls

mk4controls.gif (262.57 KiB) Viewed 7908 times

To start the program (re)activate the Start constant combinator. Normally it contains I1 which will start at address 1. If you reaaaally want to single step you can also start at some other address. (Just change the I value).
To stop the program activate the Stop constant combinator, this will place a negative address on the instruction bus and stop the execution. Before restarting, you must deactivate Stop combinator.
Have fun and if you have any questions please ask.

[XKnight]

For the past couple of months, I've been working on/off on a new version of CPU (i.e. MK4). Even though it's not ready for general release as it needs more testing, I'd thought to show what I have for comments (good or bad).

MK4markup.GIF

Description
Boxes outline different functional areas
white- PC (ish)
brown- X,S,Y,Z registers (X on a top)
blue – read/write assists
green –pipeline ahem. spine
red - arithmetic unit (i.e. +,-,*,/)
teal - accumulator and buffer
yellow- branch logic
the two stacks peeking from the bottom are ROM and RAM

more description and discussion

From a high level architectural perspective, MK4 is a single accumulator CPU with a simple 4 function arithmetic unit and several assist registers (X,S,Y,Z) All registers have full transfer/load functionality (i.e can receive or send data: to accumulator,memory and other registers) and can be used as scratchpad memory. Their main purpose however, is generation of different addressing modes. To that end contents of the registers can be used to generate read or write (RAM) addresses.
X and S have additional functionality. S is used for (quick) stack addressing, whereas X has special assist for REPEAT instruction which is useful in dealing with arrays,block moves,strings,etc. Y,Z registers are intended to be used as base registers ( i.e. they hold address offsets) allowing a certain degree of indirection.
Instruction and data buses are fully separated (physically and logically),so the CPU is a full Harvard. Call and Return "instructions" OTOH require a 'bridge' between the two and have therefore been provided with instruction.address<->data translator primitives. These could be used to construct computed GOTOs or some really strange multiple entry routines.

Basic instruction cycle is 2 ticks, thus enabling peak execution rate of 30 IPS. However, certain instructions degrade execution speed by a considerable amount.
RETURN instruction takes 4 ticks, and BRANCH a whopping 7. Average execution rate will be highly dependent on the nature of the program.
Assuming 14.3% branches and 5% returns, the average time will be 2.81 ticks or 21.3 IPS.

MK4's most significant difference from its predecessors is the lack of instruction decoder. Instruction primitives are stored directly in the instruction memory. This of course, significantly complicates instruction assembly, and makes certain forms of memory (e.g. multi-signal storage) much more difficult,but has the positive side effects of speeding up execution, reducing the combinator count, and the not so obvious -instruction merging/combining.
Obviously, instruction merge is very situational and should be approached with caution (or at least some testing:-),but can accomplish significant speedups, as several instruction equivalents can be executed in one cycle.
In general, the issue of code “density” (or how much work each instruction can/should do) has been hotly debated for years (decades actually) with consensus that the RISC side won (kinda...sorta... if you squint really hard and ignore the 800 lb gorilla called Intel).
OTOH consider the following (contrived) example
-We need a code segment that moves n words from address a to address b while adding 5 to each moved word .
In this (hypothetical) CPU the code might look like this:
R1=n // this will be our counter
R2=5 // number to be added to each word
R3=a // R3 will generate read address
R4=b // R4 write address
again: R5=[R3]
R5=R5+R2
[R4]=R5
R3 +=1
R4 +=1
R1 -=1
if (R1>0) again

So we have a 4 instruction setup + 7 instruction loop, executed n times. This CPU runs at 1 tick/instruction (although if you can get a branch to run in 1 tick, please tell me how) .
Total time = 7n +4.

MK4 code would look something like this:
X= n
Y= a
Z= b
repeat 0 [Z+X]=[Y+X]+5

Total time = 2n +6.
So the bottom line is that raw IPS is not that helpful.

Speedup potential
Two approaches come to mind when considering speedup.
1.move to a single tick execution cycle
In essence this would entail driving the instruction addresses via free running counter and letting the control instructions (jump,branch,call,return) override it. Basic instructions would then execute in 1 tick,however ALL the control instructions would take 1 tick longer. Assuming these comprise 30-40% of running code,the net speedup would be .2-.4 ticks (23-25 IPS).
2.The other approach is to tackle the root cause (I.e. BRANCH).
In order to reduce the branch time, some form of branch prediction is necessary. The simplest (continue and rollback if fail) could reduce BRANCH instruction time to 4 ticks average,but would require storing of 'old' values of all registers (5), a write cache and flush/restore circuitry. The net impact of this would be to speedup average execution by 3/7 tick to 25.2 IPS.

Possible enhancements,tweaks
-Second SP might be nice in order to separate parameter,return stacks.
-Second index register ? or adding 'stride' to y enabling 2d arrays or tables (I.e. addr=y*stride+ x)
-ALU enhancements: %,bits,logic (v0.14?)
-Compiler – Na-aah! Don't need no stinking NIST compiler

Branch in 7 ticks? do you eat those ticks on the breakfast or you are using them to mine bitcoins?
But seriously, branch instruction should be 2 or 3 (in the worst case) ticks long, and the second tick you can use for unconditional instruction.
Instruction merging = good to know that you are using this.
Main execution cycle should be 1 tick long = this is must have.
As for me, futher improvements is extending alu to be able process up to 150 different instructions per tick, and adding special commands that may be unrolled in several simpler commands (example: array processing by 10 cells per tick). But these new instructions won't be able to fully load new alu, so you should go into paralelization direction (here you may lost several ticks in main execution cycle).

[piriform]

do you eat those ticks on the breakfast

Gaah! I would not eat them even on top of the steak. (well maybe..on a bet..if I was really drunk)
Seriously though, the issue is this
read memory from register takes 2 ticks
AU takes 2 ticks to compute the new result
Branch logic another 2 ticks to compute branch address
and on the 7th tick the new instruction is addressed
In the meantime instructions are marching forth 1x1 every 2 ticks, but if branching the successors must be halted until branch figures out the result

extending alu to be able process up to 150 different instructions per tick,

Sounds pretty awesome. Can't wait to see it cook. Are you planning an action video.

Main execution cycle should be 1 tick long = this is must have.

But I'm afraid of breaking my (beloved) registers I guess you were not impressed by my CISC/RISC example

example: array processing by 10 cells per tick

That seems like a popular theme. I've seen at least one example of that.
I've been noodling something related, only more of a peripheral (or pre=processor)
Consider:
F=(S ? N) where S is a set of input signals and N a set of control values associated with each signal
An arbitrary expression could be constructed from several of these, e.g. F1 & F2 ! F3 or (F1!F2)&(F3!F4) (currently not sure what form would be most optimal).
A Moore-Mealy type of machine might even be possible, in which case you'd end up with a generic sequencer that could deal with hundreds of signals very very quickly.
Perfect for factory control. (except programming would be a real PITA).

[siggboy]

Branch in 7 ticks? do you eat those ticks on the breakfast
Main execution cycle should be 1 tick long = this is must have.

Normally this would be the point where you accept a self posed "challenge" and publish your own CPU that fixes all those issues.

Too much work? Too difficult?

Regarding the CPU: I love it, don't let XKnight spoil the fun. Personally I'd prefer to have a good general purpose setup, that is not too difficult to program. Even if you can make some specialized functions, like having extreme paralellism for certain instructions, that is only interesting if those are useful in the general case.

E.g. encryption primitives would be impressive and also utterly useless. Something that allows efficient polling of data points, or replacing the polling with something better would be great (that's something that you need if you control a factory or trains).

Interrupts (and a sane way to use them) are still a must have, it's difficult to make anything useful without them unless you resort to excessive polling or custom hardware. Polling is way too expensive with only 20 IPS.

[piriform]

Regarding the CPU: I love it, don't let XKnight spoil the fun

Thanks for the kind words and no worries. I don't consider XKnight's comments discouraging. If anything, I think he is trying to encourage others, as am I. We just have a different approach.

Re Interrupts, but of course. IRQ will be part of MK4! Right after the demo.

Re generality vs special instructions. I think you've put the finger on the exact issue I've been struggling with for some time now.
It's fairly easy to design a "Sweet-16" style of CPU that is complete and fast. Where I struggle (not being an expert ) is deciding what to add to it. The problem is that anything you add has a cost and improves only a certain part of the whole (none of this sculptor metaphor for me ). For example, I decided that efficient array handling is a must. To that end I've added addressing modes and even instructions (REPEAT) that enable this aspect of computation. Every once in a while I get a nagging suspicion that this is not the only, nor necessarily the best method to handle anticipated problems.

A big part of the problem is not fully understanding the problem Case in point, I've intended for this CPU series to become capable of controlling a factory, only t o realize that I have no idea what that means. Sure, you could point out bits and pieces and say: "Well, this could be controlled ... and this".

The problem is that this addresses only a tiny part of a very big problem space. Non inclusive list of categories would include:resource needs, BOM, material routing,production facility setup/take down, refactoring,prioritization, damage control .....

Hmm.., I wonder whether it would be a good idea to open a new forum topic on "Factory control- what does it mean?".

[siggboy]

A big part of the problem is not fully understanding the problem Case in point, I've intended for this CPU series to become capable of controlling a factory, only t o realize that I have no idea what that means. Sure, you could point out bits and pieces and say: "Well, this could be controlled ... and this".

If you can make a logistic train network and a kanban factory it's fine, I guess.

I don't really see at the moment what else you might want to make that really serves the ultimate goal (which is minmaxing rocket production, let's be honest). Combat is not interesting and not circuit controllable.

[matjojo]

Holy shit, I just saw this on the subreddit in a comment somewhere, and I must say, this looks amazingly comlicated, I myself do not have any idea what you are doing here, but I see what it does in the end, keep it up!

[siggboy]

Holy shit, I just saw this on the subreddit in a comment somewhere, and I must say, this looks amazingly comlicated, I myself do not have any idea what you are doing here, but I see what it does in the end, keep it up!

It's a CPU, it's what inside your mobile phone and your PC (and your microwave oven). Only smaller.

[matjojo]

Holy shit, I just saw this on the subreddit in a comment somewhere, and I must say, this looks amazingly comlicated, I myself do not have any idea what you are doing here, but I see what it does in the end, keep it up!

It's a CPU, it's what inside your mobile phone and your PC (and your microwave oven). Only smaller.

Yeah, I got that, but HOW it works I don't know:)

[piriform]

this looks amazingly comlicated

Actually, if you drill down, and look at all the bits and pieces separately, they are simple and easy to understand. (i.e. this bit does this, that bit this etc.)
In fact you can think of them (sorta) as lines of code (i.e. X=Y+1,;Z=X*(Y>), etc..). The trick ,if any, is getting them to work together.
I see you made a mod or two. This is not any more complicated than that (you just have to wrap your head around the combinators ).

[siggboy]

I think what makes combinators a lot harder than programming is that you cannot see the code. Even conventional digital circuits (as in conventional EE) are easier to "read" from a circuit diagram than combinators.

Add to that the lack of debugging and visualization tools and you have a challenge.

[Gertibrumm]

Main execution cycle should be 1 tick long = this is must have.

Couldn't agree more!

Holy shit, this looks amazingly comlicated, keep it up!

sorry for faking
Thats where my approach to the issue comes in:
- Sadly I have no clue what branching means -> made me think of multicore
- I have no idea what kind of syntax assembler or archetecture you guys are deriving your fancy words from (all I kown is how the stuff works)
- No clue why one would need a stack and
- I have no idea why we need array processing in factorio. Seems to me we have it because we can! And that brings me to my next point

-> The usage of a factorio CPU:
Personally I think the usage of a CPU kind of falls short for the average factioran. Reminder: we are talking about a simplified CPU, not a simple buffer circuit for my chests . Maybe you "Gurus" as they call you can take some time off from your worrying that "the usual player" doesn't understand logic and focus on your own higher level problems:

Lets challenge ourselfs a little bit for the coming 0.14 update!
Chances are high we are getting "set assembler recipe via circuit network"

Code: Select all

Challenge:
build a factorio where you can enter your desired endproduct and all outposts or lab arrays and rockets are always getting filled while you stand nearby the complex mess, proud, watching your digital clockwork.
Rules:
- Factory must produce your demand (count accurate)
- All being controlled by a CPU of your choice
- You are not allowed to set recipes (this is 0.14)
- Unlimited Coal, Oil, Ore for making things easier
(+ is optional)
+ Controlled train network with only 1 locomotive for factory-supply (to satisfy  siggboy)
+ 1 Rocket silo, 10 labs, must be getting their stuff unless demand is prioritized

How does that sound for a challenge?
If some of you agree, Ill start a thread or ask a moderator if he starts a thread for this specific challenge as I think this can get pretty interesting.
(I consider it the ultimate goal; hardest but best possible way)
Please add further ideas and criticize

[siggboy]

@Gertiprumm

This is a GENERAL PURPOSE CPU, the scope and functionality of which is very clearly defined: a universal computer that you feed with programs and input and that generates an output.

What you propose is custom hardware, which is not the point when you're trying to design a general purpose CPU. That is I have nothing against custom hardware, my train controller is nothing else (and it does use as many combinators as the CPU by now, modulo RAM/ROM).

Branching means "If X then jump to Y". A conditional "goto" statement. Remember this is an actual computer, not some special purpose contraption.

A stack is useful in computer programming (to make function calls and returns), that's why you need one.

Array processing is another staple of computer programming, that's why it's in the CPU.

[piriform]

sorry for faking

You do know that faking will get you only so far. Sooner or later you run out.

Couldn't agree more!

Do you also agree that doing three times the work in two ticks is worse then twice in two?

No clue why one would need a stack

I'm currently writing a program that uses stack extensively. A demo will be posted on YouTube,within a week (time depending). If you study the program (which I will also provide) you will learn how to (ab)use the stack.

Lets challenge ourselfs a little bit for the coming 0.14 update!

I agree with siggboy on you proposed 'challenge'. Having said that, if a 'valid' benchmark can be devised, I would not be opposed to having a go.

@siggboy
what's your take on computing with Sets (eg set of stations, set of trains, conditions, some magical operators and poof dispatch list)?

[siggboy]

what's your take on computing with Sets (eg set of stations, set of trains, conditions, some magical operators and poof dispatch list)?

That's basically what the scheduler does:

Phase 1: Set of requesters R (each requesting a set of resources), set of providers P (each providing a set of resources), output the set of resources that are in both sets. Then take one arbitrary resource from that set (we have to decide on one and we need to know which one it is). That's the resource to be delivered.
Phase 2: Take one requester 'r' from R and one provider 'p' from P associated with the resource from phase 1. Here we also want to know from 'p' how much it can provide.
Phase 3: Pick a lane from the set of lanes with waiting trains. Dispatch train.

Right now the one thing that would make a lot of things easier is an operator that gives me "Anything" from a set of signals (not "each", not "everything", just one single signal out of a set of many). XKnight has already proposed to add something like that for a better interaction with the filter inserters.
But it's also great if you need to pick single values from a set.

So, yeah, some operations on sets of signals, that preserve both the value and the type of the signal are definitely very useful.

[Gertibrumm]

Maybe I was a little too cheeky last post I should keep in mind that

This is a GENERAL PURPOSE CPU

and my approach always was to aid the game, not build a CPU which like all the minecraft computers to name an example dont really do, they just are, they dont do .

Branching means "If X then jump to Y".

thanks! I was probably thinking about subroutine or multithread which are usually OS based.

Stack...(to make function calls and returns)

thanks for clearing up.

Do you also agree that doing three times the work in two ticks is worse then twice in two?

I would agree to "Doing as much work in less time"
Even though it doesn't imrove speed alot (maybe 20% in my builds) it is a good starting point to keep things fast and as simple as possible.

Looking forward to your stack session piriform!

To your need for a standardized benchmark:
The challenge would kind of be a benchmark on its own! For this autonomous factory to work you have to make a good use for your CPU. Your CPU is as I think of it just as good as your application can benefit from it.
If you just want to crunch bare numbers then calculate how long your program performs or measure PC CPU temperature and see if it melts when playing factorio .

What you need is not a benchmark but a debugging device, or an assembler editor which visualizes and simulates your CPU.

Back to the challenge: Which I see as a competitive game to improve our selfs and aid the game to integrate this stuff more!
I dont like to see things getting extremly advanced and focused while the progress keeps others off because they dont want to bother with things they cannot get involved into.
Maybe challenges only rule should be: "Build a factory which produces count accurate demand and supplies eg a rocket while you are not allowed to set recipes"

A challenge is what we need to actually improve progress in factorio and to make good use of the features we are getting!!

[siggboy]

Branching means "If X then jump to Y".

thanks! I was probably thinking about subroutine or multithread which are usually OS based.

Nothing of that is OS based. The operating system is concerned with distributing resources among the programs that are running. So if you need disk space or RAM, then you go through the OS.

Multithreading is simply a programming paradigm, you do not need the OS to do multithreading.

"Branching" and "subroutines" are not even paradigms, they're just very simple operations without which you couldn't write a structured program. Well, a "subroutine" is a piece of code that is called in a specific way, it's not an "operation" in the actual sense.

What you need to do is to write a program or two, and learn about these things and then it will be much clearer what most of this means.

A challenge is what we need to actually improve progress in factorio and to make good use of the features we are getting!!

Yes, but this thread is showcasing a general purpose CPU. Your challenge has basically nothing to do with that.

If you have a better CPU, maybe one with 60 IPS performance and some amazing features, then you can come back and pose a "challenge". But first you need to learn what a CPU actually IS. So there is some road ahead :).

[Gertibrumm]

Even though you are challenging me all you say is discouraging.

If you have a better CPU, maybe one with 60 IPS performance and some amazing features, then you can come back and pose a "challenge". But first you need to learn what a CPU actually IS. So there is some road ahead .

It is a little discouraging because when you are challenging me this way, Ill probably never come back due to lack of possibility.
I hope you ever tried to make read and write in 60 IPS! Because at the moment I can not (I can do it in 20 IPS). And I assume you cant either

I hope discouragement is not intended because I do know a thing or two about what you are talking about, I just happend to be interested in actual use of the things we are doing, not just some proof of concept.

And I know this challenge has nothing to do with piriforms fantastic concepts 1-4, I am just trying to ask some people if they are interested in such a challenge.

And if my initial question hasn't yet seeped through: "Does anyone of you so called "Gurus" want to participate in such a challenge"