# US 2017/0255500 A1 · Dispatching jobs for execution in parallel by multiple processors

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2017/0255500 A1
- Document ID: US20170255500A1
- Status: Published application
- Kind: A1
- Application number: 15/223,657
- Filed: 2016-07-29
- Published: 2017-09-07
- Earliest claimed: 2016-03-07
- Assignees: International Business Machines Corporation
- Applicants: International Business Machines Corporation
- Inventors: Giulia Carnevale; Marzia E. Castellani; Marco Gianfico; Roberto Ragusa
- Web page: https://patentgrep.com/patent/US20170255500A1

## CPC

- G06F 9/4881: {Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues}
- 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)}
- G06F 2209/483: Multiproc
- G06F 2209/484: Precedence
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A method, and associated system and computer program product, for dispatching two or more jobs for execution in a computing system including processors configured to execute the jobs in parallel. Each processor is associated with a corresponding queue having a queue size equal to a maximum number of jobs that may be in the queue. A new job requested for execution is assigned to a current class. An indication is retrieved of a last processor of the processors of the current class to which a last job of jobs of the current class has been submitted for execution. An indication is retrieved of a delta number of the jobs submitted for execution to the last processor of the current class after the last job of the current class. The new job for execution is submitted to a last processor of the current class or a selected processor.

## Claims

### Claim 1

A method for dispatching a plurality of jobs for execution in a computing system comprising a plurality of processors configured to execute the jobs in parallel, said plurality of processors comprising one or more processors, each processor of the plurality of processors being associated with a queue having a queue size equal to a maximum number of jobs that may be in the queue while the jobs in the queue are waiting to be executed by the processor associated with the queue, said method comprising:
receiving, by the one or more processors, a request for execution of a new job of the plurality of jobs;
assigning, by the one or more processors, the new job to a current class of a plurality of classes, wherein the jobs of different classes do not have execution dependencies;
retrieving, by the one or more processors, an indication of a last processor of the processors of the current class to which a last job of jobs of the current class has been submitted for execution;
retrieving, by the one or more processors, an indication of a delta number of the jobs being submitted for execution to the last processor of the current class after the last job of the current class; and
submitting, by the one or more processors, the new job for execution to a submission processor of the plurality of processors, said submission processor being set to the last processor of the current class or to a selected processor of the plurality of processors according to a comparison between the delta number and the queue size of the last processor of the current class.

### Claim 2 (depends on 1)

The method of claim 1, wherein said submitting the new job for execution comprises:
submitting the new job for execution to the last processor of the current class in response to a determination that the delta number is equal to or lower than the queue size of the last processor of the current class, or
submitting the new job for execution to the selected processor response to a determination that the delta number is higher than the queue size of the last processor of the current class.

### Claim 3 (depends on 1)

The method of claim 1, wherein a last processor memory structure associates each class with an indication of a last processor of the processors of one class to which a last job of jobs of the one class has been submitted for execution, said retrieving an indication of a last processor of the processors of the current class comprising:
reading the indication of the processor associated with the current class from the last processor memory structure;
said submitting the new job for execution comprising, response to a determination that the submission processor is the selected processor, associating an indication of the selected processor with the current class in the last processor memory structure.

### Claim 4 (depends on 1)

The method of claim 1, wherein a total number memory structure associates each processor of the plurality of processors with a total number of the jobs being submitted for execution to each processor from a starting time, wherein a last number memory structure associates each class with a last number indicating the total number of the last processor of each class at a submission thereto of the last job of each class, said retrieving an indication of a delta number comprising:
reading the total number of the last processor of the current class from the total number memory structure;
reading the last number of the current class from the last number memory structure; and
calculating the delta number according to a difference between the total number of the last processor of the current class and the last number of the current class,
said submitting the new job comprising:
incrementing the total number associated with the submission processor in the total number memory structure; and
setting the last number of the current class in the last number memory structure according to the total number associated with the submission processor.

### Claim 5 (depends on 1)

