On some global operations in faulty SIMD hypercubes

Author

Sengupta, Amit ; Raghavendra, C.S.

Author_Institution

Sch. of Electr. Eng. & Comput. Sci., Washington State Univ., Pullman, WA, USA

fYear

1996

fDate

15-19 Apr 1996

Firstpage

579

Lastpage

583

Abstract

Extends our prior results [Raghavendra & Sridhar (1992, 1993), Sengupta & Raghavendra (1994)] to obtain algorithms for performing all-to-all broadcast, global sum and broadcast operation in an N-node (N=2ⁿ), n-dimensional faulty SIMD hypercube, Q_n (n⩾9), with the number of faults n-1<f⩽2n-3. We also discuss optimal algorithms for one-to-all personalized broadcasting and all-to-one personalized broadcasting in a Q_n with the number of faults f⩽n-1. Our broadcasting and global sum algorithms require 2n+19 steps and n+O(log n) steps, whereas the all-to-all broadcast algorithm requires 10N+15 steps

Keywords

broadcasting; computational complexity; fault tolerant computing; hypercube networks; parallel algorithms; all-to-all broadcasting; all-to-one personalized broadcasting; broadcast operation; faulty SIMD hypercubes; global operations; global sum algorithm; one-to-all personalized broadcasting; optimal algorithms; Broadcasting; Casting; Computer science; Concurrent computing; Emulation; Fault tolerance; Hypercubes; Network topology; Robustness; Routing;

fLanguage

English

Publisher

ieee

Conference_Titel

Parallel Processing Symposium, 1996., Proceedings of IPPS '96, The 10th International

Conference_Location

Honolulu, HI

Print_ISBN

0-8186-7255-2

Type

conf

DOI

10.1109/IPPS.1996.508115

Filename

508115