Least common ancestor networks
- 31 December 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 507-513
- https://doi.org/10.1109/ipps.1993.262825
Abstract
Least common ancestor networks (LCANs) are introduced and shown to be a class of networks that include fat-trees, baseline networks, SW-banyans and the router networks of the TRAC 1.1 and 2.0, and the CM-5. Some LCAN properties are stated and the permutation routing capabilities of an important subclass are analyzed. Simulation results for three permutation classes verify the accuracy of an iterative solution for a randomized routing strategy.Keywords
This publication has 10 references indexed in Scilit:
- The network architecture of the Connection Machine CM-5 (extended abstract)Published by Association for Computing Machinery (ACM) ,1992
- The KYKLOS multicomputer network: interconnection strategies, properties, and applicationsIEEE Transactions on Computers, 1991
- On Finding Lowest Common Ancestors: Simplification and ParallelizationSIAM Journal on Computing, 1988
- Fat-trees: Universal networks for hardware-efficient supercomputingIEEE Transactions on Computers, 1985
- Fast Algorithms for Finding Nearest Common AncestorsSIAM Journal on Computing, 1984
- A Survey of Interconnection NetworksComputer, 1981
- A Self-Routing Benes Network and Parallel Permutation AlgorithmsIEEE Transactions on Computers, 1981
- On a Class of Multistage Interconnection NetworksIEEE Transactions on Computers, 1980
- Parallel Permutations of Data: A Benes Network Control Algorithm for Frequently Used PermutationsIEEE Transactions on Computers, 1978
- A Study of Non-Blocking Switching NetworksBell System Technical Journal, 1953