Dynamically allocated cluster system

• US 7,065,764 B1
• Filed: 07/20/2001
• Issued: 06/20/2006
• Est. Priority Date: 07/20/2001
• Status: Active Grant

• Current Assignee: Callidus Software, Inc. (SAP SE)
• Original Assignee: NetRendered, Inc.
• Inventors: Prael, Charles Evert, Tymes, Adrian Jeremy
• Primary Examiner(s): An, Meng-Al T.
• Assistant Examiner(s): To, Jennifer N.
• Application Number:
  US09/910,445
• Time in Patent Office: 1,796 Days
• Field of Search: 718100-108, 709/220, 709/221, 709/222, 709/208, 703/2, 705/9, 710/10
• 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 of scheduling jobs including the steps of:

receiving at least one job to be processed from at least one customer;

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

placing each of said at least one job to be processed in a queue of jobs to be processed;

sorting said queue of jobs to be processed;

scheduling said at least one job to be processed, wherein said job is scheduled to be performed by processing resources that are already reserved for another larger job if said at least one job to be processed can be processed by those reserved processing resources before other processing resources required for said larger job are available;

configuring dynamically the size of at least one cluster of processing resources from a pool of processing resources responsive to at least one attribute of said job to be processed;

processing said at least one job to be processed from said queue of jobs to be processed 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 step of configuring dynamically a pool of processing resources into at least one cluster of processing resources responsive to at least one attribute of said at least one job to be processed 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 said at least one job to be processed.

2. A method of claim 1, wherein said receiving further includes at least one attribute specific to said at least one job to be processed including at least one of the following attributes:

(1) priority of processing, (2) type of processing, and (3) a tolerance time.

3. A method as in claim 2, wherein said step of sorting said queue of jobs to be processed includes consideration of said request for priority of processing of said at least one job to be pressed.

4. A method of claim 2, wherein said tolerance time includes a time for completion acceptable to said at least one customer that is later in time than the estimated time for completion, and said step of querying includes offering a fee discount to said at least one customer for said tolerance time.

5. A method as in claim 4, wherein said step of sorting said queue of jobs to be processed includes consideration of said tolerance time attributed to said at least one job to be processed.

6. 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 time for completion of processing with said at least one customer.

7. 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.

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

24. A method as in claim 1, wherein said step of rebooting said cluster of processing resources comprises soft rebooting said cluster of processing resources.

26. A method as in claim 1, further including the step of querying if said at least one customer is willing to accept a tolerance time that includes a time for completion that is later than the estimated time for completion, wherein said step of configuring is responsive to a result of said step of querying.

9. An apparatus including

means for receiving at least one job to be processed from at least one customer;

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

means for placing each of said at least one job to be processed in a queue of jobs to be processed;

means for sorting said queue of jobs to be processed;

means for scheduling said at least one job to be processed, wherein said job is scheduled to be performed by processing resources that are already reserved for another larger job if said at least one job to be processed can be processed by those reserved processing resources before other processing resources required for said larger job are available;

means for configuring dynamically the size of at least one cluster of processing resources from a pool of processing resources responsive to at least one attribute of said job to be processed;

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

means for making a result of said processing of said at least one job to be processed available to said at least one customer;

wherein said means for configuring dynamically a pool of processing resource into at least one cluster of processing resources responsive to at least one attribute of said at least one job to be processed further includes;

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

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

means for 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.

10. An apparatus of claim 9, wherein said means for receiving further includes at least one attribute specific to said at least one job to be processed including at least one of the following attributes:

(1) priority of processing, (2) type of processing, and (3) a tolerance time.

11. An apparatus as in claim 10 wherein said means for sorting said queue of jobs to be processed includes consideration of said request for priority of processing of said at least one job to be processed.

12. An apparatus of claim 10, wherein said tolerance time includes a time for completion acceptable to said at least one customer that is later in time than the estimated time for completion, and said means for querying offers a fee discount to said at least one customer for said tolerance time.

13. An apparatus as in claim 12, wherein means for sorting said queue of jobs to be processed includes consideration of said tolerance time attributed to said at least one job to be processed.

14. An apparatus as in claim 9, wherein said means for estimating a time for completion of processing of said at least one job to be processed further includes means for confirming said time for completion of processing with said at least one customer.

15. An apparatus as in claim 9, wherein said means for making a result of said processing of said at least one job to be processed available to said at least one customer further includes means for charging a fee for said result.

25. An apparatus as in claim 9, wherein said means for rebooting said cluster of processing resources soft reboots said cluster of processing resources.

27. An apparatus as in claim 9, further including means for querying if said at least one customer is willing to accept a tolerance time that includes a time for completion that is later than the estimated time for completion, wherein said means for configuring is responsive to a result from said means for querying.

16. An apparatus as in clam 15, wherein said fee is based on said time for completion of processing for said at least one job to be processed.

17. 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;

a queue of jobs to be processed and disposed to being sorted according to a priority assigned to each of said at least one job to be processed, said queue of jobs to be processed being in communication with said pool of processing resources;

a smart scheduler that schedules said at least one job to be processed to be performed by processing resources that are already reserved for another larger job if said at least one job to be processed can be processed by those reserved processing resources before other processing resources required for said larger job are available; and

said pool of processing resources configured to run at least one job to be processed, said pool of processing resources and disposed to being dynamically divided into clusters of processing resources which may run in parallel;

wherein said pool of processing resources are disposed to being dynamically divided into clusters of processing resources which may run in parallel is responsive to at least one attribute of said at least one job to be processed, and further include

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 processing 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.

18. A system as in claim 17, wherein said receiver element further includes at least one attribute specific to said at least one job to be processed including at least one of the following attributes:

(1) priority of processing, (2) type of processing, and (3) a tolerance time.

19. A system as in claim 18, wherein said queue of jobs to be processed may be sorted based on consideration of said request for priority of processing of said at least one job to be processed.

20. A system as in claim 18, wherein said tolerance time includes a time later than an estimated time for completion of said at least one job to be processed, and the querying by said querying element includes offering a fee discount to said at least one customer for said tolerance time.

21. A system as in claim 20, wherein said queue of jobs to be processed are sorted based on consideration of said tolerance time attributed to said at least one job to be processed.

22. A system as in claim 17, wherein at least one customer is charged a fee for said delivery of said result.

23. A system as in claim 22, wherein said fee is based on at least one of said attributes attributed to said at least one job to be processed.

28. A system as in claim 17, further including a querying element configured to query if said at least one customer is willing to accept a tolerance time that includes a time for completion of said at least one job to be processed that is later than an estimated time for completion of said at least one job to be processed, wherein sorting of said queue of jobs is responsive to a result of the querying by said querying element.