hiebeler@turing.cs.rpi.edu (Dave Hiebeler) (11/02/90)
The people in the Information Mechanics Group at MIT designed and built a series of cellular automata machines (CAMs). I have one in my PC right now; it's a plug-in board that runs cellular automata at about the speed of the earlier cray's: 256x256 array, updated 60 times/second. Much cheaper than a Cray, too. :-) It's not a truly parallel machine; it's basically a tight pipeline that loops over the array to update the cells. If anyone's interested, I can send more information. I don't want to sound too much like an advertisement. There have been other CA hardware implementations, such as LGM-1, RAP2, but I am not as familiar with them. (Although I can supply a couple of references if there's interest). There is also, of course, the Connection Machine, as someone mentioned. It can run CA pretty darn quickly, although it's not a dedicated CA machine -- people have written all sorts of applications on the CM. -- Dave Hiebeler | Internet: hiebeler@turing.cs.rpi.edu Computer Science Dept., Amos Eaton Bldg.| hiebeler@heretic.lanl.gov RPI | Bitnet: userF3JL@rpitsmts Troy, NY 12180-3590 |
tarquin@athena.mit.edu (Robert P Poole) (11/02/90)
Such a hard-wired "LIFE computer" implementing Conway's rules of the game of Life has already been built. Some grad student here at MIT built the computer while LIFE was a popular thing at the AI lab. Not sure if it used the same massive parallelism as you describe, but that kind of parallelism is hard to wire unless you are (a) patient, or (b) into monolithic VLSI design. You could build a version of this with off-the-shelf components for $100 or so, assuming a limited array size of 20x20 or so. But I don't envy your cramps from all that wire-wrapping. -- Robert P. Poole tarquin@athena.mit.edu 46 Massachusetts Avenue MIT Course VIII 311B Bexley Hall "We make Idols of our concepts, but Cambridge, MA 02139 wisdom is born of wonder."
bwhite@oucsace.cs.OHIOU.EDU (Bill White) (11/03/90)
In article <10440@milton.u.washington.edu> whit@milton.u.washington.edu (John Whitmore) writes: > The lowest parts count cell I've seen uses analog techniques; >you use a summing junction (resistors) and two comparators (one >for 'starvation', one for 'nonsupport') with two latches. The output >of latch#2 is the cell state (and feeds the summing junctions of >the node and its neighbors). Latch #1 takes its input from the >AND of the two comparators (if both conditions for cell survival >are met, it'll be there next turn); its output feeds latch#2, >on a slightly delayed clock (to allow for skew in the comparators). I've actually built such a beast. I designed and built it exactly the same as you describe (the above is pretty much the optimal solution, and not that hard to come by). In theory, it'd be easier, I'm sure, to use a "bucket-brigade" of two storage elements, if one were to put the whole LIFE cell on a chip; but for discrete components I just used a latch chip. Each "cell" is a little cube, with an LED on the front (I wanted to use a 2cm x 2cm LCD "shutter", but couldn't find one cheap), and pin and socket contacts all around. Each face (up,down,left,right) has four pins and four sockets, and they plug together to make an arbitrarily large array. Internal configuration has the four immediate neighboring cells' outputs fed additionally out through one quarter-turn rotation, and the input from a quarter-turn rotation goes into the comparators as well; this allows all eight neighbors (four diagonal as well as four immediate) to be connected without using actual octagonal pin configurations. It sounds complicated, but it isn't. Basically, if you have cells ABCDEFGHI as follows: A B C D E F G H I Cell A's output gets fed through D into E, cell G's through H into E, cell I through F into E, cell C through B into E. And so on. In addition, there are clock lines and power lines, which I implemented as one pin/socket pair horizontally (+5V and ground), and one pin/socket pair vertically (two phase-offset clocks). The horizontal pin/socket and vertical pin/socket were not interchangable; thus the cells couldn't be plugged in with power going into the clock and vice-versa. I only built three; it was too hard to do without some form of mass-production which I don't have access to. I still have the schematic if anyone wants it (if I can find it). I never got it clocking really fast, tho. I also designed (but didn't build) variant cells such as a pseudo-random-noise generator (using a 5XXX white noise generator), a true-random-noise generator (using a cheap op-amp), an "edge reflector" unit, various cell types, etc. In theory, any cellular automaton system could be implemented, provided it only took into account a limited number of neighbors. As for mass production, the best for a binary-output (on/off) CA might be a single-chip decoder. Possibly even a ROM -- after all, it'd only be 256 bits, and that'd fit onto a chip with two latches, no problem. Anyone out there rich? > John Whitmore > whit@milton.u.washington.edu -- | Bill White Internet: bwhite@oucsace.cs.ohiou.edu | | MR. COLE'S AXIOM: | | The sum of the intelligence on the planet is | | a constant; the population is growing. |
DBG@SLACVM.SLAC.STANFORD.EDU (11/06/90)
I built a Life implementation in hardware in 1970-71, using a TV display (black and white) for output and a homemade trackball for input. The game topology was spiral-wound torus, i.e. the right-hand neighbor of the bottom right cell is the top left cell. This made it easy to do all the cell storage in shift registers. I had 19 rows of 25 cells, and could do a generation in 1/60 second but had a variable hold-off to slow it down and even stop it. The shift registers had taps in 9 places to allow counting neighbors, and one extra row-long appendage register to keep the previous state of the row just updated. Neighbor counting was done with current summing resistors and comparators, taking advantage of some nonlinearity in the obvious simple circuit (8 resistors plus diodes connected to one summing resistor) to spread the 2 and 3-neighbor cases over the lion's share of the available voltage, so the comparators were trivially easy. Oscillators looked very smooth because there was no time-sharing interference as on the computerized versions of the day, and glider arrays could fly around and around wrapping forever. I was in touch with Gardiner (Scientific American) and about to publish info on it, when I took bad advice and decided to keep it secret so I could get patents and make a fortune selling it. Dumb idea, as there is no violence and no simple competitive aspect to keep people interested; the only market was a very tiny intellectual one, and at that time one would have had to put a coin slot on it to make it commercially feasible. My patent application would have been several months after the Sanders/Magnavox (Using TV for Game Status Display) one, close but useless. The circuit is either trivially obvious from the above discussion or completely obsolete because none of the logic devices I used are commercially available anymore, so don't bother to ask for it. It's not the way you'd do it anymore--though I suspect it's a better approach than building discrete physical cells and connecting them together!!! -- David B. Gustavson, Computation Research Group, SLAC, POB 4349 MS 88, Stanford, CA 94309 tel (415)926-2863 fax (415)961-3530 -- What the world needs next is a Scalable Coherent Interface! -- Any opinions expressed are mine and not necessarily those of the Stanford Linear Accelerator Center, the University, or the DOE.