# US 2017/0286157 A1 · Work Conserving, Load Balancing, and Scheduling

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

- Number: US 2017/0286157 A1
- Document ID: US20170286157A1
- Status: Published application
- Kind: A1
- Application number: 15/089,522
- Filed: 2016-04-02
- Published: 2017-10-05
- Earliest claimed: 2016-04-02
- Assignees: Intel Corporation
- Applicants: Intel Corporation
- Inventors: Joseph R. Hasting; William G. Burroughs
- Web page: https://patentgrep.com/patent/US20170286157A1

## CPC

- G06F 9/4843: {by program, e.g. task dispatcher, supervisor, operating system}
- 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 9/505: {considering the load}
- G06F 2209/5021: Priority
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A system and method are described for work conserving, load balancing, and scheduling by a network processor. For example, one embodiment of a system includes a plurality of processing cores, including a scheduling circuit, at least one source processing core that generates at least one task and at least one destination processing core that receives and processes the at least one task, and generates a response. The scheduling circuit of the exemplary system receives the at least one task and conducts a load balancing to select the at least one destination processing core. In an embodiment, the scheduling circuit further detects a critical sequences of tasks, schedules those tasks to be processed by a single destination processing core, and, upon completion of the critical sequence, conducts another load balancing to potentially select a different processing core to process more tasks.

## Claims

### Claim 1

A system comprising:
a plurality of processing cores, including at least one source processing core to generate at least one task and at least one destination processing core to receive and process the at least one task, and to generate a response; and
a scheduling circuit comprising:
a task linked list to store received tasks;
a ready linked list to store tasks ready to be assigned to destination processing cores; and
a scheduled linked list to store tasks that have been assigned to destination processing cores;
wherein the scheduling circuit to: receive the at least one task, associate it with a flow identifier, store it in the task linked list to be processed, store it in the ready linked list to be scheduled, select the at least one destination processing core to process it, store it in the scheduled linked list to be transmitted, and transmit it to the at least one destination processing core; and
wherein the at least one destination processing core is selected because of its relatively low load compared to other processing cores among the plurality of processing cores.

### Claim 2 (depends on 1)

The system of claim 1, wherein the scheduling circuit further to identify a critical sequence of tasks associated with the flow identifier, and to schedule the tasks of the critical sequence to be processed atomically by a single destination processing core among the plurality of processing cores.

### Claim 3 (depends on 1)

The system of claim 1, wherein the selecting the at least one destination processing core comprises a work conserving load balancing.

### Claim 4 (depends on 1)

The system of claim 1, wherein the at least one task is associated with the flow identifier because its header shares a commonality with other tasks associated with the flow identifier.

### Claim 5 (depends on 2)

The system of claim 2, wherein the scheduling circuit further to, upon completion of the critical sequence, if more tasks are associated with the flow identifier, repeat the load balancing to select a potentially different destination processing core that has a relatively low load compared to other processing cores among the plurality of processing cores.

### Claim 6 (depends on 1)

The system of claim 1, wherein the scheduling circuit further to assign multiple flows of tasks associated with multiple flow identifiers to a single destination processing core among the plurality of processing cores, and to cycle through the multiple flows, scheduling at least zero tasks from each flow on each cycle.

### Claim 7 (depends on 1)

The system of claim 1, wherein the scheduling circuit further to assign multiple flows of tasks associated with multiple flow identifiers to a single destination processing core among the plurality of processing cores, and to cycle through the multiple flows, scheduling multiple tasks associated with a first flow before scheduling tasks from a second flow.

### Claim 8 (depends on 2)

The system of claim 2, the scheduling circuit further comprising a sequential state machine circuit comprising hardware registers to maintain states associated with each of the flow identifiers, the states comprising IDLE, READY, SCHEDULED, and EMPTY,
wherein processing of the flow identifier associated with the critical sequence to start in the IDLE state to await receipt of tasks, to transition to the READY state to await selection of the at least one destination processing core, to transition to the SCHEDULED state to await transmission to the at least one destination processing core, and to remain in the SCHEDULED state until completion of scheduling of the critical sequence, and
wherein, after completion of scheduling of the critical sequence, if additional tasks are associated with the flow identifier, the flow identifier to return to the READY state to be re-load balanced and potentially to select a different destination processing core.

### Claim 9

