System and method of providing a fixed time offset based dedicated co-allocation of a common resource set

• US 7,870,552 B2
• Filed: 02/09/2006
• Issued: 01/11/2011
• Est. Priority Date: 02/09/2005
• 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.
• Primary Examiner(s): Puente, Emerson C
• Assistant Examiner(s): Lee, Adam
• Application Number:
  US11/276,013
• Publication Number:
  US 20060179438A1
• Time in Patent Office: 1,797 Days
• Field of Search: None
• US Class Current: 718/101
• CPC Class Codes: G06F 2209/484 Precedence
• CPC Class Codes: G06F 2209/5014 Reservation
• CPC Class Codes: G06F 2209/506 Constraint
• CPC Class Codes: G06F 9/46 Multiprogramming arrangements
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues
• 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

Abstract

Disclosed are a system, method and computer-readable medium relating to managing resources within a compute environment having a group of nodes or computing devices. The method comprises, for each node in the compute environment: traversing a list jobs having a fixed time relationship, wherein for each job in the list, the following steps occur: obtaining a range list of available timeframes for each job, converting each availability timeframe to a start range, shifting the resulting start range in time by a job offset, for a first job, copying the resulting start range into a node range, and for all subsequent jobs, logically AND'"'"'ing the start range with the node range. Next, the method comprises logically OR'"'"'ing the node range with a global range, generating a list of acceptable resources on which to start and the timeframe at which to start and creating reservations according to the list of acceptable resources for the resources in the group of computing devices and associated job offsets.

Claims

1. A method of managing resources within a computing environment, the method comprising:

A. for each resource in the compute environment;

(1) traversing a list of jobs having a fixed time relationship between at least two jobs in the list of jobs, wherein for each job in the list of jobs, the method comprises;

a. obtaining a range list of available timeframes for the each job to consume the each resource in the compute environment;

b. converting each availability timeframe in the range list of available timeframes to a first start range;

c. shifting the first start range in time by a job offset to yield a shifted first start range;

d. for the each job, determining a second start range based on a node range, wherein the each job has a respective second start range and a respective node range;

(2) for the each job, logically AND'"'"'ing the respective second start range with the respective node range to yield a second node range;

B. logically OR'"'"'ing the second node range with a global node range to yield an acceptable node range, wherein the global node range reflects timeframes and resource quantities available to all jobs including jobs in the list of jobs where the all jobs can simultaneously consume requested resources at specified offsets on a same set of allocated resources;

C. generating a list of acceptable resources based on the acceptable node range on which to start jobs from the list of jobs to consume resources and a timeframe at which to start the jobs; and

D. creating at least one reservation in the compute environment according to the list of acceptable resources and associated job offsets.

2. The method of claim 1, wherein parameters associated with the each job which are used to identify a history of available timeframes comprise at least one of duration, resource requirements, allocated resources and actions.

3. The method of claim 1, wherein the fixed time relationship between each of the at least two jobs is established by specifying and enforcing the offset-based relationship between the jobs.

4. The method of claim 1, further comprising:

determining whether a job of the least two jobs has a highest priority, and if yes, providing first access to all currently available resources to the job with the highest priority.

5. The method of claim 1, wherein the each resource in the compute environment referenced in step A is a node.

6. The method of claim 1, wherein the fixed time relationship between each of the at least two jobs results in at least one of job overlap, job juxtaposition and an offset-based relationship between jobs.

7. A system for managing resources within a computing environment, the system comprising:

A. a first module configured, for each resource in the compute environment, to;

(1) traverse a list of jobs having a fixed time relationship between at least two jobs in the list of jobs, wherein for each job in the list of jobs, the first module is further configured to;

a. obtaining a range list of available timeframes for the each job to consume the each resource in the compute environment;

b. converting each availability timeframe in the range list of available timeframes to a first start range;

c. shifting the first start range in time by a job offset to yield a shifted first start range;

d. for the each job, determining a second start range based on a node range, wherein the each job has a respective second start range and a respective node range;

(2) for the each job, logically AND'"'"'ing the respective second start range with the respective node range to yield a second node range;

B. a second module configured to logically OR the second node range with a global node range to yield an acceptable node range, wherein the global node range reflects timeframes and resource quantities available to all jobs including jobs in the list of jobs where the all jobs can simultaneously consume requested resources at specified offsets on a same set of allocated resources;

C. a third module configured to generate a list of acceptable resources based on the acceptable node range on which to start jobs from the list of jobs to consume resources and a timeframe at which to start the jobs; and

D. a fourth module configured to create at least one reservation of resources in the compute environment according to the list of acceptable resources and associated job offsets.

8. The system of claim 7, wherein parameters associated with the each job which are used to identify a history of available timeframes comprise at least one of duration, resource requirements, allocated resources and actions.

9. The system of claim 7, wherein the fixed time relationship between each of the at least two jobs is established by specifying and enforcing the offset-based relationship between the jobs.

10. The system of claim 7, further comprising:

determining whether a job of the least two jobs has a highest priority, and if yes, providing first access to all currently available resources to the job with the highest priority.

11. The system of claim 7, wherein the each resource in the compute environment referenced in step A is a node.

12. The system of claim 7, wherein the fixed time relationship between each of the at least two jobs results in at least one of job overlap, job juxtaposition and an offset-based relationship between jobs.

13. A non-transitory computer-readable medium storing instructions comprising:

A. for each resource in the compute environment;

(1) traversing a list of jobs having a fixed time relationship between at least two jobs in the list of jobs, wherein for each job in the list of jobs, the method comprises;

a. obtaining a range list of available timeframes for the each job to consume the each resource in the compute environment;

b. converting each availability timeframe in the range list of available timeframes to a first start range;

c. shifting the first start range in time by a job offset to yield a shifted first start range;

d. for the each job, determining a second start range based on a node range, wherein the each job has a respective second start range and a respective node range;

(2) for the each job, logically AND'"'"'ing the respective second start range with the respective node range to yield a second node range;

B. logically OR'"'"'ing the second node range with a global node range to yield an acceptable node range, wherein the global node range is associated with timeframes and resource quantities available to all jobs in addition to jobs in the list of jobs where the all jobs can simultaneously consume requested resources at specified offsets on a same set of allocated resources;

C. generating a list of acceptable resources based on the acceptable node range on which to start jobs from the list of jobs to consume resources and a timeframe at which to start the jobs; and

D. creating at least one reservation of resources in the compute environment according to the list of acceptable resources and associated job offsets.

14. The non-transitory computer readable medium of claim 13, wherein parameters associated with the each job which are used to identify a history of available timeframes comprise at least one of duration, resource requirements, allocated resources and actions.

15. The non-transitory computer readable medium of claim 13, wherein the fixed time relationship between each of the at least two jobs is established by specifying and enforcing the offset-based relationship between the jobs.

16. The non-transitory computer readable medium of claim 13, further comprising:

determining whether a job of the least two jobs has a highest priority, and if yes, providing first access to all currently available resources to the job with the highest priority.

17. The non-transitory computer readable medium of claim 13, wherein the each resource in the compute environment referenced in step A is a node.

18. The non-transitory computer readable medium of claim 13, wherein the fixed time relationship between each of the at least two jobs results in at least one of job overlap, job juxtaposition and an offset-based relationship between jobs.