System and method of co-allocating a reservation spanning different compute resources types

• US 7,971,204 B2
• Filed: 03/11/2005
• Issued: 06/28/2011
• Est. Priority Date: 03/13/2004
• Status: Active Grant

• Current Assignee: III Holdings 12, LLC (Intellectual Ventures LLC)
• Original Assignee: Adaptive Computing Enterprises, Inc. (Ala Services LLC)
• Inventors: Jackson, David Brian
• Primary Examiner(s): To, Jennifer N.
• Application Number:
  US10/530,582
• Publication Number:
  US 20070094665A1
• Time in Patent Office: 2,300 Days
• Field of Search: 718/104
• US Class Current: 718/104
• CPC Class Codes: G06F 2209/5014 Reservation
• CPC Class Codes: G06F 2209/506 Constraint
• CPC Class Codes: G06F 9/50 Allocation of resources, e.g. of the central processing unit [CPU]
• CPC Class Codes: G06F 9/5027 the resource being a machine, e.g. CPUs, Servers, Terminals
• 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

Abstract

A system and method of co-allocating resources within a compute environment are disclosed. The method embodiment of the invention comprises receiving a request for a reservation for a first type of resource, analyzing constraints and guarantees associated with the first type of resource, identifying a first group of resources that meet the request for the first type of resource and storing in a first list, receiving a request for a reservation for a second type of resource, analyzing constraints and guarantees associated with the second type of resource, identifying a second group of resources that meet the request for the second type of resource and storing in a second list, calculating a co-allocation parameter between the first group of resources and the second group of resources and reserving resources according to the calculated co-allocation parameter of the first group of resources and the second group of resources. The request may also request exclusivity of the reservation.

Claims

1. A method of co-allocating resources within a compute environment, the method comprising:

receiving a first request for a reservation for a first type of resource in a compute environment comprising a plurality of networked computing devices;

analyzing first constraints and service level agreement guarantees associated with the first request, the first constraints and guarantees related to use of the compute environment;

identifying a first group of resources that meet the first request;

receiving a second request for a reservation for a second type of resource in the compute environment;

analyzing second constraints and service level agreement guarantees associated with the second request, the second constraints and service level agreement guarantees related to use of the compute environment, wherein the first type of resource and second type of resource span at least one computing device of the plurality of networked computing devices, wherein each computing device of the plurality of networked computing devices has a homogeneous processor architecture;

identifying a second group of resources that meet the second request; and

generating a co-allocation map between the first group of resources and the second group of resources, wherein the co-allocation map comprises at least one of (1) intersecting time frames in which both the first request and the second request may be simultaneously satisfied, and (2) all time frames where available resources exist that satisfy the first request and the second request.

2. The method of claim 1, further comprising reserving resources according to the co-allocation map.

3. The method of claim 1, wherein generating the co-allocation map comprises identifying a reduced map of quantities of resources that can simultaneously satisfy the first request and the second request.

4. The method of claim 1, wherein the first and second types of resources comprise at least one of:

compute resources, disk storage resources, network bandwidth resources, memory resources, and licensing resources.

5. The method of claim 1, wherein generating the co-allocation map further comprises identifying an intersection of an availability of each of the first type of resource and the second type of resource.

6. The method of claim 1, further comprising:

generating a resulting array of events describing the intersecting time frames.

7. The method of claim 6, wherein the resulting array of events comprises at least one of resource quantity, resource quality, time frames, quality of information and cost.

8. The method of claim 1, wherein the first request and the second request comprise at least one of:

a job description, at least one time frame availability, a description of minimum resources, a description of resource types and attributes, and a reservation duration minimum.

9. The method of claim 1, wherein identifying the first group of resources and the second group of resources further comprises analyzing events associated with the first request and the second request and how resource availability changes over time.

10. The method of claim 9, wherein the events comprise at least one of job start, job completion, state change, boundaries, reservations, and policy enforcement limits.

11. The method of claim 1, further comprising reporting at least one of the following parameters associated with the identified first and second group of resources:

cost, quality of information data, resource quantity data, time frame data, and resource quality data.

12. The method of claim 1, further comprising reporting at least one of the following parameters associated with the identified first and second group of resources:

cost, quality of information data, resource quantity data, time frame data, and resource quality data.

13. The method of claim 12, further comprising:

performing again, under constraints identified by the co-allocation map, the step of identifying a second group of resources that meet the request for the second type of resource.

14. The method of claim 1, wherein:

receiving a request for a reservation for a first type of resource further comprises receiving a request for the first type of resource for a first time frame, and wherein the identifying and analyzing steps for the first type of resource take into account the first time frame;

receiving a request for a reservation for a second type of resource further comprises receiving a request for the second type of resource for a second time frame, wherein the identifying and analyzing steps for the second type of resource take into account the second time frame; and

generating the co-allocation map between the first group of resources and the second group of resources further comprises calculating an intersection of the first time frame and the second time frame.

15. The method of claim 1, wherein constraints of the first constraints, the second constraints and the service level agreement guarantees are at least one of resource matching in terms of type, attribute or quantity.

16. The method of claim 1, wherein the first constraints, the second constraints and the service level agreement guarantees associated with the first request and the second request relate to resource-based policies.

17. The method of claim 1, wherein the first constraints, the second constraints and the service level agreement guarantees associated with the first request and the second request relate to time-based policies.

18. The method of claim 17, wherein the time-based policies limit requestors to a pre-determined quantity of resources at any given moment in time.

