Fast router and hardware-assisted fast routing method

• US 7,342,414 B2
• Filed: 01/31/2003
• Issued: 03/11/2008
• Est. Priority Date: 02/01/2002
• Status: Expired due to Fees

• Current Assignee: California Institute of Technology, Regents of the University of California (University of California)
• Original Assignee: California Institute of Technology, Regents of the University of California (University of California)
• Inventors: Wawrzynek, John, Huang, Randy, DeHon, André
• Primary Examiner(s): Barnie; Rexford
• Assistant Examiner(s): White; Dylan
• Application Number:
  US10/356,710
• Publication Number:
  US 20030174723A1
• Time in Patent Office: 1,866 Days
• Field of Search: 326 37- 41, 326/47
• US Class Current: 326/41
• CPC Class Codes: H04L 45/26 Route discovery packet
• CPC Class Codes: H04L 49/10 characterised by the switching fabric construction
• CPC Class Codes: H04L 49/15 Interconnection of switching modules
• CPC Class Codes: H04L 49/1507 Distribute and route fabrics, e.g. sorting-routing or Batcher-Banyan
• CPC Class Codes: H04L 49/25 Routing or path finding in a switch fabric
• CPC Class Codes: H04L 49/253 using establishment or release of connections between ports
• CPC Class Codes: H04L 49/30 Peripheral units, e.g. input or output ports
• CPC Class Codes: H04L 49/50 Overload detection or protection within a single switching element

Abstract

A fast router and a fast hardware-assisted routing method are disclosed in a network having endpoints, switches and interconnect links. The switches are programmable to allow endpoints to be connected through a particular configuration of switches. The switches also comprise: propagation circuitry which allows a search signal to be propagated through the network; allocation circuitry to set the configuration of switches once a path has been found; and deallocation circuitry to clear a configuration of switches once no path has been found.

Claims

1. A network comprising:

a plurality of endpoints connectable through interconnect links; and

a plurality of switchpoints to programmably connect one or more of the interconnect links, a path between endpoints being determined by a configuration of switchpoints,

wherein the switchpoints include propagation circuitry to propagate a search signal in parallel through a plurality of unused paths in the network, to identify the configuration of switchpoints allowing a path between a first endpoint and a second endpoint to be established.

2. The network of claim 1, wherein the switchpoints include switchpoints having at least one parent channel and at least two child channels, the propagation circuitry comprising a first OR gate to send a status signal of the child channels to the at least one parent channel.

3. The network of claim 2, wherein the child channels are connectable to the parent channel and between themselves through up-down switches controlling connection between the parent channel and a child channel and a crossover switch controlling connection between the child channels, the status signal having a status path distinct from a child-parent path connecting the child channels to the parent channels and a child-child path connecting the child channels between themselves.

4. The network of claim 3, wherein the propagation circuitry further comprises enabling circuitry to enable the status signal to be received by the parent channel.

5. The network of claim 4, wherein the enabling circuitry comprises a tristate buffer enabling the status signal to be received by the parent channel during a time period where the up-down switches do not establish a connection between the parent channel and a child channel.

6. The network of claim 5, wherein the status signal is not sent to the parent channel in case the crossover switch establishes a connection between the child channels.

7. The network of claim 1, wherein the switchpoints further comprise delay circuitry, to delay the search signal each time a switchpoint is in use.

8. The network of claim 7, wherein the delay circuitry comprises a delay flip-flop.

9. The network of claim 3, further comprising:

a delay circuit selectively connected to the first OR gate, wherein the status signal is delayed when at least one up-down switch is in use and is not delayed when no up-down switch is in use.

10. The network of claim 3, further comprising:

a delay circuit selectively connected to the first OR gate, wherein the status signal is delayed when at least one among the up-down and crossover switches is in use and is not delayed when the up-down and crossover switches are not in use.

11. The network of claim 10, further comprising

a second OR gate and a multiplexer connected to the second OR gate, wherein the second OR gate is indicative of at least one switch being set among the up-down and crossover switches, the second OR gate controlling propagation or delay of the status signal.

12. The network of claim 3, further comprising:

a delay circuit selectively connected to the first OR gate, wherein the status signal is not delayed when the up-down switches are not in use or the search signal has a direction consistent with a condition of the up-down switches and the status signal is delayed when the search signal has a direction inconsistent with a condition of the up-down switches.

13. The network of claim 1, wherein the switchpoints further comprise identification circuitry to identify the presence of the search signal on two or more child channels.

14. The network of claim 3, wherein the switchpoints comprise allocation circuitry to set the configuration of switchpoints between the first endpoint and the second endpoint once the path between the first endpoint and the second endpoint has been established.

15. The network of claim 14, wherein choice among equivalent paths is made randomly.

