Binary Cube Emulation of Butterfly Networks Encoded by Gray Code

Abstract

We present algorithms for binary cube networks that emulate butterfly network computations on binary-reflected Gray-coded data in the same time complexity as that required for binary-coded data. The code conversion required for the emulation with binary-reflected Gray-coded data is either performed in local memories or through concurrent exchanges. The emulation of a butterfly network with one or two rows mapped to each binary cube node requires n communication cycles on an n-cube. For more than two rows per node, one additional communication cycle is required for every pair of rows, with concurrent communication on all channels of every node. The encoding upon completion can be either binary, or binary-reflected Gray code, or any combination thereof, without affecting the communication complexity. © 1994 Academic Press, Inc.