Method and apparatus for scheduling grid jobs

• US 7,784,056 B2
• Filed: 06/02/2008
• Issued: 08/24/2010
• Est. Priority Date: 10/24/2005
• Status: Expired due to Fees

• Current Assignee: Kyndryl Incorporated
• Original Assignee: International Business Machines Corporation
• Inventors: Youngblood, Justin Lucus, Leonard, Brian E., Harper, Ellen Kay, Prestenback, Kyle Joseph, Berstis, Viktors
• Primary Examiner(s): An; Meng-Ai
• Assistant Examiner(s): KUMABE, BLAKE K
• Application Number:
  US12/131,235
• Publication Number:
  US 20080229322A1
• Time in Patent Office: 813 Days
• Field of Search: 718/106
• US Class Current: 718/106
• 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 computer implemented method in a grid computing system for scheduling grid jobs, the computer implemented method comprising:

characterizing a grid job based on a dependency of the grid job on network based resources required to perform the grid job to form a characterized grid job, wherein characterizing the grid job comprises determining a most probable route a data packet associated with the grid job will travel between a database associated with the grid job and a plurality of grid nodes in the grid computing system;

monitoring an amount of network traffic on a plurality of links between grid nodes of the plurality of grid nodes and between the database and the plurality of nodes;

selecting, by a processing unit, a grid node from the plurality of grid nodes 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 to form a selected grid node; and

sending the characterized grid job to the selected grid node.

2. The computer implemented method of claim 1, wherein a processor utilization monitor on a grid node in the plurality of grid nodes monitors processor utilization of the grid node with regard to grid and non-grid workloads.

3. The computer implemented method of claim 1, wherein a network utilization monitor on a grid node in the plurality of grid nodes monitors network traffic between the grid node and other grid nodes.

4. The computer implemented method of claim 3, wherein the network utilization monitor determines the most probable route a data packet will travel between the grid node and the other grid nodes.

5. The computer implemented method of claim 4, wherein a minimum capacity link between two grid nodes is determined, and wherein the minimum capacity link is set as a maximum capacity of network traffic between the two nodes.

6. The computer implemented method of claim 2, further comprising:

distinguishing 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 computer implemented method of claim 1, wherein expected network and processor capacity is determined 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 computer implemented method of claim 1, wherein the step of selecting a grid node further comprises:

mapping the plurality of grid nodes in the grid computing system utilizing a clustering algorithm in accordance with a network proximity of a grid node to at least one of a submission point, a database, and an other grid node.

9. The computer implemented method of claim 1, further comprising:

generating a two-dimensional plot of grid node clusters based on both processor resource availability and network resource availability for each cluster.

10. The computer implemented method of claim 1, wherein the selection step comprises:

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.

11. The computer implemented method of claim 10, wherein if no selected grid node is identified, lowering the minimum processor threshold and the minimum network threshold.

12. The computer implemented method of claim 11, wherein if lowering the minimum threshold values to include an additional grid node results in reduced or diminishing returns, indicating that a suitable scheduling cannot be accomplished.

13. The computer implemented method of claim 1, further comprising:

selecting a source of additional grid nodes from a plurality of sources of additional grid nodes to extend the computing grid to include the additional grid nodes.

14. A computer program product comprising:

computer readable storage medium including computer usable program code for scheduling grid jobs in a grid computing system, the computer program product comprising;

computer usable program code for mapping a plurality of grid nodes in the grid computing system to form a map, wherein the map provides connections between the plurality of grid nodes;

computer usable program code for identifying a network capacity and a processor capacity for the plurality of grid nodes to form an identified capacity;

computer usable program code for determining a most probable route a data packet associated with the grid job will travel between a database associated with the grid job and a plurality of grid nodes in the grid computing system;

computer usable program code for monitoring an amount of network traffic on a plurality of links between grid nodes of the plurality of grid nodes and between the database and the plurality of nodes;

computer usable program code for selecting a set of nodes from the plurality of nodes based on the identified capacity for processing grid job, 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.

15. The computer program product of claim 14, wherein the computer usable program code for selecting a set of nodes from the plurality of nodes using the map and the identified capacity comprises:

computer usable program code for clustering the plurality of grid nodes using the map to form a set of clusters; and

computer usable program code for selecting the set of nodes from the set of clusters using the map and the identified capacity.

16. The computer program product of claim 15, wherein the computer usable program code for selecting a set of nodes from the plurality of nodes using the map and the identified capacity for processing grid jobs further comprises;

computer usable program code for identifying a set of nodes from the set of clusters that has sufficient capacity to execute a grid job in a designated time period and exceeds a minimum processor threshold and a minimum network threshold for the grid job.

17. The computer program product of claim 14, wherein the computer usable program code for selecting a set of nodes from the plurality of nodes using the map and the identified capacity for processing grid jobs further comprises;

computer usable program code for generating a two-dimensional plot of a set of grid nodes based on both the processor resource availability and network resource availability for a set of grid node clusters.

18. The computer program product of claim 16, wherein if a set of nodes from the set of clusters is not selected, lowering the minimum processor threshold and the minimum network threshold.

19. The computer program product of claim 14, further comprising:

computer usable program code for selecting a source of additional grid nodes from a plurality of sources of additional grid nodes to extend the computing grid to include additional grid nodes.

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

A computer comprising;

a bus;

a storage device connected to the bus, wherein the storage device contains computer usable program code;

a communications unit connected to the bus;

a processing unit connected to the bus, wherein the processing unit is configured to execute the computer usable program code to characterize a grid job based on a dependency of the grid job on network based resources required to perform the grid job to form a characterized grid job;

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

monitor an amount of network traffic on a plurality of links between grid nodes of the plurality of grid nodes and between the database and the plurality of nodes;

select a grid node from a plurality of grid nodes 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 to form a selected grid node; and

send the characterized grid job to the selected grid node.