# US 2018/0321983 A1 · Method and apparatus for job pre-scheduling by distributed job manager in a digital multi-processor system

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

- Number: US 2018/0321983 A1
- Document ID: US20180321983A1
- Status: Published application
- Kind: A1
- Application number: 15/588,240
- Filed: 2017-05-05
- Published: 2018-11-08
- Earliest claimed: 2017-05-05
- Assignees: Cavium, Inc.
- Applicants: Cavium, Inc.
- Inventors: Kalyana Sundaram Venkataraman; Tejas Maheshbhai Bhatt; Hong Jik Kim; Eric Marenger; Ahmed Shahid; Jason Daniel Zebchuk; Gregg Alan Bouchard
- Web page: https://patentgrep.com/patent/US20180321983A1

## CPC

- G06F 9/5044: {considering hardware capabilities}
- G06F 9/4881: {Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues}
- G06F 9/5027: {the resource being a machine, e.g. CPUs, Servers, Terminals}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A method and a system embodying the method for job pre-scheduling in a processing system comprising distributed job management, encompassing: determining a maximum amount of pre-schedulable jobs for each of a plurality of engines; setting for each of the plurality of engines a threshold less than or equal to the maximum amount; pre-scheduling by a scheduler an amount of jobs less than or equal to the threshold to at least one of a plurality of job managers; determining at the at least one of the plurality of job managers managing one of the plurality of engines one of a plurality of data processing devices in order for each pre-scheduled job; and assigning the job to the determined data processing device.

## Claims

### Claim 1

An apparatus for job pre-scheduling in a processing system comprising distributed job management, comprising:
a host configured to set a threshold less than or equal to maximum amount determined for each of a plurality of engines; and
a scheduler, communicatively coupled to the host, configured to pre-schedule an amount of jobs less than or equal to the threshold to at least one of a plurality of job managers communicatively coupled to the scheduler; wherein
the at least one of the plurality of job managers managing one of the plurality of engines is configured to:
determine one of a plurality of data processing devices in order for each pre-scheduled job; and
assign the pre-scheduled job to the determined data processing device.

### Claim 2 (depends on 1)

The apparatus as claimed in claim 1, wherein the host sets a threshold less than or equal to the maximum amount for each of the plurality of engines by being configured to:
determine the threshold in accordance with parameters comprising characteristics of a processing algorithm and characteristics of the processing system.

### Claim 3 (depends on 1)

The apparatus as claimed in claim 1, further comprising:
a comparator configured to compare the threshold to the maximum amount; and
the scheduler or the job manager further configured to set the threshold to the maximum amount if the threshold is greater than the maximum amount.

### Claim 4 (depends on 1)

The apparatus as claimed in claim 1, wherein the host is further configured to:
program the maximum amount and the threshold into the scheduler; and
wherein the scheduler pre-schedules the amount of jobs less than or equal to the threshold to the at least one of a plurality of job managers by being configured to pre-schedule the jobs upon the jobs becoming available for scheduling.

### Claim 5 (depends on 1)

The apparatus as claimed in claim 1, wherein the host is further configured to:
program the maximum amount and the threshold into the job manager; and wherein:
the at least one of the plurality of job manager is configured to request an amount of jobs less than or equal to the threshold; and
the scheduler pre-schedules the amount of jobs less than or equal to the threshold to at least one of a plurality of job managers in response to the request.

### Claim 6 (depends on 1)

The apparatus as claimed in claim 1, wherein the host is further configured to:
program the maximum amount into the job manager;
program the threshold into the scheduler; and wherein:
the at least one of the plurality of job manager requests an amount of jobs equal to the maximum value; and
the scheduler pre-schedules the amount of jobs less than or equal to the threshold in response to the request.

### Claim 7 (depends on 1)

The apparatus as claimed in claim 1, wherein the host is further configured to:
program the maximum amount into the job manager;
program the threshold into the scheduler; and
wherein the scheduler requests an amount of jobs to be pre-scheduled from the job manager, and pre-schedules the amount of jobs less than or equal to the threshold in response to a request for the maximum amount from the job manager.

### Claim 8 (depends on 1)

The apparatus as claimed in claim 1, wherein the at least one of the plurality of job managers determines one of the plurality of data processing devices at a managed one of the plurality of engines in order for each pre-scheduled job by being configured to:
determine a number of free job slots for each of the plurality of data processing devices;
assign the pre-scheduled job to a job slot identified by a job_slot_id of the data processing device with the highest number of free job slots; and
recalculate the value of job_slot_id of the data processing device that was assigned the job.

### Claim 9 (depends on 8)

The apparatus as claimed in claim 8, wherein the at least one of the plurality of job managers assigns the job to a job slot identified by a job_slot_id of the data processing device with the highest number of free job slots, by being configured to:
assign the pre-scheduled job to the job slot identified by a job_slot_id of the data processing device with the highest number of free job slots when a single data processing device has the highest number of free job slots;
determine one of a multiple data processing device in accordance with a pre-determined policy when multiple data processing devices have the highest number of free job slots; and
assign the pre-scheduled job to a job slot identified by a job_slot_id of the determined data processing device.

