# US 2024/0176656 A1 · System and Method for Queuing Work within a Virtualized Scheduler Based on In-Unit Accounting of In-Unit Entries

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

- Number: US 2024/0176656 A1
- Document ID: US20240176656A1
- Status: Published application
- Kind: A1
- Application number: 18/434,110
- Filed: 2024-02-06
- Published: 2024-05-30
- Earliest claimed: 2019-08-28
- Assignees: Marvell Asia Pte Ltd
- Applicants: Marvell Asia Pte, Ltd.
- Inventors: Jason D. Zebchuk; Wilson P. Snyder, II
- Web page: https://patentgrep.com/patent/US20240176656A1

## CPC

- G06F 9/4881: {Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues}
- G06F 9/50: Allocation of resources, e.g. of the central processing unit [CPU]
- 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 system and corresponding method queue work within a virtualized scheduler based on in-unit accounting (IUA) of in-unit entries (IUEs). The system comprises an IUA resource and arbiter. The IUA resource stores, in association with an IUA identifier, an IUA count and threshold. The IUA count represents a global count of work-queue entries (WQEs) that are associated with the IUA identifier and occupy respective IUEs of an IUE resource. The IUA threshold limits the global count. The arbiter retrieves the IUA count and threshold from the IUA resource based on the IUA identifier and controls, as a function of the IUA count and threshold, whether a given WQE from a given scheduling group, assigned to the IUA identifier, is moved into the IUE resource to be queued for scheduling. The IUA count and threshold prevent group(s) assigned to the IUA identifier from using more than an allocated amount of IUEs.

## Claims

### Claim 1

A system comprising:
an arbiter coupled to an in-unit accounting (IUA) resource and an in-unit entry (IUE) resource, the arbiter configured to move a work queue entry (WQE) from a per-group transitory admission queue (TAQ) into a per-group in-unit admission queue (IAQ) in the IUE resource to be queued for scheduling by a work scheduler, the per-group TAQ and per-group IAQ assigned to a scheduling group,
the arbiter further configured to retrieve an IUA count and an IUA threshold from the IUA resource, based on an IUA identifier, and to control, as a function of the IUA count and IUA threshold retrieved, whether the WQE from the scheduling group, assigned to the IUA identifier, is moved into the IUE resource to be queued for scheduling by the work scheduler.

### Claim 2 (depends on 1)

The system of claim 1, wherein a plurality of scheduling groups is assigned to the IUA identifier and wherein the plurality of scheduling groups includes the scheduling group.

### Claim 3 (depends on 1)

The system of claim 1, wherein the work scheduler is configured to access the IUE resource.

### Claim 4 (depends on 1)

The system of claim 1, wherein:
the IUE resource includes a plurality of in-unit entries (IUEs); and
in an event the arbiter determines that the WQE is to be moved into the IUE resource, the arbiter is further configured to:
allocate a free IUE of the plurality of IUEs to be used as an IUE for moving the WQE into the IUE resource;
move the WQE from the per-group TAQ to the IUE;
add the IUE to the per-group IAQ for the scheduling group or associate the IUE with the scheduling group to create the per-group IAQ for the scheduling group; and
cause the IUA count in the IUA resource to be updated.

### Claim 5 (depends on 4)

The system of claim 4, wherein, to cause the IUA count to be updated, the arbiter is further configured to cause the IUA count to be incremented.

### Claim 6 (depends on 4)

The system of claim 4, wherein:
moving the WQE to occupy the IUE enables the WQE to be available for scheduling by the work scheduler; and
in an event the work scheduler determines that the WQE is to be scheduled, the work scheduler is configured to assign the WQE to a workslot of a plurality of workslots.

### Claim 7 (depends on 6)

The system of claim 6, wherein:
in an event the WQE is assigned to the workslot and work associated with the WQE is completed, the work scheduler is further configured to free the IUE for reuse and either the work scheduler or the arbiter is further configured to cause the IUA count in the IUA resource to be decremented.

### Claim 8 (depends on 1)

The system of claim 1, wherein the IUA threshold is a maximum value for the IUA count and represents a maximum number of IUEs in the IUE resource that are permitted to be occupied by respective WQEs from among all scheduling groups assigned to the IUA identifier.

### Claim 9 (depends on 1)

The system of claim 1, wherein the IUA count represents a global count of work-queue entries (WQEs), wherein the IUA threshold is set to limit the global count, wherein the IUE resource includes a plurality of IUEs, and wherein the global count of WQEs is a total number of all admitted, conflicted, scheduled, and descheduled WQEs that are associated with the IUA identifier and occupy respective IUEs of the plurality of IUEs.