19. The method of claim 1, wherein receiving a request for a reservation for a first type of resource further comprises receiving a request for a reservation for the first type of resource having an attribute.

20. The method of claim 19, wherein the attribute is at least one of disk storage space, memory, license scope, network bandwidth capability, clock speed and central processing power.

21. The method of claim 1, wherein the co-allocation map is computed as one of an intersection, a union or a distinct response.

22. The method of claim 21, further comprising, before reserving compute resources, presenting to a requestor of a reservation of the first and second type of resources an analysis of the compute resources and a possible reservation.

23. The method of claim 22, wherein the presented analysis relates to a quantity and quality of the compute resources in relation to a request for a reservation for resources.

24. The method of claim 23, further comprising:

receiving from the requestor of a reservation a revised request for resources based on the presented analysis.

25. The method of claim 21, wherein a requestor may select that generating the co-allocation map returns an analysis according to at least one of the intersection, union or distinct response.

26. The method of claim 25, wherein the analysis returned to the requestor, according to at least one of the intersection, union or distinct response, corresponds to an analysis of the quantity of resources and a degree of fulfillment of the first request and the second request according to available resources.

27. The method of claim 26, wherein the analysis returned to the requestor further comprises a list of resources that can fulfill the first request and the second request.

28. The method of claim 26, wherein the analysis returned to the requestor further comprises a transaction ID associated with the analysis.

29. The method of claim 28, further comprising presenting to the requestor an option to submit the first request and the second request with reference to the transaction ID.

30. A method of claim 1, wherein the co-allocation map represents a set of resources associated with at least one of the first request or the second request.

31. The method of claim 30, wherein the first request specifies exclusivity of a set of reasons for the first request.

32. A system for co-allocating resources within a compute environment, the system comprising:

a processor;

means that controls the processor to receive a first request for a reservation for a first type of resource in a compute environment comprising a plurality of networked computing devices;

means that controls the processor to analyze first constraints and service level agreement guarantees associated with the first request, the first constraints and service level agreement guarantees related to use of the compute environment;

means that controls the processor to identify a first group of resources that meet the request for the first type of resource;

means that controls the processor to receive a second request for a reservation for a second type of resource in the compute environment;

means that controls the processor to analyze second constraints and service level agreement guarantees associated with the second request, the second constraints and service level agreement guarantees related to use of the plurality of networked computing devices within the compute environment, wherein the first type of resource and second type of resource span at least one computing device of the plurality of networked computing devices, wherein each computing device of the plurality of networked computing devices has a homogeneous processor architecture;

means that controls the processor to identify a second group of resources that meet the request for the second type of resource; and

means that controls the processor to generate a co-allocation map between the first group of resources and the second group of resources, wherein the co-allocation map comprises at least one of (1) intersecting time frames in which both the first request and the second request may be simultaneously satisfied, and (2) all time frames where available resources exist that satisfy the first request and the second request.

33. The system of claim 32, further comprising means that controls the processor to reserve resources according to the co-allocation map.

34. A system for co-allocating resources within a compute environment, the system comprising:

a processor;

a first module controlling the processor to receive a first request for a reservation for a first type of resource in a compute environment comprising a plurality of networked computing devices;

a second module controlling the processor to analyze first constraints and service level agreement guarantees associated with the first request, the first constraints and service level agreement guarantees related to use of the compute environment;

a third module controlling the processor to identify a first group of resources that meet the request for the first type of resource;

a fourth module controlling the processor to receive a second request for a reservation for a second type of resource in the compute environment;

a fifth module controlling the processor to analyze second constraints and service level agreement guarantees associated with the second request, the second constraints and service level agreement guarantees related to use of the compute environment, wherein the first type of resource and second type of resource span at least one computing device of the plurality of networked computing devices, wherein each computing device of the plurality of networked computing devices has a homogeneous processor architecture;

a sixth module controlling the processor to identify a second group of resources that meet the request for the second type of resource; and

a seventh module controlling the processor to generate a co-allocation map between the first group of resources and the second group of resources, wherein the co-allocation map comprises at least one of (1) intersecting time frames in which both the first request and the second request may be simultaneously satisfied, and (2) all time frames where available resources exist that satisfy the first request and the second request.

35. The system of claim 34, further comprising a module controlling the processor to reserve resources according to the co-allocation map.

36. A non-transitory computer-readable medium storing instructions for controlling a computing device to co-allocate resources within a compute environment, the instructions causing the computing device to perform steps comprising:

receiving a first request for a reservation for a first type of resource in a compute environment comprising a plurality of networked computing devices;

analyzing first constraints and service level agreement guarantees associated with the first request, the first constraints and service level agreement guarantees related to use of the compute environment;

identifying a first group of resources that meet the request for the first type of resource;

receiving a second request for a reservation for a second type of resource in the compute environment;

analyzing second constraints and service level agreement guarantees associated with the second request, the second constraints and service level agreement guarantees related to use of the compute environment, wherein the first type of resource and second type of resource span at least one computing device of the plurality of networked computing devices, wherein each computing device of the plurality of networked computing devices has a homogeneous processor architecture;

identifying a second group of resources that meet the request for the second type of resource; and

generating a co-allocation map between the first group of resources and the second group of resources, wherein the co-allocation map comprises at least one of (1) intersecting time frames in which both the first request and the second request may be simultaneously satisfied, and (2) all time frames where available resources exist that satisfy the first request and the second request.

37. The non-transitory computer-readable medium of claim 36, wherein the instructions further comprise reserving resources according to the co-allocation map.