Massachusetts Institute of Technology Laboratory for Computer Science

CAM-8:

A uniform, scalable multiprocessor

Claims information for patent purposes

Prepared by Norman Margolus

Contents

i

Prefaced with appropriate background material, we present a list of the claims that we would like to include in our patent application related to our cellular automata work, along with a somewhat detailed description of the ideas (including our present plans for best implementation).

1 Background

As the basis of a computer architecture, cellular automata[?, ?, ?, ?] have much to recommend them: they are a local and uniform paradigm ideally suited for implementation in terms of highly parallel digital hardware. The basic cellular automaton (CA) model consists of an array of simple processors distributed uniformly in space, each communicating only with nearby neighboring processors. Each processor contains a small amount of state information (a cell) that is updated iteratively as a function of the state of neighboring processors.

Unlike more “sophisticated” approaches to massively parallel computation, in CA there is no difficulty associated with coordinating the activities of the processors or dividing up the task. The computation is mapped identically onto the action of the processors, and the burden of making effective use of this approach is shifted entirely onto the task of finding CA “rules” for the processors that perform computations of interest. In return for formulating computations in this format, the user is rewarded with the availability of massive computing power that cannot be made available in any other way: the locality of interconnections permits extremely fast iterations, and also allows the number of processors to be scaled astronomically.

1.1 An example

Cellular automata rules are sometimes arrived at by deliberately stylizing microscopic physics[?, ?, ?, ?, ?, ?, ?, ?, ?, ?, ?, ?, ?]. For example, Pomeau[?] constructed a simple lattice gas (known as the HPP gas) as follows:

Particles move on a Cartesian lattice, all at unit speed (one cell per time step) and in one of the four principal lattice directions. All particles are identical, and when two particles collide head-on, they come out at right angles to their original motion—in all other cases, particles move straight.

To implement this lattice gas as a cellular automaton, we must formulate it as a rule that applies to cells. This can be done as follows:

Cells are arranged in a rectangular mesh, with nearest neighbor interactions. Each cell contains 4-bits of state information—one bit for each of the four possible particle directions. For each of these bits, a 1 indicates the presence in that cell of a particle moving in the corresponding direction, a 0 indicates the absence—thus each cell can contain up to four particles. Updating is a two stage process: first we move each particle one position in the appropriate direction, and then we update the contents of each cell. These two stages are repeated alternately in order to produce a dynamical evolution corresponding to our stylized physical model.

The movement of data can be visualized as four bit-planes, each of which is shifted as a unit. All of the bits corresponding to particles moving right would constitute one of the bit-planes: by shifting this sheet of data bits one position to the right, we would cause all appropriate particles to move one position right. The other three kinds of bits are treated similarly.

The updating of cells is a process that involves looking at the contents of a given cell, and changing it according to our rule. If we have both a rightmoving and a left-moving particle in a given cell, and no other particles, then this is a head-on collision. In this case, the new contents of the cell should be particles moving in the other two directions, and no other particles. All cases in which there is no head-on collision should leave the cell contents unchanged, so that particles moving in a given direction continue to move in that direction.

In Figure ?? (taken from reference [?]) we illustrate the propagation of a “sound” wave in this lattice gas—note that despite the discrete velocities of the individual particles, the sound wave is circular. Slightly more complicated lattice gas models such as the FHP model[?, ?] (which involves six particle directions, rather than four) and related models[?] can be used for realistic simulations of fluid flows[?, ?, ?, ?, ?].

The HPP lattice gas model will be a good example to keep in mind in Section ?? where we describe the architecture of cam-8, as this is the sort of model that maps most directly onto the architecture of this machine.

Figure 1: A sound wave in the HPP lattice gas. In (a) we have a random distribution of particles on a 256×256 lattice, with a clump of a few thousand particles in the center. In (b) and (c) we see snapshots of its subsequent evolution, at about 30 and 90 steps respectively.

1.2 Partitioning cellular automata

A scheme such as the HPP lattice gas discussed above in which we partition the bits in our cellular space into disjoint groupings which are updated separately we call a partitioning cellular automaton (PCA). Such CA are convenient for modeling physics, since each block of the partition is a little window in which we can specify which scene follows a given scene (in the lattice gas example, we were able to easily include particle conservation, momentum conservation and microscopic reversibility into our model). PCA are also convenient in terms of hardware, since each bit of the current state is accessed exactly once in the process of constructing the new state (makes efficient use of memory bandwidth to cell state), and each block of the partition is updated separately from every other block (allowing blocks to be updated in any order).

