Setup algorithms for cube-connected parallel computers using recursive Karnaugh maps
- 1 February 1991
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. 40 (2) , 217-221
- https://doi.org/10.1109/12.73592
Abstract
Optimal setup procedures for cube-connected networks are described. The setup patterns include paths, transpositions, cycles, and one-pass permutations. It is shown that for an N-input cube-connected network, the procedure for paths requires O(log/sub 2/ N) steps and O(N) space, the procedure for transportations and cycles requires O(N) steps and O(N) space, and the procedure for permutations takes O(N log/sub 2/ N) steps and O(N) space. It is also shown that the time complexities of the setup procedures for transpositions, cycles, and permutations can be improved as O(log/sub 2/ N) by using O(N) processors.Keywords
This publication has 15 references indexed in Scilit:
- A Microprocessor-based Hypercube SupercomputerIEEE Micro, 1986
- Finite State Model and Compatibility Theory: New Analysis Tools for Permutation NetworksIEEE Transactions on Computers, 1986
- The cosmic cubeCommunications of the ACM, 1985
- Invariant Properties of the Shuffle-Exchange and a Simplified Cost-Effective Version of the Omega NetworkIEEE Transactions on Computers, 1983
- A Survey of Interconnection NetworksComputer, 1981
- Performance of Processor-Memory Interconnections for MultiprocessorsIEEE Transactions on Computers, 1981
- The Reverse-Exchange Interconnection NetworkIEEE Transactions on Computers, 1980
- On a Class of Multistage Interconnection NetworksIEEE Transactions on Computers, 1980
- The Indirect Binary n-Cube Microprocessor ArrayIEEE Transactions on Computers, 1977
- The map method for synthesis of combinational logic circuitsTransactions of the American Institute of Electrical Engineers, Part I: Communication and Electronics, 1953