System and method of performing a pre-reservation analysis to yield an improved fit of workload with the compute environment

• US 10,445,148 B2
• Filed: 09/27/2017
• Issued: 10/15/2019
• Est. Priority Date: 03/13/2004
• Status: Active Grant

• Current Assignee: III Holdings 12, LLC (Intellectual Ventures LLC)
• Original Assignee: III Holdings 12, LLC (Intellectual Ventures LLC)
• Inventors: Jackson, David B.
• Primary Examiner(s): Zhao, Bing
• Application Number:
  US15/717,392
• Publication Number:
  US 20180018205A1
• Time in Patent Office: 748 Days
• Field of Search: None
• CPC Class Codes: G06F 2209/5014 Reservation
• CPC Class Codes: G06F 2209/506 Constraint
• 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/5083 Techniques for rebalancing the load in a distributed system

Abstract

A system and method are disclosed for receiving a request for resources in a compute environment to process workload, the request including a specification of a quality of fit. The system generates a substantial maximum potential quality of fit based on compute environment with an assumption of no competing workload to yield an analysis. The system evaluates a first resource allocation and a second resource allocation against the analysis to yield the first fit in a respective second fit. The system selects one of the first resource allocation and the second resource allocation based on a comparison of the first fit to the second fit as well as a cost associated with any delays.

Claims

1. A method comprising:

receiving a request for resources to process workload in a compute environment;

generating a substantially optimal effective speed of fulfilling the request for a potential allocation of the resources in the compute environment and a potential time of allocation;

comparing the effective speed of fulfilling the request for each of a plurality of resource allocations and times of allocation that are different from the resource allocation and time of allocation that yields the substantially optimal effective speed of fulfilling the request with the substantially optimal effective speed of fulfilling the request;

selecting one of the plurality of resource allocations and times of allocation and the potential allocation that yields the substantially optimal effective speed of fulfilling the request based on (i) the comparison of the effective speeds of fulfilling the request for each of the plurality of resource allocations and times of allocation and the substantially optimal effective speed of fulfilling the request and (ii) a cost associated with a difference between the time of allocation associated with each of the plurality of resource allocations and times of allocation and the time associated with the potential allocation that yields the substantially optimal effective speed of fulfilling the request; and

if one the plurality of resource allocations and time of allocation is selected, generating a co-allocation map between the resource allocations in the selected resource allocation and the resource allocations in the potential allocation that yields the substantially optimal effective speed of fulfilling the request.

2. The method of claim 1, further comprising:

reserving the resources in the compute environment based on the selecting.

3. The method of claim 1, wherein the difference relates to a start time when the workload starts in the plurality of resource allocations and times of allocation.

4. The method of claim 1, wherein the selecting one of the plurality of resource allocations and times of allocation and the potential allocation that yields the substantially optimal effective speed of fulfilling the request is further based on a cost associated with a difference in the resource allocations in each of the plurality of allocations and the resource allocation in the potential allocation that yields the substantially optimal effective speed of fulfilling the request.

5. The method of claim 4, further comprising:

reserving the resources in the compute environment based on the selecting.

6. A system comprising:

a processor; and

a computer-readable storage medium storing instructions which, when executed by the processor, cause the processor to perform operations comprising;

receiving a request for resources to process workload in a compute environment;

generating a substantially optimal effective speed of fulfilling the request for a potential allocation of the resources in the compute environment and a potential time of allocation;

comparing the effective speed of fulfilling the request for each of a plurality of resource allocations and times of allocation that are different from the resource allocation and time of allocation that yields the substantially optimal effective speed of fulfilling the request with the substantially optimal effective speed of fulfilling the request;

selecting one of the plurality of resource allocations and times of allocation and the potential allocation that yields the substantially optimal effective speed of fulfilling the request based on (i) the comparison of the effective speeds of fulfilling the request for each of the plurality of resource allocations and times of allocation and the substantially optimal effective speed of fulfilling the request and (ii) a cost associated with a difference between the time of allocation associated with each of the plurality of resource allocations and times of allocation and the time associated with the potential allocation that yields the substantially optimal effective speed of fulfilling the request; and

if one the plurality of resource allocations and time of allocation is selected, generating a co-allocation map between the resource allocations in the selected resource allocation and the resource allocations in the potential allocation that yields the substantially optimal effective speed of fulfilling the request.

7. The system of claim 6, wherein the computer-readable storage medium stores further instructions which, when executed by the processor, cause the processor to perform a further operation comprising:

reserving the resources in the compute environment based on the selecting.

8. The system of claim 6, wherein the difference relates to a start time when the workload starts in the plurality of resource allocations and times of allocation.

9. The system of claim 6, wherein the selecting one of the plurality of resource allocations and times of allocation and the potential allocation that yields the substantially optimal effective speed of fulfilling the request is further based on a cost associated with a difference in the resource allocations in each of the plurality of allocations and the resource allocation in the potential allocation that yields the substantially optimal effective speed of fulfilling the request.

10. The system of claim 9, further comprising:

reserving the resources in the compute environment based on the selecting.

11. A non-transitory computer-readable storage device storing instructions which, when executed by a processor, cause the processor to perform operations comprising:

receiving a request for resources to process workload in a compute environment;

generating a substantially optimal effective speed of fulfilling the request for a potential allocation of the resources in the compute environment and a potential time of allocation;

comparing the effective speed of fulfilling the request for each of a plurality of resource allocations and times of allocation that are different from the resource allocation and time of allocation that yields the substantially optimal effective speed of fulfilling the request with the substantially optimal effective speed of fulfilling the request;

selecting one of the plurality of resource allocations and times of allocation and the potential allocation that yields the substantially optimal effective speed of fulfilling the request based on (i) the comparison of the effective speeds of fulfilling the request for each of the plurality of resource allocations and times of allocation and the substantially optimal effective speed of fulfilling the request and (ii) a cost associated with a difference between the time of allocation associated with each of the plurality of resource allocations and times of allocation and the time associated with the potential allocation that yields the substantially optimal effective speed of fulfilling the request; and

if one the plurality of resource allocations and time of allocation is selected, generating a co-allocation map between the resource allocations in the selected resource allocation and the resource allocations in the potential allocation that yields the substantially optimal effective speed of fulfilling the request.

12. The non-transitory computer-readable storage device of claim 11, wherein the computer-readable storage device stores instructions which, when executed by the processor, cause the processor to perform a further operation comprising:

reserving the resources in the compute environment based on the selecting.

13. The non-transitory computer-readable storage device of claim 11, wherein the difference relates to a start time when the workload starts in the plurality of resource allocations and times of allocation.

14. The non-transitory computer-readable storage device of claim 11, wherein the selecting one of the plurality of resource allocations and times of allocation and the potential allocation that yields the substantially optimal effective speed of fulfilling the request is further based on a cost associated with a difference in the resource allocations in each of the plurality of allocations and the resource allocation in the potential allocation that yields the substantially optimal effective speed of fulfilling the request.

15. The non-transitory computer-readable storage device of claim 14, wherein further operation comprising:

reserving the resources in the compute environment based on the selecting.