Name
Abstract | ||
|---|---|---|
In this paper, we develop algorithms in order of efficiency for all-to-all broadcast problem in an N = 2n-node n-dimensional faulty SIMD hypercube, Qn, with up to n$-$ 1 node faults. The algorithms use a property of a certain ordering of dimensions. Our analysis includes startup time(驴) and transfer time(β). We have established the lower bound for such an algorithm to be n驴 + (2N$-$ 3)Lβ in a faulty hypercube with at most n$-$ 1 faults (each node has a value of L bytes). Our best algorithm requires 2n驴 + 2NLβ and is near-optimal. We develop an optimal algorithm for matrix multiplication in a faulty hypercube using all-to-all broadcast and compare the efficiency of all-to-all broadcast approach with broadcast approach and global sum approach for matrix multiplication. The algorithms are congestion-free and applicable in the context of available hypercube machines. |
Year | DOI | Venue |
|---|---|---|
1998 | 10.1109/71.689442 | IEEE Trans. Parallel Distrib. Syst. |
Keywords | Field | DocType |
all-to-all broadcast,best algorithm,global sum approach,all-to-all broadcast problem,broadcast approach,n-dimensional faulty simd hypercube,faulty hypercube,matrix multiplication,available hypercube machine,faulty simd hypercubes,all-to-all broadcast approach,lower bound,linear algebra,concurrent computing,broadcast,fault tolerance,hypercubes,computer networks,image processing,matrices,broadcasting,parallel algorithms,routing | Broadcasting,Byte,All to all broadcast,Computer science,Upper and lower bounds,SIMD,Fault tolerance,Matrix multiplication,Hypercube,Distributed computing | Journal |
Volume | Issue | ISSN |
9 | 6 | 1045-9219 |
Citations | PageRank | References |
1 | 0.41 | 21 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Amit Sengupta | 1 | 8 | 1.72 |
| C. S. Raghavendra | 2 | 1 | 0.41 |