Improved pattern growth and reconfiguration methods for a fault- tolerant cellular architecture

TR Number



Journal Title

Journal ISSN

Volume Title


Virginia Polytechnic Institute and State University


The subject of three dissertations and a thesis written at Va. Tech under the direction of Dr. Gray, has been the development of a fault tolerant parallel architecture. The main thrust of this research has been on distributing the control of the parallel architecture through the use of the ideas behind cellular automata. The control has been distributed, because having a single control unit constitutes a "hard-core," in that a single failure in the control unit can bring down the whole system.

The parallel architectures for which these distributed control methods are relevant are described in Chapter I. These architectures include systolic arrays and ensemble architectures, such as Snyder's CHiP computer. It may be possible to extend the same ideas to the distributed control of other architectures, but this has not been investigated here. Chapter II gives the mathematical background of cellular automata on which the control methods are couched. Chapter III describes a new method for growing patterns of control states and analyzes the new method and previous methods. Chapter IV describes the corrections and improvements to Kumar's distributed reconfiguration methods that were found necessary after simulation. Chapter V documents the simulator used to verify the pattern growth and reconfiguration algorithms. The simulator may be easily extended to include solutions to the problems of distributed fault diagnosis and distributed I/0 after the solutions to these problems are fully developed.