About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Paper
An efficient algorithm for gray-to-binary permutation on hypercubes
Abstract
Both Gray code and binary code are frequently used in mapping arrays into hypercube architectures. While the former is preferred when communication between adjacent array elements is needed, the latter is preferred for FFT-type communication. When different phases of computations have different 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 hypercube with communication restricted to one input and one output channel per node at a time. Our algorithm improves over the best previously known algorithm (J. Parallel Distrib. Comput. 4, 2 (Apr. 1987), 133-172) 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 confirmed by measurements on an Intel iPSCI2 hypercube. © 1994 Academic Press, Inc.