Dynamic job processing based on estimated completion time and specified tolerance time

• US 7,937,705 B1
• Filed: 06/09/2006
• Issued: 05/03/2011
• Est. Priority Date: 07/20/2001
• Status: Active Grant

• Current Assignee: Callidus Software, Inc. (SAP SE)
• Original Assignee: I2Z Technology LLC (Innovation Management Sciences, LLC)
• Inventors: Prael, Charles Evert, Tymes, Adrian Jeremy
• Primary Examiner(s): To; Jennifer N
• Application Number:
  US11/450,152
• Time in Patent Office: 1,789 Days
• Field of Search: 718/102
• US Class Current: 718/102
• CPC Class Codes: G06F 2209/5014 Reservation
• CPC Class Codes: G06F 9/50 Allocation of resources, e.g. of the central processing unit [CPU]
• CPC Class Codes: G06F 9/5038 considering the execution order of a plurality of tasks, e.g. taking priority or time dependency constraints into consideration scheduling strategies G06F9/4881 and subgroups
• CPC Class Codes: G06F 9/5072 Grid computing
• CPC Class Codes: G06F 9/5077 Logical partitioning of resources; Management or configuration of virtualized resources specific details on emulation or internal functioning of virtual machines G06F9/455

Abstract

The invention provides a system and method for managing clusters of parallel processors for use by groups and individuals requiring supercomputer level computational power. A Beowulf cluster provides supercomputer level processing power. Unlike a traditional Beowulf cluster; however, cluster size in not singular or static. As jobs are received from users/customers, a Resource Management System (RMS) dynamically configures and reconfigures the available nodes in the system into clusters of the appropriate sizes to process the jobs. Depending on the overall size of the system, many users may have simultaneous access to supercomputer level computational processing. Users are preferably billed based on the time for completion with faster times demanding higher fees.

Claims

1. A method for scheduling a plurality of jobs including the steps of:

receiving at least one job to be processed from at least one customer, wherein said receiving further includes receiving at least one attribute specific to said at least one job to be processed including a tolerance time;

estimating a time for completion of processing for said at least one job to be processed;

placing said at least one job to be processed in a queue having other jobs to be processed, wherein each of said other jobs includes an estimate time for completion and a tolerance time;

sorting said at least one job and said other jobs to be processed in said queue based on said tolerance time and said estimated time for completion of said at least one job to be processed and said other jobs;

configuring dynamically at least one cluster of processing resources from a pool of processing resources responsive to said tolerance time and said estimate time for completion of said at least one job to be processed;

processing said at least one job to be processed from said sorted queue by assigning said at least one job to be processed to said at least one cluster of processing resources; and

making a result of said processing of said at least one job to be processed available to said at least one customer,

wherein said tolerance time includes a time of completion acceptable to said at least one customer that is later in time than said estimated time for completion.

2. A method as in claim 1, wherein said step of sorting said queue of jobs to be processed further includes consideration of a priority of said at least one job to be processed.

3. A method as in claim 1, wherein the step of estimating a time for completion of processing of said at least one job to be processed further includes the step of confirming said estimated time for completion of processing with said at least one customer.

4. A method as in claim 1 wherein said step of configuring dynamically a pool of processing resources into at least one cluster of processing resources further includes the steps of:

saving said cluster of processing resources from said pool of processing resources as they become available such that they are earmarked for creating a specific cluster to be used for processing said at least one job to be processed;

saving a configuration file on said cluster of processing resources; and

rebooting said cluster of processing resources to configure dynamically said cluster of processing resources for processing of said at least one job to be processed.

5. A method as in claim 1, wherein said making a result of said processing of said at least one job to be processed available to said at least one customer further includes charging a fee for said result.

6. A method as in claim 5, wherein said fee is based on said time for completion of processing for said at least one job to be processed.

7. A system including:

a request receiver element configured to receive at least one job to be processed from at least one customer, said request receiver element in communication with a pool of processing resources, wherein said request receiver element is further configured to receive at least one attribute specific to said at least one job to be processed including a tolerance time;

a queue having jobs to be processed including said at least one job, wherein each of said jobs includes an estimated time for completion and a tolerance time, wherein said queue being sorted according to said tolerance time and said estimated time for completion of said jobs and said at least one job, said queue being in communication with said pool of processing resources; and

said pool of processing resources configured to run jobs to be processed from said sorted queue, said pool of processing resources disposed to being dynamically divided into clusters of processing resources, which may run in parallel, in response to said estimated completion time and said tolerance time of said at least one job and said jobs,

wherein said tolerance time includes a time later than an estimated time for completion of said at least one job to be processed.

8. A system as in claim 7, wherein said queue of jobs to be processed may be sorted based on consideration of a priority of said at least one job to be processed.

9. A system as in claim 7, wherein said pool of processing resources are disposed to being dynamically divided into clusters of processing resources further including;

a procuring element disposed to collect processing resources from said pool of processing resources as they become available such that they are earmarked for creating a specific cluster to be used for processing said at least one job to be processed;

an initializing element disposed to save a configuration file on said cluster of processing resources;

a rebooting element disposed to soft reboot said cluster of processing resources such that said cluster of processing resources is dynamically created;

an executing element configured to run said at least one job to be processed on said cluster of programming resources; and

a transfer element disposed to deliver a result of said run of said at least one job to be processed to said at least one customer.

10. A system as in claim 9, wherein a billing element charges said at least one customer a fee for said result.

11. A system as in claim 10, wherein said billing element determines said fee based on time for completion of running said at least one job to be processed.

12. A method for scheduling a plurality of jobs including the steps of:

receiving at least one job to be processed from at least one customer, wherein said receiving further includes receiving at least one attribute specific to said at least one job including at least the attribute of a tolerance time;

estimating a time for completion of processing for said at least one job;

placing said at least one job in a queue having at least a second job to be processed, wherein said second job includes an estimated time for completion and a tolerance time;

sorting said queue in response to said tolerance time and said estimated time for completion of said at least one job and said second job;

configuring dynamically at least one cluster of processing resources from a pool of processing resources responsive to said tolerance time and said estimate time for completion of said at least one job;

processing said at least one job in said sorted queue by assigning said at least one job to said cluster of processing resources; and

making a result of said processing of said at least one job available to said customer,

wherein said tolerance time is a time of completion acceptable to said customer that is later in time than said estimated time for completion.

13. A method as in claim 12, wherein said step of sorting said queue further includes consideration of a priority of said at least one job to be processed.