Low latency dynamic route selection

• US 9,507,745 B1
• Filed: 01/12/2015
• Issued: 11/29/2016
• Est. Priority Date: 09/21/2009
• Status: Active Grant

• Current Assignee: Mellanox Technologies Limited (NVIDIA Corporation)
• Original Assignee: E.Z. Chip Technologies, Ltd.
• Inventors: Bratt, Ian Rudolf, Ramey, Carl G., Mattina, Matthew
• Primary Examiner(s): Pollack, Melvin H
• Application Number:
  US14/594,299
• Time in Patent Office: 687 Days
• Field of Search: 370/237
• US Class Current: 1/1
• CPC Class Codes: G06F 11/1482 by means of middleware or OS functionality
• CPC Class Codes: G06F 12/00 Accessing, addressing or allocating within memory systems or architectures digital input from, or digital output to record carriers, e.g. to disk storage units, G06F3/06
• CPC Class Codes: G06F 12/02 Addressing or allocation; Relocation program address sequencing G06F9/00; arrangements for selecting an address in a digital store G11C8/00
• CPC Class Codes: G06F 12/0806 Multiuser, multiprocessor or multiprocessing cache systems
• CPC Class Codes: G06F 12/0808 with cache invalidating means G06F12/0815 takes precedence
• CPC Class Codes: G06F 12/0815 Cache consistency protocols
• CPC Class Codes: G06F 12/0844 Multiple simultaneous or quasi-simultaneous cache accessing
• CPC Class Codes: G06F 12/0848 Partitioned cache, e.g. separate instruction and operand caches
• CPC Class Codes: G06F 12/0855 Overlapped cache accessing, e.g. pipeline G06F12/0846 takes precedence
• CPC Class Codes: G06F 12/0864 using pseudo-associative means, e.g. set-associative or hashing
• CPC Class Codes: G06F 12/0888 using selective caching, e.g. bypass
• CPC Class Codes: G06F 12/0891 using clearing, invalidating or resetting means
• CPC Class Codes: G06F 12/10 Address translation
• CPC Class Codes: G06F 12/1027 using associative or pseudo-associative address translation means, e.g. translation look-aside buffer [TLB]
• CPC Class Codes: G06F 12/12 Replacement control
• CPC Class Codes: G06F 12/121 using replacement algorithms
• CPC Class Codes: G06F 12/122 of the least frequently used [LFU] type, e.g. with individual count value
• CPC Class Codes: G06F 12/123 with age lists, e.g. queue, most recently used [MRU] list or least recently used [LRU] list
• CPC Class Codes: G06F 12/128 adapted to multidimensional cache systems, e.g. set-associative, multicache, multiset or multilevel
• CPC Class Codes: G06F 13/4068 Electrical coupling
• CPC Class Codes: G06F 13/4221 : being an input/output bus, e.g. ISA bus, EISA bus, PCI bus, SCSI bus
• CPC Class Codes: G06F 15/16 : Combinations of two or more digital computers each having at least an arithmetic unit, a program unit and a register, e.g. for a simultaneous processing of several programs coordinating program control therefor G06F9/52; in regulating and control system G05B
• CPC Class Codes: G06F 15/8023 : Two dimensional arrays, e.g. mesh, torus
• CPC Class Codes: G06F 21/79 : in semiconductor storage media, e.g. directly-addressable memories
• CPC Class Codes: G06F 2212/452 : Instruction code
• CPC Class Codes: G06F 2212/502 : using adaptive policy
• CPC Class Codes: G06F 2212/601 : Reconfiguration of cache memory
• CPC Class Codes: G06F 2212/6032 : Way prediction in set-associative cache
• CPC Class Codes: G06F 2212/621 : Coherency control relating to peripheral accessing, e.g. from DMA or I/O device
• CPC Class Codes: G06F 9/3004 : to perform operations on memory
• CPC Class Codes: G06F 9/4825 : Interrupt from clock, e.g. time of day
• CPC Class Codes: G06F 9/4881 : Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues
• CPC Class Codes: G06F 9/5022 : Mechanisms to release resources
• CPC Class Codes: G06F 9/544 : Buffers; Shared memory; Pipes
• CPC Class Codes: H04L 45/08 : Learning-based routing, e.g. using neural networks or artificial intelligence
• CPC Class Codes: H04L 45/22 : Alternate routing
• CPC Class Codes: H04L 45/28 : using route fault recovery
• CPC Class Codes: H04L 47/823 : Prediction of resource usage
• CPC Class Codes: H04L 47/83 : based on usage prediction
• CPC Class Codes: H04L 49/109 : Integrated on microchip, e.g. switch-on-chip

Abstract

Communicating among cores in a computing system comprising a plurality of cores, each core comprising a processor and a switch, includes: routing a packet from a core or from a device coupled to at least one core to a destination over a route including one or more cores, with an order of dimensions associated with the route being selected dynamically upon construction of the packet; routing the packet to a first core in the route over the first selected dimension; and routing the packet from the first core to the destination over the second dimension.

Claims

1. A method for communicating among cores in a computing processor comprising a plurality of cores interconnected by a mesh network, each core comprising a processor and a switch, the method comprising:

constructing a packet to route from one of the cores or from a device coupled to one of the cores;

dynamically determining a route for the packet, by selecting for the packet between a first dimension and a second, different dimension, a first oriented route that routes in the first dimension unless a turn is encountered in the route;