### Claim 10 (depends on 8)

The apparatus as claimed in claim 8, wherein the at least one of the plurality of job managers recalculates the value of job_slot_id of the data processing device that was assigned the job, by being configured to:
apply the equations
next job_slot_id=mod(job_slot_id+1;q) (Eq. 1)
job_slot_id=next job_slot_id (Eq. 2)
wherein mod is a modulo operation; and
q is a number of job slots for the engine.

### Claim 11 (depends on 8)

The apparatus as claimed in claim 8, wherein the at least one of the plurality of job managers is further configured to:
initialize for each of the plurality of data processing devices a job_slot_id to a predetermined value.

### Claim 12

A method for job pre-scheduling in a processing system comprising distributed job management, comprising:
determining a maximum amount of pre-schedulable jobs for each of a plurality of engines;
setting, for each of the plurality of engines, a threshold less than or equal to the maximum amount;
pre-scheduling by a scheduler an amount of jobs less than or equal to the threshold to at least one of a plurality of job managers;
determining, by the at least one of the plurality of job managers managing one of the plurality of engines, one of a plurality of data processing devices in order for each pre-scheduled job; and
assigning the pre-scheduled job to the determined data processing device.

### Claim 13 (depends on 12)

The method as claimed in claim 12, wherein the setting, for each of the plurality of engines, a threshold less than or equal to the maximum amount comprises:
determining by a host the threshold in accordance with parameters comprising characteristics of a processing algorithm and characteristics of the processing system.

### Claim 14 (depends on 12)

The method as claimed in claim 12, further comprising:
comparing the threshold to the maximum amount; and
setting the threshold to the maximum amount if the threshold is greater than the maximum amount.

### Claim 15 (depends on 12)

The method as claimed in claim 12, further comprising:
programming the maximum amount and the threshold into the scheduler; and
wherein the pre-scheduling by a scheduler an amount of jobs less than or equal to the threshold to at least one of a plurality of job managers comprises pre-scheduling the jobs upon the jobs becoming available for scheduling.

### Claim 16 (depends on 12)

The method as claimed in claim 12, further comprising:
programming the maximum amount and the threshold into the job manager; and
wherein the pre-scheduling by a scheduler an amount of jobs less than or equal to the threshold to at least one of a plurality of job managers comprises:
requesting by the at least one of the plurality of job manager an amount of jobs less than or equal to the threshold; and
pre-scheduling by the scheduler the amount of jobs less than or equal to the threshold in response to the request.

### Claim 17 (depends on 12)

The method as claimed in claim 12, further comprising:
programming the maximum amount into the job manager;
programming the threshold into the scheduler; and
wherein the pre-scheduling by a scheduler an amount of jobs less than or equal to the threshold to at least one of a plurality of job managers comprises:
requesting by the at least one of the plurality of job manager an amount of jobs equal to the maximum value; and
pre-scheduling by the scheduler the amount of jobs less than or equal to the threshold in response to the request.

### Claim 18 (depends on 12)

The method as claimed in claim 12, further comprising:
programming the maximum amount into the job manager;
programming the threshold into the scheduler; and
wherein the pre-scheduling by a scheduler an amount of jobs less than or equal to the threshold to at least one of a plurality of job managers comprises:
requesting by the scheduler an amount of jobs to be pre-scheduled from the job manager; and
pre-scheduling by the scheduler the amount of jobs less than or equal to the threshold in response to a request for the maximum amount from the job manager.

### Claim 19 (depends on 12)

The method as claimed in claim 12, wherein the determining, by the at least one of the plurality of job managers managing one of the plurality of engines, one of a plurality of data processing devices in order for each pre-scheduled job comprises:
determining a number of free job slots for each of the plurality of data processing devices;
assigning the pre-scheduled job to a job slot identified by a job_slot_id of the data processing device with the highest number of free job slots; and
recalculating the value of job_slot_id of the data processing device that was assigned the job.

### Claim 20 (depends on 19)

The method as claimed in claim 19, wherein the assigning the job to a job slot identified by a job_slot_id of the data processing device with the highest number of free job slots, comprises:
assigning the pre-scheduled job to the job slot identified by a job_slot_id of the data processing device with the highest number of free job slots when a single data processing device has the highest number of free job slots;
determining one of a multiple data processing device in accordance with a pre-determined policy when multiple data processing devices have the highest number of free job slots; and
assigning the pre-scheduled job to a job slot identified by a job_slot_id of the determined data processing device.

### Claim 21 (depends on 19)

The method as claimed in claim 19, wherein the recalculating the value of job_slot_id of the data processing device that was assigned the job, comprises:
applying the equations
next job_slot_id=mod(job_slot_id+1;q) (Eq. 1)
job_slot_id=next job_slot_id (Eq. 2)
wherein mod is a modulo operation; and
q is a number of job slots for the engine.

### Claim 22 (depends on 19)

The method as claimed in claim 19, further comprising:
initializing for each of the plurality of data processing devices a job_slot_id to a predetermined value.