The method of claim 1, wherein said submitting the new job for execution comprises, in response to a determination that the submission processor is the current processor:
submitting the new job for execution to the current processor in a blocking mode; and waiting for acceptance, by the current processor, of the new job for execution in response to a determination that a current number of the jobs being queued for execution by the current processor is lower than the queue size of the current processor.

### Claim 6 (depends on 1)

The method of claim 1, wherein said submitting the new job for execution comprises, in response to a determination that the submission processor is the selected processor:
selecting the selected processor according to one or more selection criteria.

### Claim 7 (depends on 1)

The method of claim 1, wherein said submitting the new job for execution comprises, in response to a determination that the submission processor is the selected processor, executing each iteration of a loop that comprises one or more iterations, wherein for each iteration said executing comprises:
determining a new candidate processors of the plurality of processors for the selected processor;
attempting to submit the new job for execution to the candidate processor; and
receiving a return code from the candidate processor in response to said attempting to submit the new job for execution to the candidate processor;
exiting the loop if an exit condition is fulfilled, wherein executing a last iteration of the loop comprises determining that the exit condition is fulfilled in the last iteration.

### Claim 8 (depends on 7)

The method of claim 7, wherein the exit condition is that a maximum number of repetitions of the iterations is reached, said submitting the new job for execution comprising, in response to said determining that the exit condition is fulfilled without acceptance of the submission of the new job by the candidate processor:
submitting the new job for execution to the selected processor in a blocking mode; and waiting for acceptance of the submission of the new job by the selected processor in response to a determination that a current number of the jobs being queued for execution by the selected processor is lower than the queue size of the selected processor.

### Claim 9 (depends on 7)

The method of claim 7, wherein the exit condition is that the return code from the candidate processor is indicative of acceptance of the submission of the new job by the candidate processor, wherein the acceptance of the submission of the new job by the candidate processor is in response to a determination that a current number of the jobs being queued for execution by the candidate processor is lower than the queue size of the candidate processor.

### Claim 10 (depends on 1)

The method of claim 1, wherein said submitting the new job for execution to the submission processors comprises:
submitting the new job for execution to the submission processor in a blind mode without receiving any notification of completion of the execution of the new job by the submission processor.

### Claim 11 (depends on 1)

The method of claim 1, wherein a number of the classes is higher than a number of the processors of the plurality of processors.

### Claim 12

A computer program product, the computer program product comprising one or more computer readable hardware storage devices having computer readable program code stored therein, said program code containing instructions executable by one or more processors to implement a method for dispatching a plurality of jobs for execution in a computing system comprising a plurality of processors configured to execute the jobs in parallel, said plurality of processors comprising the one or more processors, each processor of the plurality of processors being associated with a queue having a queue size equal to a maximum number of jobs that may be in the queue while the jobs in the queue are waiting to be executed by the processor associated with the queue, said method comprising:
receiving, by the one or more processors, a request or execution of a new job of the plurality of jobs;
assigning, by the one or more processors, the new job to a current class of a plurality of classes, wherein the jobs of different classes do not have execution dependencies;
retrieving, by the one or more processors, an indication of a last processor of the processors of the current class to which a last job of jobs of the current class has been submitted for execution;
retrieving, by the one or more processors, an indication of a delta number of the jobs being submitted for execution to the last processor of the current class after the last job of the current class; and
submitting, by the one or more processors, the new job for execution to a submission processor of the plurality of processors, said submission processor being set to the last processor of the current class or to a selected processor of the plurality of processors according to a comparison between the delta number and the queue size of the last processor of the current class.

### Claim 13 (depends on 12)

The computer program product of claim 12, wherein said submitting the new job for execution comprises:
submitting the new job for execution to the last processor of the current class in response to a determination that the delta number is equal to or lower than the queue size of the last processor of the current class; or
submitting the new job for execution to the selected processor in response to a determination that the delta number is higher than the queue size of the last processor of the current class.

### Claim 14 (depends on 12)

