Optimized multi-component co-allocation scheduling with advanced reservations for data transfers and distributed jobs

• US 8,782,246 B2
• Filed: 06/11/2012
• Issued: 07/15/2014
• 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 Brian
• Primary Examiner(s): JEAN, FRANTZ B
• Application Number:
  US13/493,300
• Publication Number:
  US 20120246660A1
• Time in Patent Office: 764 Days
• Field of Search: 709/201, 709/226, 709/229
• 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 comprising:

converting a topology of first compute resources available 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 first compute resources to at least one endpoint compute to yield mapped replica resources;

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

receiving a request to reserve second compute resources of the first compute resources to process a workload; and

reserving the second compute resources for the workload based on the identified schedule costs.

2. The method of claim 1, further comprising:

processing the workload on the second compute resources.

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

4. The method of claim 1, wherein the 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 first 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, or cost metrics.

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 comprising:

a processor; and

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

converting a topology of first compute resources available 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 first compute resources to at least one endpoint compute to yield mapped replica resources;

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

receiving a request to reserve second compute resources of the first compute resources to process a workload; and

reserving the second compute resources for the workload based on the identified schedule costs.

14. The system of claim 13, wherein the computer-readable storage medium stores further instructions which, when executed by the processor, cause the processor to perform further operations comprising:

processing the workload 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 the 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 first 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, wherein the computer-readable storage medium further, which, when executed by the processor, perform a step comprising:

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

20. A computer-readable storage device storing instructions which, when executed by a computing device, cause the computing device to perform operations comprising:

converting a topology of first compute resources available 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 first compute resources to at least one endpoint compute to yield mapped replica resources;

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

receiving a request to reserve second compute resources of the first compute resources to process a workload; and

reserving the second compute resources for the workload based on the identified schedule costs.