GUNK - a simulator for amorphous computing
Will Ware, (c) 1998
Version 0.01
Amorphous computing is a branch of computer science being developed at MIT, Xerox PARC, and elsewhere. In a few years, it will probably become very cost-effective to build large disorganized swarms of unreliable processors, connected locally by unreliable communication links, providing much cheaper MIPS than are available today. Cheap swarms of processors will be embedded into "smart materials" and "smart paint". The processors will form an amorphous mass of computational gunk. There is a short list of technical problems to be solved, mainly power distribution and communication.
I learned about amorphous computing in a talk at MIT given by Gerald Sussman in December 1997. The topic caught my interest and I have been tinkering with simulators on and off for most of a year now. Professor Sussman's extensive collection of web pages on his research into amorphous computing make fascinating reading. "Gunk" is a cute term that Sussman's group used for one of their early amorphous hardware prototypes.
This simulator portrays a rectangular surface coated with colored points, each representing a 68000 processor with some memory. Program memory is read-only, and identical for each processor. Because of simulation memory limitations, the memory for stack and variables is small, but controllable with a command line option.
Sussman is looking for the abstractions, principles, and languages appropriate for programming amorphous computers. He makes assumptions designed to ensure that his programs will run robustly on cheap low-reliability hardware. The assumptions are that processors are manufactured identically and then poured or stirred or sifted into something like paint or gel or concrete, where they will receive power and be able to communicate with nearby neighbors, but where they lack any sort of a-priori knowledge of who their neighbors are, how many neighbors they can reliably communicate with, and their physical location.
Here are some web sites about amorphous computing:
The Amorphous Computing Home Page at MIT http://www-swiss.ai.mit.edu/~switz/amorphous/index.html
Sussman's "amorphous computing manifesto" http://www-swiss.ai.mit.edu/~switz/amorphous/white-paper/amorph-new/amorph-new.html
Some DARPA info about Sussman's work
http://www.darpa.mil/ito/Summaries97/E569_0.html
An idea for an actual VLSI hardware prototype! How cool! http://www-swiss.ai.mit.edu/~switz/amorphous/white-paper/amorph-new/node11.html
An early prototype system built with 68HC11 microcontrollers http://www-swiss.ai.mit.edu/~switz/amorphous/HC11/index.html
*** Compiling and running Gunk
There are two steps. One is to build the Gunk program itself, and the other is to build a set of 68000 cross-development tools. The second step involves GNU binutils and GCC.
Building Gunk is easy. On any Linux system, do this:
cp -f Makefile.linux Makefile
make gunk
The assembled and linked example programs are in the form of S-records, an ASCII format commonly used for Motorola processor object files. To try the examples, simply type:
gunk -f srecs/hflow.srec
gunk -f srecs/gwave.srec
The 'gwave.srec' program expects you to click the mouse on a processor, which will start a wave of message traffic moving circularly outward across the swarm. The 'hflow.srec' program is a simulation of heat flow. You can try both these programs without building a 68000 cross-compiler.
*** Commands, options
Keyboard command (for X windows display):
Press '>' to make the window unreasonably large
Press '<' to return the window to a reasonable size
Press 'P' to pause/unpause
Press 'Q' to quit
Command line options:
-n <number> select the number of nodes, defaults to 500
-s <number> select the data memory size per node, default 1024
-f <filename> select a SRE file, defaults to stdin
-X set X size, defaults to 300
-Y set Y size, defaults to 200
-h, -? print all this help stuff
*** Arranging a 68K development environment
For those (like me) with little or no memory of the details of the 68K architecture, there's some useful 68K information at these sites: http://ironbark.bendigo.latrobe.edu.au/courses/bcomp/c206/ http://www.dgp.utoronto.ca/people/van/courses/csc258/ http://www.massena.com/darrin/pilot/resources.htm
Here are a couple of useful 68K manuals in PDF format. The 68000
programming reference manual is the most useful:
http://www.mot.com/hpesd/aesop/68k/68kprm.pdf
This is a data sheet for the chip, which doesn't go into a lot of
instruction set specifics:
http://www.mot.com/SPS/WIRELESS/pdf/MC68000/UM_REV9/COMPLETE.PDF
*** Building GNU binutils
First pick up the source code for GNU binutils. If you can't find it on a Linux CDROM, try either of these FTP directories: ftp://ftp.cdrom.com/pub/linux/slackware/source/d/binutils/ ftp://tsx-11.mit.edu/pub/linux/packages/GCC/ and look for something with a name like binutils-2.9.1.0.7.tar.gz. Avoid precompiled binary packages (which may have 'bin' in the name), you want the source code.
Unpack the binutils source code, go into the binutils directory (where the "configure" script is), and type:
./configure --host=i486-pc-linux-gnu --target=m68k-sun-sunos4
If you're building on a SunOS machine, type this instead:
./configure --host=sparc-sun-sunos4.1.4 --target=m68k-sun-sunos4
When the configure script finishes, type "make". When that finishes, it's time to install the new executables in your /usr/local directory. If you're a trusting soul, simply type "make install" (you'll probably need to log in as root for write access to /usr/local). If you're feeling more timid, just copy the two executables, like this:
mkdir /usr/local/m68k-sun-sunos4
mkdir /usr/local/m68k-sun-sunos4/bin
cp ld/ld-new /usr/local/m68k-sun-sunos4/bin/ld
cp gas/as-new /usr/local/m68k-sun-sunos4/bin/as
*** Configuring GCC as a 68k cross-compiler
Find the source for GCC and unpack it somewhere convenient. It is quite large. Notice that the top directory for GCC has a script called "configure". We'll use that shortly. This section assumes you have already built GNU binutils and installed 'as' and 'ld'.
Before building GCC, you'll want to generate a file called libgcc1.a and put it in the GCC top directory. Go into the GCC top directory and type:
cp ..../gunk-0.01/libgcc1.s .
/usr/local/m68k-sun-sunos4/bin/as -o libgcc1.o libgcc1.s
/usr/local/m68k-sun-sunos4/bin/ld -o libgcc1.a libgcc1.o
./configure --host=i486--linux --target=m68k-sun-sunos4
make
The make process will plod along, and eventually hit a problem of one sort of another. But we don't care because the cross-compiler has already been built. Now it's time to install the cross-compiler, so log in as root and type:
cp xgcc /usr/local/m68k-sun-sunos4/bin
cp cc1 /usr/local/m68k-sun-sunos4/bin
Examples of how to use the cross-compiler, cross-assembler, and cross-linker appear in Makefile.common, but here's a quick run-down. Suppose you have some C code in foo.c and some assembly language in foo2.s. Then you can type:
/usr/local/m68k-sun-sunos4/bin/xgcc -S foo.c
/usr/local/m68k-sun-sunos4/bin/as -a=foo.lst -o foo.o foo.s
/usr/local/m68k-sun-sunos4/bin/as -a=foo2.lst -o foo2.o foo2.s
/usr/local/m68k-sun-sunos4/bin/ld -T ./ldscript \
-o foo.srec foo2.o foo.o -Map foo.map
*** Address map
I had to make assumptions about the address map available to each processor. I've given each one 64K of program memory and a small, variable amount of data memory. You can change the data memory size as a command line option. Due to the assumptions about the programming environment for amorphous computing, program memory is the same for each of the processors. The memory map looks like this:
0x0 - 0x10000 program memory 0x10000 - 0x10400 data memory
(these are one byte wide)
0x400000 red color
0x400001 green color
0x400002 blue color
0x400004 sensor
0x400005 receive buffer
0x400006 transmit buffer
0x400007 carrier detect
(these are four bytes)
0x400008 timer
0x40000C random number generator
0x400010 X position
0x400014 Y position
0x400018 X size of swarm
0x40001C Y size of swarm
NOTE: Reading the X and Y positions and sizes is cheating! When the really cheap hardware arrives, processors will have no a-priori knowledge of their physical positions, or the size of the swarm they inhabit. They are blind, and can only infer their approximate positions from message-passing behavior, which is pretty noisy anyway.
If you decide you want to change the memory map (e.g. increase PROG_MEM_SIZE to get more program memory), make sure you update the 'ldscript' file, or otherwise inform the linker about the changes, so it will know where to put memory segments.
*** Acknowledgements
Thanks to:
Professor Sussman and his colleagues, for providing an interesting idea that has given me a lot to think about, and some entertaining coding to do.
Tan Phan and Jay Lloyd of North Carolina State University for their 68000 simulator. Nice clean code, easy to work with, and very nearly bug-free.
O'Reilly & Associates, Inc., for the examples in their books on X Windows programming. The xwin.c file evolved from examples in their books.
*** Things to do in future
The X Windows interface is pretty crude. It doesn't handle color palettes well, and there are no GUI controls, and there's no way to save screen shots.
It would be nice if Gunk could be built with other processors. The 8051 microcontroller is a very plausible candidate for early amorphous hardware. I have tried to keep the interface simple between the 68K simulator and everything else, to make this easier when I find either the source code for an 8051 simulator, or the time and energy to write my own.
It probably makes sense to add a transmit interrupt, which fires when the transmitter finishes shifting out a byte. Also, there might be another bit added to the communication status register, indicating that the transmitter is busy. Currently, writes to the transmit buffer actually pause the processor until the transmit buffer is empty, which is pretty cheesy.
Add some more interesting applications. Maybe some digital signal processing, or some kind of video hack, or dumb but pretty "gunk art" with flashing meaningless colors.