3 ms·

Someone's already figured out a way to run Conway's Game of Life asynchronously. Check it out: http://ieeexplore.ieee.org/search/wrapper.jsp?arnumber=1029886 h

Someone's already figured out a way to run Conway's Game of Life asynchronously. Check it out: http://ieeexplore.ieee.org/search/wrapper.jsp?arnumber=1029886 http://ieeexplore.ieee.org/search/wrapper.jsp?arnumber=10298... I didn't read the paper carefully enough to be sure how it works, but it looks like each cell (or region of cells) maintains a count of how many generations have passed, and it blocks until adjacent cells have caught up to it. So time propagates across the board like waves on a pond. > That adder sounds like a bit of magic, do you have a link for that? Sure! Here's the paper: http://www1.cs.columbia.edu/async/publications/cheng-unger-theobald-tc2000.pdf http://www1.cs.columbia.edu/async/publications/cheng-unger-t... I'll summarize it briefly. You know about ripple carry adders, where the carry bits propagate across the adder and it takes O(n) time? Well, the adder for each bit can sometimes precompute its carry output. If both inputs are 1, it knows that its carry output will be 1. There are some other tricks like that. Anyway, the upshot of all this is that an asynchronous ripple carry adder can operate in O(lg n) average time, and an asynchronous carry-lookahead adder can work in O(lg lg n) average time. Or about twice as fast as a synchronous carry lookahead adder, according to transistor-level simulations. > I can picture the cpu that 'sleeps on 0', basically the transitions are what clocks it forward so as long as you keep sending it 0's it simply never changes state right? (no state changes -> minimal power consumption). Asynchronous design is like ideal clock gating: when part of a processor doesn't need to do anything, it just stays idle and doesn't dissipate dynamic power. In the example of a bit-serial length-adaptive datapath that I mentioned, the leading zero bits are simply ignored, and no processor work needs to be done to deal with them. Here's a paper on it: http://vlsi.cornell.edu/~rajit/ps/bitsnap.pdf http://vlsi.cornell.edu/~rajit/ps/bitsnap.pdf

jacquesm 17y ago
> it looks like each cell (or region of cells) maintains a count of how many generations have passed, Hah! That's exactly what I came up with :) I finished it at 5 am this morning and it works. The code is here: http://ww.com/asynclife.php.txt http://ww.com/asynclife.php.txt Thanks for the other papers, I'll be reading. edit: I've written a blog post about all this: http://jacquesmattheij.com/asynchronous+life http://jacquesmattheij.com/asynchronous+life I can't read the IEEE paper without paying for it, so I think I'll forego the honour of doing so, pity because I would like to see what they came up with exactly. Especially whether or not they clued in to the fact that if you have a 'generation' counter you only need the lower two bits of it to keep going forever.
- sketerpot 17y ago
  Oh man, that's awesome! Have you considered modeling a more "real-world" computing fabric? Your cells would have randomly-distributed computation and communication delays, and you could make some sort of visualization of the time waves propagating, and it would just be really cool. I initially didn't think this would be possible to implement in simple physical hardware, but your insight that you only need a two-bit time counter changes things. Of course, ultimately, I think what you'd want to look at is amorphous computing. It's a fascinating new branch of computer science that looks at organizing a large number of unreliable small processors, sensors, and actuators, with only local communication, into a working system. Here's the big intro paper (Abelson and Sussman are among the authors, BTW): http://groups.csail.mit.edu/mac/projects/amorphous/papers/aim1665.pdf http://groups.csail.mit.edu/mac/projects/amorphous/papers/ai... I think you'll really enjoy amorphous computing. It's already getting some use in wireless sensor networks, especially the stuff having to do with establishing reliable communication channels, or figuring out the spatial distribution of the sensors based on ping times, or keeping clocks more-or-less synchronized.
  - jacquesm 17y ago
    > Oh man, that's awesome! Thanks :) It was a lot of fun. > Have you considered modeling a more "real-world" computing fabric? That's what this is leading in to, the simplest unit is just a way for me to know that it is doable. If I can't do 'life' then there is no point in going any further with it. One of the HN members here is very far in coming up with a higher level concept but I feel that it needs to be done from the 'gate level' up. > Your cells would have randomly-distributed computation and communication delays, and you could make some sort of visualization of the time waves propagating, and it would just be really cool. I did that for a bit, it is easy enough to show the generations as colours. > I initially didn't think this would be possible to implement in simple physical hardware, but your insight that you only need a two-bit time counter changes things. Yes, that's what made me really happy :) I realized that with a 'full' generation count you could make it work but that would always limit the maximum generation count to the number of bits in the counters. So why not turn it around and see how few bits you can use and handle the 'wrapping' properly. The number is 2, and that's low enough to use a simple 4-to-1 demultiplexer to select the right state line (current or previous generation). > Of course, ultimately, I think what you'd want to look at is amorphous computing. I had not heard the term before, more reading to do! > I think you'll really enjoy amorphous computing. Yes, that sounds like it is exactly the way to go. I will write a fair sized article at the end of this month about where I feel computing is headed, this as a follow up on the new years day posting about what we think the future will bring. I thought the question was an important one and I'm hitting two birds with one stone here, first the interest in cell computing and second the information I'm gathering to answer that question about the future. Fascinating stuff.

