Physica D 666 (1992) 1–0 North-Holland, Amsterdam

PROGRAMMABLE MATTER: CONCEPTS AND REALIZATION

Tommaso Toffoli and Norman Margolus

MIT Laboratory for Computer Science

Cambridge, MA 02139, USA

Received 31 January 1990

Revised manuscript received 31 January 1990

This paper is a manifesto, a brief tutorial, and a call for experiments on programmable matter machines.

1. Introduction

After several years of issue analysis (see [?,?,?,?] and [?,?,?,?,?]), conceptual design[?,?,?,?,?,?], and hands-on experience with more modest realizations[?,?,?,?], we have finally embarked on the construction of cam-8, a scalable cellular automata machine offering unprecedented performance in the fine-grained modeling of distributed, spatially-extended systems.

Technically speaking, one could describe cam-8 as a fine-grained multiprocessor, and elaborate on design issues[?]. Here, however, we will concentrate on the most essential feature of the cam-8 architecture: it embodies the concept of programmable matter.

In programmable matter, the same cubic meter of machinery can become a wind tunnel at one moment, a polymer soup at the next; it can model a sea of fermions, a genetic pool, or an epidemiology experiment at the flick of a console key. Ten times as large a simulation will simply require ten cubic meters of machinery, instead of one. Flexibility, instant reconfigurability, variable resolution, total accessibility, and handling safety make such programmable matter worth a premium over ordinary matter.

All computers can realize programmable matter to some extent. The real question is whether the above features can be achieved today on a sufficiently large scale (in terms of spatial resolution and updating rate) and with sufficient flexibility (in terms of choice of the underlying fine-grained model) for the concept of ‘programmable matter’ to come to life. It is in this respect that cam-8, a machine optimized for fine-grained material simulations, has a role to play. In brief, cam-8 will provide a general-purpose instrument for the systematic exploration of a previously inaccessible region of the computational spectrum.

Our principal goal in this paper is to make the scientific community—physicists in particular— aware of the possibilities of this kind of instrument, and to invite suggestions for experiments that will make significant use of its novel capabilities.

2. Fine-grained models of matter

The properties of ‘gold’ as a material (for instance, specific weight, hardness, conductivity) are quite distinct from the properties of an isolated gold atom (atomic number, mass, spin, etc.). Certain statistical features emerge and become better and better characterized as we consider a larger and larger lump of gold; beyond a certain size, these bulk properties have stabilized enough that we can speak of ‘gold’ in a generic way, without having to specify the size or the shape of the lump. Similarly, if we consider an indefinitelyextended, uniformly interconnected network of identical personal computers, we will have defined

0167-2789/92/$03.50 \begin{matrix}c \\ ◯ \end{matrix} Elsevier Science Publishers B.V. (North-Holland)

T. Toffoli, N. H. Margolus / Programmable Matter 2

a synthetic “material” having well-defined bulk properties. These properties remain (to a good approximation) well characterized even when we implement only a finite—but sufficiently large— portion of the network. Connecting together three personal computers does not yield a larger personal computer—it yields a new kind of object; but joining together three large pieces of this material does yield a larger piece of the same material.

If we changed the network’s interconnection pattern, or if we replaced the processor at every node with a different kind of processor, we would obtain a different “material,” with potentially different bulk properties.

So far we have been speaking in rather metaphorical terms—we would really like our computer networks to be able to mimic real materials. With this in mind, lets consider certain aspects of our computer-network model more carefully.

– Fine grain. A personal computer contains a large amount of state. Even if it had only 256 bytes of memory (instead of a million or so), it would still be able to run programs having on the order of 2^{8·256} (≈10^{600}) distinct states—much longer (at one new state every microsecond) than the life of the universe. With so much potential for complexity hidden in each node, well-characterized bulk properties might emerge only on a scale spanning an astronomical number of nodes. To ensure that bulk properties emerge at a reasonably short scale (today we can build networks with millions or billions of nodes at most) the nodes must be very simple, i.e., to each node there must be associated just a few bits’ worth of state variables. This is what we mean by a fine-grained computing network. Our focus on fine-grained models is motivated, of course, by conceptual as well as practical considerations. By Occam’s razor, before resorting to complex building blocks one should try to synthesize complex behavior from simple building blocks.