routing the packet from the core or from the device coupled to the one of the cores to a destination over the dynamically determined route over the first selected dimension.

2. The method of claim 1, wherein the packet is routed from the core or the device in the first dimension, until a turn is encountered in the route, with the method further comprising:

routing the packet from a subsequent one of the cores to the destination core over the second, different dimension.

3. The method of claim 1, wherein the first dimension is selected randomly for packets.

4. The method of claim 1, wherein the first dimension is selected using congestion based information.

5. The method of claim 1, wherein the first dimension is selected using destination based information.

6. The method of claim 1, wherein the cores are divided into a first subset of cores located in a first region of the mesh network, and a second subset of cores are located in a second region of the mesh network that does not overlap with the first region, with the first subset of cores routing based on dynamically determining a route, and the second subset of cores using a routing policy that is static.

7. The method of claim 1, wherein at least four devices are connected to respective cores on the perimeter of the mesh network on four different sides, and at least some of the devices:

select an order of dimensions associated with routes for respective packets from the respective cores statically before construction of the packets when the routes send a packet towards a predetermined one of the sides, and select an order of dimensions associated with routes for respective packets from the respective cores dynamically upon construction of the packets when the routes do not send a packet towards the predetermined one of the sides.

8. The method of claim 1, wherein only devices connected to a core on a predetermined one of the sides select an order of dimensions associated with routes for respective packets from the respective cores dynamically upon construction of the packets.

9. The method of claim 8, wherein the selected order of the dimensions associated with the route depends on congestion in the mesh network, wherein congestion in the mesh network is measured based on a count that characterizes activity associated with a port of a switch in the mesh network.

10. The method of claim 9, wherein the count comprises a count of a number of cycles the port has been active.

11. The method of claim 9, wherein the count comprises a count of a number of messages waiting to be routed from the port.

12. The method of claim 9, wherein the count is stored in a register in the core that includes the switch.

13. The method of claim 9, wherein the order is selected to include in the resulting route fewer congested links.

14. The method of claim 1, wherein the selected order of the dimensions associated with the route depends on the location of the destination and on the location of the core or device from which the packet originates.

15. A computer-readable hardware storage device that tangibly stores a computer program for communicating among cores in a multicore processor that comprises a plurality of cores interconnected by a mesh network, each core comprising a processor element and a switch, the computer program comprising instructions for causing the processor to:

construct a packet to route from one of the cores or from a device coupled to one of the cores;

dynamically determine a route for the packet, by selecting for the packet between a first dimension and a second, different dimension, a first oriented route that routes in the first dimension unless a turn is encountered in the route;

route the packet from the core or from the device coupled to the one of the cores to a destination over the dynamically determined route over the first selected dimension.

16. The computer-readable hardware storage device of claim 15, wherein computer program includes instructions to select the first dimension by at least one policy that randomly selects the first dimension for packets or uses congestion based information or using destination based information.

17. The computer-readable hardware storage device of claim 15, wherein computer program includes instructions to select the first dimension based on congestion in the mesh network, with congestion in the mesh network measured based on a count that characterizes activity associated with a port of a switch in the mesh network.

22. The computer-readable hardware storage device of claim 15, wherein the instructions constrain the types of possible routes within the network to avoid deadlocks.

23. The method of claim 22, wherein the mesh network has two sides controlled by two I/O controllers, and the instructions limit the dynamically ordering to one of the two sides of the mesh network to avoid deadlock.

18. A multicore processor, comprising:

a plurality of cores;

a mesh network interconnecting the plurality of cores;

each of one or more of the cores comprising a switch; and

each of one or more of the cores comprising a processor, the processors configured to;

construct a packet to route from one of the cores or from a device coupled to one of the cores;

dynamically determine a route for the packet, by selecting for the packet between a first dimension and a second, different dimension, a first oriented route that routes the packet in the first dimension and when a turn is encountered, in a second dimension;

route the packet from the core or from the device coupled to the one of the cores to a destination over the dynamically determined route over the first selected dimension; and

route the packet in a second selected dimension when a turn is required in the route to the destination.

19. The multicore processor of claim 18, wherein the cores are divided into a first subset of cores located in a first region of the mesh network, and a second subset of cores are located in a second region of the mesh network that does not overlap with the first region, with the first subset of cores routing based on the dynamically determining a route, and the second subset of cores using a routing policy that is static.

20. The multicore processor of claim 18, wherein at least four devices are connected to respective cores on the perimeter of the mesh network on four different sides, and at least some of the devices:

select an order of dimensions associated with routes for respective packets from the respective cores statically before construction of the packets when the routes send a packet towards a predetermined one of the sides, and select an order of dimensions associated with routes for respective packets from the respective cores dynamically upon construction of the packets when the routes do not send a packet towards the predetermined one of the sides.

21. The multicore processor of claim 18, wherein only devices connected to a core on a predetermined one of the sides select an order of dimensions associated with routes for respective packets from the respective cores dynamically upon construction of the packets.

24. The multicore processor of claim 18, wherein at least one of the processors are configured to constrain the types of possible routes within the network to avoid deadlocks.

25. The multicore processor of claim 18, wherein the mesh network has two sides controlled by two I/O controllers, and the multicore processor is configured to limit the dynamically ordering to one of the two sides of the mesh network to avoid deadlock.