Optimized Multi-Component Co-Allocation Scheduling With Advanced Reservations for Data Transfers and Distributed Jobs

• US 20100287283A1
• Filed: 07/23/2010
• Published: 11/11/2010
• Est. Priority Date: 06/15/2006
• Status: Active Grant

• Current Assignee: III Holdings 12, LLC (Intellectual Ventures LLC)
• Original Assignee: Adaptive Computing Enterprises, Inc. (Ala Services LLC)
• Inventors: Jackson, David B.
• Granted Patent: US 8,200,824 B2
• Time in Patent Office: Days
• US Class Current: 709/226
• CPC Class Codes: G06F 9/5066 Algorithms for mapping a plurality of inter-dependent sub-tasks onto a plurality of physical CPUs mappping at compile time, see G06F8/451
• CPC Class Codes: G06F 9/5072 Grid computing
• CPC Class Codes: H04L 67/10 in which an application is distributed across nodes in the network software deployment G06F8/60; multiprogramming arrangements G06F9/46
• CPC Class Codes: H04L 67/60 Scheduling or organising the servicing of application requests, e.g. requests for application data transmissions using the analysis and optimisation of the required network resources admission control or resource allocation H04L47/70

Abstract

Disclosed are systems, methods, computer readable media, and compute environments for establishing a schedule for processing a job in a distributed compute environment. The method embodiment comprises converting a topology of a compute environment to a plurality of endpoint-to-endpoint paths, based on the plurality of endpoint-to-endpoint paths, mapping each replica resource of a plurality of resources to one or more endpoints where each respective resource is available, iteratively identifying schedule costs associated with a relationship between endpoints and resources, and committing a selected schedule cost from the identified schedule costs for processing a job in the compute environment.

Claims

1. A method of processing a job using compute resources, the method comprising:

converting a topology of compute resources available from a multinode compute environment for reservation to a plurality of endpoint-to-endpoint paths;

based on the plurality of endpoint-to-endpoint paths, mapping each replica resource of the compute resources to at least one endpoint where each respective resource is available to yield mapped replica resources;

identifying a schedule cost associated with each endpoint of the at least one endpoint to yield identified schedule costs; and

reserving compute resources in the multinode compute environment based on the identified schedule costs to yield reserved compute resources.

2. The method of claim 1, further comprising:

processing a job on the reserved compute resources.

3. The method of claim 1, wherein the compute resources comprise different resources, each having at least one endpoint associated with a respective resource.

4. The method of claim 1, wherein mapped replica resources are one of identical or determined to be sufficiently similar by a similarity analysis based on a threshold.

5. The method of claim 4, wherein the threshold is one of static and dynamic.

6. The method of claim 1, wherein each resource of the compute resources is one of data, a file, a portion of a file, a bandwidth, a CPU time, a software environment, a processor instruction set, a storage space, a contiguous storage space, a license, or a database.

7. The method of claim 1, further comprising:

before identifying the schedule cost, sorting the mapped replica resources.

8. The method of claim 1, wherein identifying a schedule cost further comprises:

generating a plurality of replica groupings by organizing resources into groups with identical endpoint locations;

sorting the plurality of replica groupings by availability;

for each of the plurality of replica groupings, generating a task availability range list for a source-to-destination paths;

for each of the plurality of replica groupings, prioritizing a pool of all ranges coming from all endpoints based on at least one of earliest availability, contention metrics, or cost metrics;

for each of the plurality of replica groupings and for each range in the availability range list;

(a) assigning resources in a current replica grouping thereby consuming available task slots;

(b) identifying a schedule cost for resources assigned in step (a);

(c) reducing task availability from all endpoint-to-endpoint and component level ranges which overlap in space and time; and

(d) continuing to a next endpoint if the schedule cost is greater than or equal to the schedule cost of a current best schedule; and

replacing the current best schedule with an identified endpoint, the schedule cost, and the schedule solution as the best schedule if the schedule cost is less than the schedule cost of the current best schedule.

9. The method of claim 8, wherein the plurality of replica groupings is sorted by constraint level from most constrained to least constrained.

10. The method of claim 8, wherein the pool of all ranges coming from all endpoints is prioritized based on one or more of earliest availability, contention metrics, cost metrics, or other parameters.

11. The method of claim 8, further comprising:

recording all schedule costs;

soliciting input from a user to select one of the recorded schedule costs; and

replacing the best schedule with the selected schedule.

12. The method of claim 8, wherein certain endpoints are favored or avoided based on one or more instructions.

13. A system for processing a job using compute resources, the system comprising:

a processor;

a first module configured to control the processor to convert a topology of compute resources available from a multinode compute environment for reservation to a plurality of endpoint-to-endpoint paths;

a second module configured to control the processor, based on the plurality of endpoint-to-endpoint paths, to map each replica resource of the compute resources to at least one endpoint where each respective resource is available to yield mapped replica resources;

a third module configured to control the processor to identify a schedule cost associated with each endpoint of the at least one endpoint to yield identified schedule costs; and

a fourth module configured to control the processor to reserve compute resources in the multinode compute environment based on the identified schedule costs to yield reserved compute resources.

14. The system of claim 13, further comprising:

a fifth module configured to control the processor to process a job on the reserved compute resources.

15. The system of claim 13, wherein the compute resources comprise different resources, each having at least one endpoint associated with a respective resource.

16. The system of claim 13, wherein mapped replica resources are one of identical or determined to be sufficiently similar by a similarity analysis based on a threshold.

17. The system of claim 16, wherein the threshold is one of static and dynamic.

18. The system of claim 13, wherein each resource of the compute resources is one of data, a file, a portion of a file, a bandwidth, a CPU time, a software environment, a processor instruction set, a storage space, a contiguous storage space, a license, or a database.

19. The system of claim 13, further comprising:

a fifth module configured to control the processor, before identifying the schedule cost, to sort the mapped replica resources.

20. A non-transitory computer-readable storage medium storing instructions for controlling a computing device to process a job using compute resources, the instructions comprising:

converting a topology of compute resources available from a multinode compute environment for reservation to a plurality of endpoint-to-endpoint paths;

based on the plurality of endpoint-to-endpoint paths, mapping each replica resource of the compute resources to at least one endpoint where each respective resource is available to yield mapped replica resources;

identifying a schedule cost associated with each endpoint of the at least one endpoint to yield identified schedule costs; and

reserving compute resources in the multinode compute environment based on the identified schedule costs to yield reserved compute resources.