Unlike PCA, conventional CA are unconstrained in their use of neighbor bits. They are close kin to finite difference equations: the new state of a given cell is (in general) a function of all of the bits in some group of neighboring cells. This means that each cell-bit is (in general) used as a neighbor by several other cells during each updating step, and so unless all cells are updated simultaneously we cannot simply replace the contents of a given cell with its new value: we must keep a copy of its old value available for use by neighbors until they have all been updated. This extra data buffering, along with increased memory bandwidth demands needed in order to access each cell bit several times during each step are disadvantages from a hardware point of view.

Since conventional cellular automata can be efficiently embedded into PCA (cf. Footnote ?? and reference [?]) and since PCA are both more natural for the sorts of physics-minded models we are most interested in and much better suited for being turned into hardware, we made the decision to base cam-8 on PCA.

2 CAM-8

In light of current technological constraints and opportunities, we have designed a machine which simulates fully parallel CA, and hence inherits their scalability and natural parallelism. Our machine, however, has far fewer processors than cells—each processor is time-shared among a large number of cells. This allows us to use more flexible processors suitable for general purpose experimental work (we actually use large static-RAM lookup tables as processors in our design) and allows us to use commercial memories intended for serial machines for storage of state information.

Our machine continues to be a uniform array of processors, but in our case each processor handles a million cells. Our 16-bit cells are stored in banks of 16 1-megabit DRAMs, and wires interconnecting processors are time shared just as the processors themselves are, so that we reduce the number of wires needed for interconnect by a factor of a million, as compared to a fully parallel approach. Of course we also slow the machine down by a similar factor, and so we are emphasizing size over speed; but by simply having each processor only handle a portion of its cell memory (leaving the remainder unused) we can achieve much greater speed in those applications that require speed rather than size.

3 Our claims

What we claim is new in all of this is the scheme we have come up with for bringing neighbor bits together in a way which allows us to have a rich variety of neighbor choices while retaining the millionfold saving in interconnect made possible by time-sharing the processors, and while also permitting the use of commodity DRAM chips for the cell state memory. This scheme involves two ideas: virtual shifts (instantaneous data movement within each processing module achieved by pointer manipulation), and gluing (zero-overhead inter-module communication made possible by lockstep processing). Both of these techniques only become available to an architecture based on PCA (which we are the first to recognize as a distinct class of CA) and for this reason we believe their application to parallel computation to be new.

Unlike traditional CA, PCA permit great freedom in the order in which cells are updated, and we take advantage of this property in our architecture for display and analysis purposes. Again because of the novelty of PCA, we believe that the schemes we have come up with for allowing our machines to provide realtime display and analysis of the simulation being run are also new.

Finally, our machine is made out of modules and can be expanded by simply adding more modules in order to simulate larger spaces of cells with no increase in the time required to update every cell of the space once. Similarly, smaller machines composed of just a few modules can run the same simulations as the biggest machines, but only scaled down to involve fewer cells. Thus small simulations developed inexpensively using a few modules can be transferred without change to run on large machines—this allows the interactivity and ease of program development of a personal computer to be coupled to the raw computing power of cellular automata supercomputers. Since such scalabilility is new, this property is also new (whether such an idea is patentable I don’t know).

In addition to these claims based on the design of cam-8, in Section ?? we discuss some other possible claims that we might make based on various extensions and variations of cam-8 ideas.

3.1 Virtual shifts

In cam-8, cell data is processed within each module in a sequential fashion: all of the data movement (within modules) required by PCA can be accomplished by controlling the order of data accessing. Since control information can be set up for the next scan of the data array while the current scan is running, this data movement doesn’t slow down the simulation.

More specifically, in our design each processor is responsible for the updating of an array consisting of a million 16-bit cells. The array handled by a single processor can in principle be organized in any number of dimensions, just as it could be in an ordinary digital computer. In our machine, the cell array is divided up physically into 16 bit-arrays: each bit-array contributes one bit to each cell.

Cell memory is updated as follows: each bit-array is scanned separately, and the resulting groups of 16 1-bit values are the cell values presented to the processor for updating; 16-bit results are inserted back into the cell array. We control the groupings of bits which get presented as a unit to the processor by controlling the relative order of scanning the different bit-slices.

In the cases of greatest interest, the cell array as a whole is scanned as a two or three dimensional matrix in a fixed order. If all bit-slices were scanned in the same order, we would simply present the individual cells to the processor as isolated 16-bit systems. Instead, we consider the contents of each bit-slice to be a spatially organized object (a sheet in 2-dimensions, or a block in 3-dimensions) and bodily shift this object by controlling our scan.

For example, in two dimensions we have 16 bit-planes which can be imagined as 16 sheets of graph paper lying one on top of another, with each square on the paper representing a single bit of a cell. A shift of one of these sheets with wraparound (i.e., as bits are shifted out one edge, they reappear at the opposite edge) corresponds to one particular relative order of scanning the bit slices. Such shifts only involve a decision about how to scan, rather than the movement of any actual data, and so we refer to them as virtual shifts.

