Performing dynamic request routing based on broadcast queue depths

• US 8,077,602 B2
• Filed: 02/01/2008
• Issued: 12/13/2011
• Est. Priority Date: 02/01/2008
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Arimilli, Lakshminarayana B., Arimilli, Ravi K., Drerup, Bernard C., Joyner, Jody B., Lewis, Jerry D.
• Primary Examiner(s): Ryman, Daniel J
• Assistant Examiner(s): DIVECHA, NISHANT B
• Application Number:
  US12/024,514
• Publication Number:
  US 20090198957A1
• Time in Patent Office: 1,411 Days
• Field of Search: None
• US Class Current: 370/217
• CPC Class Codes: G06F 15/17 using an input/output type connection, e.g. channel, I/O port

Abstract

Mechanisms for performing dynamic request routing based on broadcast depth queue information are provided. Each processor chip in the system may use a synchronized heartbeat signal it generates to provide queue depth information to each of the other processor chips in the system. The queue depth information identifies a number of requests or amount of data in each of the queues of a processor chip that originated the heartbeat signal. The queue depth information from each of the processor chips in the system may be used by the processor chips in determining optimal routing paths for data from a source processor chip to a destination processor chip. As a result, the congestion of data for processing at each of the processor chips along each possible routing path may be taken into account when selecting to which processor chip to forward data.

Claims

1. A processor chip, comprising:

at least one processor;

a plurality of communication ports for directly coupling the processor chip to a plurality of other processor chips via bus connections; and

heartbeat signal generation logic for generating a heartbeat signal for broadcasting over the plurality of communication ports to the plurality of other processor chips, wherein the heartbeat signal generation logic transmits queue depth information associated with the plurality of communication ports of the processor chip in the heartbeat signal broadcast over the plurality of communication ports to the plurality of other processor chips, wherein;

the heartbeat signal is a signal broadcast by the processor chip to the plurality of other processor chips at a regular interval that is synchronized with a master processor chip through a synchronization process, and

the queue depth information comprises queue depth information for the communication ports of the processor chip and queue depth information for communication ports of each of the plurality of other processor chips to which the processor chip is directly coupled, queue depth information for communication ports of other processor chips to which the processor chip is indirectly coupled and which are present in a same processor book or different processor books of a same supernode, and queue depth information of additional processor chips in other supernodes that are indirectly coupled to the current processor chip via the other processor chips in the same processor book and different processor books of the same supernode.

2. The processor chip of claim 1, further comprising:

routing logic for selecting a route over which to transmit a data message to a destination processor chip, wherein the routing logic selects the route based on the queue depth information received from the plurality of other processor chips.

3. The processor chip of claim 1, further comprising:

queue depth data structure storage that stores the queue depth information for the plurality of other processor chips received in heartbeat signals from the plurality of other processor chips via the plurality of communication ports.

4. The processor chip of claim 3, further comprising:

queue depth transmission and routing logic that sends the queue depth information of the processor chip in the heartbeat signal generated by the heartbeat signal generation logic and that selects a route for transmission of data from the at least one processor to a destination processor chip based on the queue depth information stored in the queue depth data structure storage.

5. The processor chip of claim 4, wherein the queue depth information for the plurality of other processor chips is stored in association with processor chip identifiers and is correlated with routing table data structure information, based on the processor chip identifiers, when the queue depth transmission and routing logic selects the route for transmitting the data to the destination processor chip.

6. The processor chip of claim 4, wherein the queue depth transmission and routing logic is integrated with an integrated switch/router of the processor chip.

7. The processor chip of claim 4, wherein the queue depth transmission and routing logic selects the route to transmit the data by:

selecting a set of one or more candidate routes from the first processor chip to the destination processor chip based on an identity of the destination processor chip and which routes from the first processor chip to the destination processor chip are still available for routing of the data to the destination processor chip; and

selecting the route to be used to transmit the data to the destination processor chip based on the queue depth information, stored in the queue depth data structure storage, for processor chips along each route in the candidate set of routes.

8. The processor chip of claim 7, wherein the route that is selected to be used to transmit the data to the destination processor chip is a route, in the candidate set of routes, having a lowest total queue depth as determined by the queue depth information for processor chips along the route.

9. The processor chip of claim 7, wherein selecting the route to be used to transmit the data to the destination processor chip further comprises selecting the route based on at least one of a number of hops from the processor chip to the destination processor chip along the routes in the set of candidate routes or reported error conditions of links along the routes in the set of candidate routes.

10. The processor chip of claim 1, wherein the processor chip and plurality of other processor chips are part of a computing cluster that comprises a multi-tiered full graph interconnect architecture data processing system having a plurality of supernodes, each supernode having one or more processor books, and each processor book having one or more processor chips of the plurality of processor chips.

11. A method, in a data processing system, comprising:

receiving, in a first processor chip of the data processing system, a plurality of first heartbeat signals from a plurality of second processor chips coupled to the first processor chip via one or more communication ports, wherein the plurality of first heartbeat signals have first queue depth information associated with respective processor chips of the plurality of second processor chips;

storing the first queue depth information in a queue depth information data structure storage of the first processor chip; and

performing routing of data from the first processor chip to a destination processor chip in the data processing system based on the first queue depth information stored in the queue depth information data structure storage, wherein;

each first heartbeat signal in the plurality of first heartbeat signals is a signal broadcast by a corresponding second processor chip to the first processor chip and other second processor chips at a regular interval that is synchronized with a master processor chip through a synchronization process, and

