Real-time emulations of bounded-degree networks

DOI10.1016/S0020-0190(98)00064-7zbMath0925.68032OpenAlexW2058010109MaRDI QIDQ1128816

Bruce M. Maggs, Eric J. Schwabe

Publication date: 13 August 1998

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0020-0190(98)00064-7

zbMATH Keywords

interconnection networksbounded-degree processor networksreal-time and work-preserving emulations

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10)

Related Items

Feedback vertex sets in mesh-based networks ⋮ Optimal broadcast on parallel locality models

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Improved sorting networks with O(log N) depth
• A framework for solving VLSI graph layout problems
• Sorting in \(c \log n\) parallel steps
• Efficiency of universal parallel computers
• Embedding meshes of trees into deBruijn graphs
• On the complexity of an optimal non-blocking commutation scheme without reorganization
• Constant-slowdown simulations of normal hypercube algorithms on the butterfly network
• Tight Bounds on the Complexity of Parallel Sorting
• Efficient Simulations among Several Models of Parallel Computers
• On multidimensional arrays of processors
• An O (log N ) deterministic packet-routing scheme
• Randomized Routing and Sorting on Fixed-Connection Networks
• Deterministic on-line routing on area-universal networks
• Optimal emulations by butterfly-like networks
• Work-preserving emulations of fixed-connection networks
• Reconfiguring Arrays with Faults Part I: Worst-Case Faults
• On-Line Algorithms for Path Selection in a Nonblocking Network
• Time-optimal simulations of networks by universal parallel computers
• Parallel Processing with the Perfect Shuffle