Title :
Optimal triple modular redundancy embeddings in the hypercube
Author :
Brown, Larry ; Wu, Jie
Author_Institution :
Dept. of Comput. Sci. & Eng., Florida Atlantic Univ., Boca Raton, FL, USA
Abstract :
To achieve reliability without sacrificing performance, the tasks of a computation are redundantly assigned to the processors of a hypercube multiprocessor. The computation is represented by a task interaction graph in which nodes represent tasks, and edge weights represent the amount of communication between tasks. To provide fault tolerance, each node in the graph is replaced by three nodes that act together as a triple modular redundancy (TMR) unit. We develop a formula to calculate the number of TMR units that can be supported in an n-dimensional hypercube, and a formula to calculate the distance between true TMR units. Then we give algorithms for TMR embeddings of weighted 1-level k-ary trees and unweighted rings in a hypercube. These algorithms minimize expansion, and are optimal in that they minimize dilation for a given expansion
Keywords :
fault tolerant computing; hypercube networks; redundancy; trees (mathematics); TMR embeddings; TMR unit; edge weights; fault tolerance; hypercube multiprocessor; n-dimensional hypercube; optimal triple modular redundancy embeddings; reliability; task interaction graph; triple modular redundancy; unweighted rings; weighted 1-level k-ary trees; Checkpointing; Computer science; Concurrent computing; Hardware; Hypercubes; Optimal scheduling; Processor scheduling; Redundancy; Scheduling algorithm;
Conference_Titel :
Massively Parallel Computing Systems, 1994., Proceedings of the First International Conference on
Conference_Location :
Ischia
Print_ISBN :
0-8186-6322-7
DOI :
10.1109/MPCS.1994.367027