Returning to our HPP lattice gas example of Section ??, we can directly implement this model on cam-8 by using 4 bit-planes and virtual shifts of one position. Similar rules (such as FHP and its relatives) involving more particle directions and speeds can be realized by simply using more bit-planes and other virtual shifts.

Figure 2: Gluing modules together: a 1-dimensional analogy. To shift left by 3 positions,

(1) data in alphabetical order in 4 modules is (2) rotated within each module. Shaded data should have shifted into adjacent modules for a true shift, and in (3) it is used by neighboring modules at the appropriate moment.

3.2 Gluing

What remains is the heart of our design: the method used to tie all of the processing modules in our machine into a single uniform cellular computation without slowing the individual modules down.

In a machine consisting of many modules, each module will produce a window onto a chunk of a larger space, with the various bit-slices of this larger space shifted relative to one another. Each module will be responsible for updating its own chunk of this space: the cells of the chunk are presented— one at a time—to the processor, and the result is inserted into the cell-state memory belonging to that module.

Thus it is really only the cells that need to be “glued” together into a uniform space in such a way that each module sees a section of this space— the updating is then straightforward.

If data is to shift between modules, clearly they must be physically interconnected: in our design, modules are connected together to form a uniform three dimensional array. Each module is connected to each of its six nearest neighboring modules (in three dimensions) by 16 wires—enough to make one cell of each of the neighboring modules visible to the given module. Now in order to show a window into a shifted (and glued) bit-slice, each module simply gets data from adjacent modules as needed.

This gluing technique is illustrated in Fig. ?? using a one dimensional analogue. In (1) we show a 16-cell space, with each cell containing a letter of the alphabet. The cells are divided up evenly among four modules, and we wish to shift all of the data 3 positions to the left, with wraparound. In (2) we show each module with its own data internally shifted 3 positions to the left with wraparound internally—the three letters that should have shifted out of the left hand side of each module have been reinjected into the right hand side. Note that each letter has moved the correct amount for the desired shift; the shaded letters are simply in the wrong modules. Now in (3) we make use of the wires interconnecting the modules. As each module scans its data, presenting items one at a time for processing, each module simply borrows the data from the module to its right at the appropriate moment by substituting cell values scanned by the neighboring module for internally scanned values—the arrows indicate the direction of data movement. Note that because of the cyclic shifting within each module, data that one module needs to borrow is made visible by the neighboring module at exactly the moment in the scan when the data is needed—thus there is no slowdown or buffering overhead involved in coordinating the communications activities of the various modules needed for gluing.

In an exactly analogous manner, cam-8 modules are glued together one dimension at a time by a combination of internal shifts with wraparound and data source multiplexing. The internal shifts are achieved exactly as described in the previous section, and there are three hardware levels of data multiplexing: we first multiplex one dimensional chains of modules into homogeneous strips, then multiplex strips into sheets, and finally we multiplex sheets of modules into a uniform three dimensional space.

In cam-8, each module will have 2^{20} cells—using nearest neighbor connections, this means that the neighborhood of a given cell in three dimensions consists of 8 million cells surrounding it. That is, any bit within a volume of 8 million cells surrounding a given cell can be shifted into the given cell, to be used together with other shifted bits as the new cell value to be updated. Since bit-slices are shifted as a unit, all cells will see the same neighborhood: if one cell gets a bit from 50 positions to the right, all cells do. Similarly, if we arrange the modules in a two dimensional configuration (so that only two levels of glue multiplexing are used) then the neighborhood consists of an area containing 4 million cells.

Note that in both two and three dimensions, even with only nearest neighboring modules connected, some data from next-nearest neighbors will become available to a given module by virtue of the several levels of multiplexing. In addition to this, we plan to also provide connections between second-neighbors along all six principal lattice directions. This is primarily intended to allow the space to be divided up into up to eight independent sublattices, which will then be able to intercommunicate in order to perform error monitoring or multistep updating with double buffering. When not used for these purposes, these connections will allow the range of gluing to be extended, giving even larger neighborhoods.

Note also that arrays of various shapes and sizes can be achieved by simultaneously controlling the scanning within each module and the multiplexing between modules: shifting of cell data in more than three dimensions can be achieved by simply controlling the scanning of cells within individual modules. The second-neighbor connections will actually allow hardware gluing to be extended to up to six dimensions, although three of these dimensions will only be two modules deep.

4 Hardware details

Cam-8 will consist of a number of space modules, each handling the simulation of a chunk of cellular space. In our initial machine, we plan to have each space module contain one million 16-bit cells, along with a 64K×16 lookup table used for updating, and various counters and registers used for data analysis and error detection/correction (see Figure ??). Direct access to each module’s scan is permitted by the flywheel inputs and outputs, which are provided to allow external hardware to be attached to various points in our simulated space (see Section ??). The I/O bus is used for communication with a host computer that is responsible for initializing cell and table data, determining the size and shape of the cell space, and supervising shifting, display, analysis, and error handling.