A method to be performed by a plurality of processing cores and a scheduling circuit, the method comprising:
generating at least one task by at least one source processing core among the plurality of processing cores; and
receiving the at least one task by the scheduling circuit, associating it with a flow identifier, storing it in a task linked list to be processed, storing it in a ready linked list to be scheduled, selecting at least one destination processing core to process it, storing it in the scheduled linked list to be transmitted, and transmitting it to the at least one destination processing core;
wherein the at least one destination processing core is selected because of its relatively low load compared to other processing cores among the plurality of processing cores.

### Claim 10 (depends on 9)

The method of claim 9 further comprising storing the at least one task in a memory, the plurality of processing cores and the scheduling circuit to access the memory.

### Claim 11 (depends on 9)

The method of claim 9, wherein selecting the at least one destination processing core comprises a work conserving load balancing.

### Claim 12 (depends on 9)

The method of claim 9, wherein the at least one task is associated with the flow identifier because its header shares a commonality with other tasks associated with the flow identifier.

### Claim 13 (depends on 9)

The method of claim 9, further comprising the scheduling circuit using a sequential state machine circuit associated with the flow identifier, the sequential state machine comprising hardware registers to maintain states, and being used to control scheduling of tasks associated with the flow identifier, wherein scheduling the flow identifier to start in an IDLE state to await tasks, to transition to a READY state to await scheduling, to be load balanced and assigned to the at least one destination processing core, to transition to a SCHEDULED state to await transmission, to be transmitted to the at least one destination processing core, after no additional tasks remain to be scheduled, to transition to an EMPTY state to await completion of scheduled tasks, and then to transition back to the IDLE state.

### Claim 14 (depends on 13)

The method of claim 13, further comprising the scheduling circuit identifying a critical sequence of tasks associated with the flow identifier.

### Claim 15 (depends on 14)

The method of claim 14,
further comprising using the finite state machine during processing of the critical sequence, wherein the finite state machine to start in the IDLE state, to transition to the READY state, to be load balanced and scheduled for processing by the at least one destination processing core, to transition to the SCHEDULED state, and to complete scheduling of the critical sequence, wherein the scheduling circuit selects a single destination processing core among the plurality of processing cores to process tasks of the critical sequence atomically.

### Claim 16 (depends on 15)

The method of claim 15, further comprising, if more tasks are associated with the flow identifier after completion of the critical sequence, moving the flow identifier from the SCHEDULED state to the READY state to effect a renewed load balancing.

### Claim 17

A non-transitory computer readable medium containing instructions that when executed, cause a plurality of processing cores and a scheduling circuit to perform a process comprising:
generating at least one task by at least one source processing core among the plurality of processing cores; and
receiving the at least one task by the scheduling circuit, associating it with a flow identifier, storing it in a task linked list to be processed, storing it in a ready linked list to be scheduled, selecting at least one destination processing core to process it, storing it in the scheduled linked list to be transmitted, and transmitting it to the at least one destination processing core;
wherein the at least one destination processing core is selected because of its relatively low load compared to other processing cores among the plurality of processing cores.

### Claim 18 (depends on 17)

The non-transitory computer readable medium of claim 17, the process further comprising:
the scheduling circuit using a finite state machine circuit associated with the flow identifier to control scheduling of tasks associated with the flow identifier, wherein scheduling the flow identifier is to start in an IDLE state, to transition to a READY state, to be load balanced and assigned to the at least one destination processing core, to transition to a SCHEDULED state, to be transmitted to the at least one destination processing core, after no additional tasks remain to be scheduled, to transition to an EMPTY state await completion of the scheduled tasks, and then to transition back to the IDLE state.

### Claim 19 (depends on 18)

The non-transitory computer readable medium of claim 18, the process further comprising the scheduling circuit identifying a critical sequence of tasks associated with the flow identifier.

### Claim 20 (depends on 19)

The non-transitory computer readable medium of claim 19, the process further comprising
using the finite state machine during processing of the critical sequence, wherein the finite state machine to start in the IDLE state, to transition to the READY state, to be load balanced and assigned to the at least one destination processing core, to transition to the SCHEDULED state, to complete scheduling of the critical sequence, wherein the scheduling circuit selects a single destination processing core among the plurality of processing cores to process tasks of the critical sequence atomically; and
if more tasks are associated with the flow identifier after completion of the critical sequence, moving the flow identifier from the scheduled state to the ready state to effect a renewed load balancing.
