Fast algorithms for bit-serial routing on a hypercube

DOI10.1007/BF02090402MaRDI QIDQ3357513zbMATH OpenOpenAlexFDO

Authors Bruce M. Maggs, William Aiello, F. Thomson Leighton, M. E. J. Newman

Publication date 1991

Published in Mathematical Systems Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf02090402

zbMATH Keywords

hypercuberoutingon-line circuit switching

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Parallel algorithms in computer science (68W10) Mathematical problems of computer architecture (68M07)

Recommendations

• Tight bounds for oblivious routing in the hypercube
• Almost optimal permutation routing on hypercubes
• Randomized routing on generalized hypercubes
• Routing automorphisms of the hypercube
• Some permutation routing algorithms for low-dimensional hypercubes

Cites work

• A Scheme for Fast Parallel Communication
• Deadlock-Free Message Routing in Multiprocessor Interconnection Networks
• Deterministic sorting in nearly logarithmic time on the hypercube and related computers
• Efficient dispersal of information for security, load balancing, and fault tolerance
• Hamming Codes, Hypercube Embeddings, and Fault Tolerance
• How to emulate shared memory
• Parallel Algorithms to Set Up the Benes Permutation Network
• Randomized Routing and Sorting on Fixed-Connection Networks
• Routing, merging, and sorting on parallel models of computation
• Sorting in \(c \log n\) parallel steps
• Tight bounds for oblivious routing in the hypercube
• Virtual cut-through: A new computer communication switching technique

Cited in

(8)

• Flit-serial packet routing on meshes and tori
• Communication in the two-way listen-in vertex-disjoint paths mode
• A new routing algorithm for cyclic shifts on BRGC hypercubes
• A unified framework for off-line permutation routing in parallel networks
• Routing multiple paths in hypercubes
• On the benefit of supporting virtual channels in wormhole routers
• Locality-preserving hash functions for general purpose parallel computation
• On the theory of interconnection networks for parallel computers

This page was built for publication: Fast algorithms for bit-serial routing on a hypercube

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3357513)