System and method for topology-aware job scheduling and backfilling in an HPC environment

• US 9,904,583 B2
• Filed: 11/16/2015
• Issued: 02/27/2018
• Est. Priority Date: 04/15/2004
• Status: Active Grant

• Current Assignee: Raytheon Company (Rtx Corporation)
• Original Assignee: Raytheon Company (Rtx Corporation)
• Inventors: Davidson, Shannon V., Richoux, Anthony N.
• Primary Examiner(s): Lee, James J
• Application Number:
  US14/942,214
• Publication Number:
  US 20160132361A1
• Time in Patent Office: 834 Days
• CPC Class Codes: G06F 11/1482 by means of middleware or OS functionality
• CPC Class Codes: G06F 11/2025 using centralised failover control functionality
• CPC Class Codes: G06F 2201/815 Virtual middleware or OS functionality using virtual machines to implement generic software techniques for error detection or fault masking G06F11/1484
• 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/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
• 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: G06F 9/5077 Logical partitioning of resources; Management or configuration of virtualized resources specific details on emulation or internal functioning of virtual machines G06F9/455
• CPC Class Codes: G06F 9/5083 Techniques for rebalancing the load in a distributed system

Abstract

A method for job management in an HPC environment includes determining an unallocated subset from a plurality of HPC nodes, with each of the unallocated HPC nodes comprising an integrated fabric. An HPC job is selected from a job queue and executed using at least a portion of the unallocated subset of nodes.

Claims

1. A method comprising:

identifying, using one or more processors, one or more nodes of a first virtual cluster of nodes that are available for processing a job, the first virtual cluster of nodes being one of a plurality of virtual clusters of nodes;

selecting a job from a job queue;

determining whether the identified nodes are sufficient to process the selected job, wherein the determining includes determining whether a topology of the identified nodes accommodates a shape of the selected job;

in response to determining the identified nodes are not sufficient to process the selected job, selecting one or more nodes from other nodes of the plurality of virtual clusters of nodes that are not currently available for processing the selected job;

allocating the selected one or more nodes and the identified nodes for processing the selected job; and

processing the selected job using the allocated nodes after the selected one or more nodes becoming available to process the selected job.

2. The method of claim 1 further comprising:

identifying a shape that sufficiently matches the shape of the selected job;

identifying one or more shapes of the available nodes; and

wherein determining whether the identified nodes are sufficient to process the selected job includes determining whether the identified nodes match the identified one or more shapes of the available nodes.

3. The method of claim 2, wherein the identified one or more shapes of the available nodes includes one or more of (1) a cube in which nodes of the available nodes are allocated in a logical cubic volume so as to allow tasks of the selected job to exchange data with other tasks of the selected job so as to minimize a distance between nodes that exchange data, and (2) a sphere in which nodes of the available nodes are allocated in a logical spherical volume so as to allow a first task of the selected job to be placed in a center node of the sphere with remaining tasks of the selected job placed on nodes surrounding the center node so as to minimize a distance between the first task and the remaining tasks.

4. The method of claim 1, wherein the selected one or more nodes are from the first virtual cluster of nodes.

5. The method of claim 1, wherein at least one of the selected one or more nodes are from a second virtual cluster of nodes, the second virtual cluster of nodes is one of the plurality of virtual clusters of nodes.

6. The method of claim 1, wherein the nodes are grouped according to a type of job that they can process, and wherein determining whether the identified nodes are sufficient to process the selected job includes determining if the selected job matches a job type of identified nodes.

7. The method of claim 6, wherein the nodes are further allocated to process job requests from users that submit similar jobs, and wherein determining whether the identified nodes are sufficient to process the selected job includes determining if the selected nodes are allocated to process a job from a user that submitted the selected job.

8. The method of claim 1, further comprising:

after selecting one or more nodes from the virtual clusters of nodes that are not currently available for processing the selected job, waiting for another job being processed by the selected one or more nodes to finish processing.

9. The method of claim 8, further comprising:

wherein processing the selected job occurs in response to the processing of the another job finishing.

10. A non-transitory machine-readable storage device including instructions stored thereon that, when executed by a machine, cause the machine to perform operations comprising:

identifying one or more nodes of a first virtual cluster of nodes that are available for processing a job, the first virtual cluster of nodes being one of a plurality of virtual clusters of nodes;

selecting a job from a job queue;

determining whether the identified nodes are sufficient to process the selected job, wherein the determining includes determining whether a topology of the identified nodes accommodates a shape of the selected job;

in response to determining the identified nodes are not sufficient to process the selected job, selecting one or more nodes from other nodes of the plurality of virtual clusters of nodes that are not currently available for processing the selected job;

allocating the selected one or more nodes and the identified nodes for processing the selected job; and

