Loading...
Please wait, while we are loading the content...
Similar Documents
An Eecient Algorithm for Gray{to{binary Permutation on Hypercubes an Eecient Algorithm for Gray{to{binary Permutation on Hypercubes
| Content Provider | Semantic Scholar |
|---|---|
| Author | Ho, Ching-Tien Johnsson, S. Lennart Raghunath, M. T. |
| Copyright Year | 1992 |
| Abstract | Both Gray code and binary code are frequently used in mapping arrays into hy-percube architectures. While the former is preferred when communication between adjacent array elements is needed, the latter is preferred for FFT-type communication. When diierent phases of computations have diierent types of communication patterns, the need arises to remap the data. We give a nearly optimal algorithm for permuting data from a Gray code mapping to a binary code mapping on a hy-percube with communication restricted to one input and one output channel per node at a time. Our algorithm improves over the best previously known algorithm 6] by nearly a factor of two and is optimal to within a factor of n=(n ? 1) with respect to data transfer time on an n-cube. The expected speedup is connrmed by measurements on an Intel iPSC/2 hypercube. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://rodin.cs.uh.edu/~johnsson/rpt/tr-20-92.ps.gz |
| Alternate Webpage(s) | http://www.cs.uh.edu/~johnsson/rpt/tr-20-92.ps.gz |
| Alternate Webpage(s) | http://www2.cs.uh.edu/~johnsson/rpt/tr-20-92.ps.gz |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
