# US 12,008,397 B2 · Common priority information for multiple resource arbitration

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

- Number: US 12,008,397 B2
- Document ID: US12008397B2
- Status: Granted
- Kind: B2
- Application number: 16/362,960
- Filed: 2019-03-25
- Published: 2019-09-26
- Granted: 2024-06-11
- Earliest claimed: 2018-03-23
- Assignees: Imagination Technologies Limited
- Applicants: Imagination Technologies Limited
- Inventors: Jonas Olof Gunnar Källén
- Web page: https://patentgrep.com/patent/US12008397B2

## CPC

- G06F 9/4881: {Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues}
- G06F 9/48: Program initiating; Program switching, e.g. by interrupt
- G06F 9/4806: {Task transfer initiation or dispatching}
- G06F 9/4818: {Priority circuits therefor}
- G06F 9/4831: {with variable priority}
- G06F 9/50: Allocation of resources, e.g. of the central processing unit [CPU]
- G06F 9/5005: {to service a request}
- G06F 9/5027: {the resource being a machine, e.g. CPUs, Servers, Terminals}
- 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 13/16: for access to memory bus (G06F13/28 takes precedence)
- G06F 13/1605: {based on arbitration (arbitration in handling access to a common bus or bus system G06F13/36)}
- G06F 13/18: based on priority control (G06F13/1605 takes precedence)
- G06F 13/20: for access to input/output bus
- G06F 13/28: using burst mode transfer, e.g. direct memory access {DMA}, cycle steal (G06F13/32 takes precedence)
- G06F 13/364: using independent requests or grants, e.g. using separated request and grant lines
- G06F 16/9027: {Trees}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Methods and systems for generating common priority information for a plurality of requestors in a computing system that share a plurality of computing resources for use in a next cycle to arbitrate between the plurality of requestors, include generating, for each resource, priority information for the next cycle based on an arbitration scheme; generating, for each resource, relevant priority information for the next cycle based on the priority information for the next cycle for that resource, the relevant priority information for a resource being the priority information that relates to requestors that requested access to the resource in the current cycle and were not granted access to the resource in the current cycle; and combining the relevant priority information for the next cycle for each resource to generate the common priority information for the next cycle.

## Claims

### Claim 1

A method of arbitrating between a plurality of requestors in a computing system that share a plurality of computing resources, the method comprising:
generating, at priority selection hardware, for each resource, priority information for a next cycle based on an arbitration scheme, the priority information indicating which of the plurality of requestors has priority in the next cycle;
generating, at the priority selection hardware, for each resource, relevant priority information for the next cycle by extracting from the priority information for the next cycle for that resource information that relates to requestors that requested access to the resource in a current cycle and were not granted access to the resource in the current cycle;
combining, at the priority selection hardware, the relevant priority information for the next cycle for each resource to generate common priority information for the next cycle;
storing the common priority information for the next cycle in a storage unit;
selecting, at an arbiter for each resource, an active requestor for the corresponding resource in the next cycle to be granted access to that resource based on the common priority information stored in the storage unit, wherein an active requestor for a resource in the next cycle is a requestor that requested access to that resource in the next cycle; and
notifying each resource of the selected requestor for that resource for the next cycle.

### Claim 2 (depends on 1)

The method of claim 1, wherein generating the relevant priority information for the next cycle for a resource comprises modifying the priority information for the next cycle for that resource to indicate that any requestor that did not request access to the resource in the current cycle does not have priority.

### Claim 3 (depends on 2)

The method of claim 2, wherein the priority information for the next cycle for a resource comprises a bit for each requestor that indicates whether that requestor has priority for that resource in the next cycle, and modifying the priority information for the next cycle for a resource comprises:
receiving active information for the resource that comprises a bit for each requestor that indicates whether that requestor requested access to the resource in the current cycle; and
performing a bitwise AND operation on the priority information for the next cycle for the resource and the active information for that resource to generate the relevant priority information for the next cycle for the resource.

### Claim 4 (depends on 1)

The method of claim 1, wherein the relevant priority information for the next cycle for each resource comprises a bit for each of the requestors indicating whether that requestor has priority in the next cycle, and combining the relevant priority information for the next cycle for the resources to generate the common priority information comprises performing a bit-wise OR operation on the relevant priority information for the next cycle for all the resources.

### Claim 5 (depends on 1)

The method of claim 1, wherein generating priority information for a first set of requestors of the plurality of requestors for at least one resource in accordance with an arbitration scheme comprises:
receiving information identifying a requestor granted access to the resource in the current cycle;
receiving priority information for the current cycle for the resource that indicates which requestors have priority in the current cycle;
determining from the information identifying the requestor granted access to the resource in the current cycle and the priority information for the current cycle for the resource whether the requestor granted access to the resource in the current cycle has priority in the current cycle;
in response to determining that the requestor granted access to the resource in the current cycle has priority in the current cycle, generating first priority information for the first set of requestors for the next cycle for the resource; and
in response to determining that the requestor granted access to the resource in the current cycle does not have priority in the current cycle, generating second priority information for the first set of requestors for the next cycle for the resource.

### Claim 6 (depends on 5)

The method of claim 5, wherein:
the plurality of requestors are ordered from lowest to highest according to one or more criteria; and
for at least one resource:
the first priority information for the first set of requestors for the next cycle for the resource indicates that all higher ordered requestors in the first set of requestors relative to the requestor granted access to the resource in the current cycle have priority in the next cycle; and
the second priority information for the first set of requestors for the next cycle for the resource indicates that all of the requestors in the first set of requestors, except the requestor that was granted access to the resource in the current cycle, have priority in the next cycle.

