Cube connected Mobius ladders: an inherently deadlock-free fixed degree network
- 1 January 1993
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Parallel and Distributed Systems
- Vol. 4 (1) , 111-117
- https://doi.org/10.1109/71.205658
Abstract
The authors introduce a multiprocessor interconnection network, known ascube-connected Mobius ladders, which has an inherently deadlock-free routing strategyand hence has none of the buffering and computational overhead required bydeadlock-avoidance message passing algorithms. The basic network has a diameter phi of4n-1 for n2/sup n+2 /nodes and has a fixed node degree of 4. The network can beinterval routed in two stages and can be represented as a Cayley graph. This is the onlypractical fixed degree topology of size O(2/sup phi /) which has an inherentlydeadlock-free routing strategy, making it ideally suited for medium and large sizedtransputer networks.Keywords
This publication has 13 references indexed in Scilit:
- A combinatorial problem on Trapezoidal wordsTheoretical Computer Science, 2002
- The de Bruijn multiprocessor network: a versatile parallel processing and sorting network for VLSIIEEE Transactions on Computers, 1989
- Interval RoutingThe Computer Journal, 1987
- A DAG-Based Algorithm for Prevention of Store-and-Forward Deadlock in Packet NetworksIEEE Transactions on Computers, 1981
- Prevention of Deadlocks in Packet-Switched Data Transport SystemsIEEE Transactions on Communications, 1981
- Deadlock Avoidance in Store-and-Forward Networks--I: Store-and-Forward DeadlockIEEE Transactions on Communications, 1980
- The cube-connected-cycles: A versatile network for parallel computationPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1979
- Deadlock-free packet switching networksPublished by Association for Computing Machinery (ACM) ,1979
- A large scale, homogeneous, fully distributed parallel machine, IACM SIGARCH Computer Architecture News, 1977
- Parallel Processing with the Perfect ShuffleIEEE Transactions on Computers, 1971