Fast algorithms for bit-serial routing on a hypercube

DOI10.1007/BF02090402zbMath0731.68009OpenAlexW2010442238MaRDI QIDQ3357513

Bruce M. Maggs, M. E. J. Newman, William Aiello, Frank Thompson Leighton

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)

Related Items

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

Cites Work

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