### Claim 10 (depends on 1)

The system of claim 1, wherein, to control whether the WQE is moved, the arbiter is further configured to implement an IUA test and, based on a positive result for the IUA test implemented, to move the WQE from the per-group TAQ, assigned to the scheduling group, and into the IUE resource, wherein the positive result is based on determining that the IUA count is less than the IUA threshold.

### Claim 11 (depends on 10)

The system of claim 10, wherein the positive result is further based on determining that a free count is greater than zero and wherein the free count is a total number of unoccupied IUEs of a plurality of available IUEs of a plurality of IUEs of the IUE resource, the plurality of available IUEs available to the arbiter for moving WQEs into the IUE resource for queueing.

### Claim 12 (depends on 11)

The system of claim 11, wherein at least one IUE, of the plurality of IUEs, is reserved and wherein the plurality of available IUEs excludes the at least one IUE reserved.

### Claim 13 (depends on 11)

The system of claim 11, wherein the positive result is further based on determining that a group count is less than or equal to a group reserved threshold and wherein:
the group count is a total number of IUEs, of the plurality of IUEs, that are occupied by respective WQEs that belong to the scheduling group and have never been scheduled by the work scheduler; and
the group reserved threshold is a number of reserved IUEs, of the plurality of IUEs, that are reserved for the scheduling group for occupancy by WQEs that belong to the scheduling group and have never been scheduled by the work scheduler.

### Claim 14 (depends on 13)

The system of claim 13, wherein:
a first portion of IUEs, of the plurality of IUEs, is arranged to form the per-group IAQ in the IUE resource for the scheduling group, the per-group IAQ created by the arbiter by allocating free IUEs of the plurality of IUEs and moving WQEs belonging to the scheduling group into the free IUEs allocated;
a second portion of IUEs, of the plurality of IUEs, is arranged to form a per-group conflict queue in the IUE resource for the scheduling group, the second portion of IUEs occupied by respective WQEs that were moved by the work scheduler, from the per-group IAQ to the per-group conflict queue, in response to respective attempts to schedule the respective WQEs, the respective attempts having failed due to respective scheduling conflicts; and
WQEs occupying respective IUEs of the per-group IAQ and the per-group conflict queue representing the respective WQEs that belong to the scheduling group and have never been scheduled by the work scheduler.

### Claim 15 (depends on 14)

The system of claim 14, wherein the arbiter is further configured to increment the group count in an event the WQE is moved into the IUE resource and wherein, in an event the WQE is scheduled by the work scheduler and work associated with the WQE is completed, either the arbiter or the work scheduler is configured to decrement the group count.

### Claim 16 (depends on 13)

The system of claim 13, wherein the positive result is further based on determining that a) the free count is greater than a reserved free count, wherein the reserved free count is counted as part of the free count, and b) a group count is less than a group maximum threshold.

### Claim 17 (depends on 16)

The system of claim 16, wherein:
the reserved free count is a total number of unoccupied reserved IUEs from among reserved IUEs, of the plurality of IUEs, that are reserved for moving WQEs of respective scheduling groups into the IUE resource;
the group count is a total number of IUEs, of the plurality of IUEs, that are occupied by respective WQEs that belong to the scheduling group and have never been scheduled by the work scheduler; and
the group maximum threshold is a maximum number of IUEs, of the plurality of IUEs, that are permitted to be occupied by WQEs that are from the scheduling group and that have never been scheduled by the work scheduler.

### Claim 18 (depends on 17)

The system of claim 17, wherein:
the IUE resource includes the per-group IAQ for the scheduling group and a per-group conflict queue for the scheduling group; and
the WQEs that are from the scheduling group and that have never been scheduled occupy respective IUEs of: the per-group IAQ, per-group conflict queue, or a combination thereof.

### Claim 19 (depends on 16)

The system of claim 16, wherein the positive result is further based on determining that a group count is less than or equal to a group reserved threshold or that a) the free count is greater than a reserved free count, wherein the reserved free count is counted as part of the free count, and b) a group count is less than a group maximum threshold.

### Claim 20 (depends on 1)

The system of claim 1, wherein, in an event the IUA count is greater than or equal to the IUA threshold, the arbiter is further configured to disregard the WQE from consideration for movement into the IUE resource.

### Claim 21 (depends on 1)