– Polynomial interconnection. We have mentioned uniform, indefinitely-extended networks— i.e., networks whose geometry is invariant under an infinite group of transformations—but we have

Fig. 1. In the exponential network at left, the number of new nodes reachable in n steps grows as 2^{n}; in the polynomial network at right, it grows as n^{2}.

not mentioned what kinds of group we have in mind. The essential distinction, illustrated in Fig. ??, is between groups having exponential growth (the number of new nodes one can reach from a given node in n steps grows as a^{n}) and groups having polynomial growth (this number grows as n^{a}). Malthus’ centuries-old argument still holds: the physical world does not support indefinite exponential growth. One can conceive of an exponential architecture—say, a binary-tree network; but one cannot concretely implement it for an indefinite number of levels using uniform technological parameters (same wire size, clock rate, etc.) at all levels. In the end, the exponential structure will have to be embedded within a polynomial architecture—at most three-dimensional, to be specific. Our attention, therefore, will be restricted to polynomial networks that extend indefinitely in at most three spatial dimensions.

For concreteness, let’s give a simple example of the kind of synthetic “materials” we’d like to be able to program within a programmable-matter machine—namely, a fluid modeled by a lattice gas. The idea behind lattice-gas hydrodynamics is to model a fluid by a system of particles that move in discrete directions at discrete speeds, and undergo discrete interactions. In the HPP lattice gas[?], identical particles move at unit speed on a two-dimensional orthogonal lattice, in one of the

Fig. 2. In the HPP gas, particles colliding head-on are scattered at right angles (a), while particles crossing one another’s paths go through unaffected (b).

four possible directions. Isolated particles move in straight lines. When two particles coming from opposite directions meet, the pair is “annihilated” and a new pair, traveling at right angles to the original one, is “created” (Fig. ??a). In all other cases, i.e., when two particles cross one another’s paths at right angles (Fig. ??b) or when more than two particles meet, all particles just continue straight on their paths.

As soon as the numbers involved become large enough for averages to be meaningful—say, averages over spacetime volume elements containing thousands of particles and involving thousands of collisions—a definite continuum dynamics emerges. And, in the present example, it is a rudimentary fluid dynamics, with quantities recognizably playing the roles of density, pressure, flow velocity, viscosity, etc.

According to Pomeau, seeing this model of his running on one of our early cellular automata machines made him realize that what had been conceived primarily as a conceptual model could indeed be turned, by using suitable hardware, into a computationally accessible model: this stimulated his interest in finding lattice-gas rules which would provide better models of fluids. A landmark was reached with the slightly more complicated FHP model[?], (it uses six rather than four particle directions) which gives, in an appropriate macroscopic limit, a fluid obeying the wellknown Navier-Stokes equation, and thus suitable for modeling actual hydrodynamics (see [?] for a tutorial). Soon after, analogous results for threedimensional models were obtained by a number of researchers[?].

On what scale can one implement models of the above kind? Let ℓ be the linear size of the lattice, so that a three-dimensional lattice of roughly cubic shape will consist of ℓ^{3} nodes. Typically, the duration t (number of updates of the entire network) of a significant experiment will be at least one order of magnitude greater than ℓ (since macroscopic motion will be much slower than the maximum speed of information transmission in the computing medium). Taking t ≈ 10ℓ, the experiment will entail ≈ 10ℓ^{4} individual site updates, or events.

With today’s fastest general-purpose computers, fine-grained three-dimensional models of physically interesting phenomena (e.g., low-Reynolds-number hydrodynamics, diffusion in nonhomogeneous media, phase separation in twocomponent systems) can be updated at a rate of about 10^{8} events/sec[?,?,?]. Note that processing speed rather than memory size is the limiting factor; it is remarkable that machines with such different architectures as a Cray X-MP and a Thinking Machines CM-2 yield comparable performance in tasks of this kind.