processing the selected job using the allocated nodes after the selected one or more nodes becoming available to process the selected job.

11. The storage device of claim 10 further comprising instructions that, when executed by the machine, cause the machine to perform further operations comprising:

identifying a shape that sufficiently matches the shape of the selected job;

identifying one or more shapes of the available nodes; and

wherein determining whether the identified nodes are sufficient to process the selected job includes determining whether the identified nodes match the identified one or more shapes of the available nodes.

12. The storage device of claim 11, wherein the identified one or more shapes of the available nodes includes one or more of (1) a cube in which nodes of the available nodes are allocated in a logical cubic volume so as to allow tasks of the selected job to exchange data with other tasks of the selected job so as to minimize a distance between nodes that exchange data, and (2) a sphere in which nodes of the available nodes are allocated in a logical spherical volume so as to allow a first task of the selected job to be placed in a center node of the sphere with remaining tasks of the selected job placed on nodes surrounding the center node so as to minimize a distance between the first task and the remaining tasks.

13. The storage device of claim 10, wherein the selected one or more nodes are from the first virtual cluster of nodes.

14. The storage device of claim 10, wherein at least one of the selected one or more nodes are from a second virtual cluster of nodes, the second virtual cluster of nodes one of the plurality of virtual clusters of nodes.

15. The storage device of claim 10, wherein the nodes are grouped according to a type of job that they can process, and wherein the instructions for determining whether the identified nodes are sufficient to process the selected job include instructions for determining if the selected job matches a job type of identified nodes.

16. The storage device of claim 15, wherein the nodes are further allocated to process job requests from users that submit similar jobs, and wherein the instructions for determining whether the identified nodes are sufficient to process the selected job include instructions for determining if the selected nodes are allocated to process a job from a user that submitted the selected job.

17. The storage device of claim 10, further comprising instructions that, when executed by the machine, cause the machine to perform further operations comprising:

after selecting one or more nodes from the virtual dusters of nodes that are not currently available for processing the selected job, waiting for another job being processed by the selected one or more nodes to finish processing.

18. The storage device of claim 17, wherein the instructions for processing the selected job include instructions for processing the selected job in response to the processing of the another job finishing.

19. A system comprising:

a cluster management engine;

virtual clusters of nodes, each node of the virtual clusters comprising a processing device; and

the cluster management engine configured to;

identify one or more nodes of a first virtual cluster of nodes that are available for processing a job, the first virtual cluster of nodes is one of the virtual clusters of nodes;

selecting a job from a job queue;

determine whether the identified nodes are sufficient to process the selected job, wherein the determining includes determining whether a topology of the identified nodes accommodates a shape of the selected job;

in response to a determination that the identified nodes are not sufficient to process the selected job, select one or more nodes from other nodes of the plurality of virtual clusters of nodes that are not currently available for processing the selected job; and

allocate the selected one or more nodes and the identified nodes for processing the selected job; and

the allocated nodes to process the selected job, using the processing device, after the selected one or more nodes becoming available to process the selected job.

20. The system of claim 19, wherein the selected one or more nodes are from the first virtual cluster of nodes.

21. The system of claim 19, wherein at least one of the selected one or more nodes are from a second virtual cluster of nodes, the second virtual cluster of nodes is one of the virtual clusters of nodes.

22. The system of claim 19, wherein the cluster management engine is further to:

identify a shape that sufficiently matches the shape of the selected job;

identify one or more shapes of the available nodes; and

wherein a determination of whether the identified nodes are sufficient to process the selected job includes the cluster management engine to determine whether the identified nodes match the identified one or more shapes of the available nodes.

23. The system of claim 22, wherein the identified one or more shapes of the available nodes includes one or more of (1) a cube in which nodes of the available nodes are allocated in a logical cubic volume so as to allow tasks of the selected job to exchange data with other tasks of the selected job so as to minimize a distance between nodes that exchange data, and (2) a sphere in which nodes of the available nodes are allocated in a logical spherical volume so as to allow a first task of the selected job to be placed in a center node of the sphere with remaining tasks of the selected job placed on nodes surrounding the center node so as to minimize a distance between the first task and the remaining tasks.

24. The system of claim 19, further comprising a cluster agent for each of the virtual clusters of nodes communicatively coupled between the cluster management engine and a respective node of the virtual clusters of nodes, the cluster agent to convey a status of the respective node to the cluster management engine.

25. The system of claim 19, wherein the cluster management engine is further to, after selecting one or more nodes from the virtual clusters of nodes that are not currently available for processing the selected job, wait for another job being processed by the selected one or more nodes to finish processing.

26. The system of claim 25, wherein processing the selected job occurs in response to the processing of the another job finishing.