Index Transformation Algorithms in a Linear Algebra Framework
1994 (English)In: IEEE Transactions on Parallel and Distributed Systems, ISSN 1045-9219, E-ISSN 1558-2183, Vol. 5, no 12, 1302-1309 p.Article in journal (Refereed) Published
We present a linear algebraic formulation for a class of index transformations such as Gray code encoding and decoding, matrix transpose, bit reversal, vector reversal, shuffles, and other index or dimension permutations. This formulation unifies, simplifies, and can be used to derive algorithms for hypercube multiprocessors. We show how all the widely known properties of Gray codes, and some not so well-known properties as well, can be derived using this framework. Using this framework, we relate hypercube communications algorithms to Gauss-Jordan elimination on a matrix of 0's and 1's.
Place, publisher, year, edition, pages
1994. Vol. 5, no 12, 1302-1309 p.
BINARY-COMPLEMENT PERMUTE; BINARY HYPERCUBE; CONNECTION MACHINE; GRAY CODE; INDEX TRANSFORMATION; MULTIPROCESSOR COMMUNICATION; ROUTING; SHUFFLE
Computer and Information Science
IdentifiersURN: urn:nbn:se:kth:diva-90985DOI: 10.1109/71.334903OAI: oai:DiVA.org:kth-90985DiVA: diva2:507635
NR 201408052012-03-052012-03-05Bibliographically approved