With one day’s worth of computer time, or about 10^{5} sec, one obtains ≈ 10^{13} events, corresponding to ℓ ≈ 1000. This allows one to get a glimpse, but just a glimpse, at bulk dynamics. In fact, to arrive at bulk properties we typically have to average over volume elements containing (at least) a thousand sites, and thus having a diameter of (at least) 10 sites. If each of these volume elements corresponds to a “pixel” in the resulting macroscopic picture, with ℓ ≈ 1000 we are left with a picture having a resolution of only 100 pixels per side.

If an amount of electronic hardware (chips, wires, etc.) comparable to that in an X-MP or a CM-2 is reconfigured into an appropriate architecture—such as that of cam-8—one obtains a flexible computer capable of running this class of models at least two (and in many cases three or four) orders of magnitude faster. This means that each of the four factors in ℓ^{3}t can grow by up to one order of magnitude with respect to current computers, making new phenomena accessible to fine-grained simulation.

3. What is programmable in programmable matter?

Once you are satisfied that the above claims are valid, you may be tempted to say: “I’ll grant you a gain of a few orders of magnitude over a general-purpose computer; but of course—you must understand—yours is an extremely specialized piece of hardware, designed to do just one thing over and over.”

In fact, with a really dedicated machine—a VLSI implementation of a specific fine-grained model (think of a “silicon wind tunnel”)—one could easily gain many more orders of magnitude in performance (cf., e.g., [?]). Such a castin-concrete machine might eventually be able to play an important role in a production environment, but would probably be of much less use as a research tool. On the other hand, in spite of its definite specialization, cam-8 remains a widepurpose architecture.

With the benefit of hindsight, let us define programmable matter as a three-dimensional, uniformly textured, fine-grained computing “medium” having the following properties:

(1) It can be assembled into lumps of arbitrary size (the limits being given by economics rather than technology).

(2) It can be dynamically reconfigured into any uniform, polynomially-interconnected, finegrained computing network,

(3) It can be interactively driven, in the sense that its dynamical evolution can be started, interrupted, and resumed at any moment in response to the occurrence of specified internal or external events.

(4) It is totally accessible to real-time observation, analysis, and modification.

Cam-8 substantially meets all of the above specifications. Much of its flexibility derives from a careful compromise between parallel and serial processing. Briefly, the machine consists of a three-dimensional array of modules, with each module responsible for a certain “volume” of simulation space consisting of millions of sites (the actual number is 2^{n}, where n depends on the current dram technology and is, in the near term, in the range 22–24, corresponding to 4–16 million sites). Site updating within a module is performed serially, with all modules operating in parallel and in lockstep. Overall, the array of modules is controlled by a host computer (which may be a conventional workstation).

Total simulation volume, as in point (1), can be “programmed” by simply purchasing the appropriate number of modules. As for point (2), the programmability of cam-8 “matter” extends to the following features:

– Number of dimensions. The total simulation volume can be logically configured into an array having, besides the three main dimensions x, y and z which are indefinitely extendible, a number of extra dimensions of bounded size. This number is, of course, limited by the fact that the product of the sizes along all dimensions cannot exceed the total volume of programmable matter available, and the product of the sizes of the extra dimensions cannot exceed the volume of a module.

– Aspect ratio. Within the above bounds, the size of each dimension is independently adjustable (by powers of 2), so that one can choose, for instance, a square array or a long-and-thin one.

– Interconnectivity. Direct communication between sites is not restricted to first neighbors in the array. For a given number of dimensions d and aspect ratio, there is defined a d-parallelepiped of volume slightly greater than 2^{n+d} centered on the given site, such that any site within that volume can be chosen as a neighbor. For example, in two dimensions, and with n = 22, at each step a site can have neighbors anywhere within a 4K×4K square; in three dimensions, and with n = 24, anywhere within a 512×512×512 cube. Furthermore, by slowing the simulation down by a factor k, the diameter of the neighborhood can be increased by a factor of k. This rich interconnectivity is the most significant innovation of cam-8: earlier cellular automata machines were handcuffed by the limitations of “canned’ neighborhoods (cf. [?] and [?]). Now one can perform three dimensional simulations, synthesize a variety of spacetime “crystallographic groups,” and use widely different speeds of propagation of information within the same simulation (e.g., fast “photons” and slow “electrons”).

– Amount of state per site. For a given overall number of bits of state, one can trade off number of sites for number of bits per site.