The computer program product of claim 12, wherein a total number memory structure associates each processor of the plurality of processors with a total number of the jobs being submitted for execution to each processor from a starting time, wherein a last number memory structure associates each class with a last number indicating the total number of the last processor of each class at a submission thereto of the last job of each class, said retrieving an indication of a delta number comprising:
reading the total number of the last processor of the current class from the total number memory structure;
reading the last number of the current class from the last number memory structure; and
calculating the delta number according to a difference between the total number of the last processor of the current class and the last number of the current class,
said submitting the new job comprising:
incrementing the total number associated with the submission processor in the total number memory structure; and
setting the last number of the current class in the last number memory structure according to the total number associated with the submission processor.

### Claim 15

A computing system, comprising a plurality of processors that includes one or more processors, one or more memories, and one or more computer readable hardware storage devices, said one or more hardware storage device containing program code executable by the one or more processors via the one or more memories to implement a method for dispatching a plurality of jobs for execution in the computing system, said plurality of processors configured to execute the jobs in parallel, each processor of the plurality of processors being associated with a queue having a queue size equal to a maximum number of jobs that may be in the queue while the jobs in the queue are waiting to be executed by the processor associated with the queue, said method comprising:
receiving, by the one or more processors, a request for execution of a new job of the plurality of jobs;
assigning, by the one or more processors, the new job to a current class of a plurality of classes, wherein the jobs of different classes do not have execution dependencies;
retrieving, by the one or more processors, an indication of a last processor of the processors of the current class to which a last job of jobs of the current class has been submitted for execution;
retrieving, by the one or more processors, an indication of a delta number of the jobs being submitted for execution to the last processor of the current class after the last job of the current class; and
submitting, by the one or more processors, the new job for execution to a submission processor of the plurality of processors, said submission processor being set to the last processor of the current class or to a selected processor of the plurality of processors according to a comparison between the delta number and the queue size of the last processor of the current class

### Claim 16 (depends on 15)

The computing system of claim 15, wherein said circuitry for submitting the new job for execution comprises:
submitting the new job for execution to the last processor of the current class in response to a determination that the delta number is equal to or lower than the queue size of the last processor of the current class; or
submitting the new job for execution to the selected processor in response to a determination that the delta number is higher than the queue size of the last processor of the current class.

### Claim 17 (depends on 15)

The computing system of claim 15, wherein a total number memory structure associates each processor of the plurality of processors with a total number of the jobs being submitted for execution to each processor from a starting time, wherein a last number memory structure associates each class with a last number indicating the total number of the last processor of each class at a submission thereto of the last job of each class, said retrieving an indication of a delta number comprising:
reading the total number of the last processor of the current class from the total number memory structure;
reading the last number of the current class from the last number memory structure; and
calculating the delta number according to a difference between the total number of the last processor of the current class and the last number of the current class,
said submitting the new job comprising:
incrementing the total number associated with the submission processor in the total number memory structure; and
setting the last number of the current class in the last number memory structure according to the total number associated with the submission processor.

### Claim 18 (depends on 15)

The method of claim 15, wherein said submitting the new job for execution comprises, in response to a determination that the submission processor is the current processor:
submitting the new job for execution to the current processor in a blocking mode and waiting for acceptance, by the current processor, of the new job for execution in response to a determination that a current number of the jobs being queued for execution by the current processor is lower than the queue size of the current processor.

### Claim 19 (depends on 15)

The method of claim 15, wherein said submitting the new job for execution comprises, in response to a determination that the submission processor is the selected processor:
selecting the selected processor according to one or more selection criteria.

### Claim 20 (depends on 15)

The method of claim 15, wherein said submitting the new job for execution comprises, in response to a determination that the submission processor is the selected processor, executing each iteration of a loop that comprises one or more iterations, wherein for each iteration said executing comprises:
determining a new candidate processors of the plurality of processors for the selected processor;
attempting to submit the new job for execution to the candidate processor; and
receiving a return code from the candidate processor in response to said attempting to submit the new job for execution to the candidate processor;
exiting the loop if an exit condition is fulfilled, wherein executing a last iteration of the loop comprises determining that the exit condition is fulfilled in the last iteration.
