After talking to ‘david927’ and more recently ‘morphle’ my interest in a longtime dormant project called ‘softbricks’ has woken up again.
The idea behind softbricks is a computing fabric that you can create out of simple building blocks connected to each other in two or three dimensions.
Think ‘lego’ but make it calculate.
The question then becomes how simple can you make a brick, how many ‘gates’ do you need to make it all work.
One of the problems that you run in to if you design a system like this is clock propagation. A global ‘clock’ is a very limiting thing, it needs to propagate across the fabric before you can switch to the next state.
I didn’t feel that that was the way to go (there are some other decisions like that, such as what kind of addressing mode to use and I feel that ‘relative’ is superior to ‘absolute’).
After some searching I found this:
http://hep.uchicago.edu/~rosner/p226/proj09/lewis.pdf
Paper that describes a hardware implementation of ‘life’, and indeed the author mentions the clock as an issue.
So I figured if I can prove that an asynchronous ‘life’ is possible then by extension (because life is already Turing complete) I can prove that an asynchronous computing fabric of infinite size is possible.
I asked about that here:
http://news.ycombinator.com/item?id=1071989
And got back a lot of interesting information, including a ‘forget it, the physics make it impossible’.
That one slowed me down for a bit, but after reading the wikipedia article I actually felt better, since the way in which I envisioned solving it does not need any complex arbitration.
I wrote some code, re-implementing life quick-and-dirty, in - yes, yuck - PHP. It’s the tool of choice because it is very close in syntax to C and I’ve programmed lots of code in it so I can whip out something small like this in a couple of hours.
I ran in to one nasty little bug that kept me down for about 2 hours waiting for the chance to burn some midnight oil, and at 6 am I had it working.
This is how it works, please keep in mind that this is a theoretical solution and that for speed reasons I’ve cut a corner or two.
Each cell maintains a few state variables, it has it’s current state, the state during the previous generation, it has its position (because it needs to address the cells left and right of it, in ‘real’ life this would not be required, the other cells would be reached via hardwired links so no need for addresses), and it holds a ‘gen’ counter which contains the number of the current generation associated with the ‘state’ variable.
The generation is a full ‘int’, 32 bits right now, and it is passed to the cells around the current one. But that’s overkill, 2 bits is enough for this, that gives you 1 cycle ‘room’ between the head and the tail of the generation counts.
Here is the code: http://ww.com/asynclife.php.txt
Apologies for the code quality, it is (obviously) not meant as production code, merely an implementation of a ‘thought experiment’.
The optimization is (php is slow!) to create cells only when needed.
‘Dead’ cells remain active after they have been used to continue to propagate the generation number across the fabric in such a way that no two cells can ever be more than two generations apart across the entire fabric.
Of course like everything else in this world, this had already been invented by someone else.
See this comment by ‘sketerpot’: http://news.ycombinator.com/item?id=1072973 which I found after waking up scandalously late. That’s what you get for having lousy google fu.
In a way that’s a pity, after all, to be ‘late to the party’ is something that happens with some regularity, but in a way I’m very happy I didn’t know that.
After all this gave me an excellent opportunity to think this whole problem through and that gave me a much better understanding of the issues that computing fabrics face.
I hope this was somehow useful to you.
Now I’m off to read ‘sketerpots’ other links.
Oh, and I just discovered this link:
http://en.wikipedia.org/wiki/Asynchronous_cellular_automaton
Which is also very much worth reading.