– Transition function. In the current implementation, the local transition function, that is, the rule used to update a site as a function of its neighbors, is determined by a lookup table, and thus can be assigned in an arbitrary way. This lookup table is double-buffered, so that a new table can be downloaded while an updating step is in progress, in preparation for a subsequent updating step that will use a different rule. The size of the lookup tables is currently 16×2^{16}, corresponding to 16 inputs and 16 outputs, and thus direct lookup can be used as long as the amount of input to a node does not exceed 16 bits. For a state-variable set larger than that, graceful degradation occurs as one makes more and more recourse to table composition.

– Serial/parallel ratio. Finally, the same number of physical processors can be concentrated on relatively few sites, for maximum speed, or shared by many sites, for maximum simulation size. Intermediate choices are of course possible.

4. Programmer’s model

The generality of cam-8’s programmable matter is reflected in a very simple “programmer’s model” for the machine.

We are all familiar with representing the history—and thus the evolution—of a system by a spacetime diagram: a cycle-free directed graph whose arcs represent signals and whose nodes represent events in spacetime (Fig. ??a).

Cam-8 supports spacetime diagrams that are uniform and fine-grained (Fig. ??b). Uniform means that the layout of arcs and nodes is invariant for spacetime translations; of course, the values of the signals will in general change from place to place. Fine-grained means that only a small number of signals can interact at each event, and each signal has a small set of available states. (In fact, in cam-8 all arcs carry binary signals; more complex signals can, of course, be synthesized by bundling together a few arcs.)

Fig. 3. (a) A spacetime diagram, consisting of signals (arcs) and events (nodes). (b) A uniform spacetime diagram.

The operation of cam-8 is simply the steady unfolding of such a uniform and fine-grained spacetime history.

Basically, all one has to do to program cam-8 is

– Signals. Specify the diagram’s interconnection pattern. Since the diagram is uniform, it is enough to specify the geometry of a “primitive unit cell.” This, in turn, is simply given by a list of neighborhood vectors, one for each of the arcs that impinge on a node, specifying where each arc comes from.

– Events. Specify the event’s transition function, i.e., for each possible combination of states for the signals that converge to an event, specify the desired combination of states for the signals that radiate out of it. (Note that, by construction, there is exactly one output signal for each input signal.)

– Initial conditions. Assign the values of the signals that cross a spacelike surface, typically of the form t_{0} = const (cf. Fig. ??).

For example, for the diagram of Fig. ??, which represents the time evolution of a one-dimensional system, the neighborhood vectors are (−2), (0), (+1), and (+1), since the four signals converging on any event at time t originate from events at time t − 1 that are offset by those amounts with respect to the destination event.

Fig. ?? illustrates the spacetime layout for the HPP gas mentioned in the previous section. The four directions of travel for the particles are labeled a, b, c, d, and the transition function is la-

Fig. 4. A spacetime diagram with four input signals associated with each event.

beled f. For this system, the neighborhood vectors are

\begin{matrix}a : & (−1, −1) \\ b : & (+1, −1) \\ c : & (+1, +1) \\ d : & (−1, +1) \end{matrix} ,

and the transition function f is given by the table

\begin{aligned}& in & out \\ & abcd & abcd \\ & 0000 & 0000 \\ & 0001 & 0001 \\ & 0010 & 0010 \\ & 0011 & 0011 \\ & 0100 & 0100 \\ ∗ & 0101 & 1010 \\ & 0110 & 0110 \\ & 0111 & 0111 \end{aligned}  \begin{aligned}& in & out \\ & abcd & abcd \\ & 1000 & 1000 \\ & 1001 & 1001 \\ ∗ & 1010 & 0101 \\ & 1011 & 1011 \\ & 1100 & 1100 \\ & 1101 & 1101 \\ & 1110 & 1110 \\ & 1111 & 1111 \end{aligned}

where 1 represents the presence and 0 the absence of a particle on a particular spacetime track. Note that in only two cases (marked with an asterisk) out of sixteen does an interaction take place; in all other cases, each signal proceeds undisturbed.

Uniformity of structure at the hardware level does not mean, of course, that one cannot have properties in the modeled system that vary from place to place.