### Claim 7 (depends on 5)

The method of claim 5, wherein for at least one resource the first priority information for the first set of requestors for the next cycle for the resource indicates a same set of requestors in the first set of requestors that have priority in the current cycle have priority in the next cycle, except for the requestor granted access to the resource in the current cycle; and
the second priority information for the first set of requestors for the next cycle for the resource indicates all requestors in the first set of requestors have priority in the next cycle except the requestor that was granted access to the resource in the current cycle.

### Claim 8 (depends on 5)

The method of claim 5, wherein for at least one resource the first priority information for the first set of requestors for the next cycle for the resource indicates a same set of requestors in the first set of requestors that have priority in the current cycle have priority in the next cycle, except the requestor granted access to the resource in the current cycle; and
the second priority information for the first set of requestors for the next cycle for the resource indicates those requestors in the first set of requestors that requested access to the resource in the current cycle have priority in the next cycle except the requestor granted access to the resource in the current cycle.

### Claim 9 (depends on 5)

The method of claim 5, wherein the first set of requestors comprises all of the plurality of requestors.

### Claim 10 (depends on 5)

The method of claim 5, wherein:
the plurality of requestors are ordered from lowest to highest according to one or more criteria;
the first set of requestors comprises all of the plurality of requestors except a highest ordered requestor; and
generating priority information for the highest ordered requestor for the next cycle for the resource comprises generating information indicating the highest ordered requestor does not have priority.

### Claim 11 (depends on 1)

A non-transitory computer readable storage medium having encoded thereon computer readable instructions that, when executed at an arbiter system comprising priority selection hardware and a plurality of arbiters, cause the arbiter system to perform the method as set forth in claim 1.

### Claim 12

An arbiter system for arbitrating between a plurality of requestors in a computing system that share a plurality of computing resources, the arbiter system comprising:
priority selection hardware comprising:
priority generation logic for each resource that is configured to generate priority information for a next cycle based on an arbitration scheme, the priority information indicating which of the plurality of requestors has priority in the next cycle,
modification logic for each resource that is configured to generate relevant priority information for the next cycle by extracting from the priority information for the next cycle for that resource information that relates to requestors that requested access to the resource in a current cycle and were not granted access to the resource in the current cycle, and
combination logic configured to combine the relevant priority information for each resource to generate common priority information for the next cycle, and store the common priority information for the next cycle in a storage unit; and
an arbiter for each resource, each arbiter configured to:
select an active requestor for the corresponding resource in the next cycle to be granted access to that resource based on the common priority information stored in the storage unit, wherein an active requestor for a resource in the next cycle is a requestor that requested access to that resource in the next cycle, and
notify the corresponding resource of the selected requestor for that resource for the next cycle.

### Claim 13 (depends on 12)

The arbiter system of claim 12, wherein the modification logic for a resource is configured to generate the relevant priority information for the next cycle for the resource by modifying the priority information for the next cycle for that resource to indicate that any requestor that did not request access to the resource in the current cycle does not have priority.

### Claim 14 (depends on 13)

The arbiter system of claim 13, wherein the priority information for the next cycle for a resource comprises a bit for each requestor that indicates whether that requestor has priority for that resource in the next cycle, and the modification logic is configured to modify the priority information for the next cycle for the resource by:
receiving active information for the resource that comprises a bit for each requestor that indicates whether that requestor requested access to the resource in the current cycle; and
performing a bitwise AND operation on the priority information for the resource and the active information for that resource to generate the relevant priority information for the next cycle for the resource.

### Claim 15 (depends on 12)

The arbiter system of claim 12, wherein the relevant priority information for the next cycle for each resource comprises a bit for each of the requestors indicating whether that requestor has priority in the next cycle, and the combination logic is configured to combine the relevant priority information for the next cycle for the resources to generate the common priority information by performing a bit-wise OR operation on the relevant priority information for the next cycle for all the resources.

### Claim 16 (depends on 12)

The arbiter system of claim 12, wherein the priority generation logic for at least one resource is configured to generate the priority information for a first set of requestors of the plurality of requestors for the next cycle by:
receiving information identifying a requestor granted access to the resource in the current cycle;
receiving priority information for the current cycle for the resource that indicates which requestors have priority in the current cycle;
determining from the information identifying the requestor granted access to the resource in the current cycle and the priority information for the current cycle for the resource whether the requestor granted access to the resource in the current cycle has priority in the current cycle;
in response to determining that the requestor granted access to the resource in the current cycle has priority in the current cycle, generating first priority information for the first set of requestors for the next cycle for the resource; and
in response to determining that the requestor granted access to the resource in the current cycle does not have priority in the current cycle, generating second priority information for the first set of requestors.

### Claim 17 (depends on 16)

The arbiter system of claim 16, wherein for at least one resource the first priority information for the first set of requestors for the next cycle for the resource indicates a same set of requestors in the first set of requestors that have priority in the current cycle have priority in the next cycle except for the requestor granted access to the resource in the current cycle; and
the second priority information for the first set of requestors for the next cycle for the resource indicates all requestors in the first set of requestors have priority in the next cycle, except the requestor granted access to the resource in the current cycle or the second priority information for the first set of requestors for the next cycle for the resource indicates those requestors in the first set of requestors that requested access to the resource in the current cycle have priority in the next cycle except the requestor granted access to the resource in the current cycle.

### Claim 18 (depends on 12)

A non-transitory computer readable storage medium having stored thereon a computer readable dataset description of the arbiter system as set forth in claim 12 that, when processed in an integrated circuit manufacturing system, causes the integrated circuit manufacturing system to manufacture an integrated circuit embodying the arbiter system.