System and Method for Routing Information Through a Data Processing System Implementing a Multi-Tiered Full-Graph Interconnect Architecture

• US 20090063814A1
• Filed: 08/27/2007
• Published: 03/05/2009
• Est. Priority Date: 08/27/2007
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Arimilli, Ravi K., Rajamony, Ramakrishnan, Arimilli, Lakshminarayana B., Speight, William E.
• Granted Patent: US 7,904,590 B2
• Time in Patent Office: Days
• US Class Current: 712/30
• CPC Class Codes: G06F 15/17381 Two dimensional, e.g. mesh, torus

Abstract

A method, computer program product, and system are provided for routing information through the data processing system. Data is received at a source processor within a set of processors that is to be transmitted to a destination processor, where the data includes address information. A first determination is performed as to whether the destination processor is within a same processor book as the source processor based on the address information. A second determination is performed as to whether the destination processor is within a same supernode as the source processor based on the address information if the destination processor is not within the same processor book. A routing path is identified for the data based on results of the first determination, the second determination, and one or more routing table data structures. The data is then transmitted from the source processor along the identified routing path toward the destination processor.

Claims

1. A method, in a data processing system, of routing information through the data processing system, the data processing system comprising a plurality of supernodes, the plurality of supernodes comprising a plurality of processor books, and the plurality of processor books comprising a plurality of processors, the method comprising:

receiving data at a source processor within a set of processors that is to be transmitted to a destination processor, wherein the data includes address information;

performing a first determination as to whether the destination processor is within a same processor book as the source processor based on the address information;

performing a second determination as to whether the destination processor is within a same supernode as the source processor based on the address information if the destination processor is not within the same processor book;

identifying a routing path for the data based on results of the first determination, the second determination, and one or more routing table data structures; and

transmitting the data from the source processor along the identified routing path toward the destination processor.

2. The method of claim 1, wherein:

the address information comprises a processor book identifier and a supernode identifier of the destination processor;

performing the first determination comprises comparing the processor book identifier in the address information with a processor book identifier associated with the source processor; and

the destination processor is determined to be within a same processor book as the source processor if the processor book identifier associated with the source processor matches the processor book identifier in the address information.

3. The method of claim 2, wherein:

performing the second determination comprises comparing the supernode identifier in the address information with a supernode identifier associated with the source processor; and

the destination processor is determined to be within a same supernode as the source processor if the supernode identifier associated with the source processor matches the supernode identifier in the address information.

4. The method of claim 1, wherein identifying the routing path for the data based on results of the first determination, the second determination, and one or more routing table data structures comprises:

performing a lookup operation of a processor chip identifier in the address information in a processor chip routing table data structure if results of the first determination indicate that the destination processor is within a same processor book as the source processor.

5. The method of claim 4, wherein a result of the lookup operation of the processor chip identifier is a path within the same processor book from the source processor to the destination processor.

6. The method of claim 1, wherein identifying the routing path for the data based on results of the first determination, the second determination, and one or more routing table data structures comprises:

performing a lookup operation of a processor book identifier in the address information in a processor book routing table data structure if results of the first determination indicate that the destination processor is not within a same processor book as the source processor and the second determination indicates that the destination processor is within a same supernode as the source processor.

7. The method of claim 6, wherein a result of the lookup operation of the processor book identifier is a path within the same supernode from the source processor to a processor in a processor book in which the destination processor is provided.

8. The method of claim 1, wherein identifying the routing path for the data based on results of the first determination, the second determination, and one or more routing table data structures comprises:

performing a lookup operation of the supernode identifier in the address information in a supernode routing table data structure if results of the first determination indicate that the destination processor is not within a same processor book as the source processor and the second determination indicates that the destination processor is not within a same supernode as the source processor.

9. The method of claim 8, wherein a result of the lookup operation of the supernode identifier is a path between supernodes from the source processor to a processor in another supernode in the data processing system.

10. The method of claim 9, wherein the path from the source processor to a processor in another supernode is a direct path, and wherein the another supernode is a supernode in which the destination processor is provided.

11. The method of claim 9, wherein the path from the source processor to a processor in another supernode is an indirect path, and wherein the another supernode is an intermediary supernode in which the destination processor is not provided.

12. The method of claim 1, wherein the one or more routing table data structures comprises a processor chip routing table data structure, a processor book routing table data structure, and a supernode routing table data structure, and wherein each processor within the set of processors has each of the one or more routing table data structures.

13. A computer program product, for routing information through a data processing system, comprising a computer useable medium having a computer readable program, wherein the computer readable program, when executed in a source processor in the data processing system, causes the source processor to:

receive data at the source processor within a set of processors that is to be transmitted to a destination processor, wherein the data includes address information;

perform a first determination as to whether the destination processor is within a same processor book as the source processor based on the address information;

perform a second determination as to whether the destination processor is within a same supernode as the source processor based on the address information if the destination processor is not within the same processor book;

identify a routing path for the data based on results of the first determination, the second determination, and one or more routing table data structures; and

transmit the data from the source processor along the identified routing path toward the destination processor, wherein the data processing system comprises a plurality of supernodes, the plurality of supernodes comprising a plurality of processor books, and the plurality of processor books comprising a plurality of processors.

14. The computer program product of claim 13, wherein the address information comprises a processor book identifier and a supernode identifier of the destination processor, wherein the computer readable program to performing the first determination further comprises computer readable program that causes the data processing system to compare the processor book identifier in the address information with a processor book identifier associated with the source processor, and wherein the destination processor is determined to be within a same processor book as the source processor if the processor book identifier associated with the source processor matches the processor book identifier in the address information.

15. The computer program product of claim 14, wherein the computer readable program to perform the second determination further comprises computer readable program that causes the data processing system to compare the supernode identifier in the address information with a supernode identifier associated with the source processor, and wherein the destination processor is determined to be within a same supernode as the source processor if the supernode identifier associated with the source processor matches the supernode identifier in the address information.

16. The computer program product of claim 13, wherein identifying the routing path for the data based on results of the first determination, the second determination, and one or more routing table data structures further comprises the computer readable program causing the data processing system to perform at least one of:

a lookup operation of a processor chip identifier in the address information in a processor chip routing table data structure if results of the first determination indicate that the destination processor is within a same processor book as the source processor;

a lookup operation of a processor book identifier in the address information in a processor book routing table data structure if results of the first determination indicate that the destination processor is not within a same processor book as the source processor and the second determination indicates that the destination processor is within a same supernode as the source processor;

or

a lookup operation of the supernode identifier in the address information in a supernode routing table data structure if results of the first determination indicate that the destination processor is not within a same processor book as the source processor and the second determination indicates that the destination processor is not within a same supernode as the source processor.

17. A data processing system for routing information comprising:

a source processor; and

a memory coupled to the source processor, wherein the memory comprises instructions which, when executed by the source processor, cause the source processor to;

receive data at the source processor within a set of processors that is to be transmitted to a destination processor, wherein the data includes address information;

perform a first determination as to whether the destination processor is within a same processor book as the source processor based on the address information;

perform a second determination as to whether the destination processor is within a same supernode as the source processor based on the address information if the destination processor is not within the same processor book;

identify a routing path for the data based on results of the first determination, the second determination, and one or more routing table data structures; and

transmit the data from the source processor along the identified routing path toward the destination processor, wherein the data processing system comprises a plurality of supernodes, the plurality of supernodes comprising a plurality of processor books, and the plurality of processor books comprising a plurality of processors.

18. The data processing system of claim 17, wherein the address information comprises a processor book identifier and a supernode identifier of the destination processor, wherein the instruction to perform the first determination comprises further instructions that cause the processor to compare the processor book identifier in the address information with a processor book identifier associated with the source processor, and wherein the destination processor is determined to be within a same processor book as the source processor if the processor book identifier associated with the source processor matches the processor book identifier in the address information.

19. The data processing system of claim 18, wherein the instruction to perform the second determination comprises further instructions that cause the processor to compare the supernode identifier in the address information with a supernode identifier associated with the source processor, and wherein the destination processor is determined to be within a same supernode as the source processor if the supernode identifier associated with the source processor matches the supernode identifier in the address information.

20. The data processing system of claim 17, wherein the instruction to identify the routing path for the data based on results of the first determination, the second determination, and one or more routing table data structures comprises further instructions that cause the processor to performing at least one of:

a lookup operation of a processor chip identifier in the address information in a processor chip routing table data structure if results of the first determination indicate that the destination processor is within a same processor book as the source processor;

a lookup operation of a processor book identifier in the address information in a processor book routing table data structure if results of the first determination indicate that the destination processor is not within a same processor book as the source processor and the second determination indicates that the destination processor is within a same supernode as the source processor;

or

a lookup operation of the supernode identifier in the address information in a supernode routing table data structure if results of the first determination indicate that the destination processor is not within a same processor book as the source processor and the second determination indicates that the destination processor is not within a same supernode as the source processor.