Deadlock-Free Message Routing in Multiprocessor Interconnection Networks

DOI10.1109/TC.1987.1676939zbMath0617.68037OpenAlexW2154323564MaRDI QIDQ4727425

Charles L. Seitz, Bill Dally

Publication date: 1987

Published in: IEEE Transactions on Computers (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1109/tc.1987.1676939

zbMATH Keywords

communication networksinterconnection networksmultiprocessorsparallel processingconcurrent computationmessage passingcube-connected cyclesgraph modelvirtual channelsshuffle-exchange networksdeadlock-free routing algorithmk-ary n-cubes

Mathematics Subject Classification ID

Deterministic network models in operations research (90B10) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Applications of graph theory to circuits and networks (94C15) Theory of operating systems (68N25) Theory of software (68N99)

Related Items (49)

Methods for message routing in parallel machines ⋮ Minimal fully adaptive wormhole routing on hypercubes ⋮ Communication algorithms in \(k\)-ary \(n\)-cube interconnection networks ⋮ Flit-serial packet routing on meshes and tori ⋮ Optimal algorithms for dissemination of information in generalized communication modes ⋮ Methods and problems of communication in usual networks ⋮ Acyclic orientations do not lead to optimal deadlock-free packet routing algorithms ⋮ Deadlock-free interval routing schemes ⋮ AN ADAPTIVE FAULT-TOLERANT WORMHOLE ROUTING ALGORITHM FOR HYPERCUBES ⋮ Multiplicative circulant networks. Topological properties and communication algorithms ⋮ Deadlock-free dynamic reconfiguration over InfiniBand™ NETWORKS ⋮ A message-routing strategy for multicomputer systems ⋮ Communication throughput of interconnection networks ⋮ Augmented \(k\)-ary \(n\)-cubes ⋮ Deadlock prevention by acyclic orientations ⋮ Proof pearl: a formal proof of Dally and Seitz' necessary and sufficient condition for deadlock-free routing in interconnection networks ⋮ Deadlock-free routing in k-ary hypercube network in presence of processor failures ⋮ Worst-case end-to-end delays evaluation for \texttt{SpaceWire} networks ⋮ A mathematical model of deterministic wormhole routing in hypercube multicomputers using virtual channels ⋮ A deadlock-free communication kernel for loop architecture ⋮ On the theory of interconnection networks for parallel computers ⋮ A new approach to model virtual channels in interconnection networks ⋮ Communication delay analysis of fault-tolerant pipelined circuit switching in torus ⋮ A new general method to compute virtual channels occupancy probabilities in wormhole networks ⋮ Topological properties of the directional hypercube ⋮ NuMesh: An architecture optimized for scheduled communication. ⋮ Adaptive and fault-tolerant routing algorithms for high performance 2D torus interconnection network ⋮ Optimal routing in toroidal networks ⋮ Stirling networks: A versatile combinatorial topology for multiprocessor systems ⋮ PERFORMANCE ANALYSIS OF k-ARY n-CUBE NETWORKS WITH PIPELINED CIRCUIT SWITCHING ⋮ The restricted edge-connectivity and restricted connectivity of augmentedk-aryn-cubes ⋮ The 2D SEM: A novel high-performance and low-power mesh-based topology for networks-on-chip ⋮ An introduction to compilation issues for parallel machines ⋮ Communication in the two-way listen-in vertex-disjoint paths mode ⋮ On the benefit of supporting virtual channels in wormhole routers ⋮ Fast algorithms for bit-serial routing on a hypercube ⋮ A unified framework for off-line permutation routing in parallel networks ⋮ A Deadlock Free Shortest Path Routing Algorithm for WK-Recursive Meshes ⋮ Routing multiple paths in hypercubes ⋮ Fault-tolerant and deadlock-free routing in 2-D meshes using rectilinear-monotone polygonal fault blocks ⋮ Efficient Parallel Buffer Structure and Its Management Scheme for a Robust Network-on-Chip (NoC) Architecture ⋮ Sparse hypercube -- a minimal \(k\)-line broadcast graph. ⋮ Modeling Cache Coherence to Expose ⋮ Routing algorithms in honeycomb meshes ⋮ Real-time analysis of priority-preemptive NoCs with arbitrary buffer sizes and router delays ⋮ A survey on interval routing ⋮ PERFORMANCE ANALYSIS OF WORMHOLE ROUTED K-Ary N-TREES ⋮ An optimal multicast algorithm for cube-connected cycles ⋮ Real-time application mapping for many-cores using a limited migrative model

This page was built for publication: Deadlock-Free Message Routing in Multiprocessor Interconnection Networks