Space modules are interconnected to have the topology of a three dimensional array of processors, each communicating with its nearest neighbor in each of six directions (see Fig. ??). Note that the host bus actually consists of several buses, each of which connects a fraction of the modules to the host; the flywheel bus permits direct access to the time-multiplexed cell values scanned separately by the different modules.

Figure 3: A single module. A million cells are scanned internally, data from neighboring modules is incorporated into this scan, and the net result is converted by table lookup into the new cell values.

Figure 4: Interconnection of modules. Bidirectional connections 16 bits wide connect each module to its 6 neighbors in a cubic lattice. The flywheel bus, distributed throughout the machine, makes every cell “visible” somewhere during each step in which it participates. The I/O bus allows the host to communicate with modules.

The cell-data portion of each space module, along with some control and analysis circuitry (i.e., everything but the lookup table) constitutes a cell module. Each cell module consists, in turn, of 16 bit-modules, each of which handles a bit-slice of the cell data consisting of one bit from each of the million cells. A bit-module consists of only two chips: a 256K×4 DRAM, and a semicustom controller chip. Thus a cell module consists of 32 chips, and when we add a 64K×16 SRAM module, we have a complete space module.

4.1 The controller chip

Except for the controller chips, this design consists entirely of standard commodity RAM chips: DRAM chips for cell-state storage, and SRAM chips for lookup-table processors. For a machine operating with a 40ns clock, we would use SRAMs with somewhat faster than 40ns access, and DRAMs with a static-column mode read/modify/write cycle of somewhat less than 160ns (since we are using nybble-wide memories, our bit bandwidth to the DRAMs is multiplied by four).

The main function of each controller chip is to provide a sequence of addresses to its associated DRAM chip, in order to coordinate the relative order of scan of the 16 bit-modules. In addition, these chips handle a number of other important roles. First, they are involved in the data I/O of the DRAMs during updating: this involves changing nybbles into a serial bitstream as the DRAMs are scanned, and grouping bits into nybbles in preparation for storing the updated cell bits back into the DRAM memories. To save address setup time on the DRAMs, the new data is stored back into the address that has just been read from, using a read/modify/write cycle. Because of unavoidable serializing/unserializing delays, as well as the time actually taken for the table lookup, the data written in a given nybble after updating will correspond to different cells than the nybble’s previous contents. This extra shift is simply compensated for, however, by an adjustment to the virtual shift applied to each bit slice. By picking one of the longest dimensions of our space to be the first scanned along, and associating it with a portion of a single memory row, we can make effective use of static column mode in our DRAMs. Note that the use of nybble-wide memory in order to increase memory I/O bandwidth also makes it necessary to use up to three bits of extra pipelining in order to allow arbitrary shifts along this first dimension. Of course the controller chip must combine its own internally shifted data with data available from its neighbors in order to produce a ‘glued’ window into a uniform cellular space, as discussed earlier.

In addition to this data scanning/buffering/gluing function, each controller is responsible for selecting what signal goes to one address bit of a lookup table, and what is done with one bit that the table returns. For example, the glued data constructed by a given controller could be looped back and stored in memory, turning a virtual shift into actual data movement without any use being made of the bit returned by the lookup table. In such a case, that bit of the lookup table might be programmed to provide some information useful for data analysis: the number of ones in the resultant serial bitstream could be accumulated on the controller chip. Even the bit sent by the controller to the table need not be the cell data: for example, a constant of 1 or 0 could be substituted, chosen separately for each updating step in order to select one or another of two possible subtables.

All such choices, as well as control of scanning order, dimensionality, gluing, and many other details are supervised via a bussed connection to a conventional von Neumann architecture computer used as a control-host. By talking over this bus to controller chips, the host configures the system, initializes cells and tables, shifts bit-slices between updating steps, and reads various counters in order to analyze cell data and detect errors.

4.2 The flywheel bus

In addition to the host bus, there is a second kind of “bus” supported by this architecture. As is shown in Fig. ??, the connections to the lookup table processor may be broken, and the glued output may be made directly available to external circuitry, while the cell-bit input may be taken from an external source. Since the entire window into the cell space produced by a given bit-module is visible in a time-multiplexed way at the glued output as the cell data is scanned, you can picture the data as sitting on a data flywheel which turns around and around. Since all bits in a bit-module share this single output line, we refer to it as a bit of the flywheel output; in a 1024 processor machine, this bus is 16K bits wide. Similarly, we have 16K flywheel input lines which can be used to input to any and all cell bits active during a given step. Whether flywheel inputs or outputs are used is of course determined by the controller.