jacquesm 17y ago

> it looks like each cell (or region of cells) maintains a count of how many generations have passed, Hah! That's exactly what I came up with :) I finished it at 5 am this morning and it works. The code is here: http://ww.com/asynclife.php.txt http://ww.com/asynclife.php.txt Thanks for the other papers, I'll be reading. edit: I've written a blog post about all this: http://jacquesmattheij.com/asynchronous+life http://jacquesmattheij.com/asynchronous+life I can't read the IEEE paper without paying for it, so I think I'll forego the honour of doing so, pity because I would like to see what they came up with exactly. Especially whether or not they clued in to the fact that if you have a 'generation' counter you only need the lower two bits of it to keep going forever.

sketerpot 17y ago
Oh man, that's awesome! Have you considered modeling a more "real-world" computing fabric? Your cells would have randomly-distributed computation and communication delays, and you could make some sort of visualization of the time waves propagating, and it would just be really cool. I initially didn't think this would be possible to implement in simple physical hardware, but your insight that you only need a two-bit time counter changes things. Of course, ultimately, I think what you'd want to look at is amorphous computing. It's a fascinating new branch of computer science that looks at organizing a large number of unreliable small processors, sensors, and actuators, with only local communication, into a working system. Here's the big intro paper (Abelson and Sussman are among the authors, BTW): http://groups.csail.mit.edu/mac/projects/amorphous/papers/aim1665.pdf http://groups.csail.mit.edu/mac/projects/amorphous/papers/ai... I think you'll really enjoy amorphous computing. It's already getting some use in wireless sensor networks, especially the stuff having to do with establishing reliable communication channels, or figuring out the spatial distribution of the sensors based on ping times, or keeping clocks more-or-less synchronized.
- jacquesm 17y ago
  > Oh man, that's awesome! Thanks :) It was a lot of fun. > Have you considered modeling a more "real-world" computing fabric? That's what this is leading in to, the simplest unit is just a way for me to know that it is doable. If I can't do 'life' then there is no point in going any further with it. One of the HN members here is very far in coming up with a higher level concept but I feel that it needs to be done from the 'gate level' up. > Your cells would have randomly-distributed computation and communication delays, and you could make some sort of visualization of the time waves propagating, and it would just be really cool. I did that for a bit, it is easy enough to show the generations as colours. > I initially didn't think this would be possible to implement in simple physical hardware, but your insight that you only need a two-bit time counter changes things. Yes, that's what made me really happy :) I realized that with a 'full' generation count you could make it work but that would always limit the maximum generation count to the number of bits in the counters. So why not turn it around and see how few bits you can use and handle the 'wrapping' properly. The number is 2, and that's low enough to use a simple 4-to-1 demultiplexer to select the right state line (current or previous generation). > Of course, ultimately, I think what you'd want to look at is amorphous computing. I had not heard the term before, more reading to do! > I think you'll really enjoy amorphous computing. Yes, that sounds like it is exactly the way to go. I will write a fair sized article at the end of this month about where I feel computing is headed, this as a follow up on the new years day posting about what we think the future will bring. I thought the question was an important one and I'm hitting two birds with one stone here, first the interest in cell computing and second the information I'm gathering to answer that question about the future. Fascinating stuff.