Method and computer program product for job selection and resource allocation of a massively parallel processor

• US 8,028,291 B2
• Filed: 01/22/2007
• Issued: 09/27/2011
• Est. Priority Date: 01/22/2007
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Altshuler, Yaniv, Domany, Tamar, Goldshmidt, Oleg, Naveh, Yehuda, Shmueli, Edi
• Primary Examiner(s): An; Meng A
• Assistant Examiner(s): KUMABE, BLAKE K
• Application Number:
  US11/625,352
• Publication Number:
  US 20080178187A1
• Time in Patent Office: 1,709 Days
• Field of Search: 718/104, 703/2
• US Class Current: 718/104
• 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
• 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

Abstract

A method for job selection and resource allocation of massively parallel processors, the method includes: providing to a constraint satisfaction problem solver multiple domains, variables, and constraints representative of a massively parallel processor, of queued job requests and of jobs being processed by the massively parallel processor, and generating, by the constraint satisfaction problem solver a result representative of multiple jobs to be executed, at least partially in parallel, by multiple resources of the massively parallel processor.

Claims

1. A method for job selection and resource allocation of massively parallel processors, the method comprises:

building a constraint satisfaction problem model, the constraint satisfaction problem model comprising multiple domains wherein each domain is of at least one dimension, multiple variables wherein each variable comprises at least one value within at least one of the domains, and multiple constraints expressed as mathematical relations between the variables, wherein the domains, variables and constraints are representative of;

a massively parallel processor, queued requests wherein each of the queued request is associated with a job, and jobs being processed by the massively parallel processor;

providing the constraint satisfaction problem model to a constraint satisfaction problem solver; and

generating, by the constraint satisfaction problem solver a satisfactory result, said generating based on the constraint satisfaction problem model,

wherein the satisfactory result is representative of at least two jobs associated with at least two of the queued requests, the at least two jobs selected to be executed, at least partially in parallel, by multiple resources of the massively parallel processor, and wherein the result comprises values indicating resources allocated for each of the at least two jobs.

2. The method according to claim 1 further comprising assigning at least one expiration threshold to at least one job and wherein result indicates if the at least one job was processed before the occurrence of the at least one expiration threshold.

3. The method according to claim 2 further comprising

generating a non-satisfactory result;

amending at least one variable of constraints; and

repeating the stages of providing.

4. The method according to claim 2 further comprising amending at least one expiration threshold and repeating the stages of providing and generating.

5. The method according to claim 1 further comprising selecting a subset of queued job requests and providing to the constraint satisfaction problem solver domains, variables, and constraints representative of a massively parallel processor, of the subset of the queued job requests and of jobs being processed by the massively parallel processor.

6. The method according to claim 1 further comprising:

performing the stages of providing and generating when a workload management selection criterion is fulfilled; and

,

if the workload management selection criterion is not fulfilled, selecting a head-of-queue job to be executed by the massively parallel processor by a non-constraint satisfaction problem job selection process and selecting which resources of the massively parallel processor in response to the selection.

7. The method according to claim 1 wherein the generating comprises generating a result representative of multiple jobs to be executed, at least partially in parallel, by multiple resources of the massively parallel processor that is arranged as K-dimensional array of nodes, wherein K is a positive integer that exceeds two.

8. The method according to claim 1 further comprising executing the multiple jobs in response to the result.

9. The method according to claim 1 wherein the method comprises receiving an indication that the massively parallel processor completed an execution of at least one job and repeating the stages of providing and generating.

10. The method according to claim 1 further comprising executing the stages of providing and generating to provide a first result;

storing the first result;

providing the first result, multiple domains, variables, and constraints representative of the massively parallel processor, of queued job requests and of jobs being processed by the massively parallel processor; and

generating, by the constraint satisfaction problem solver a second result representative of multiple jobs to be executed, at least partially in parallel, by multiple resources of the massively parallel processor.

11. The method according to claim 1 further comprising defining a set of expected job selection and resource allocation characteristics;

and wherein the generating comprises generating a result in response to the job selection and resource allocation characteristics.

12. A computer program product comprising a non-transitory computer usable medium including a computer readable program, wherein the computer readable program when executed on a computer causes the computer to:

build a constraint satisfaction problem model, the constraint satisfaction problem model comprising multiple domains wherein each domain is of at least one dimension, multiple variables wherein each variable comprises at least one value within at least one of the domains, and multiple constraints expressed as mathematical relations between the variables, wherein the domains, variables and constraints are representative of;

a massively parallel processor, queued requests wherein each of the queued request is associated with a job, and jobs being processed by the massively parallel processor;

provide the constraint satisfaction problem model to a constraint satisfaction problem solver;

generate, by the a constraint satisfaction problem solver and based on the constraint satisfaction problem model, a satisfactory result,

wherein the satisfactory result is representative of at least two jobs associated with at least two of the queued requests, the at least two jobs selected to be executed, at least partially in parallel, by multiple resources of the massively parallel processor, and wherein the result comprises values indicating resources allocated for each of the at least two jobs.

13. The computer program product according to claim 12, wherein the computer readable program when executed on a computer causes the computer to assign at least one expiration threshold to at least one job and wherein the result indicates if the at least one job was processed before the occurrence of the at least one expiration threshold.

14. The computer program product according to claim 13, wherein the computer readable program when executed on a computer causes the computer to:

generate a non-satisfactory result;

amend at least one variable of constraints; and

repeating the stages of providing.

15. The computer program product according to claim 13, wherein the computer readable program when executed on a computer causes the computer to amend at least one expiration threshold and repeating the stages of providing and generating.

16. The computer program product according to claim 12, wherein the computer readable program when executed on a computer causes the computer to select a subset of queued job requests and to apply the constraint satisfaction problem solving process on the subset of the queued job requests.

17. The computer program product according to claim 12, wherein the computer readable program when executed on a computer causes the computer to:

provide multiple domains and to generate a result using a constraint satisfaction problem solving process, when a workload management selection criterion is fulfilled; and

if the workload management selection criterion is not fulfilled, to select a head-of-queue job to be executed by the massively parallel processor by a non-constraint satisfaction problem job selection process and select which resources of the massively parallel processor in response to the selection.

18. The computer program product according to claim 12, wherein the computer readable program when executed on a computer causes the computer to generate a result representative of multiple jobs to be executed, at least partially in parallel, by multiple resources of the massively parallel processor that is arranged as K-dimensional array of nodes, wherein K is a positive integer that exceeds two.

19. The computer program product according to claim 12, wherein the computer readable program when executed on a computer causes the computer to execute the multiple jobs in response to the result.

20. The computer program product according to claim 12, wherein the computer readable program when executed on a computer causes the computer to generate a result in response to job selection and resource allocation characteristics.