Scheduling in a high-performance computing (HPC) system

• US 8,209,395 B2
• Filed: 10/07/2008
• Issued: 06/26/2012
• Est. Priority Date: 11/17/2004
• Status: Active Grant

• Current Assignee: Raytheon Company (Rtx Corporation)
• Original Assignee: Raytheon Company (Rtx Corporation)
• Inventors: Richoux, Anthony N.
• Primary Examiner(s): Ngo, Ricky
• Assistant Examiner(s): Nguyen, Phuongchau B
• Application Number:
  US12/246,783
• Publication Number:
  US 20090031316A1
• Time in Patent Office: 1,358 Days
• Field of Search: 709/217, 709226-227
• US Class Current: 709/217
• CPC Class Codes: G06F 2209/483 Multiproc
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues
• CPC Class Codes: G06F 9/5027 the resource being a machine, e.g. CPUs, Servers, Terminals

Abstract

In one embodiment, a method for scheduling in a high-performance computing (HPC) system includes receiving a call from a management engine that manages a cluster of nodes in the HPC system. The call specifies a request including a job for scheduling. The method further includes determining whether the request is spatial, compact, or nonspatial and noncompact. The method further includes, if the request is spatial, generating one or more spatial combinations of nodes in the cluster and selecting one of the spatial combinations that is schedulable. The method further includes, if the request is compact, generating one or more compact combinations of nodes in the cluster and selecting one of the compact combinations that is schedulable. The method further includes, if the request is nonspatial and noncompact, identifying one or more schedulable nodes and generating a nonspatial and noncompact combination of nodes in the cluster.

Claims

1. A non-transitory computer-readable medium encoded with logic for scheduling in a high-performance computer (HPC) system, wherein the logic operates when executed to:

receive a call from a management engine operable to manage a cluster of nodes in a HPC system, the call specifying a request comprising a job for scheduling, the job comprising one or more processes for execution at one or more nodes in the cluster, the call further specifying a number of nodes for executing the job;

determine whether the request is spatial, compact, or nonspatial and noncompact, the request being spatial if the job assumes spatial relationships between nodes executing the job, the request being compact if the job assumes proximity between nodes executing the job, the request being nonspatial and noncompact if the job assumes no spatial relationships or proximity between nodes executing the job;

generate one or more combinations of nodes in the cluster, the one or more combinations generated according to whether the request is spatial, compact, or nonspatial and noncompact; and

communicate a return to the management engine, the return identifying one or more nodes in at least one combination of nodes in the cluster for executing the job.

2. The non-transitory computer-readable medium of claim 1, wherein:

if the request is spatial, generating one or more combinations of nodes comprises generating one or more spatial combinations of nodes in the cluster accommodating the number of nodes specified in the call and further accommodating the assumed spatial relationships between nodes executing the job;

the logic further operates when executed to select one of the spatial combinations that is schedulable according to a list of nodes in the cluster available for scheduling; and

the communicated return identifies one or more nodes in the selected spatial combination of nodes in the cluster for executing the job.

3. The non-transitory computer-readable medium of claim 2, wherein, if the request is spatial and three dimensional, the logic further operates when executed to rotate a mesh accommodating the number of nodes specified in the call and further accommodating the assumed spatial relationships between nodes executing processes in the job to one of six orientations to generate one of the spatial combinations.

4. The non-transitory computer-readable medium of claim 2, wherein, if the request is spatial and two dimensional, the logic further operates when executed to fold an unused dimension of the job to generate a mesh accommodating the number of nodes specified in the call from the management engine and rotate the mesh to one of six orientations to generate one of the spatial combinations.

5. The non-transitory computer-readable medium of claim 2, wherein, if the request is spatial and one dimensional, the logic further operates when executed to fold two unused dimensions of the job to generate a mesh accommodating the number of nodes specified in the call from the management engine and rotate the mesh to one of six orientations to generate one of the spatial combinations.

6. The non-transitory computer-readable medium of claim 2, wherein the logic further operates when executed to use a scan algorithm that searches for a start point for the job in the cluster of nodes to select one of the spatial combinations that is schedulable according to a list of nodes in the cluster available for scheduling.

7. The non-transitory computer-readable medium of claim 1, wherein:

if the request is compact, generating one or more combinations of nodes comprises generating one or more compact combinations of nodes in the cluster accommodating the number of nodes specified in the call;

the logic further operates when executed to select one of the compact combinations that is schedulable according to the list of nodes in the cluster available for scheduling and that is more compact than other compact combinations that are schedulable according to the list of nodes in the cluster available for scheduling; and

the communicated return identifies one or more nodes in the selected compact combination of nodes in the cluster for executing the job.

8. The non-transitory computer-readable medium of claim 7, wherein generating one or more compact combinations of nodes in the cluster accommodating the number of nodes specified in the call from the management engine comprises:

