Boolean Cube Emulation of Butterfly Networks Encoded by Gray Code
1994 (English)In: Journal of Parallel and Distributed Computing, ISSN 0743-7315, E-ISSN 1096-0848, Vol. 20, no 3, 261-179 p.Article in journal (Refereed) Published
The authors present algorithms for butterfly emulation on binary-reflected Gray coded data that require the same number of element transfers in sequence in a Boolean cube network as for a binary encoding. The required code conversion is either performed in local memories, or through concurrent exchanges not effecting the number of element transfers in sequence. The emulation of a butterfly network with one or two elements per processor requires n communication cycles on an n-cube. For more than two elements per processor, one additional communication cycle is required for every pair of elements. The encoding on completion can be either binary, or binary reflected Gray code, or any combination thereof, without affecting the communication complexity.
Place, publisher, year, edition, pages
1994. Vol. 20, no 3, 261-179 p.
ALGORITHMS, BOOLEAN FUNCTIONS, SIMULATION
Computer and Information Science
IdentifiersURN: urn:nbn:se:kth:diva-90993OAI: oai:DiVA.org:kth-90993DiVA: diva2:507644
NR 201408052012-03-052012-03-05Bibliographically approved