16. The network of claim 14, wherein the allocation circuitry comprises:

circuitry acting as a global route binary tree within the network, said circuitry been able to retrieve path-forming switchpoints once the path from the first endpoint to the second endpoint has been established, the path-forming switchpoints including a crossover switchpoint, the crossover switchpoint having at least a crossover switchpoint parent channels and at least two crossover switchpoint child channels, the search signal having been propagated to the crossover switchpoint child channels;

means for deasserting the search signal from the crossover switchpoint child channels;

means for establishing connection of the crossover switchpoint child channels to a voltage source, thus establishing an allocation voltage value on the crossover switchpoint child channels;

means to propagate the allocation voltage value to other path-forming switchpoints; and

means for setting the other path-forming switchpoints once the other path-forming switchpoints have been reached by the propagated allocation voltage value.

17. The network of claim 16, wherein choice among equivalent paths is made randomly.

18. The network of claim 1, wherein the switchpoints comprise deallocation circuitry to clear switchpoints pertaining to an existing configuration of switchpoints once no path between the first endpoint and the second endpoint has been established.

19. A network comprising:

a plurality of endpoints connectable through interconnects; and

a plurality of programmable switchpoints to connect one or more of the interconnects,

wherein the switchpoints and the interconnects act as;

search circuitry during a search phase where a search signal is propagated in parallel through a plurality of free paths in the network to identify a configuration of switchpoints establishing a path between a first endpoint and at least one second endpoint;

allocation circuitry during an allocation phase where the switchpoints of the configuration of switchpoints establishing the path are set;

victimization circuitry during a deallocation phase where set switchpoints are cleared; and

path-establishing circuitry during normal operation of the network.

20. A hardware-assisted method to route a signal between a first endpoint and a second endpoint on a network having connections and switchpoints, comprising:

determining unused network connections; and

driving a search signal into the network along a plurality of the unused network connections to identify a configuration of switchpoints allowing a path between the first endpoint and the second endpoint to be established.

21. The method of claim 20, further comprising:

allocating the established path by setting the configuration of switchpoints.

22. The method of claim 20,

wherein driving a search signal comprises:

driving a first search signal from the first endpoint to a first switchpoint;

driving a second search signal from the second endpoint to a second switchpoint; and

propagating the first and second search signal through the plurality of the unused network connections from the first and second switchpoint to other switchpoints,

wherein the path between the first endpoint and the second endpoint is established once a switchpoint to which both the first search signal and the second search signal have been propagated is determined.

23. The method of claim 20, wherein, when multiple configurations of switchpoints allowing a path between the first and second endpoint to be established are determined, a single configuration is selected.

24. The method of claim 23, wherein the single configuration is selected randomly.

25. The method of claim 24, wherein the single configuration is selected according to a Pseudo-Random Number Generator—

Cyclic-Segmented Parallel Prefix (PRNG-CSPP) generation scheme.

26. The method of claim 20, wherein, when no configuration of switchpoints allowing a path between the first and second endpoint to be established are determined, the path is established by using resources from an already existing path.

27. The method of claim 26, wherein the already existing path is the least congested path among existing paths.

28. The method of claim 20, wherein, when no configuration of switchpoints allowing a path between the first and second point to be established are determined, the path is established by victimizing at least one conflicting path to expose an available path.

29. The method of claim 28, wherein the path to be victimized is selected randomly.

30. The method of claim 28, wherein the path to be victimized is the path with least congestion among existing paths.

31. The method of claim 28, wherein the path to be victimized is selected randomly from among the paths with least congestion among existing paths.

32. The method of claim 28 wherein victimizing is performed by hardware.

33. The method of claim 28 wherein victimizing is performed by software.

34. A network comprising:

a plurality of endpoints connectable through interconnects; and

a plurality of switching elements to programmably connect one or more of the interconnects, a path between endpoints being determined by a configuration of switching elements,

wherein the switching elements comprise propagation hardware to propagate a search signal in parallel through a plurality of available paths in the network, in order to identify a configuration of switching elements allowing a path between one endpoint and a plurality of other endpoints to be established.

35. The network of claim 34, wherein each switching element comprises a state bit to be set during a current net search.

36. A method for searching a path, in a network having a plurality of switchpoints, between a source and a plurality of destinations, the method comprising, for each destination:

propagating a search signal from the destination along a plurality of unused network connections in parallel to identify path-establishing switchpoints establishing a path between the source and the destination; and

allocating the established path by setting the path-establishing switchpoints.

37. The method of claim 36, further comprising:

ordering each destination according to a length of a path between the source and that destination before propagating a search signal.

38. A method for establishing a route between a source and at least a destination on a programmable routing network having a plurality of switchpoints, comprising:

in a first time step, starting a route search by driving a search signal from the source along a plurality of unused network connections originating from the source;

upon reaching of a switchpoint, in a second time step, propagating the search signal along a plurality of unused network connections originating from the switchpoint;

in case the search signal reaches the switchpoint from more than one direction, determining a preferred direction of propagation of the search signal originating from the switchpoint; and

terminating the route search when the search signal reaches the at least one destination.

39. The method of claim 38, further comprising keeping track of a number of time steps used to reach any switchpoint.

40. The method of claim 38, wherein an allocation signal is sent along a preferred route determined during the route search.

41. A method for establishing a route between a source and at least one destination on a programmable routing network having a plurality of switchpoints, comprising:

starting a route search by driving a search signal from the source to one or more first switchpoints;

propagating the search signal in parallel along a plurality of paths from the one or more first switchpoints to other switchpoints; and

terminating the route search when the signal reaches the at least one destination.

42. The method of claim 41, wherein the search signal is driven along multiple directions, and wherein a preferred direction is chosen each time a switchpoint is reached from multiple directions.

43. A network comprising:

a plurality of endpoints connectable through interconnect links; and

a plurality of switchpoints to programmably connect one or more of the interconnect links, a path between endpoints being determined by a configuration of switchpoints,

wherein the switchpoints include propagation circuitry to propagate a search signal through the network, to identify the configuration of switchpoints allowing a path between a first endpoint and a second endpoint to be established,

wherein the switchpoints include switchpoints having at least one parent channel and at least two child channels, the propagation circuitry comprising a first OR gate to send a status signal of the child channels to the at least one parent channel,

wherein the child channels are connectable to the parent channel and between themselves through up-down switches controlling connection between the parent channel and a child channel and a crossover switch controlling connection between the child channels, the status signal having a status path distinct from a child-parent path connecting the child channels to the parent channels and a child-child path connecting the child channels between themselves,

wherein the propagation circuitry further comprises enabling circuitry to enable the status signal to be received by the parent channel,

wherein the enabling circuitry comprises a tristate buffer enabling the status signal to be received by the parent channel during a time period where the up-down switches do not establish a connection between the parent channel and a child channel.

44. The network of claim 43, wherein the status signal is not sent to the parent channel in case the crossover switch establishes a connection between the child channels.

45. A network comprising:

a plurality of endpoints connectable through interconnect links; and

a plurality of switchpoints to programmably connect one or more of the interconnect links, a path between endpoints being determined by a configuration of switchpoints, wherein the switchpoints include propagation circuitry to propagate a search signal through the network, to identify the configuration of switchpoints allowing a path between a first endpoint and a second endpoint to be established, wherein the switchpoints include switchpoints having at least one parent channel and at least two child channels, the propagation circuitry comprising a first OR gate to send a status signal of the child channels to the at least one parent channel,

wherein the child channels are connectable to the parent channel and between themselves through up-down switches controlling connection between the parent channel and a child channel and a crossover switch controlling connection between the child channels, the status signal having a status path distinct from a child-parent path connecting the child channels to the parent channels and a child-child path connecting the child channels between themselves,

a delay circuit selectively connected to the first OR gate, wherein the status signal is delayed when at least one among the up-down and crossover switches is in use and is not delayed when the up-down and crossover switches are not in use; and

a second OR gate and a multiplexer connected to the second OR gate, wherein the second OR gate is indicative of at least one switch being set among the up-down and crossover switches, the second OR gate controlling propagation or delay of the status signal.

46. A network comprising:

a plurality of endpoints connectable through interconnect links; and

a plurality of switchpoints to programmably connect one or more of the interconnect links, a path between endpoints being determined by a configuration of switchpoints, wherein the switchpoints include propagation circuitry to propagate a search signal through the network, to identify the configuration of switchpoints allowing a path between a first endpoint and a second endpoint to be established, wherein the switchpoints include switchpoints having at least one parent channel and at least two child channels, the propagation circuitry comprising a first OR gate to send a status signal of the child channels to the at least one parent channel,

wherein the child channels are connectable to the parent channel and between themselves through up-down switches controlling connection between the parent channel and a child channel and a crossover switch controlling connection between the child channels, the status signal having a status path distinct from a child-parent path connecting the child channels to the parent channels and a child-child path connecting the child channels between themselves,

a delay circuit selectively connected to the first OR gate, wherein the status signal is not delayed when the up-down switches are not in use or the search signal has a direction consistent with a condition of the up-down switches and the status signal is delayed when the search signal has a direction inconsistent with a condition of the up-down switches.

47. A network comprising:

a plurality of endpoints connectable through interconnect links; and