No enormous connector is brought out of this machine containing these 32K lines: this bus is distributed throughout the machine as positions at which external circuitry can attach. In particular, display data is taken directly off this bus. Special purpose measurement and analysis equipment can be attached at certain positions in our array of processors, just as specialized equipment is positioned to capture data in a scientific experiment. Similarly, external equipment can control localized input processes (such as smoke particle sources in a wind tunnel simulation).

4.3 Doubling the connections

In addition to the physical interconnections described earlier which involve a single bidirectional wire linking each bit-module to the closest neighboring bit-module in each of six directions, our design includes a second wire linking each bit-module to its second nearest neighbor in each of these same six directions.

There are a number of reasons for providing these additional interconnections. One reason is that this permits the space to be divided up into halves, quarters or eighths: by substituting second nearest neighbor interconnections for the nearest ones along one dimension, we split the machine into two halves, and further splitting can then be done along the other two dimensions.

The most important reason for splitting the space in half has to do with error detection and correction (see Section ??). For large assemblages of cam-8 machines, it will often be useful to split the space in half and have both halves doing the same computation while continuously checking one against the other. Notice that when we use the second neighbor connections along some direction to split the space, the nearest neighbor wires along this direction become available for passing the monitoring information between the two halves.

Another reason to split the space is to allow a given cell bit to be used simultaneously by two modules, something that is not supported by the nearest neighbor shifting mechanism. Again, the nearest neighbor wires connect the two halves: in this case, they carry the duplicate information. Such duplication is useful, for example, when one half of the machine is used to analyze what is happening in the other half while it is running, or when we do a multistep updating that requires double buffering.^{1} Splitting cam-8 is also useful in implementing rules that need more than 16 bits of input. Corresponding cells in the two halves are strongly coupled: a bit from either cell may be used by both. By using some cell bits within each coupled pair of cells to store intermediate values, rules that involve more than 16 bits of neighborhood can be synthesized as a composition of completely arbitrary 16-input/16-output logical functions.

One additional benefit of these interconnections is that the width of the neighborhood along each direction which we don’t split will be doubled. This is particularly helpful in the 1K×1K×1K 3-dimensional mode, where doubling the neighborhood along the single short dimension will allow us to have a uniform neighborhood involving about 16 million cells (257×257×257).

Finally, if we call a 2×2×2 block of space modules a super module, and build cam-8 out of such super modules which are never split between different circuit boards, then we can replace all of the (single-wire) nearest neighbor interconnections within each super module with pairs of wires without increasing the number of wires going between boards. This would give us all of the connectivity needed to treat each splitting of the machine as the creation of depth in an extra dimension: we would actually be able to provide hardware gluing in 6 dimensions (although three of the dimensions would only be two modules deep). This more general interconnection between halves of the machine would also provide additional flexibility in applications that rely on strong coupling between corresponding cells.

4.4 Data analysis

Each bit-module contains a number of counters that are used for real-time data analysis, error detection/correction, or both.

Table outputs are always counted (number of ones in each output). A step with simultaneous analysis can be performed by having some bit-arrays remain unchanged (or just shift) while the corresponding table outputs are being counted. For example, if a bit-array is being used to store a spatial parameter (such as an obstacle in a fluid-flow experiment) the associated table output is not needed for updating, and may be programmed for data analysis and counted. If there aren’t enough such “free” tables, or if the analysis requires a different neighborhood than the updating, separate analysis steps may be interleaved between updating steps by rewriting tables.

1For example, to simulate a 3×3 2-dimensional neighborhood with one bit per cell, we could run cam as two 32K×16K arrays of cells, and treat the 16 bits in each cell as a 4×4 region of a bit-plane. Half the machine holds the “old” data while we construct the “new”

data in the other half using several steps by shifting around the 4×4 window and updating the four center elements after each shift. This allows us to run a space of 8 billion 1-bit cells.

The table output counters can be used to perform local averaging by appropriately controlling the scan. For example, a large 3-dimensional array can be updated as a collection of small cubes, with table counts read immediately after each cube is updated (these cubes can be much smaller than the region serviced by each cell module).

When cam-8 is operated as two half-machines, table outputs can be continuously compared between corresponding parts of the two halves and the number of differences counted by the table correlation counters. Space and time autocorrelations can be accumulated by running two versions of the same system simultaneously, with a constant space or time shift between them.

Note that all counters are double-buffered, and can be read at any time by the host without affecting a step that is in progress.

4.5 Error handling

Like cam-6, each cam-8 machine will constitute a “building block” from which one can build much larger machines. For example, forty such blocks used together will have 40 billion cells and will perform one trillion cell updates every second. While there are no inherent architectural limits on how many cam-8’s can be hooked together, there is a practical problem which grows as more and more cam “blocks” are added, namely, error handling. Because of the built-in analysis capabilities described in the previous section, and additional hardware consistency checks, it will be possible to discover and recover from hardware errors.

