Optimal routing algorithms for mesh-connected processor arrays

DOI10.1007/BF01758834zbMath0753.68011MaRDI QIDQ1188114

Thanasis Tsantilas, Sanguthevar Rajasekaran

Publication date: 13 August 1992

Published in: Algorithmica (Search for Journal in Brave)

zbMATH Keywords

randomizationgridpacket routinginterprocessor communication

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Network design and communication in computer systems (68M10) Distributed algorithms (68W15)

Related Items

Flit-serial packet routing on meshes and tori ⋮ Towards a better understanding of pure packet routing ⋮ Fast deterministic selection on mesh-connected processor arrays ⋮ Shorter queues for permutation routing on meshes ⋮ List-ranking on interconnection networks. ⋮ Randomized multipacket routing and sorting on meshes ⋮ PERMUTATION ROUTING AND SORTING ON THE RECONFIGURABLE MESH

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Lower bounds for sorting on mesh-connected architectures
• Oblivious routing with limited buffer capacity
• Indexing functions and time lower bounds for sorting on a mesh-connected computer
• A \(2n-2\) step algorithm for routing in an \(n \times n\) array with constant-size queues
• An Efficient Implementation of Batcher's Odd-Even Merge Algorithm and Its Application in Parallel Sorting Schemes
• Systolic Sorting on a Mesh-Connected Network
• An optimal routing algorithm for mesh-connected Parallel computers
• A Self-Routing Benes Network and Parallel Permutation Algorithms
• Ultracomputers
• A Scheme for Fast Parallel Communication
• Implementation of Permutation Functions in Illiac IV-Type Computers
• Sorting on a mesh-connected parallel computer