Title :
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
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=2n), n-dimensional faulty SIMD hypercube, Qn (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 Qn 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;
Conference_Titel :
Parallel Processing Symposium, 1996., Proceedings of IPPS '96, The 10th International
Conference_Location :
Honolulu, HI
Print_ISBN :
0-8186-7255-2
DOI :
10.1109/IPPS.1996.508115