For instance, we may want to study turbulence by letting a fluid flow past a solid obstacle. Then one bit at each site will be used as a parameter (left unchanged by the transition function) specifying whether that site belongs to the obstacle or to the space occupied by the fluid. Depending on the value of that bit, different sections of the lookup table, and thus different laws, will be activated.

Similarly, by using extra state at each site, one can model systems with sources and sinks, potential wells, lenses, etc.[?,?], and even systems in which the initial conditions are specified on a spacelike surface which isn’t flat[?].

In the next section we’ll briefly mention other ways of “modulating” in space or time (or both) the structural parameters of the computing network.

Finally, a few words about data analysis. Cam-8 will generate new data at a steady rate of about 0.5 Giga-bits/sec per module. Of course, one can always suspend the simulation for a moment and read out the entire state of the system (“core dump”), but this involves a lot of data transfer and puts the entire analysis burden on the host. In ordinary circumstances one would want data selection, compression, and extraction to take place continuously, in real time, and without significantly interfering with the updating itself. Therefore, flexible resources for low-level data reduction must be built-in, and must grow in direct proportion to the size of the system.

We have seen that the transition function is responsible for producing the output signals of an event as arbitrary functions of its input signals. Using the same machinery, one can produce additional binary outputs, each telling whether the input signals represent an occurrence of an arbitrarily specified condition (for example, whether there is a collision involving an even number of particles). The number of these occurrences is integrated over selected portions of space and time (for this, we take advantage of cam-8’s flexible scanning order, as explained in the next section); the corresponding counts, accumulated by dedicated hardware counters, are made available to the host computer.

For instance, for a lattice gas, one can subdivide the array into a number of volume elements each containing a few thousand sites, and (in par-

Fig. 5. Spacetime layout of the HPP gas.

allel with the updating) tabulate the total number of particles moving in each direction in each step—thus constructing a macroscopic picture of the flow. Instead of many Giga-bits/sec of finegrained detail (which is, in a sense, an artifact of this type of model), the host will see only the relevant hydrodynamical data—at a rate a few thousand times slower than the raw data rate.

5. Implementation notes

To give the reader a feeling for quantitative aspects of cam-8’s modeling environment, we shall briefly discuss how some of the functional behavior described in the previous section is achieved in practice. This section may be skipped without loss of continuity; a more detailed discussion of the hardware appears in an earlier paper[?].

Consider a regular array of bits that extends indefinitely in all directions (for concreteness, you may think of a two-dimensional array—a “bitplane”); we shall call such an array a layer. We will now superpose, in good registration, a number p of layers—so that at each site we have a pile of p bits. This entire collection of bits will be made to evolve by repeated application of the following procedure, called a step, consisting of two stages:

– Data movement. Each layer is independently shifted as a whole by an arbitrary number of positions in an arbitrary direction. We still end up with a pile at each site, but with a new make-up.

– Data interaction. We now take each pile and we send it to a p-input, p-output lookup table; the lookup table returns a new pile, which we put in place of the original one.

Note that at the interaction stage each pile is processed independently, so that the order in which the piles are updated is irrelevant. We could even have several copies of the lookup table, and do some (or all) of the processing in parallel. Also note that, at the data movement stage, the shift performed on each layer is a uniform and datablind operation (each bit is moved by a fixed offset, quite independently of its position and its value); thus, it becomes possible, in a suitable implementation, to replace this operation by one that shifts the frame of reference (by incrementing a single pointer) rather than moving the data themselves.

There is an obvious one-to-one correspondence between a dynamics specified in this way and one defined by a uniform, fine-grained spacetime diagram as in the previous section. For example, in Fig. ??, all the arcs labeled a make up a layer (and similarly those labeled b, c, and d); the corresponding neighborhood vector (−2) specifies the amount of shift of this layer at the data movement stage. Events represent the data interaction stage: still referring to Fig. ??, the four arcs entering a node represent the make-up of a pile just before being given to the lookup table, and the four arcs leaving it, the pile as it comes out of the lookup table.

The present way of specifying a dynamics in terms of movement of layers and updating of piles closely reflects cam-8’s hardware organization, briefly described below.