The system of claim 1, wherein the IUA resource includes a lookup table configured to store a plurality of respective IUA count and IUA threshold pairings each associated with a respective IUA identifier.

### Claim 22 (depends on 1)

The system of claim 1, wherein the WQE includes:
an identifying pointer;
a tag value, the tag value associating the WQE with a unique work-flow;
a tag-type, the tag-type specifying whether the unique work-flow is ordered, atomic, or un-ordered; and
a group identifier, the group identifier corresponding to the scheduling group.

### Claim 23

A method comprising:
moving, by an arbiter, a work-queue entry (WQE) from a per-group transitory admission queue (TAQ) into a per-group in-unit admission queue (IAQ) in an in-unit entry (IUE) resource to be queued for scheduling by a work scheduler, the per-group TAQ and per-group IAQ assigned to the scheduling group, the moving including:
retrieving, by the arbiter, an in-unit accounting (IUA) count and IUA threshold from an IUA resource based on an IUA identifier, the arbiter coupled to the IUA resource and IUE resource; and
controlling, by the arbiter as a function of the IUA count and IUA threshold retrieved from the IUA resource based on the IUA identifier, whether the WQE from the scheduling group, assigned to the IUA identifier, is moved into the IUE resource to be queued for scheduling by the work scheduler.

### Claim 24 (depends on 23)

The method of claim 23, further comprising assigning a plurality of scheduling groups to the IUA identifier, the plurality of scheduling groups including the scheduling group.

### Claim 25 (depends on 23)

The method of claim 23, wherein the controlling includes determining whether the WQE is to be moved and, in an event it is determined that the WQE is to be moved, the method further comprises:
allocating a free IUE of a plurality of in-unit entries (IUEs) of the IUE resource, the free IUE to be used as an IUE for admitting the WQE into the IUE resource;
moving the WQE from the per-group TAQ to the IUE;
adding the IUE to the per-group IAQ for the scheduling group or associating the IUE with the scheduling group to create the per-group IAQ for the scheduling group; and
updating the IUA count in the IUA resource based on the IUA identifier, wherein the per-group TAQ includes queued work-queue entries (WQEs) received for the scheduling group.

### Claim 26 (depends on 25)

The method of claim 25, wherein updating the IUA count includes incrementing the IUA count.

### Claim 27 (depends on 25)

The method of claim 25, wherein moving the WQE to occupy the IUE enables the WQE to be available for scheduling and wherein, in an event the WQE is scheduled, the method further comprises:
assigning the WQE to a workslot of a plurality of workslots.

### Claim 28 (depends on 27)

The method of claim 27, wherein the method further comprises:
in response to a notification that work associated with the WQE has been completed, freeing the IUE for reuse; and
causing the IUA count in the IUA resource to be decremented.

### Claim 29 (depends on 25)

The method of claim 25, wherein the IUA threshold is a maximum value for the IUA count and represents a maximum number of IUEs in the IUE resource that are permitted to be occupied by respective WQEs from among all scheduling groups assigned to the IUA identifier.

### Claim 30 (depends on 25)

The method of claim 25, wherein the IUA count represents a global count of work-queue entries (WQEs), wherein the IUA threshold is set to limit the global count, and wherein the method further comprises:
retrieving the global count from the IUA resource based on the IUA identifier, wherein the global count is a total number of all admitted, conflicted, scheduled, and descheduled WQEs that are associated with the IUA identifier and occupy respective IUEs of the plurality of IUEs.

### Claim 31 (depends on 25)

The method of claim 25, wherein the controlling includes:
implementing an IUA test, the implementing including comparing the IUA count to the IUA threshold; and
based on a positive result for the IUA test implemented, moving the WQE from the per-group TAQ, assigned to the scheduling group, and into the IUE resource, wherein the positive result is based on determining that the IUA count is less than the IUA threshold as a function of the comparing.

### Claim 32 (depends on 31)

The method of claim 31, wherein the positive result is further based on determining that a free count is greater than zero and wherein the free count is a total number of unoccupied IUEs of a plurality of available IUEs of the plurality of IUEs, the plurality of available IUEs available to an arbiter for moving WQEs into the IUE resource for queueing.

### Claim 33 (depends on 32)

The method of claim 32, further comprising reserving at least one IUE, of the plurality of IUEs, and wherein the plurality of available IUEs excludes the at least one IUE reserved.

### Claim 34 (depends on 31)

