DIRECT NETWORK HAVING PLURAL DISTRIBUTED CONNECTIONS TO EACH RESOURCE

• US 20140169211A1
• Filed: 12/13/2012
• Published: 06/19/2014
• Est. Priority Date: 12/13/2012
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Peterson, Eric C., Harper, David T., Santaniello, Mark A.
• Granted Patent: US 9,258,191 B2
• Time in Patent Office: Days
• US Class Current: 370/254
• CPC Class Codes: G06F 15/173 using an interconnection network, e.g. matrix, shuffle, pyramid, star, snowflake
• CPC Class Codes: G06F 15/17381 Two dimensional, e.g. mesh, torus
• CPC Class Codes: H04L 12/42 Loop networks
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/06 Deflection routing, e.g. hot-potato routing
• CPC Class Codes: H04L 45/58 Association of routers
• CPC Class Codes: H04L 49/109 Integrated on microchip, e.g. switch-on-chip

Abstract

A direct network is described in which each resource is connected to a switching fabric via a set of two or more routing nodes. The routing nodes are distributed so as to satisfy at least one inter-node separation criterion. In one case, the separation criterion specifies that, for each resource, a number of routing nodes that share a same coordinate value with another routing node in the set (in a same coordinate dimension) is to be minimized. In some network topologies, such as a torus network, this means a number of unique loops of the direct network to which each resource is connected is to be maximized. The routing provisions described herein offer various performance benefits, such as improved latency-related performance.

Claims

1. A direct network, comprising:

a plurality of routing nodes;

a plurality of communication links that connect the routing nodes together to form a direct network topology; and

a plurality of resources,

each resource being connected to a set of two or more routing nodes,

said two or more routing nodes being dispersed within a coordinate space defined by the direct network topology, so as to satisfy at least one inter-node separation criterion.

2. The direct network of claim 1, wherein the direct network topology is a k-ary n-cube network topology.

3. The direct network of claim 1, wherein the direct network topology is a Cayley network topology.

4. The direct network of claim 1, wherein the plurality of resources includes one or more resources selected from:

processing resources;

memory resources; and

communication resources.

5. The direct network of claim 1, wherein the separation criterion specifies that, for each resource, a number of routing nodes that share a coordinate value, in a same coordinate dimension, with another resource node in the set is to be minimized.

6. The direct network of claim 1, wherein:

the direct network topology is formed by a plurality of loops, and

the separation criterion specifies that a number of unique loops to which each resource is connected is to be maximized.

7. The direct network of claim 1, wherein:

the direct network topology is formed by a plurality of loops, and

the separation criterion specifies that no more than one routing node from each set of routing nodes can be connected to a same loop.

8. The direct network of claim 1, wherein the separation criterion specifies, for each resource, that a number of pairs of routing nodes from the set that are contiguously arranged with respect to each other is to be minimized.

9. The direct network of claim 1, wherein the separation criterion specifies, for each resource, that a number of pairs of routing nodes from the set that are contiguously arranged with respect to each other is zero.

10. The direct network of claim 1, wherein said at least one separation criterion specifies, for each resource, that path lengths between pairs of routing nodes are to satisfy a path length constraint, each path length being measured in hop counts.

11. The direct network of claim 1, wherein said at least one separation criterion specifies, for each resource, that a distribution of the routing nodes in the set is to satisfy an entropy constraint.

12. The direct network of claim 1, wherein said at least one separation criterion specifies that the direct network is to exhibit a prescribed latency performance.

13. The direct network of claim 1, wherein, for each resource, the routing nodes in the set also satisfy at least one distance-based separation criterion which places a constraint on a physical distance between pairs of routing nodes in the set.

14. A method of constructing a direct network, comprising:

providing a plurality of routing nodes;

providing a plurality of communication links that connect the routing nodes together to form a direct network topology; and

connecting a plurality of resources to the routing nodes such that;

each resource is connected to a set of two or more routing nodes, and

said two or more routing nodes in the set are distributed so as to minimize a number of routing nodes that share a coordinate value, in a same coordinate dimension, with another resource node in the set.

15. The method of claim 14, wherein the direct network is formed on at least one common substrate.

16. The method of claim 15, wherein said at least one common substrate is a semiconductor chip.

17. The method of claim 15, wherein said at least one common substrate is a circuit board.

18. A direct network, comprising:

a plurality of routing nodes;

a plurality of communication links that connect the routing nodes together to form a direct network topology; and

a plurality of sets of resource links,

each set of resource links coupling a respective set of two or more routing nodes to a single resource,

the routing nodes in each set being distributed within a coordinate space defined by the direct network topology to ensure a prescribed latency performance of the direct network.

19. The direct network of claim 18, for each set, said two or more routing nodes in the set are distributed such that no pair of routing nodes in the set share a same coordinate value with respect to a same coordinate dimension.

20. The direct network of claim 18, wherein, for each set, no more than a prescribed number of routing nodes from the set are contiguously arranged with respect to each other.