It will be convenient to consider for a moment layers that wrap around on themselves along each dimension (the topology is that of a hypertorus) and so have finite size. In a cam-8 module, there are p = 16 of these layers, each represented by a separate dram chip. To implement the data interaction stage, these chips are sequentially scanned in lockstep, site by site, providing a 16-bit pile (one bit per layer) at every clock cycle. The lookup table is implemented by a sram chip (16 inputs, 16 outputs) which accepts a pile at every clock cycle (30 nsec) and returns new piles at the same rate. Each new pile is deposited back where the corresponding old one came from, again one bit per layer. One complete scan represents one updating step for the entire volume encompassed by the module.

To visualize the scanning order, think of a nested do-loop, with one nesting level for each spatial dimension. Each of the indices of the loop deals with one component (x, y, etc.) of the site address, and drives a separate subset of the dram address lines. The state of the complete set of these lines represents the current site address. The “volume” represented by the dram chip is shaped into the desired number of dimensions and aspect ratio (cf. Sect. 2) by altering the parameters of the do-loop.

Now, even though the same site address is intended for use by all 16 dram chips, we route a separate copy of these lines to each individual chip. This allows us, by inserting an adder stage in the address path, to add a different offset to the site address for each chip. This offset determines from where—along each dimension—the scanning of the chip’s internal data will actually start. As far as the stream of data that comes out of the chip during an updating step is concerned, changing the offset is equivalent to shifting the entire contents of the chip. This mechanism, then, implements the data transport stage.

More specifically, the current offset is kept in the layer’s offset register, which is incremented before each updating pass by the value of that layer’s neighborhood vector (cf. previous section), which is kept in the kick register. All these registers have the same width as the site address, and like it are subdivided into sections each corresponding to one spatial dimension. Addition is performed independently on each section, i.e., the carry is inhibited at the boundary between one section and the next. (This splitting of the site address is simply controlled by the dimension register, each of whose bits, when set, inhibits carry propagation at the corresponding position in the adders.)

The above discussion explains the operation of a single module, with space wrapped around within the module itself. When we lay an indefinite number of modules side-by-side in order to achieve an arbitrarily large spatial extent, we must cut open the individual pieces of space and glue them edgeto-edge. Because each module is updating only one cell at a time, only 16 wires are required to glue two adjacent modules together—one per layer. To understand the basic technique, think of a one dimensional chain of modules. When a given layer is shifted by less than the width of a module, all of the new data for a given module comes either from what is already inside of that module, or from one of its nearest neighbors—via a connecting wire. Moreover, since all of the layer shifts in the same direction, each interconnection need only carry data in one direction. By updating the shifted data before storing it away, we can combine the shift and the update, just as in the single module case.

The fine-grained dynamics of cam-8 is completely determined by the contents of the lookup table (1 Mbyte of sram) and the neighborhood vectors (a few bytes stored in the kick registers). Typically, this information will be the same for all modules. By rewriting tables and vectors, one gets a new dynamics. This can be done at every step, thus obtaining an arbitrarily time-dependent dynamics.

Since scanning order is under our control, we can even scan, for instance, all even-positioned sites first; then change the dynamics, and scan all odd-positioned sites. As long as the number of sites scanned between changes is large compared to the number of changes in the lookup table, this way of modulating the spatial aspects of the dynamics entails little or no overhead. Thus, it becomes possible to use “checkerboard” dynamics (one rule for black, one for white) and similar coarser-grained spacetime textures for the dynamics. More complicated textures can be obtained in a similar manner by using the extra dimensions discussed earlier to group bits together: using a time-dependent dynamics allows one to perform arbitrary function compositions on these groups.

Finally, a few words about efficiency. The two main resources needed by any simulation model are memory, for the state variables, and processing, for the updating of these variables. Finegrained models offer great conceptual simplicity and the sincerity that comes from relying as far as possible on first principles; but, in exchange, they demand very large amounts of memory and processing resources.