generating a first compact combination of nodes in the cluster accommodating the number of nodes specified in the call from the management engine;

generating one or more second compact combinations of nodes in the cluster accommodating the number of nodes specified in the call from the management engine, each second compact combination being less compact than the first compact combination; and

sorting the first and second compact combinations according to compactness for selection of one of the first and second compact combinations.

9. The non-transitory computer-readable medium of claim 1, wherein:

if the request is nonspatial and noncompact, the logic further operates to identify one or more nodes schedulable according to the list of nodes in the cluster available for scheduling;

generating one or more combinations of nodes comprises generating a nonspatial and noncompact combination of nodes in the cluster accommodating the number of nodes specified in the call, the nonspatial and noncompact combination comprising one or more of the one or more identified nodes that are schedulable according to the list of nodes in the cluster available for scheduling; and

the communicated return identifies one or more nodes in the nonspatial and noncompact combination of nodes in the cluster for executing the job.

10. The non-transitory computer-readable medium of claim 9, wherein generating a nonspatial and noncompact combination of nodes in the cluster accommodating the number of nodes specified in the call from the management engine comprises:

making a first loop through the cluster with respect to a first dimension of the cluster until a first node unavailable for scheduling according to the list of nodes in the cluster available for scheduling is reached;

making a second loop through the cluster with respect to a second dimension of the cluster until a second node unavailable for scheduling according to the list of nodes in the cluster available for scheduling is reached; and

making a third loop through the cluster with respect to a third dimension of the cluster until a third node unavailable for scheduling according to the list of nodes in the cluster available for scheduling is reached.

11. The non-transitory computer-readable medium of claim 10, wherein the logic further operates when executed to repeat the first loop, the second loop, and the third loop to cover all the nodes in the cluster.

12. The non-transitory computer-readable medium of claim 1, wherein the call further specifies:

whether the request is spatial, compact, or nonspatial and noncompact;

if the request is spatial, a size of the job;

an aggressive flag indicating a degree of leeway for scheduling the job;

a size of the cluster in terms of a number of switches in the cluster;

a number of nodes coupled to each switch in the cluster;

a number of nodes available for scheduling; and

the list of nodes in the cluster available for scheduling.

13. The non-transitory computer-readable medium of claim 1, wherein the return to the management engine further identifies a Message Passing Interface (MPI) rank of each node in the at least one combination of nodes.

14. The non-transitory computer-readable medium of claim 1, wherein the logic further operates when executed to:

determine whether the cluster comprises enough nodes to accommodate the number of nodes for executing the one or more processes in the job specified in the call from the management engine; and

if the cluster comprises less than enough nodes to accommodate the number of nodes for executing the one or more processes in the job specified in the call from the management engine, indicate to the management engine that the job is unschedulable.

15. The non-transitory computer-readable medium of claim 1, wherein the logic is stateless.

16. The non-transitory computer-readable medium of claim 1, wherein a node is a central processing unit (CPU) coupled to two switches.

17. The non-transitory computer-readable medium of claim 1, wherein the cluster of nodes is a three dimensional torus.

18. A method for scheduling in a high-performance computing (HPC) system, the method comprising:

receiving a call from a management engine operable to manage a cluster of nodes in a HPC system, the call specifying a request comprising a job for scheduling, the job comprising one or more processes for execution at one or more nodes in the cluster, the call further specifying a number of nodes for executing the job;

determining whether the request is spatial, compact, or nonspatial and noncompact, the request being spatial if the job assumes spatial relationships between nodes executing the job, the request being compact if the job assumes proximity between nodes executing the job, the request being nonspatial and noncompact if the job assumes no spatial relationships or proximity between nodes executing the job;

generating one or more combinations of nodes in the cluster, the one or more combinations generated according to whether the request is spatial, compact, or nonspatial and noncompact; and

communicating a return to the management engine, the return identifying one or more nodes in at least one combination of nodes in the cluster for executing the job.

19. The method of claim 18, wherein:

if the request is spatial, generating one or more combinations of nodes comprises generating one or more spatial combinations of nodes in the cluster accommodating the number of nodes specified in the call and further accommodating the assumed spatial relationships between nodes executing the job;

and further comprising;

selecting one of the spatial combinations that is schedulable according to a list of nodes in the cluster available for scheduling, the communicated return identifying one or more nodes in the selected spatial combination of nodes in the cluster for executing the job.

20. The method of claim 19, further comprising:

if the request is spatial and three dimensional, rotating a mesh accommodating the number of nodes specified in the call and further accommodating the assumed spatial relationships between nodes executing processes in the job to one of six orientations to generate one of the spatial combinations.

21. The method of claim 19, further comprising:

if the request is spatial and two dimensional, folding an unused dimension of the job to generate a mesh accommodating the number of nodes specified in the call from the management engine and rotating the mesh to one of six orientations to generate one of the spatial combinations.

