Next: Call for proposals Up: CA research Previous: Collaborations

CA algorithms

One of our own most interesting new CA algorithms is a new technique for rotating three-dimensional bit-map data (Fig. 2). This is particularly effective on CAM-8 since the basic operation is a shear, which this machine can implement very efficiently.

Our CAM-8 prototype has provisions for direct camera input. An example of realtime image processing performed with CAM-8 is shown in Fig. 3. The left half of the image reflects raw data coming from the camera, the right half has been subjected to an entropy-maximizing re-binning of the pixel values in order to improve image contrast. Our small prototype can do a significant amount of image processing in real-time: it can perform about 1600 updates per second of a 512image, with an arbitrarily chosen lookup-table algorithm and complex spatial data reshuffling at every update.

Another interesting new algorithm is a generalization of our wavefront-volume-rendering algorithm. The image on the title page is a simple example of the kind of CA volume rendering that we've been doing since 1988 (cf. our CAM-8 flipbook). It was produced on CAM-8 in real-time: while a 3-D Ising dynamics governs the evolution of the matter, we continuously produce and display rendered images without appreciably slowing down our simulation. Each rendered image is constructed by sweeping a wavefront of ``light'' down through the sytem, as the processors sweep through to perform a single update of the matter. A second sweep brings reflected light forward, again while the matter is updated, and the resulting 2-D image is displayed.

More generally, a spatially organized virtual-processor machine such as CAM-8 can efficiently perform a variety of wavefront calculations: calculations that can be laid out in an -dimensional space in such a way that we're only interested in the evolution of a wavefront through the space. This can be viewed as a way of performing calculations on CAM-8 that aren't uniform in space or in time. Functional simulation of synchronous logic provides a good example of such a wavefront calculation: a synchronous circuit is laid out in -dimensions so that the direction of dataflow is always positive along one of the dimensions, and then we simulate each clock of the synchronous circuit by sweeping the signal wavefront through this dataflow-dimension once. Since the dataflow-dimension is virtual, it can be thought of as holding the time-dependance information for an dimensional spatial calculation, and so this is really just a generalization of static routing to arbitrary space-time logic. This technique has immediate application to the design of virtual-processor FPGA chips.

Finally, one of our new Physics Ph.D.'s this year was Mark Andrew Smith, who wrote his thesis on ``Cellular Automata Methods in Mathematical Physics.'' This thesis includes a number of important new techniques for modeling physical systems with cellular automata, and also a very interesting technique for getting the most out of the efficient random-variable-generating capabilities inherent in the CAM-8 architecture.

Figure 2

Figure 3

Next: Call for proposals Up: CA research Previous: Collaborations
Wed Jul 27 11:18:54 EDT 1994