As we have seen, cam-8 is able to use ordinary dram chips for its state variables. These chips are today an inexpensive commodity, and allow one to go further, in terms of simulation size, than any other practical alternative. Similarly, the cam-8 architecture is able to use ordinary sram chips for processing; these too are a relatively inexpensive commodity, and allow one to go far in terms of processing power. The “glue” that turns these raw commodities into programmable matter is a gate array of moderate complexity (≈ 10K gates), 16 copies of which go into each module.

A clock period of 30 nsec will use 30-nsec sram chips at full bandwidth. While the contents of a pile, which is used as an address to the sram, is essentially unpredictable, the bits within the dram chips are accessed in a predictable sequence; thus, one can make use of nybble-wide drams, for which, as long as one remains in the same memory row, four consecutive bits can be read and four written in 120 nsec, i.e., in four clock cycles. Therefore, this organization allows one to use storage and processing resources at full bandwidth on a closeto-100% duty-cycle.

Independently of the number of modules, the updating rate for the model as a whole will range from 8 steps per second (when all of a module’s dram capacity is actually allocated to sites) to thousands of steps per second (when, for sake of speed, each lookup table is time-shared over thousands rather than millions of sites).

Though we have in mind substantial installations consisting of hundreds or thousands of modules—with a processing power of up to a few Tera-events/sec—we are also developing a minimal, two-module version (66 Mega-events/sec, 8 Mega-sites), suitable for individual interactive experimentation, with a hardware complexity and cost comparable to that of an inexpensive workstation computer. Such a machine will act as its own frame buffer, able to synchronize its scan with the beam of various raster-scan monitors so that, for instance, the contents of a module scanning a 512×512 array can be viewed in real time at 60 frames/sec, and 1024×1024 at 15 frames/sec.

6. Conclusions

We have presented a hardware structure that is optimized for the fine-grained simulation of spatially-extended physical systems. There is the attractive possibility, in the near term, of achieving systems consisting of hundreds of billions of sites, updated a few times per second. Likely applications will immediately come to mind to any scientist who has worked with lattice models; many other scientists are already aware, at least in a vague way, of the possibilities that lie behind such a tool.

The simplicity of cam-8’s functional description does not, of course, mean that physical modeling is thereby made trivial. It should, however, spare those attempting to implement fine grained neighborhood models the significant effort needed to twist such models to fit conventional architectures efficiently. This, together with unprecedented computing power, should make such models attractive to a wide range of disciplines.

The book [?] illustrates a variety of modeling techniques suitable for the modeling environment discussed here. Much of the recent literature on cellular automata and lattice gases discusses specific fine-grained models of physics-like systems, and thus provides a wealth of examples.

The reader should be aware that our main interest is in the fundamental connections between physics and computation, and one of the reasons we developed cam-8 is to work on certain questions in that area (cf. [?,?]). As theoretical material scientists—for one—we are mere amateurs, and undoubtedly many of the most obvious applications of cam-8 have not yet come to our attention. For this reason, we solicit proposals for imaginative and demanding experiments to be performed on this machine—on themes spannining physics, mathematics, and computer science— that will allow us to exercise its design, possibly avoid costly mistakes or omissions, and help make hardware, software, and methodology accessible to more people in a shorter time.

7. Acknowledgments

This research was supported in part by the Defense Advanced Research Projects Agency (N00014-89-J-1988), and in part by the National Science Foundation (8618002-IRI).

References

[1] Bennett, Charles, Margolus, Norman, and Toffoli, Tommaso, “Bond-energy variables for Ising spin-glass dynamics,” Phys. Rev. 37B (1988), 2254.

[2] Boghosian, Bruce H., Washington Taylor, and Daniel Rothman, “A cellular-automaton simulation of two-phase flow on the CM-2 computer,” in Proc. “Supercomputing ’88,” vol. 2: Science and Applications (ed. J. Margin and Stephen Lundstrom), IEEE (1989), 34–44.

[3] Boghosian, Bruce, personal communication.

[4] Clouqueur, André, and Dominique d’Humières, “RAP1, A cellular automaton machine for fluid dynamics,” Complex Systems 1 (1987), 585–597.

[5] Chopard, Bastien, “A cellular automata model of large scale moving objects,” to appear in J. Phys. A.

[6] Despain, A., “Prospects for a lattice-gas computer,” Lattice-Gas Methods for Partial Differential Equations (Gary Doolen et al., ed.), Addison-Wesley (1990), 211–218.

