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

fYear

1994

fDate

2-6 May 1994

Firstpage

600

Lastpage

610

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;

fLanguage

English

Publisher

ieee

Conference_Titel

Massively Parallel Computing Systems, 1994., Proceedings of the First International Conference on

Conference_Location

Ischia

Print_ISBN

0-8186-6322-7

Type

conf

DOI

10.1109/MPCS.1994.367027

Filename

367027