CaltechAUTHORS
  A Caltech Library Service

Deadlock Free Message Routing in Multiprocessor Interconnection Networks

Dally, William J. and Seitz, Charles L. (1986) Deadlock Free Message Routing in Multiprocessor Interconnection Networks. California Institute of Technology . (Unpublished) http://resolver.caltech.edu/CaltechCSTR:1986.5206-tr-86

[img]
Preview
Other (Adobe PDF (1.2MB))
See Usage Policy.

1185Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechCSTR:1986.5206-tr-86

Abstract

A deadlock-free routing algorithm can be generated for arbitrary interconnection networks using the concept of virtual channels. A necessary and sufficient condition for deadlockfree routing is the absence of cycles in the channel dependency graph. Given an arbitrary network and a routing function, the cycles of the channel dependency graph can be removed by splitting physical channels into groups of virtual channels. This method is used to develop deadlock-free routing algorithms for k-ary n-cubes, for cube connected cycles, and for shuffleexchange networks.


Item Type:Report or Paper (Technical Report)
Group:Computer Science Technical Reports
Record Number:CaltechCSTR:1986.5206-tr-86
Persistent URL:http://resolver.caltech.edu/CaltechCSTR:1986.5206-tr-86
Usage Policy:You are granted permission for individual, educational, research and non-commercial reproduction, distribution, display and performance of this work in any format.
ID Code:26907
Collection:CaltechCSTR
Deposited By: Imported from CaltechCSTR
Deposited On:30 Nov 2001
Last Modified:26 Dec 2012 14:09

Repository Staff Only: item control page