[7] Frisch, Uriel, Brosl Hasslacher, and Yves Pomeau, “Lattice-Gas Automata for the Navier-Stokes Equation,” Phys. Rev. Lett. 56 (1986), 1505–1508.

[8] Frisch, Uriel, et al., “Lattice gas hydrodynamics in two and three dimensions,” Lattice-Gas Methods for Partial Differential Equations (Gary Doolen et al., ed.), Addison-Wesley (1990), 77–135.

[9] Hardy, J., O. de Pazzis, and Yves Pomeau, “Molecular dynamics of a classical lattice gas: Transport properties and time correlation functions,” Phys. Rev. 13A (1976), 1949–1960.

[10] Hasslacher, Brosl, “Discrete Fluids,” Los Alamos Science, Special Issue No. 15(1987), 175–200 and 211– 217.

[11] Margolus, Norman, “Physics-like models of computation,” Physica 10D (1984), 81–95.

[12] Margolus, Norman, “Physics and Computation” (Ph. D. Thesis) Tech. Rep. MIT/LCS/TR-415, MIT Laboratory for Computer Science (1988).

[13] Margolus, Norman, “Cellular Automata Machines— A New Environment for Modeling,” in the proceedings of the 1988 Rochester Forth Conference (L. Forsley ed.), Institute for Applied Forth Research (1988).

[14] Margolus, Norman, Toffoli, Tommaso, “Cellular Automata Machines,” Complex Systems 1, 967–993 (1987).

[15] Margolus, Norman, Tommaso Toffoli, “Cellular Automata Machines,” revised version of [?], in Lattice-Gas Methods for Partial Differential Equations (Gary Doolen et al., ed.), Addison-Wesley (1990), 219–249.

[16] Margolus, Norman, Tommaso Toffoli, and Gérard Vichniac, “Cellular-Automata Supercomputers for Fluid Dynamics Modeling,” Phys. Rev. Lett. 56 (1986), 1694–1696.

[17] Shimomura, T., G. Doolen, B. Hasslacher, and Castor Fu, “Calculations Using Lattice Gas Techniques,” Los Alamos Science, Special Issue No. 15 (1987), 201–211.

[18] Smith, Mark, “ Representations of geometrical and topological quantities in cellular automata,” submitted to Physica D (***CA issue?***).

[19] Toffoli, Tommaso, “Cellular Automata Mechanics,” Tech. Rep. 208, Comp. Comm. Sci. Dept., The University of Michigan (1977), 255 pp.

[20] Toffoli, Tommaso, “CAM: A high-performance cellular-automaton machine,” Physica 10D (1984), 195–204.

[21] Toffoli, Tommaso, “Cellular automata as an alternative to (rather than an approximation of) differential equations in modeling physics,” Physica 10D (1984), 117–127.

[22] Tommaso Toffoli, “Frontiers in Computing,” Information Processing (G. X. Ritter ed.), North-Holland (1989), 1.

[23] Tommaso Toffoli, “How cheap can mechanics’ first principles be?” to appear in the proceedings of the workshop Complexity, Entropy, and the Physics of Information, Santa Fe Institute (April 1989).

[24] Toffoli, Tommaso, “Four topics in lattice gases: Ergodicity; Relativity; Information flow; and Rule compression for parallel lattice-gas machines,” Discrete Kinetic Theory, Lattice Gas Dynamics and Foundations of Hydrodynamics (R. Monaco ed.), World Scientific (1989), 343–354.

[25] Toffoli, Tommaso, “Cellular automata machines as physics emulators,” in Impact of Digital Microelectronics and Microprocessors on Particle Physics (M. Budinich et al., ed.), World Scientific (1988), 154– 160.

[26] Toffoli, Tommaso, and Norman Margolus, Cellular Automata Machines—A new environment for modeling, MIT Press (1987).

[27] Toffoli, Tommaso, and Norman Margolus, “A review of invertible cellular automata,” submitted to Physica D. (***CA issue?***).

[28] Vichniac, Gérard, “Simulating physics with cellular automata,” Physica 10D (1984), 96–115.