Method and Apparatus for a Multidimensional Grid Scheduler

• US 20080229322A1
• Filed: 06/02/2008
• Published: 09/18/2008
• 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
• Granted Patent: US 7,784,056 B2
• Time in Patent Office: Days
• 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;

selecting a grid node from a plurality of grid nodes based on the dependency of the grid job 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 usable 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 selecting a set of nodes from the plurality of nodes using the map and the identified capacity for processing grid jobs.

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. An apparatus 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 executes 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;

select a grid node from a plurality of grid nodes based on the dependency of the grid job to form a selected grid node; and

send the characterized grid job to the selected grid node.