the first queue depth information for a current second processor chip comprises queue depth information for communication ports of the current second processor chip and queue depth information for communication ports of each of the other second processor chips to which the current second processor chip is directly coupled, queue depth information for communication ports of other processor chips to which the current second processor chip is indirectly coupled and which are present in a same processor book or different processor books of a same supernode, and queue depth information of additional processor chips in other supernodes that are indirectly coupled to the current second processor chip via the other second processor chips in the same processor book and different processor books of the same supernode.

12. The method of claim 11, wherein the queue depth information identifies queue depths associated with a plurality of virtual channels of a corresponding processor chip in the plurality of second processor chips.

13. The method of claim 11, further comprising:

generating, in the first processor chip, a second heartbeat signal for broadcasting from the first processor chip to the plurality of second processor chips via the one or more communication ports;

encoding the second heartbeat signal with second queue depth information associated with the first processor chip; and

transmitting the encoded second heartbeat signal to the plurality of second processor chips via the one or more communication ports, wherein the second heartbeat signal is a signal broadcast by the first processor chip to the plurality of second processor chips at a regular interval that is synchronized with the master processor chip through a synchronization process, and

the second queue depth information for the first processor chip comprises queue depth information for communication ports of the first processor chip and queue depth information for communication ports of each of the plurality of second processor chips to which the first processor chip is directly coupled, queue depth information for communication ports of other processor chips to which the first processor chip is indirectly coupled and which are present in a same processor book or different processor books of a same supernode, and queue depth information of additional processor chips in other supernodes that are indirectly coupled to the first processor chip via the other second processor chips in the same processor book and different processor book of the same supernode.

14. The method of claim 11, wherein the first queue depth information for the plurality of second processor chips is stored in association with processor chip identifiers.

15. The method of claim 14, wherein performing routing of data from the first processor chip to the destination processor chip comprises correlating the first queue depth information with routing table data structure information based on the processor chip identifiers.

16. The method of claim 11, wherein performing routing of data from the first processor chip to a destination processor chip comprises:

selecting a set of one or more candidate routes from the first processor chip to the destination processor chip based on an identity of the destination processor chip and which routes from the first processor chip to the destination processor chip are still available for routing of the data to the destination processor chip; and

selecting a route to be used to transmit the data to the destination processor chip based on first queue depth information, stored in the queue depth data structure storage, for processor chips along each route in the candidate set of routes.

17. The method of claim 16, wherein the route that is selected to be used to transmit the data to the destination processor chip is a route, in the candidate set of routes, having a lowest total number of active queue depths as determined by the queue depth information for processor chips along the route.

18. The method of claim 16, wherein selecting the route to be used to transmit the data to the destination processor chip further comprises selecting the route based on at least one of a number of hops from the first processor chip to the destination processor chip along the routes in the set of candidate routes or reported error conditions of links along the routes in the set of candidate routes.

19. The method of claim 11, wherein the first processor chip and plurality of second processor chips are part of a computing cluster that comprises a multi-tiered full graph interconnect architecture data processing system having a plurality of supernodes, each supernode having one or more processor books, and each processor book having one or more processor chips of the plurality of processor chips.

20. A computer program product comprising a computer useable storage device having a computer readable program stored thereon, wherein the computer readable program, when executed in a data processing system, causes the data processing system to:

receive, in a first processor chip of the data processing system, a plurality of first heartbeat signals from a plurality of second processor chips coupled to the first processor chip via one or more communication ports, wherein the plurality of first heartbeat signals have first queue depth information associated with respective processor chips of the plurality of second processor chips;

store the first queue depth information in a queue depth information data structure storage of the first processor chip; and

perform routing of data from the first processor chip to a destination processor chip in the data processing system based on the first queue depth information stored in the queue depth information data structure storage, wherein;

each first heartbeat signal in the plurality of heartbeat signals is a signal broadcast by a corresponding second processor chip to the first processor chip and other second processor chips at a regular interval that is synchronized with a master processor chip through a synchronization process, and

the first queue depth information for a current second processor chip comprises queue depth information for communication ports of the current second processor chip and queue depth information for communication ports of each of the other second processor chips to which the current second processor chip is directly coupled, queue depth information for communication ports of other processor chips to which the current second processor chip is indirectly coupled and which are present in a same processor book or different processor books of a same supernode, and queue depth information of additional processor chips in other supernodes that are indirectly coupled to the current second processor chip via the other second processor chips in the same processor book and different processor books of the same supernode.

21. A system, comprising:

a plurality of processor chips; and

a plurality of communication links directly coupling each processor chip in the plurality of processor chips to at least one other processor chip in the plurality of processor chips via bus connections, wherein each processor chip in the plurality of processor chips comprises heartbeat signal generation logic for generating a heartbeat signal for broadcasting over one or more communication links, in the plurality of communication links, coupled to the processor chip, wherein the heartbeat signal generation logic transmits queue depth information, associated with the one or more communication links, in the heartbeat signal broadcast over the one or more communication links to the plurality of other processor chips, wherein;

the heartbeat signal is a signal broadcast by the processor chip to the plurality of other processor chips at a regular interval that is synchronized with a master processor chip through a synchronization process, and

the queue depth information comprises queue depth information for the communication ports of the current processor chip and queue depth information for communication ports of each of the other processor chips to which the current processor chip is directly coupled, queue depth information for communication ports of other processor chips to which the current processor chip is indirectly coupled and which are present in a same processor book or different processor books of a same supernode, and queue depth information of additional processor chips in other supernodes that are indirectly coupled to the current processor chip via the other processor chips in the same processor book and different processor books of the same supernode.