The method of claim 31, wherein the positive result is further based on determining that a group count is less than or equal to a group reserved threshold and wherein:
the group count is a total number of IUEs, of the plurality of IUEs, that are occupied by respective WQEs that belong to the scheduling group and have never been scheduled by the work scheduler; and
the group reserved threshold is a number of reserved IUEs, of the plurality of IUEs, that are reserved for the scheduling group for occupancy by WQEs that belong to the scheduling group and have never been scheduled by the work scheduler.

### Claim 35 (depends on 34)

The method of claim 34, wherein:
a first portion of IUEs, of the plurality of IUEs, is arranged to form the per-group IAQ in the IUE resource for the scheduling group, the per-group IAQ created by an arbiter by allocating free IUEs of the plurality of IUEs and moving WQEs belonging to the scheduling group into the free IUEs allocated;
a second portion of IUEs, of the plurality of IUEs, is arranged to form a per-group conflict queue in the IUE resource for the scheduling group, the second portion of IUEs occupied by respective WQEs that were moved by the work scheduler, from the per-group IAQ to the per-group conflict queue, in response to respective attempts to schedule the respective WQEs, the respective attempts having failed due to respective scheduling conflicts; and
WQEs occupying respective IUEs of the per-group IAQ and per-group conflict queue representing the respective WQEs that belong to the scheduling group and have never been scheduled by the work scheduler.

### Claim 36 (depends on 35)

The method of claim 35, further comprising:
incrementing the group count in an event the WQE is moved into the IUE resource; and
decrementing the group count in an event the WQE is scheduled by the work scheduler and work associated with the WQE is completed.

### Claim 37 (depends on 32)

The method of claim 32, wherein the positive result is further based on determining that a) the free count is greater than a reserved free count, wherein the reserved free count is counted as part of the free count, and b) a group count is less than a group maximum threshold.

### Claim 38 (depends on 37)

The method of claim 37, wherein:
the reserved free count is a total number of unoccupied reserved IUEs from among reserved IUEs, of the plurality of IUEs, that are reserved for moving WQEs of respective scheduling groups into the IUE resource;
the group count is a total number of IUEs, of the plurality of IUEs, that are occupied by respective WQEs that belong to the scheduling group and have never been scheduled by the work scheduler; and
the group maximum threshold is a maximum number of IUEs, of the plurality of IUEs, that are permitted to be occupied by WQEs that are from the scheduling group and that have never been scheduled by the work scheduler.

### Claim 39 (depends on 38)

The method of claim 38, wherein the IUE resource includes the per-group IAQ for the scheduling group and a per-group conflict queue for the scheduling group and wherein the WQEs that are from the scheduling group and that have never been scheduled occupy respective IUEs of: the per-group IAQ, per-group conflict queue, or a combination thereof.

### Claim 40 (depends on 39)

The method of claim 39, wherein the positive result is further based on determining that a group count is less than or equal to a group reserved threshold or that a) the free count is greater than a reserved free count, wherein the reserved free count is counted as part of the free count, and b) the group count is less than a group maximum threshold.

### Claim 41 (depends on 23)

The method of claim 23, wherein, in an event the IUA count is greater than or equal to the IUA threshold, the method further comprises disregarding the WQE from consideration for movement into the IUE resource.

### Claim 42 (depends on 23)

The method of claim 23, wherein the IUA resource includes at least one lookup table and wherein the retrieving includes:
retrieving from a lookup table of the at least one lookup table, the lookup table storing a plurality of respective IUA count and IUA threshold pairings each associated with a respective IUA identifier.

### Claim 43 (depends on 23)

The method of claim 23, wherein the WQE includes:
an identifying pointer;
a tag value, the tag value associating the WQE with a unique work-flow;
a tag-type, the tag-type specifying whether the unique work-flow is ordered, atomic, or un-ordered; and
a group identifier, the group identifier corresponding to the scheduling group.

### Claim 44

A system comprising:
means for moving a work-queue entry (WQE) from a per-group transitory admission queue (TAQ) into a per-group in-unit admission queue (IAQ) in an in-unit entry (IUE) resource to be queued for scheduling by a work scheduler, the per-group TAQ and per-group IAQ assigned to the scheduling group;
means for retrieving an in-unit accounting (IUA) count and IUA threshold from an IUA resource based on an IUA identifier; and
means for controlling, as a function of the IUA count and IUA threshold retrieved from the IUA resource based on the IUA identifier, whether the WQE from the scheduling group, assigned to the IUA identifier, is moved into the IUE resource to be queued for scheduling by the work scheduler.
