Tolerating Faults in Distributed-memory Multiprocessors

Iain Stewart
University of Durham

Abstract: The choice of interconnection network in the construction of a
distributed-memory multiprocessor is crucial to the performance of the
machine. It is preferable that such interconnection networks: come in
parameterized families and have a recursive structure (to aid scalability 
and programmability); are symmetric (to aid analysis and programmability); 
have a relatively small diameter (to improve message latency); 
are highly-connected (to aid fault-tolerance and data transfer);
contain embeddings of other such networks (to aid simulation); and so on. 
Of increasing importance is the capacity of such multiprocessors to tolerate 
faulty processors and faulty links. In this talk, I shall overview
some popular interconnection topologies and their ability to tolerate
faults in the context of Hamiltonian circuits and Hamiltonian paths.