22. The method of claim 19, further comprising:

if the request is spatial and one dimensional, folding two unused dimensions of the job to generate a mesh accommodating the number of nodes specified in the call from the management engine and rotating the mesh to one of six orientations to generate one of the spatial combinations.

23. The method of claim 19, further comprising:

using a scan algorithm that searches for a start point for the job in the cluster of nodes to select one of the spatial combinations that is schedulable according to a list of nodes in the cluster available for scheduling.

24. The method of claim 18, wherein:

if the request is compact, generating one or more combinations of nodes comprises generating one or more compact combinations of nodes in the cluster accommodating the number of nodes specified in the call;

and further comprising;

selecting one of the compact combinations that is schedulable according to the list of nodes in the cluster available for scheduling and that is more compact than other compact combinations that are schedulable according to the list of nodes in the cluster available for scheduling, wherein the communicated return identifies one or more nodes in the selected compact combination of nodes in the cluster for executing the job.

25. The method of claim 24, wherein generating one or more compact combinations of nodes in the cluster accommodating the number of nodes specified in the call from the management engine comprises:

generating a first compact combination of nodes in the cluster accommodating the number of nodes specified in the call from the management engine;

generating one or more second compact combinations of nodes in the cluster accommodating the number of nodes specified in the call from the management engine, each second compact combination being less compact than the first compact combination; and

sorting the first and second compact combinations according to compactness for selection of one of the first and second compact combinations.

26. The method of claim 18, further comprising, if the request is nonspatial and noncompact, identifying one or more nodes schedulable according to the list of nodes in the cluster available for scheduling, wherein:

generating one or more combinations of nodes comprises generating a nonspatial and noncompact combination of nodes in the cluster accommodating the number of nodes specified in the call, the nonspatial and noncompact combination comprising one or more of the one or more identified nodes that are schedulable according to the list of nodes in the cluster available for scheduling; and

the communicated return identifies one or more nodes in the nonspatial and noncompact combination of nodes in the cluster for executing the job.

27. The method of claim 26, wherein generating a nonspatial and noncompact combination of nodes in the cluster accommodating the number of nodes specified in the call from the management engine comprises:

making a first loop through the cluster with respect to a first dimension of the cluster until a first node unavailable for scheduling according to the list of nodes in the cluster available for scheduling is reached;

making a second loop through the cluster with respect to a second dimension of the cluster until a second node unavailable for scheduling according to the list of nodes in the cluster available for scheduling is reached; and

making a third loop through the cluster with respect to a third dimension of the cluster until a third node unavailable for scheduling according to the list of nodes in the cluster available for scheduling is reached.

28. The method of claim 27, further comprising:

repeating the first loop, the second loop, and the third loop to cover all the nodes in the cluster.

29. The method of claim 18, wherein the call further specifies:

whether the request is spatial, compact, or nonspatial and noncompact;

if the request is spatial, a size of the job;

an aggressive flag indicating a degree of leeway for scheduling the job;

a size of the cluster in terms of a number of switches in the cluster;

a number of nodes coupled to each switch in the cluster;

a number of nodes available for scheduling; and

the list of nodes in the cluster available for scheduling.

30. The method of claim 18, wherein the return to the management engine further identifies a Message Passing Interface (MPI) rank of each node in the at least one combination of nodes.

31. The method of claim 18, further comprising:

determining whether the cluster comprises enough nodes to accommodate the number of nodes for executing the one or more processes in the job specified in the call from the management engine; and

if the cluster comprises less than enough nodes to accommodate the number of nodes for executing the one or more processes in the job specified in the call from the management engine, indicating to the management engine that the job is unschedulable.

32. The method of claim 18, executed according to stateless logic.

33. The method of claim 18, wherein a node is a central processing unit (CPU) coupled to two switches.

34. The method of claim 18, wherein the cluster of nodes is a three dimensional torus.

35. A system for scheduling in a high-performance computing (HPC) system, the system comprising:

means for receiving a call from a management engine operable to manage a cluster of nodes in a HPC system, the call specifying a request comprising a job for scheduling, the job comprising one or more processes for execution at one or more nodes in the cluster, the call further specifying a number of nodes for executing the job;

means for determining whether the request is spatial, compact, or nonspatial and noncompact, the request being spatial if the job assumes spatial relationships between nodes executing the job, the request being compact if the job assumes proximity between nodes executing the job, the request being nonspatial and noncompact if the job assumes no spatial relationships or proximity between nodes executing the job;

means for generating one or more combinations of nodes in the cluster, the one or more combinations generated according to whether the request is spatial, compact, or nonspatial and noncompact; and

means for communicating a return to the management engine, the return identifying one or more nodes in at least one combination of nodes in the cluster for executing the job.