a plurality of switchpoints to programmably connect one or more of the interconnect links, a path between endpoints being determined by a configuration of switchpoints, wherein the switchpoints include propagation circuitry to propagate a search signal through the network, to identify the configuration of switchpoints allowing a path between a first endpoint and a second endpoint to be established, wherein the switchpoints include switchpoints having at least one parent channel and at least two child channels, the propagation circuitry comprising a first OR gate to send a status signal of the child channels to the at least one parent channel,

wherein the child channels are connectable to the parent channel and between themselves through up-down switches controlling connection between the parent channel and a child channel and a crossover switch controlling connection between the child channels, the status signal having a status path distinct from a child-parent path connecting the child channels to the parent channels and a child-child path connecting the child channels between themselves, wherein the switchpoints comprise allocation circuitry to set the configuration of switchpoints between the first endpoint and the second endpoint once the path between the first endpoint and the second endpoint has been established, wherein choice among equivalent paths is made randomly.

48. A network comprising:

a plurality of endpoints connectable through interconnect links; and

a plurality of switchpoints to programmably connect one or more of the interconnect links, a path between endpoints being determined by a configuration of switchpoints, wherein the switchpoints include propagation circuitry to propagate a search signal through the network, to identify the configuration of switchpoints allowing a path between a first endpoint and a second endpoint to be established, wherein the switchpoints include switchpoints having at least one parent channel and at least two child channels, the propagation circuitry comprising a first OR gate to send a status signal of the child channels to the at least one parent channel,

wherein the child channels are connectable to the parent channel and between themselves through up-down switches controlling connection between the parent channel and a child channel and a crossover switch controlling connection between the child channels, the status signal having a status path distinct from a child-parent path connecting the child channels to the parent channels and a child-child path connecting the child channels between themselves, wherein the switchpoints comprise allocation circuitry to set the configuration of switchpoints between the first endpoint and the second endpoint once the path between the first endpoint and the second endpoint has been established,

wherein the allocation circuitry comprises;

circuitry acting as a global route binary tree within the network, said circuitry been able to retrieve path-forming switchpoints once the path from the first endpoint to the second endpoint has been established, the path-forming switchpoints including a crossover switchpoint, the crossover switchpoint having at least a crossover switchpoint parent channels and at least two crossover switchpoint child channels, the search signal having been propagated to the crossover switchpoint child channels;

means for deasserting the search signal from the crossover switchpoint child channels;

means for establishing connection of the crossover switchpoint child channels to a voltage source, thus establishing an allocation voltage value on the crossover switchpoint child channels;

means to propagate the allocation voltage value to other path-forming switchpoints; and

means for setting the other path-forming switchpoints once the other path-forming switchpoints have been reached by the propagated allocation voltage value.

49. The network of claim 48, wherein choice among equivalent paths is made randomly.

50. A hardware-assisted method to route a signal between a first endpoint and a second endpoint on a network having connections and switchpoints, comprising:

determining unused network connections; and

driving a search signal into the network to identify a configuration of switchpoints allowing a path between the first endpoint and the second endpoint to be established,

wherein driving a search signal comprises;

driving a first search signal from the first endpoint to a first switchpoint;

driving a second search signal from the second endpoint to a second switchpoint; and

propagating the first and second search signal from the first and second switchpoint to other switchpoints,

wherein the path between the first endpoint and the second endpoint is established once a switchpoint to which both the first search signal and the second search signal have been propagated is determined.

51. A hardware-assisted method to route a signal between a first endpoint and a second endpoint on a network having connections and switchpoints, comprising:

determining unused network connections; and

driving a search signal into the network to identify a configuration of switchpoints allowing a path between the first endpoint and the second endpoint to be established, wherein, when no configuration of switchpoints allowing a path between the first and second point to be established are determined, the path is established by victimizing at least one conflicting path to expose an available path, wherein the path to be victimized is selected randomly.

52. A hardware-assisted method to route a signal between a first endpoint and a second endpoint on a network having connections and switchpoints, comprising:

determining unused network connections; and

driving a search signal into the network to identify a configuration of switchpoints allowing a path between the first endpoint and the second endpoint to be established, wherein, when no configuration of switchpoints allowing a path between the first and second point to be established are determined, the path is established by victimizing at least one conflicting path to expose an available path, wherein the path to be victimized is selected randomly from among the paths with least congestion among existing paths.

53. A method for searching a path, in a network having a plurality of switchpoints, between a source and a plurality of destinations, the method comprising, for each destination:

propagating a search signal from the destination along unused network connections to identify path-establishing switchpoints establishing a path between the source and the destination;

allocating the established path by setting the path-establishing switchpoints; and

ordering each destination according to a length of a path between the source and that destination before propagating a search signal.