InterJournal Complex Systems, 70
Status: Accepted
Manuscript Number: [70]
Submission Date: 963011
Programming a crystal-lattice computer
Author(s): David Pearson

Subject(s): CX.07

Category: Brief Article


I have spent my adult life as a computer programmer, and have learned a great deal about algorithms, programming techniques, and machine architecture, knowledge which has changed very little in that time despite the continuing revolution in microelectronics. Unfortunately, I have also had for the last 15 years a vision of what computers will look like by 2050, and its not a 50 GHz Pentium in a wristwatch. It is a crystal-lattice computer, a 3-dimensional array of identical molecular-scale cells, each capable of computation, each affected only by its immediate neighbors. The troubling part of this vision is that for once, the techniques, algorithms and languages I have been using dont apply. For once, I need to start over.

Recently I have been investigating what programming would look like on such a computer. While there may be good reason to doubt that the vision can be realized, it will not even be worth achieving if we dont solve the problem of how to program the computer when we have it. I believe that the techniques we develop along the way will prove useful whatever the future actually holds (unless its only that wristwatch Pentium).

The standard architecture for the last 50 years is generally called the Von Neumann architecture (though some claim he merely took credit for the idea). It was, in any case, a brilliant stroke, radically simplifying the possible interconnections by introducing sequential operations, read from memory, with operands and outputs also in registers or memory.

Ironically, it was also Von Neumann who first proposed cellular automata, which is the model we will use for the crystal-lattice computer. His purpose was to use cellular automata in a reductionist explanation of the self-reproduction of living creatures. He apparently didnt realize that he had also designed the first general-purpose parallel computer. The possibility of using them as practical parallel machines was recognized by several researchers at MIT, but their research focused primarily on using cellular automata to study physics. What I am investigating is the possibility that cellular automata will replace microprocessors, that we will use them for all our computation, sometime in the next century. In the following, I will use the term cellular array (or CA) to mean a practical machine architecture based on the paradigm of cellular automata.

The rest of this paper is a Cooks tour of massively parallel programming, including brief sketches of some designs. I will also try to provide a rationale for the decisions made, and the paths not taken.

Retrieve Manuscript
Submit referee report/comment

Public Comments: