Method and apparatus for scheduling grid jobs

• US 7,853,948 B2
• Filed: 10/24/2005
• Issued: 12/14/2010
• Est. Priority Date: 10/24/2005
• Status: Active Grant

• Current Assignee: Kyndryl Incorporated
• Original Assignee: International Business Machines Corporation
• Inventors: Berstis, Viktors, Youngblood, Justin Lucus, Leonard, Brian E., Harper, Ellen Kay, Prestenback, Kyle Joseph
• Primary Examiner(s): Zhen; Li B
• Assistant Examiner(s): KUMABE, BLAKE K
• Application Number:
  US11/257,444
• Publication Number:
  US 20070094662A1
• Time in Patent Office: 1,877 Days
• Field of Search: 718/106, 718/102
• US Class Current: 718/102
• CPC Class Codes: G06F 2209/508 Monitor
• CPC Class Codes: G06F 9/505 considering the load
• CPC Class Codes: G06F 9/5072 Grid computing

Abstract

A method and apparatus for scheduling execution of a grid project in accordance with multiple dimensions of dynamic load factors. The present invention provides a mechanism for determining grid node availability based on both processor load and network traffic loads on the nodes in a grid of computing devices. This availability information is used to determine scheduling of the running of grid projects.

Claims

1. A method for scheduling grid jobs in a grid computing system, the computer implemented method comprising:

determining, by a processing unit, a most probable route a data packet associated with a grid job will travel between a database associated with the grid job and a plurality of grid nodes in the grid computing system;

monitoring, by a processing unit, an amount of network traffic on a plurality of links between grid nodes of the plurality of grid nodes and between the database associated with the grid job and the plurality of grid nodes; and

selecting, by a processing unit, a grid node from the plurality of grid nodes to receive at least a portion of the grid job based on a processing capacity of the grid node, the most probable route determined that the data packet associated with the grid job will travel, and the amount of network traffic on the plurality of links.

2. The method of claim 1 further comprising:

determining, by a processing unit, a processing capacity of a plurality of grid nodes in the grid computing system.

3. The method of claim 1 further comprising:

characterizing, by a processing unit, the grid job based on a dependency of the grid job on network based resources required to perform the grid job.

4. The method of claim 3 further comprising:

determining, by a processing unit, a processing capacity of a plurality of grid nodes in the grid computing system.

5. The method of claim 1 further comprising:

monitoring, by a processing unit, utilization of processor resources on a grid node in the plurality of grid nodes of grid and non-grid workloads.

6. The method of claim 5 further comprising:

distinguishing, by a processing unit, grid and non-grid related workloads, wherein a grid client software on a grid node maintains a data structure storing an identifier of threads associated with grid jobs processing on the grid node, and wherein the data structure is compared with statistics regarding all threads processed on the grid node.

7. The method of claim 1 further comprising:

determining, by a processing unit, expected network and processor capacity by collecting network and processor utilization statistics over an “

n”

minute interval and, wherein the network and processor utilization statistics are aggregated and statistically evaluated to determine average values for a repetitive period.

8. The method of claim 1, wherein the step of selecting a grid node comprises:

selecting, by a processing unit, the grid node from the plurality of grid nodes by mapping the plurality of grid nodes in the grid computing system utilizing a clustering algorithm in accordance with a network proximity of the grid node to at least one of a submission point, a database, and another grid node.

9. The method of claim 1, wherein the step of selecting a grid node comprises:

selecting, by a processing unit, the grid node from the plurality of grid nodes by identifying a selected grid node that has sufficient total processor and network capacity to satisfy a minimum processor threshold and a minimum network threshold to execute a grid job in a designated time period.

10. A computer program product comprising:

a computer readable storage medium;

first program instructions to determine a most probable route a data packet associated with a grid job will travel between a database associated with the grid job and a plurality of grid nodes in the grid computing system;

second program instructions to monitor an amount of network traffic on a plurality of links between grid nodes of the plurality of grid nodes and between the database associated with the grid job and the plurality of grid nodes;

third program instructions to select a grid node from the plurality of grid nodes in the grid computing system to receive at least a portion of the grid job based on a processing capacity of the grid node, the most probable route determined that the data packet associated with the grid job will travel, and the amount of network traffic on the plurality of links; and

wherein the first program instructions, the second program instructions, and the third program instructions are stored on the computer readable storage medium.

11. The computer program product of claim 10 further comprising:

fourth program instructions to determine a processing capacity of a plurality of grid nodes in the grid computing system; and

wherein the fourth program instructions are stored on the computer readable storage medium.

12. The computer program product of claim 10 further comprising:

fourth program instructions to characterize the grid job based on a dependency of the grid job on network based resources required to perform the grid job;

fifth program instructions to determine a processing capacity of a plurality of grid nodes in the grid computing system; and

wherein the fourth program instructions and the fifth program instructions are stored on the computer readable storage medium.

13. The computer program product of claim 10 further comprising:

fourth program instructions to determine expected network and processor capacity by collecting network and processor utilization statistics over an “

n”

minute interval and, wherein the network and processor utilization statistics are aggregated and statistically evaluated to determine average values for a repetitive period.

14. The computer program product of claim 10, wherein the third program instructions to select the grid node comprise:

fourth program instructions to select the grid node from the plurality of grid nodes by mapping the plurality of grid nodes in the grid computing system utilizing a clustering algorithm in accordance with a network proximity of the grid node to at least one of a submission point, a database, and another grid node; and

wherein the fourth program instructions are stored on the computer readable storage medium.

15. The computer program product of claim 10, wherein the third program instructions to select the grid node comprise:

fourth program instructions to select the grid node from the plurality of grid nodes by identifying a selected grid node that has sufficient total processor and network capacity to satisfy a minimum processor threshold and a minimum network threshold to execute a grid job in a designated time period; and

wherein the fourth program instructions are stored on the computer readable storage medium.

16. A data processing system for scheduling grid jobs, comprising:

a bus;

a storage device connected to the bus;

a memory connected to the bus;

a processing unit connected to the bus;

first program instructions to determine a most probable route a data packet associated with a grid job will travel between a database associated with the grid job and a plurality of grid nodes in the grid computing system;

second program instructions to monitor an amount of network traffic on a plurality of links between grid nodes of the plurality of grid nodes and between the database associated with the grid job and the plurality of grid nodes;

third program instructions to select a grid node from the plurality of grid nodes in the grid computing system to receive at least a portion of the grid job based on a processing capacity of the grid node, the most probable route determined that the data packet associated with the grid job will travel, and the amount of network traffic on the plurality of links; and

wherein the first program instructions, the second program instructions, and the third program instructions are stored on the storage device for execution by the processing unit via the memory.

17. The data processing system of claim 16, further comprising:

fourth program instructions to characterize the grid job based on a dependency of the grid job on network based resources required to perform the grid job;

fifth program instructions to determine a processing capacity of a plurality of grid nodes in the grid computing system; and

wherein the fourth program instructions and the fifth program instructions are stored on the computer readable storage medium for execution by the processing unit via the memory.