Self-configuring array enables atomic-scale fabrication

The novel aspect of the approach is the ability of cells to modify the operation of their neighbors during run-time. That has allowed Cell Matrix engineers to define an entire circuit by initially configuring two or three cells on the boundary of an array and then allowing the cells to program their neighbors. The process resembles software bootstrapping in conventional computers, but it leads to a hardwired circuit.

"Overall, our philosophy is to get as much computing architecture into software as possible," explained Nicholas Macias, a co-founder and director of Cell Matrix. He compared the innovation with the original stored-program computer concept enunciated by John von Neumann at the beginning of the electronic computer revolution.

"The first electronic computers were configured for a computation manually by plugging in patch cords," Macias said. "Von Neumann realized that a much more efficient and flexible method would be to store the data and the instructions for the algorithm in the same form." As a result, both algorithms and the data they used could be encoded on punch cards and fed into a general-purpose computing machine.

Entirely in software

The cell matrix architecture uses a similar philosophy in that the basic hardware is simple and fixed. The cell architecture remains the same no matter how large the circuit, and an arbitrary circuit design can be represented entirely in software. The same is true for FPGAs, but their architecture is more rigid. The entire ci rcuit configuration must be downloaded in a serial bit stream before the chip can begin operating.

Cell matrix arrays are dynamically reconfigurable at run-time, and there are no unique chipwide structures to fabricate.

Macias uses a two-register implementation of an adder as a simple example of how a computation can take advantage of self-reconfiguration. Suppose that two 16-bit registers are performing an add operation that overflows. Normally, the hardware would generate an overflow condition and output the carry. It would then be up to the programmer to decide what to do next. In a cell matrix array, the same condition could be used to initiate the reconfiguration of neighboring cells to emulate longer registers, and the computation could continue without interruption.

The ability to modify neighboring cells is the key difference between the cell matrix p aradigm and other circuit types, and it allows an algorithm to expand or contract hardware resources to fit momentary conditions during a computation.

Eliminating defects

"One important advantage of this approach is that you can start fabricating functional cell matrix arrays immediately and then scale up to any size later," said Macias. Another is the ability of a circuit to automatically detect faults and eliminate defective cells.

Cell Matrix engineers undertook a project for NASA that demonstrated that cell matrix arrays could be damaged in the field and then recover operation by reconfiguring themselves. That capability would be useful in space probes and remote vehicles such as the Mars rover.

The arrays can also be programmed to route themselves around defects resulting from the fabrication process. Thus, they may be cheaper to manufacture, since yields would automatically be higher.

"With current deep-submicron chips such as the Pentium processo r, you get one fault and the whole thing goes into the garbage," Macias said.

One thing the architecture lacks is a high cell density. It would be difficult to get the same gate counts as for current FPGAs, although Macias said that current design rules would support a 50,000-cell array.

Macias thinks that the cell matrix concept will come into its own when the industry moves to atomic-scale fabrication.

"Whereas FPGAs are reconfigurable, cell matrices are self-configurable, meaning the hardware can analyze and reprogram its own configuration, autonomously," he said. "This boundary pushing is enormously convenient for crossing the macro/nano divide, because essentially everything you wish the system to do can be determined, translated and downloaded to the system once, through just a few macro/nano wires."

Local self-configurability also solves the problem of how to manage trillions of switches inside a system. And it makes the architecture scalable without introducing compl ex control structures. Such a capability would boost molecular-circuit design methods, since complex circuit configuration need not be implemented at the molecular level without defects. Massive circuits could also be built with this approach, with cell matrix software routing around defects and configuring complex circuits.

The success of the approach depends on the ability to build self-reconfiguring algorithms for any problem that's to be run on a cell matrix. The company has set up a simulator for 4 million- to 6 million-cell arrays and has been developing software on it.

Broader application

Macias believes it will be possible to bootstrap virtually any computation from just a few initially programmed cells. "We have gotten a lot of interest in this problem from people outside the company who have jumped in and begun developing this kind of software," he said.

"The run-time computations these arrays perform are data flow operations — a cell is activated when it receives data on its inputs. Computations also run in parallel, so we can transform an algorithm from a sequential time-bound form to a parallel-spatial form," Macias said.

That approach simplifies chip fabrication, since the architecture doesn't have to run at the fastest available clock speeds. The circuit is globally clocked when it is in configuration mode, although that is not a strict requirement for the architecture. Clocking the configuration phase made design easier and provided a convenient way for the cells to determine if data is arriving for processing or self-reconfiguration.

Cell Matrix has been working with nanotechnology groups, hoping to forge a new computing substrate from some type of atomic-level fabrication technique. Macias was impressed with work at Hewlett-Packard Laboratories in which a matrix defined by erbium disilicide wires that address rotaxane molecules has been proposed as an atomic-level route to massively dense FPGAs. Like Cell Matrix, the HP group is pushing the idea of building a fixed, massively parallel hardware infrastructure that would be reconfigurable in software.

Macias would like to see a hardware proposal that could support the more complex operation of his self-reconfiguring cells. Even with FPGA-style reconfigurability, the I/O problem becomes a major headache. A huge bit stream of reconfiguration data would have to be downloaded to the hardware and distributed to each cell. A cell matrix could be bootstrapped from just a few I/O connections to an atomic-level circuit.