OPTIMIZED MULTI-COMPONENT CO-ALLOCATION SCHEDULING WITH ADVANCED RESERVATIONS FOR DATA TRANSFERS AND DISTRIBUTED JOBS

• US 20070294408A1
• Filed: 06/14/2007
• Published: 12/20/2007
• Est. Priority Date: 06/15/2006
• Status: Active Grant

• Current Assignee: III Holdings 12, LLC (Intellectual Ventures LLC)
• Original Assignee: Cluster Resources, Inc. (Ala Services LLC)
• Inventors: Jackson, David B.
• Granted Patent: US 7,774,471 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 establishing a schedule for processing a job in a compute environment, the method comprising:

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.

2. The method of claim 1, wherein the plurality of resources contains different resources, each having at least one endpoint associated with the respective resource.

3. The method of claim 1, wherein mapped replica resources may be identical or wherein mapped replica resources may be determined to be sufficiently similar by a similarity analysis based on a static or dynamic threshold.

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

5. The method of claim 1, further comprising after mapping each resource and before iteratively identifying the schedule cost:

sorting the mapping of replica resources.

6. The method of claim 1, wherein iteratively identifying schedule costs 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 source-to-destination path;

for each of the plurality of replica groupings, prioritizing a pool of all ranges coming from all endpoints based on one or more 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 the schedule cost;

(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 schedule cost is greater than or equal to the schedule cost of a current best schedule; and

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

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

8. The method of claim 6, 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.

9. The method of claim 6, the method 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.

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

11. A system for establishing a schedule for processing a job in a compute environment, the system comprising:

a module configured to convert a topology of a compute environment to a plurality of endpoint-to-endpoint paths;

a module configured to map each replica resource of a plurality of resources to one or more endpoints where each respective resource is available based on the plurality of endpoint-to-endpoint paths;

a module configured to iteratively identify schedule costs associated with a relationship between endpoints and resources; and

a module configured to commit a selected schedule cost from the identified schedule costs for processing a job in the compute environment.

12. The system of claim 11, wherein the plurality of resources contains different resources, each having at least one endpoint associated with the respective resource.

13. The system of claim 11, wherein mapped replica resources may be identical or wherein mapped replica resources may be determined to be sufficiently similar by a similarity analysis based on a static or dynamic threshold.

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

15. The system of claim 11, the system further comprising after mapping each resource and before iteratively identifying the schedule cost:

a module configured to sort the mapping of replica resources.

16. The system of claim 11, wherein the module configured to iteratively identify schedule costs further comprises:

a module configured to generate a plurality of replica groupings by organizing resources into groups with identical endpoint locations;

a module configured to sort the plurality of replica groupings by availability;

a module configured to generate a task availability range list for source-to-destination path for each of the plurality of replica groupings;

a module configured to prioritize a pool of all ranges coming from all endpoints based on one or more of earliest availability, contention metrics, or cost metrics for each of the plurality of replica groupings;

a module configured to perform the following steps for each of the plurality of replica groupings and for each range in the availability range list;

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

(b) identify the schedule cost;

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

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

a module configured to replace the best schedule with the identified endpoint, schedule cost, and schedule solution if the schedule cost is less than the schedule cost of the current best schedule.

17. The system of claim 16, wherein the module configured to sort the plurality of replica groupings is configured to sort by constraint level from most constrained to least constrained.

18. The system of claim 16, 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.

19. A computer readable medium storing a computer program having instructions for establishing a schedule for processing a job in a compute environment, the instructions comprising:

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.

20. The computer readable medium of claim 19, wherein the plurality of resources contains different resources, each having at least one endpoint associated with the respective resource.

21. The computer readable medium of claim 19, wherein mapped replica resources may be identical or wherein mapped replica resources may be determined to be sufficiently similar by a similarity analysis based on a static or dynamic threshold.

22. The computer readable medium of claim 19, wherein each resource of the plurality of resources is one of data, a file, a portion of a file, bandwidth, CPU time, a software environment, a processor instruction set, storage space, contiguous storage space, a license, or a database.

23. The computer readable medium of claim 19, the instructions further comprising after mapping each resource and before iteratively identifying the schedule cost:

sorting the mapping of replica resources.

24. The computer readable medium of claim 19, wherein iteratively identifying schedule costs 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 source-to-destination path;

for each of the plurality of replica groupings, prioritizing a pool of all ranges coming from all endpoints based on one or more 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 the schedule cost;

(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 schedule cost is greater than or equal to the schedule cost of a current best schedule; and

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

25. A distributed compute environment that consumes jobs, the distributed compute environment managing workload by establishing a schedule for processing submitted jobs according to a method comprising:

converting a topology of the distributed 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 distributed compute environment.