make a website for free

Cell Matrix History

The Cell Matrix was first conceived in 1986 by Larry Henry, Murali Raju, Jimmy Hargrove and Nicholas Macias as part of a graduate VLSI class project at George Washington University. The idea came from several areas of discussion, including:

  • placing/blurring the HW/SW line (e.g. studying microcoded CPUs such as the VAX 11-780);
  • Turing's Halting Problem and its relation to introspection (self analyzing self);
  • miscellaneous discussions on artificial intelligence and machine learning;
  • design of a software program that prints itself (called a "quine," though we hadn't heard of them at the time); and
  • design of a system with ultimate testability: the ability to access internal circuit points from anywhere inside the circuit itself.


Prototypes

A first prototype was developed in 2 micron, 2-metal-layer cMOS. 64-pin chips were fabricated at MOSIS, and the result was a set of fully functioning 3x4 matrices.

Initial tests of these chips were done using a Tektronix logic analyzer, and basic behaviors were confirmed to work correctly, including configuring a single cell as a logic block; configuring a cell as an adder; and using one cell to replicate another cell.

SIMULATION

Development continued in an ad-hoc manner for the next few years, until around 1991/92, when work began on a cell-level simulator. The first version was command-line based, and used many of the same comands and conventions still used in the modern GUI-based version. This simulated the behavior of a collection of cells by repeatedly sweeping through the matrix, applying inputs and updating outputs. Because of this approach, the simulation was not very accurate in modeling race conditions, but worked as a proof of concept.

The next version was built using  X-11, which provided a graphical view of the behavior of dynamic circuitry. 24 years later, this code still compiles and runs under Ubuntu (you need to install some X11 libraries).

In the mid 90s, work moved to queue-based simulation systems. The firt such system used Visual Basic (3.0!) for the front end, and C for the underlying engine. The resulting software allowed simulation of modestly sized circuits incorporating dynamic behavior.

Jim Pearn also wrote a applet-based simulator, which is available on the original website (but appears to no longer run).

Here is a queue-based command-line simulator, though the modern GUI version allows headless execution coupled with a client.

For one summer, work was done on a Virtual PIG. This system implemented a stack-based machine for coding Cell Matrix-like behaviors in a procedural language, and allowing those virtual circuits to interact with a cell-level simulation of the matrix. This was done largely to research areas related to secure communication within the matrix, looking at ways to build comunication channels, detect when the channel has been broken-into, but also allowed controlled crossings of channels. Development only ran for a few months.

Layout Tools

For all these simulators, layout was done manually, first on paper and then using an ASCII-based layout manager. This allowed further development of larger dynamic circuits, including a ripple-carry adder endowed with support circuitry that woud detect an impending overflow and synthesize new flip flops before the overflow occurred: an "expanding counter."

A critical piece of such circuitry is the ability to build wires. Wirebuilding is probably the key to utilizing the dynamic aspects of the Cell Matrix. Various references to wirebuilding can be found in the Papers section of this site.

One early large-scale use of wirebuilding was to implement an entirely self-replicating circuit. Interestingly, the basic layout and functioning of this circuit paralleled the original self-replicating program which was part of the origin of the Cell Matrix.

PATENTS

Following several unsuccessful attempts in the mid-90 to interest others in this architecture, it was decided to apply for a patent on the self-configuring architecture itself. That patent (one of 4) issued in 1999, and was followed by the creation of Cell Matrix Corporation. Following this, a pair of papers were written for conferences later that year. The first described the use of the Cell Matrix (which, at the time, was named the Processing Integrated Grid, or “PIG”) for efficient implementation of a parallel genetic algorithm utilizing concentric rings of individuals. This paper was accepted as a poster session, and provided an opportunity to discuss the Cell Matrix concept with interested conference attendees.

FIRST PUBLIC PRESENTATION

In 1999, the first public(*) presentation on a paper on the Cell Matrix took place at the NASA/DoD Conference on Evolvable Hardware (EH-99).

(*) As a footnote, part of the talk was actually given privately a few days earlier, in a holding cell outside LAX, where the author was being detained under suspicion of being an escaped felon. When the talk turned to the topic of AI, the Sargent in charge decided this was a case of mistaken identity, and the author's release followed shortly thereafter.

FURTHER DEVELOPMENT

Numerous papers, tools, circuits, etc. have been developed as part of Cell Matrix research. In 2001, a NASA SBIR was received for work on self-repairing systems based on the Cell Matrix. This resulted in the development of a 73,000-cell “Supercell,” usable as a smart building block for self-repairing digital circuits.

Other developments included:

  • graphical layout tools;
  • text-based circuit compilers;
  • wire-building classes, callable from Java;
  • numerous patents, conference papers, journal papers, book chapters, and other papers;
  • awarding of Master's degrees to students at Utah State University for work directly related to the Cell Matrix;
  • awarding of a PhD to a student at EPFL for work peripherally related to the Cell Matrix;
  • compiler developments for injecting faults into the substrate;
  • commercial development of the “Mod-88,” an 8x8 Cell Matrix build on top of an FPGA;
  • implementation of a multi-CPU version of the simulator;
  • teaching of a one-semester Cell Matrix course at Virginia Tech; and;
  • awarding of a PhD (2011) from Virginia Tech for work directly related to the Cell Matrix.


Other Historical Artifacts

George Washington University, where the original work on the Cell Matrix began in 1986

Pictures of the original Cell Matrix prototypes

Pictures from a trip to Pennsylvannia State University to visit  Lukáš Sekanina

Pictures from the first NASA/DoD Conference on Evolvable Hardware (EH-99)

Scans of various notebooks of old Cell Matrix work. More here.

A few sketches of early neural network implementation ideas

Email sent following the first successful completion of a self-replicating circuit's replication cycle.