howell@grover.llnl.gov (Louis Howell) (11/02/90)
In article <PRGSNJX@cs.swarthmore.edu>, gessel@cs.swarthmore.edu (Daniel Mark Gessel) writes: |> In <85285@lll-winken.LLNL.GOV> howell@grover.llnl.gov (Louis Howell) writes: |> >In article <1990Nov1.185409.25802@bradley2.bradley.edu>, pwh@bradley2.bradley.edu (Pete Hartman) writes: |> >|> I had the idea some time ago to do a hardware implementation of the |> >|> Life algorithm... |> > |> >You've just described a Connection Machine, right down to the LED's. |> |> Is this really a Connection Machine? That is, does a connection machine |> cumpute using Conway's Life? I wouldn't expect that the Connection Machine |> would use a two dimensional array. |> |> Do you have any info on how to compile or program to a life "board"? |> I would be very interested. Sorry, I spoke from the hip, and didn't mean to be misleading. The CM processors can do much more than just play Life, and are not limited to a 2-D grid. There are 16 bit-serial processors per chip, and these chips are connected in a 12-dimensional hypercube (full size machine). Several different 2-D grids can be embedded in this hypercube, and other geometries as well. There are other components too, like the router, floating point chips, etc. The operations in Conway's Life map very naturally onto the Connection Machine, so you can write a parallel Life program in very few instructions in any of the CM languages. There are also large banks of LED's, which could be used to display Life patterns, though I don't know if anyone has ever done that. There are better ways to do graphics. Usual disclaimer: I don't speak for Thinking Machines, blah blah blah. As for programming using Life, I have read that streams of gliders can simulate a universal Turing machine and therefore can perform any computation a digital computer can do. Don't know the details of the proof. -- Louis Howell "A few sums!" retorted Martens, with a trace of his old spirit. "A major navigational change, like the one needed to break us away from the comet and put us on an orbit to Earth, involves about a hundred thousand separate calculations. Even the computer needs several minutes for the job."
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.dave@dptechno.UUCP (Dave Lee) (11/08/90)
Just to add to this discussion, I built a 16x16 led grid driven by a Z80 in 1985. It was primarially for animation, but I coded in a life game for fun. It used a homemade optical pen made out of a photo transistor imbeded in the empty shell of a bic pen. Anyway, as for a hardware solution being faster than a software one, well it may be, but how fast can you watch life ? I cant remember the details, but my system only took about 5 instructions per cell to compute, and running at a clock of 4Mhz, I had to put delays in all over just to make it watchable. Having each cell do its own computing is certianly elegent, fun, and probably useful for "serious" computing, but for watching a life game in real-time, a simple cpu with a little memory can certianly keep up with any desirable display speed. (IMHO of course). The chip count (and cost of course) of a simple cpu based system doesnt grow much with the number of cells. Especially if you use multiplexed display hardware (one transister and 1 bit of latch per row and per column) No matter how you do it, it's a pain to wire all those led's !!!!! More reciently, I've seen LCD grids availible (like those in hand held games) that would make the display hardware a snap. -- Dave Lee uunet!dptechno!dave