Since tables are not supposed to evolve in time, it is relatively straightforward to test whether or not a table contains an error. We can usually detect table errors by performing an analysis step during which all tables are addressed by counter bits—we simply count the number of ones in all table outputs. As long as correlated pairs of tables contain the same rule we can simultaneously perform a more detailed check by comparing table outputs. Alternatively, we can have the host perform a verify-write of all tables, in which the old contents is read and compared with what the host is writing.

Cell-memory is tested by each bit-module during every step. “Checksum” bits reflecting the number of ones last written and their positions are compared to corresponding checksums performed on the data subsequently read. Changing any bit of the configuration will, on the average, change about half of the checksum bits, making the chance of an undetected array-memory error very small.

Hard errors, caused by bad components, can be tested for whenever any error is detected. If we run an occasional analysis step during which we test tables, bad chips should always be noticed quickly.

Soft errors, in which memory bits are typically changed, are principally caused by alpha particles. Modern commercial memory chips, which constitute most of cam-8, are inherently quite reliable: even with absolutely no provision for error correction it should be possible to run this machine with 32768 memory chips for several days at a time without any errors. Thus for a single cam-8 it may be perfectly practical in most cases to simply detect errors, and rerun an experiment if any occur.

For longer runs, or for large machines built out of many cam-8’s, if we want to guarantee exactly correct operation it is probably most practical to use each machine as two correlated half-machines, both running the same experiment. Since the chance of two different bit-modules both experiencing a soft error during the same step is extraordinarily small (expected perhaps once in 10^{16} steps for a single cam-8 machine) we can assume that one out of every correlated pair of bit-modules will always be correct. Bits that were updated incorrectly are fixed by using data from the correct twin, and incorrect tables are simply rewritten.

Given a disagreement between correlated modules, there remains the problem of deciding which of the pair is incorrect. We make use of one further facility provided by the hardware in order to quickly and reliably find the error: whenever table comparisons disagree, both the original contents of the cell where the error occurred and the updated value are latched by the controller chips. By examining this information, the host can tell which of the modules was updated incorrectly.

4.6 Display

Being able to display the state of our system in real time provides important feedback as to whether or not everything is working as expected, and what parts of the system are doing something interesting that should be investigated more closely. This is particularly important in highly interactive work with fractional machines consisting of just a few modules.

Two dimensional display is not much of a problem for cam-8, since this machine can provide its data in the correct format for a color monitor. This machine can even, if desired, scan its data in the correct format for an interlaced display—since each cell is updated independently of all others the rows can be scanned in whatever order you choose.

For a complete 64K×16K display,^{2} we could cover an enormous wall with 1024 color monitors (more if several cam’s are connected), each of which would show a 1024×1024 patch (using a four-fold interlaced scan on a 15kHz monitor). Of course it would be more practical to use only one monitor (or just a few), and shift the data to move the window around.

Since all of the neighbors that would be used for a cell-update are available simultaneously, it is a simple matter to display a function of the neighborhood, rather than the neighborhood itself. For example, in a fluid-mechanics experiment you might want to show only the smoke particles that trace the flow.

Another display technique would be to let the host computer use the average data accumulated by counters (see Section ??) in order to produce a display on its own screen.

In more dimensions, how to display the cell data is less obvious. One method that allows cam-8 to always produce some sort of a display is to map the million cell array serviced by each space module into a 1024×1024 square in the most natural manner you can think of, and then display this square array. For example, a 128×128×64 configuration could be arranged as an 8×8 “sheet” of 128×128 “postage stamps.” If we now scan the data in this flattened format (which just involves a particular choice of the order in which cells are updated), then it can be displayed on a 15kHz monitor, exactly as the 1024×1024 configuration that we discussed above for 2-dimensional displays. If not all cells are being updated, then we can map the cell array into a pattern that fits within a 1024×1024 array, and display the unused areas as black areas on the monitor.^{3} If 256K cells or less are being processed, we can get a better display by mapping the cell array into a 512×512 matrix, and displaying this matrix on a 30kHz non-interlaced monitor as we scan it.

2In order to realize a 64K×16K space without adding extra interconnections, we unfold cam-8’s basic 8×8×16 array of space modules into a 64×16 sheet by appropriately programming the use of the existing interconnect wires.

In any case, a single display can be used as a window to see any part of the system by shifting the data appropriately (in however many dimensions).

Finally, suppose we are displaying a large region of a 1K×1K×1K space using a method such as the one described above that involves showing slices through a section of the space, and suppose that we would like to see a view of the cube rotated by 90 degrees about its x, y, or z axis. This is easily accomplished by cam by actually rotating all of the cell data using a simple split-and-shift algorithm.^{4} Because of the instant shifts, such rotations can be accomplished in a fraction of a second.

