Support of non-trivial scheduling policies along with topological properties

• US 8,601,480 B2
• Filed: 09/28/2009
• Issued: 12/03/2013
• Est. Priority Date: 05/11/2004
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Shpigelman, Igor
• Primary Examiner(s): Tang, Kenneth
• Application Number:
  US12/568,450
• Publication Number:
  US 20100146515A1
• Time in Patent Office: 1,527 Days
• Field of Search: None
• US Class Current: 718/102
• CPC Class Codes: G06F 13/1663 Access to shared memory
• CPC Class Codes: G06F 2209/483 Multiproc
• CPC Class Codes: G06F 2212/2542 Non-uniform memory access [NUMA] architecture
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/0629 Configuration or reconfiguration of storage systems
• CPC Class Codes: G06F 3/0644 Management of space entities, e.g. partitions, extents, pools
• CPC Class Codes: G06F 3/0689 Disk arrays, e.g. RAID, JBOD
• 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/5016 the resource being the memory

Abstract

A system and method for scheduling jobs in a multiprocessor machine is disclosed. The status of resources, including CPUs on node boards and associated shared memory in the multiprocessor machine is periodically determined. The status can indicate the resources available to execute jobs. This information is accumulated by the topology-monitoring unit and provided to the topology library. The topology library also receives a candidate host list from the scheduling unit which lists all of the resources available to execute the job being scheduled based on non-trivial scheduling. The topology library unit then uses this to generate a free map F indicative of the interconnection of the resources available to execute the job. The topology monitoring unit then matches the jobs to the resources available to execute the jobs, based on resource requirements including shape requirements indicative of interconnections of resources required to execute the job. The topology monitoring unit dispatches the job to the portion of the free map F which match the shape requirements of the job. If the topology library unit determines that no resources are available to execute the job, the topology library unit will return the job to the scheduling unit and the scheduling unit which will wait until the resources become available. The free map F may include resources which have been suspended or reserved in previous scheduling cycles, provided the job to be scheduled satisfies the predetermined criteria for execution of the job on the suspended, have a lower priority, or are reserved resources.

Claims

1. A computer system having a scheduling system to schedule a job having resource mapping requirements to resources in a computing architecture arranged at least in part on node boards in host computers, each node board having at least one central processor unit (CPU) and shared memory, said node boards being interconnected into groups of node boards providing access between the central processing units (CPUs) and shared memory on different node boards, said computer system comprising:

a processor for executing computing instructions;

memory for storing said computing instructions;

a scheduling system associated with the processor and the memory, and comprising;

a scheduling unit for scheduling jobs to at least some of said resources, said scheduling unit generating a candidate host list representing the resources available to execute the job to be scheduled based on resource requirements of the job to be scheduled;

a topology library unit comprising a machine map M of the computer system, said machine map M indicative of the interconnections of the resources to which the scheduling system can schedule the jobs;

a topology monitoring unit for monitoring a status of the resources and generating status information signals indicative of a status of the resources;

wherein the topology library unit receives the status information signals and the candidate host list and determines a free map F of resources to execute the job to be scheduled, said free map F indicative of the interconnection of the resources to which the job in a current scheduling cycle can be scheduled based on the status information signals, the candidate host list and the machine map M;

wherein the topology monitoring unit dispatches a job to the resources in the free map F which match the resource mapping requirements of the job;

wherein the jobs to be scheduled each have a priority rating and wherein the scheduling unit includes priority status information signals indicative of the priority of the job which is being executed by the jobs that have been scheduled in previous scheduling cycles but have not yet been completed; and

wherein the scheduling unit includes in the candidate host list any resources which are executing jobs having a lower priority than the priority of the job being scheduled in the current scheduling cycle and excludes from the candidate host list any resources which are executing a job having a priority that is higher than the priority of the job being scheduled in the current scheduling cycle.

2. The computer system as defined in claim 1, wherein the job to be scheduled comprises resource requirements including topological requirements specifying at least one interconnection of the resources required to execute the job;

and wherein the topological unit dispatches the job to be scheduled to a portion of the free map F which matches the topological requirements of the job to be scheduled.

3. The computer system as defined in claim 2, wherein the topology monitoring unit for monitoring the status of the resources updates the status of the resources to reflect any jobs scheduled in the current scheduling cycle and provides an updated candidate host list to the scheduling unit reflecting resources allocated to the job to be scheduled in the current scheduling cycle.

4. The computer system as defined in claim 3, wherein the updated host list reflects the status information signals received from the topology monitoring unit.

5. The computer system as defined in claim 4, wherein the updated host list reflects resources which the status information signals indicate have been configured out since a previous scheduling cycle.

6. The computer system as defined in claim 5, wherein the undated host list reflects the status information signals received from the topology monitoring unit.

7. The computer system as defined in claim 6, wherein the updated host list reflects resources which the status information signals indicate have been configured out since a previous scheduling cycle.

8. The computer system as defined in claim 1, wherein the resource mapping requirements of a job comprises shape requirements including physical interconnections of some of the resources in at least two dimensions required to execute the job;

and

wherein the topology library unit receives the shape requirements corresponding to each job to be scheduled and matches the job to be scheduled to a portion of the resources in the free map F which matches the shape requirements of the job.

9. The computer system as defined in claim 8, wherein the access between the central processing units (CPUs) and shared memory on different node boards is non-uniform.

10. The computer system as defined in claim 1, wherein if the topological library unit cannot locate a group of node boards which have the resources required to execute the job, the job scheduling unit delays allocation of the job until the status information signals indicate the resources required to execute the job are available.

11. The computer system as defined in claim 1, wherein the topology monitoring unit comprises, for each host containing computer resources of the computer system, a topology daemon for receiving jobs which have been scheduled to the corresponding host, and, said topology daemon allocating the jobs to the matched resources;

and

wherein the topology daemon communicates with the topology library unit once a job has been allocated to the matched resources.

12. The computer system as defined in claim 1, wherein the resources are partitioned into one or more virtual or physical partitions, and wherein the topology monitoring unit comprises a topology daemon associated with each partition of the computer system having resources available for execution;

wherein each topology daemon determines a status of the resources within its associated partition and generates the status information signals indicative of a status of each associated resource.

13. In a computer system comprising resources arranged at least in part in on nodes boards, each node board having at least one central processor unit (CPU) and shared memory, said node boards being interconnected to provide access between the central processing units (CPUs) and shared memory on different boards, a method of scheduling a job to said resources comprising:

(a) determining a machine map M of the computer system indicative of all of the interconnections of all of the resources in the computer system to which a scheduling system can schedule jobs and storing the machine map M in a topology library unit, wherein the jobs each have a priority rating;

(b) periodically assessing a status of the resources and sending status information signals indicative of the status of the resources to the topology library unit;

(c) assessing at the topology monitoring unit a free map F of resources indicative of the interconnection of all of resources to which the scheduling unit can schedule a job in a current scheduling cycle;

(d) assessing priority status information signals indicative of the priority of jobs being executed by the jobs that have been scheduled in previous scheduling cycles but have not yet been completed;

(e) including in the free map F any resources which are executing jobs having a lower priority than the priority of the job currently being scheduled and excluding from the free map F any resources which are executing a job having a priority that is higher than the priority of the job being scheduled;

(f) matching resource requirements, including topological requirements specifying at least one interconnection of the resources required to execute the job currently being scheduled, to resources in the free map F which match the resource requirements of the job; and

(g) dispatching the job to the matched resources.