Fault Tolerant Parallel Computing in Orthogonal Shared-Memory and Related Architectures

The aim of the research summarized in this final report was to investigate a class of orthogonal shared-memory architectures and interconnection networks, and to obtain generalized methods for implementing algorithm-based fault tolerance ABFT on multiprocessor architectures. We proposed a theory based on orthogonal graphs to represent many well-known interconnection networks such as the binary m-cube, spanning-bus meshes, multistage interconnection networks, etc. A previously proposed multiprocessor architecture called the Orthogonal Multiprocessor OMP is also a special case of this method. The simplicity of the graph construction rules permits us to characterize and understand the differences and similarities among networks like the SW-banyan, the baseline network, among others. This opens the way for discovering new structures by studying different possible combinations of the parameters which define orthogonal graphs.