Method and apparatus for deadlock-free routing around an unusable routing component in an N-dimensional network
First Claim
1. A method for deadlock-free routing around an unusable routing component, wherein the method routes data from a source router to a destination router of a network, the method comprising the steps of:
- determining a first direction from the unusable routing component to an edge of the network; and
routing a path for the data from the source router to the destination router which bypasses the unusable routing component and limits use of an immediately adjacent routing component in the network between the unusable routing component and the edge in the first direction.
1 Assignment
0 Petitions
Accused Products
Abstract
A method and apparatus for deadlock-free routing around an unusable routing component in a network reroutes paths between source and destination nodes by initially identifying an unusable routing component. A shadow direction within the network is then determined, the shadow direction being from the unusable routing component to an edge of the network. The paths between nodes are then rerouted so that the paths bypass the unusable routing component and limit the use of any routing components in the network between the unusable routing component and the edge in the shadow direction.
-
Citations
32 Claims
-
1. A method for deadlock-free routing around an unusable routing component, wherein the method routes data from a source router to a destination router of a network, the method comprising the steps of:
-
determining a first direction from the unusable routing component to an edge of the network; and routing a path for the data from the source router to the destination router which bypasses the unusable routing component and limits use of an immediately adjacent routing component in the network between the unusable routing component and the edge in the first direction. - View Dependent Claims (2, 3, 4, 5)
-
-
6. A method for deadlock-free routing around an unusable routing component, wherein the method routes data from a source router to a destination router of a network, the method comprising the steps of:
-
identifying the unusable routing component; determining a first direction from the unusable routing component to an edge of the network; identifying a plurality of shadow routing components; and routing a path for the data from the source router to the destination router which bypasses the unusable routing component and limits use of any routing components in the network between the unusable routing component and the edge in the first direction. - View Dependent Claims (7, 8)
-
-
9. A method for deadlock-free routing around an unusable routing component, wherein the method routes data from a source router to a destination router of a network, the method comprising the steps of:
-
identifying the unusable routing component; determining a first direction from the unusable routing component to an edge of the network; and routing a path for the data from the source router to the destination router in a second direction away from the edge which bypasses the unusable routing component and limits use of any routing components in the network between the unusable routing component and the edge in the first direction.
-
-
10. A method for deadlock-free routing around an unusable routing component, wherein the method routes data from a source router to a destination router of a network, the method comprising the steps of:
-
identifying the unusable routing component; determining a first direction from the unusable routing component to an edge of the network; and routing a path for the data from the source router to the destination router which bypasses the unusable routing component and limits use of any routing components in the network between the unusable routing component and the edge in the first direction, wherein the routing includes routing the data through a first router, wherein the first router is located in the network between the unusable routing component and the edge in the first direction, provided the first router is not the destination router, and provided the path does not turn at the first router.
-
-
11. A method for deadlock-free routing of data around an unusable routing component in a network, the method comprising the steps of:
-
(a) determining a shadow direction from the unusable routing component to an edge of the network; (b) determining whether the data can progress according to an original path; (c) routing the data along the original path, provided the data can progress according to the original path; and (d) moving the data in a first direction, provided the data cannot progress according to the original path, wherein the first direction is opposite the shadow direction. - View Dependent Claims (12, 13)
-
-
14. An apparatus for deadlock-free routing of data around an unusable routing component in a network, wherein the data is originally routed from a source router to a destination router, wherein the apparatus comprises:
-
an unusable router register which stores an identifier of the unusable routing component; and control logic, communicatively coupled with the unusable router register, to determine a first direction from the unusable routing component to an edge of the network and to route the data to the destination router via a path which bypasses the unusable routing component and limits use of an immediately adjacent routing component in the network between the unusable routing component and the edge in the first direction. - View Dependent Claims (15, 16, 17, 18, 19)
-
-
20. A system comprising:
-
a plurality of processing nodes, wherein each of the plurality of processing nodes includes a processor and a memory device; and a plurality of routing devices coupled to the plurality of processing nodes, wherein each of the plurality of routing devices transfers data to other routing devices, and wherein each of the plurality of routing devices includes, an unusable router register which contains an identifier of an unusable routing component, and control logic, communicatively coupled with the unusable router register, to determine a first direction from the unusable routing component to an edge of the system and to route the data via a path which bypasses the unusable routing component and limits use of an immediately adjacent routing component in the system between the unusable routing component and the edge in the first direction. - View Dependent Claims (21, 22, 23, 24)
-
-
25. An apparatus for deadlock-free routing of data around an unusable routing component, wherein the data is routed from a source router to a destination router in a network, the apparatus comprising:
-
an unusable router register to store an identifier of the unusable routing component; and control logic, communicatively coupled to the unusable router register, to determine a first direction from the unusable routing component to an edge of the network, to identify a plurality of shadow routing components, and to route the data from the source router to the destination router bypassing the unusable routing component and limiting use of any routing components between the unusable routing component and the edge in the first direction.
-
-
26. An apparatus for deadlock-free routing around an unusable routing component, wherein the data is routed from a source router to a destination router in a network, the apparatus comprising:
-
an unusable router register to store an identifier of the unusable routing component; and control logic, communicatively coupled to the unusable router register, to determine a first direction from the unusable routing component to an edge of the network, and to route the data from the source router to the destination router bypassing the unusable routing component and limiting use of any routing components in the network between the unusable routing component and the edge in the first direction, wherein the routing includes routing the data through a first router located between the unusable routing component and the edge in the first direction, provided the first router is not the destination router, and provided the routing does not turn at the first router.
-
-
27. A system comprising:
-
a plurality of processing nodes, wherein each of the plurality of processing nodes includes a processor and a memory device; and a plurality of routing devices coupled to the plurality of processing nodes, wherein each of the plurality of routing devices transfers data to other routing devices, and wherein each of the plurality of routing devices includes, an unusable router register to store identifiers of one or more unusable routing components; and control logic, communicatively coupled to the unusable router register, to determine a first direction from one of the one or more unusable routing component to an edge of the system, to identify a plurality of shadow routing components, and to route the data from a first routing device of the plurality of routing devices to a second routing device of the plurality of routing devices bypassing the one of the one or more unusable routing components and limiting use of any routing components in the system between the one of the one or more unusable routing components and the edge in the first direction.
-
-
28. A system comprising:
-
a plurality of processing nodes, wherein each of the plurality of processing nodes includes a processor and a memory device; and a plurality of routing devices coupled to the plurality of processing nodes including a first routing device, a second routing device, and a third routing device, wherein each of the plurality of routing devices transfers data to other routing devices, and wherein each of the plurality of routing devices includes, an unusable router register to store identifiers of one or more unusable routing components; and control logic, communicatively coupled to the unusable router register, to determine a first direction from a first unusable routing component of the one or more unusable routing components to an edge of the system, and to route the data from the first routing device to the second routing device bypassing the first unusable routing component, limiting use of any routing components in the system between the first unusable routing component and the edge in the first direction, and routing the data through the third routing device located between the first unusable routing component and the edge in the first direction, provided the second routing device and the third routing device are different routing devices, and provided the routing does not turn at the third routing device.
-
-
29. A machine-readable storage medium having stored therein a plurality of programming instructions for use by a processor, wherein the plurality of programming instructions implements the method steps of:
-
determining a first direction from an unusable routing component to an edge of a network; and routing a path for the data from the source router to the destination router which bypasses the unusable routing component and limits use of an immediately adjacent routing component in the network between the unusable routing component and the edge in the first direction. - View Dependent Claims (30)
-
-
31. A machine-readable storage medium having stored therein a plurality of programming instructions for use by a processor, wherein the plurality of programming instructions implements the method steps of:
-
determining a first direction from an unusable routing component to an edge of a network; identifying a plurality of shadow routing components; and routing a path for the data from the source router to the destination router which bypasses the unusable routing component and limits use of any routing components in the network between the unusable routing component and the edge in the first direction.
-
-
32. A machine-readable storage medium having stored therein a plurality of programming instructions for use by a processor, wherein the plurality of programming instructions implements the method steps of:
-
determining a first direction from an unusable routing component to an edge of the network; and routing a path for the data from the source router to the destination router which bypasses the unusable routing component and limits use of any routing components in the network between the unusable routing component and the edge in the first direction, wherein the routing includes routing the data through a first router, wherein the first router is located in the network between the unusable routing component and the edge in the first direction, provided the first router is not the destination router, and provided the path does not turn at the first router.
-
Specification