Where is my work leading to ?

My area of research interest lies generally in the field of SIMD parallel computer architectures and specifically in Cellular Automata models and architectures. I propose to build the next generation of Cellular Automata machine (CAM) which is based upon the idea of putting logic and memory together on one chip. The best performance todays fastest CAM can provide is about one billion cell updates per second. Using logic mated to DRAM we can make a chip, which would be the basis of a SIMD architecture, that performs trillions of cell updates per second. I hope to use this new CAM to implement Cellular Automata models that exist in theory but have yet to be realised. Furthermore, I believe I can improve upon current successes in the fields of fluid dynamics, realtime image processing and digital logic simulation. Finally I plan to find new areas where CA models can be applied.

Computers of the future will be nothing like today's workstations and PCs except that they will still be extremely useful tools for helping man solve his most challenging problems. Processors are running at faster and faster speeds creating the need to pack more transistors onto our chips. These transistors are getting smaller and smaller. It is obvious to everyone that at some point we will reach a barrier in size and power consumption (which expresses itself as heat dissipation) that cannot be overcome by a new fabrication process. This realization has prompted the recent interest in quantum scale computation. If we could build a logic gate based on the principles of quantum mechanics it would probably be composed of a few or even one atom. This would provide close to maximal efficiency in how we used materials to build digital devices.

This is however but one way to view quantum computation. A few people have show in theory, and believe its possible in practice, that you can use the states of a quantum system to represent the problem you are trying to solve. By carefully arranging things you can then let the physical properties of the system perform your computation. The state(s) that represent the "correct" answer persist through constructive interference and the state(s) representing the "incorrect" answers die out due to destructive interference. This is a gross simplification of what actually happens but the basic idea is to create matter that computes (programmable matter). Today we use our materials to construct a processor that does simple computation and then we string together a sequence of these simple operations to implement an algorithm for solving our problem. In the future we may simply arrange those same materials so that the problem is physically represented and then use the physics of the universe as our algorithm. Already people have begun the task of creating quantum systems capable of computation. The attraction of programmable matter is obvious: its is the most efficient way to use our resources and it is inherently parallel.

Tomorrow's computers will probably all be parallel architectures utilizing robust parallel algorithms. Indeed we are already spending considerable time and effort to come up with new programming languages and compilers to support this future. Quantum computers (Q-computers) are parallel by design. Q-computers can be thought of as SIMD architectures where the "data" is represented by particular quantum states and the "instructions" are the laws of Physics (which are the same everywhere). Current research in SIMD parallel programming touches on the problems we will face trying to program such architectures. The language our Q-computer programmers will use is Physics. They will deal with the complex dynamics of their programming tasks by breaking them into simpler dynamics which can be physically realised. A unique quality of Q-computer algorithms is that they will only involve local interactions between quantum states. The model of computation that is most like quantum computation is Cellular Automata (CA). All of the research and discoveries in the field in CA are immediately applicable to quantum computation. I believe that the first useful Q-computer will in fact be a quantum Cellular Automata machine (Q-CAM). The future of quantum level computation is closely tied to CA. For this reason we should strive to solve complex problems using CA models which will run "out of the box" on our Q-CAM when it is built.

Cellular Automata machines, such as the CAM-8 developed at the MIT Laboratory for Computer Science, have demonstrated the power of CA algorithms in the areas of Physical simulation (Ising spin models, Lattice Gas fluid dynamics models and polymer models), image processing (realtime 3D rendering, realtime edge detection and image enhancement), digital logic simulation and other areas. I had the privilege of working for the Information Mechanics Group at LCS and developing system level and application software for CAM-8. I subsequently worked at Phillips Laboratory (Hanscom Air Force Base) developing lattice gas codes for CAM-8 and other high performance computers. The group I worked with developed CA models for mutli-phase liquid/gas systems, microemulsions and multi-species liquid/gas systems. The progress made, both at MIT and Phillips Lab, is exciting but it is very much the "tip of the iceberg". CA models of fluid dynamics have promise for fast, exact simulations of complex fluid flows. Researchers in the MIT Earth and Planetary Sciences Department have also successfully used CA models to simulate flow through porous media. The full range of applications that CA models are suited to is unknown. What is needed is a simple to use but robust environment where CA models can continue to be explored.

CA models are pushing machines like CAM-8 to their limits. Current technology allows us to build a machine with many orders of magnitude better performance for about the same price. If we are to advance the field of CA research we need to build such a machine and use it as a testbed for new models. The biggest obstacle to CA research is the need for a CAM that is usable by the average researcher. Much effort is spent implementing CA models instead of exploring CA models. We also need a simple but powerful programming language to express our CA models. Fortunately the inherently SIMD nature of CA allows us to use many of the advancements that have already been made in the field of parallel programming. I believe that in the future we will solve many of our hardest programming problems using CA. Quantum level computation and CA is a natural marriage and advances in CA research will hopefully provide insights into quantum computing in general.