5 Additional claims

In addition to the claims of Section ??, there are a number of obvious extensions and variations on the cam-8 architecture which may themselves be worthwhile to claim.

5.1 More highly parallel versions

While our discussion thus far has been oriented specifically towards an implementation in terms of conventional memory chips, by abandoning this approach and by sacrificing some flexibility, we can achieve much greater performance.

3When we aren’t locked to the framing format of a monitor, we don’t waste time on these unused areas, and the number of complete updating steps per second therefore rises when we process smaller areas.

4This can be considered a special case of the problem of rotating a 2-dimensional square image, where the number of bits in each pixel is very large. To rotate such a square image 90 degrees clockwise, you can first split it into quarters, then shift the four quarters horizontally or vertically until they have each been shifted to a position 90 degrees clockwise of where they started. Each quarter is similarly rotated, and then each eighth, etc., until you reach the level of a single pixel. Pixels don’t look any different when rotated, so you’re done.

A 1024-module cam-8 machine running with a 40ns clock would be able to perform 25 billion cell updates per second on a space of up to a billion 16-bit cells.

If we were to limit ourselves to rather simple processors, able to simulate only a small variety of rules (e.g., a small set of lattice gas rules), then we could put a large number on a single chip. If we put 1024 processors on our chip, each servicing 64 8-bit cells using the scanning/shifting/gluing techniques discussed above and running with a 5ns clock, then each chip would perform 200 billion cell updates per second. Clearly a variety of architectures intermediate between this and cam-8 are possible, depending upon the neighborhood required and the dimensionality that we wish to simulate. For practical technological reasons, the physical interconnection between chips, at least at present, would be limited to connecting the edges of two-dimensional arrays of a few thousand processors (a few hundred pins). Additional dimensions would have to be internal ones, achieved by the way in which individual processors scan the cell memory that they are responsible for.

5.2 More highly pipelined versions

Cam-8 makes provision for attaching external circuitry to the cell-modules, to replace the lookup tables—in this case, additional stages to the data serializing/deserializing pipelines may be added, to allow the computation delay for such circuitry to be several bit-times longer than a lookup table (though such circuitry must finish a computation each bit time, this may have been a multistage pipelined computation). There is no reason in principal why very long pipelines, involving perhaps hundreds or thousands of stages, couldn’t be used, since the computation performed by each module is completely sequential, and the data access is perfectly predictable.

5.3 Other kinds of processors

Our decision to use 16-bit cells in cam-8 was arrived at by determining that a 16-bit address was about the most we could handle by fast table lookup. If we abandon table lookup and use other kinds of processors, cells could in some cases be much larger. For example, each cell might contains several 80 bit floating point numbers, and these numbers could be virtually shifted just as we handle the bit-slices in cam-8 (since all bits in each number would shift together, we have a lot of flexibility in deciding how (or even whether) to divide the bits up between memory chips. Pipelining, discussed above, would allow us to use commercial floating point chips to do the desired calculations.

Similarly, various compositions of moderately sized lookup tables, appropriately pipelined, could be used to handle the updating of large cells in many cases of interest.

6 What has appeared where

Cam-8 is really the latest in a line of cellular automata machines (cams) that have been developed within our group at MIT. Before discussing what has appeared in print concerning cam-8, we will briefly cover the history of our machines, since some of what has appeared about them could have a bearing on what is still patentable in cam-8.

6.1 Earlier machines

The first of our cam machines discussed in print is cam-5 (see [?]) which scans a two dimensional space and runs traditional 2-dimensional CAs while displaying its results in real time (it maintains a three line data buffer as it scans, in order to make a 3×3 window of cell values available at a time). This machine is somewhat related to image processing machines of the sort discussed in references [?, ?], but is geared towards more general operations (it does computations by table lookup) and has a real-time display of the ongoing simulation, plus some provisions for data analysis using counters to count a function of the cell data as it is sequentially updated.^{5} Cam-6 (see [?, ?, ?]) is a commercial version of this machine (commissioned by us to be produced under license by Systems Concepts in San Francisco) allowing some flexibility of neighborhood choice under software control, with bits selected from cells in a 3×3 buffered window (and some other non-cell signals). Cam-6 also has some provision for modularly expanding the space by connecting several machines together, but it uses pipeline multiplexing to achieve a larger uniform space, rather than the gluing technique discussed here. Cam-7 (see [?]) was a proposed machine which was basically a greatly scaled up cam-6, consisting of many cam-6-like modules.

5The rap1 (see [?]) is a machine closely related to cam-5 that was built by some French investigators in connection with lattice gas simulations—it has no provision for gluing, and is restricted to a very small neighborhood.

A few groups have built special purpose hardware for simulating specific CA models of physics (see, for example, [?, ?, ?]), but these are very specialized, and do not have any generality of neighborhood nor any provision for modular expansion.

6.2 References to CAM-8

We have written a book[?] about cam-6 (appeared April 1987) in which a 3line footnote hinted at the neighbor-gathering technique used by cam-8 (but only in two dimensions). This footnote mentions that it involves shifting by changing scanning order, and nothing else.^{6}

This is our earliest reference to any of the ideas claimed here. The next reference[?] appears in the August 1987 issue of Complex Systems, which wasn’t actually published until January 1988. This article contains everything discussed here except for the generalization of the gluing to three dimensions, and the doubling of the interconnections discussed in Section ??.

A revised version of this article[?], giving our present understanding of the cam-8 architecture (though without explicitly discussing more highly parallel or more highly pipelined versions) will appear sometime in the next few months in a book entitled Large Non-linear Systems, edited by Gary Doolen. Tom Toffoli has already given away copies of this paper.

6The machine mentioned in the footnote was called cam-7, but reflected later ideas than those discussed in [?]—ideas that eventually appeared in [?] (still with the name cam-7). In [?], the name was changed to cam-8.

References

[1] Burks, Arthur (ed.), Essays on Cellular Automata, Univ. Illinois Press (1970).

[2] Califano, Andrea, Norman Margolus, and Tommaso Toffoli, CAM-6 User’s Guide, Systems Concepts, San Francisco (1987).

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

[4] Creutz, Michael, “Deterministic Ising Dynamics,” Annals of Physics 167 (1986), 62–76.

[5] Doolen, Gary (ed.), “Workshop on Large Nonlinear Systems,” collected in Complex Systems 1:4–5 (August–October 1987).

[6] Farmer, Doyne, Tommaso Toffoli, and Stephen Wolfram (eds.), Cellular Automata, North-Holland (1984).

[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,” Complex Systems 1:4 (1987), 633-707.

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

[10] Herrmann, Hans, “Fast algorithm for the simulation of Ising models,” Saclay preprint no. 86-060 (1986).

[11] Hoogland, A., J. Spaa, B. Selman, and A. Compagner, “A specialpurpose processor for the Monte Carlo simulation of Ising spin systems,” J. Comp. Phys. 51 (1983), 250–260.

[12] Kadanoff, Leo, “On two levels,” Physics Today 39:9 (September 1986), 7–9.

[13] Kittler, J., and M. J. B. Duff, (eds.), Image Processing System Architectures, Research Studies Press, Ltd., John Wiley and Sons, Inc. (1985).

[14] Kugelmass, S. D., R. Squier, and K. Steiglitz, “Performance of VLSI Engines for Lattice Computations,” J. Complex Sys., 1:5 (October 1987) 939–965.

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

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

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

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

[19] Margolus, Norman, Tommaso Toffoli, “Cellular Automata Machines,” revised version of preceding reference, to appear in Large Nonlinear Systems, Gary Doolen ed. (1988).

[20] Pearson, R. B., J. L. Richardson, and D. Toussaint, “A fast processor for Monte-Carlo simulation,” J. Comp. Phys. 51 (1983), 241–249.

[21] Porter, Kenneth, CAM-6 Hardware Manual, Systems Concepts, San Francisco (1987).

[22] Preston, Kendall, and Michael J. B. Duff, Modern Cellular Automata: Theory and Applications, Plenum Press (1984).

[23] Shimomura, T., G. Doolen, B. Hasslacher, and Castor Fu, “Calculations Using Lattice Gas Techniques,” Los Alamos Science, special issue no. 15 (1987), 201.

[24] Sternberg, S. R., “Pipeline architectures for image processing,” in Multicomputers and Image Processing, Algorithms and Programs, L. Uhr ed., Academic Press (1982).

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

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

[27] Toffoli, Tommaso, “Cellular automata as physics emulators,” to appear in proceedings of Impact of Digital Microelectronics and Microprocessors on Particle Physics, a conference at the International Center for Theoretical Physics, Trieste, Italy, 28–30 March 1988.

[28] Toffoli, Tommaso, “Lorentz invariance of computations,” in preparation.

[29] Toffoli, Tommaso, and Norman Margolus, “The CAM-7 multiprocessor: A cellular automata machine,” Tech. Memo MIT/LCS/TM-289, MIT Laboratory for Computer Science (1985).

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

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

[32] Wolfram, Stephen, “Statistical mechanics of cellular automata,” Rev. Mod. Phys. 55 (1983), 601–644.

[33] Wolfram, Stephen (ed.), Theory and Applications of Cellular Automata, World Scientific (1986).

[34] Yakhot, V., and S. Orszag, “Reynolds numbers scaling of cellularautomaton hydrodynamics, Phys. Rev. Lett. 56 (1986), 1691–1693.