# US 2012/0254882 A1 · Controlling priority levels of pending threads awaiting processing

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

- Number: US 2012/0254882 A1
- Document ID: US20120254882A1
- Status: Published application
- Kind: A1
- Application number: 13/064,598
- Filed: 2011-04-01
- Published: 2012-10-04
- Earliest claimed: 2011-04-01
- Assignees: Arm Limited
- Inventors: Nebojsa Makljenovic; Edvard Fielding; Andreas Due Engh-Halstvedt
- Web page: https://patentgrep.com/patent/US20120254882A1

## CPC

- G06F 9/54: Interprogram communication
- G06F 9/3851: {from multiple instruction streams, e.g. multistreaming}
- G06F 9/38585: {with result invalidation, e.g. nullification}
- G06F 9/5011: {the resources being hardware resources other than CPUs, Servers and Terminals}
- G06F 2209/5021: Priority
- G06F 2209/507: Low-level
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A data processing apparatus comprises processing circuitry arranged to process processing threads using resources accessible to the processing circuitry. A pipeline is provided for handling at least two pending threads awaiting processing by the processing circuitry. The pipeline includes at least one resource-requesting pipeline stage for requesting access to resources for the pending threads. A priority controller controls priority levels of the pending threads. The priority levels define a priority with which pending threads are granted access to resources. When a pending thread reaches a final pipeline stage, if the request resources are not yet available then the priority level of that thread is raised selectively and the thread is returned to a first pipeline stage of the pipeline. If the requested resources are available then the thread is forwarded from the pipeline.

## Claims

### Claim 1

A data processing apparatus comprising:
processing circuitry configured to process processing threads using resources accessible to said processing circuitry;
a pipeline for handling at least two pending threads awaiting processing by said processing circuitry, said pipeline comprising at least one pipeline stage including at least one resource-requesting pipeline stage for requesting access to said resources for said pending threads;
a pipeline controller configured to determine whether requested resources are available for a pending thread in a final pipeline stage of said pipeline, to return said pending thread to a first pipeline stage of said pipeline if said requested resources are not yet available for said pending thread, and to forward said pending thread from said pipeline if said requested resources are available for said pending thread;
a priority controller for controlling priority levels of said pending threads, said priority levels defining a priority with which respective pending threads are granted access to resources, pending threads being assigned a base priority level when entering said pipeline for the first time;
wherein said priority controller is configured to selectively raise the current priority level of a pending thread in said final pipeline stage if said pipeline controller returns said pending thread to said first pipeline stage.

### Claim 2 (depends on 1)

The data processing apparatus according to claim 1, wherein said pipeline comprises a plurality of pipeline stages including said at least one resource-requesting pipeline stage.

### Claim 3 (depends on 1)

The data processing apparatus according to claim 1, wherein said final pipeline stage of said pipeline comprises at least one of said pipeline controller and said priority controller.

### Claim 4 (depends on 1)

The data processing apparatus according to claim 1, comprising an arbiter configured to select pending threads for input to said first pipeline stage;
wherein said arbiter is configured to select pending threads that are returned from said final pipeline stage by said pipeline controller in preference to new pending threads that have not yet entered the pipeline.

### Claim 5 (depends on 1)

The data processing apparatus according to claim 1, wherein said priority controller is configured to re-evaluate said current priority level of said pending thread in said final pipeline stage if said pipeline controller returns said pending thread to said first pipeline stage such that said pending thread has a re-evaluated priority level when returned to said first pipeline stage;
said re-evaluated priority level is higher than said current priority level if said current priority level is lower than a priority cap level; and
said re-evaluated priority level is equal to said current priority level if said current priority level is equal to or higher than said priority cap level.

### Claim 6 (depends on 5)

The data processing apparatus according to claim 5, wherein said priority controller is configured to lower said priority cap level if said re-evaluated priority level equals said priority cap level.

### Claim 7 (depends on 6)

The data processing apparatus according to claim 6, wherein said priority controller is configured to set said priority cap level to said current priority level of said pending thread in said final pipeline stage if said pipeline controller forwards said pending thread from said pipeline and said current priority level of said pending thread is greater than said priority cap level.

### Claim 8 (depends on 1)

The data processing apparatus according to claim 1, wherein said priority levels are represented by a set of discrete values including a base value representing said base priority level and at least one further value representing at least one higher priority level.

### Claim 9 (depends on 8)

The data processing apparatus according to claim 8, wherein said pipeline is configured to handle a maximum of N pending threads, and said set of discrete values comprises M-bit values, where N is an integer and M is the smallest integer greater than or equal to log 2(N).

### Claim 10 (depends on 8)

The data processing apparatus according to claim 8, wherein said pipeline is configured to handle a maximum of N pending threads, and said set of discrete values comprises M-bit values, where M and N are integers and M<log 2(N).

### Claim 11 (depends on 1)

The data processing apparatus according to claim 1, wherein said pipeline comprises a plurality of resource-requesting pipeline stages for requesting access to associated resources for said pending threads, and said pipeline controller is configured to return said pending thread in said final pipeline stage to said first pipeline stage if any of the associated resources associated with said plurality of resource-requesting pipeline stages is not yet available.

### Claim 12 (depends on 1)

The data processing apparatus according to claim 1, wherein said processing circuit comprises a graphics processor.

### Claim 13 (depends on 12)

The data processing apparatus according to claim 12, wherein said processing threads comprise texture mapping threads for controlling said graphics processor to perform texture mapping operations.

### Claim 14 (depends on 1)

The data processing apparatus according to claim 1, wherein said resources include at least one of:
data or instructions from a storage unit;
an allocation of space within a storage unit;
bandwidth on a network, interconnect or bus; and
use of a processing unit.

### Claim 15 (depends on 1)

The data processing apparatus according to claim 1, wherein said resources include data or instructions from a cache memory, and at least one of said resource-requesting pipeline stages comprises a cache requesting stage configured to issue to said cache memory cache access requests for data or instructions for a pending thread in said cache requesting stage.

### Claim 16 (depends on 15)

The data processing apparatus according to claim 15, wherein said cache requesting stage is configured to:
determine, if a cache access request for a pending thread in said cache requesting stage results in a cache miss, whether said cache memory includes an available storage location, and if said cache memory includes an available storage location to allocate said available cache storage location to said pending thread and trigger a memory access request for data or instructions requested by said cache access request.

### Claim 17 (depends on 16)

The data processing apparatus according to claim 16, wherein said cache requesting stage is configured to:
determine, if said cache memory does not include an available storage location, whether an unavailable cache storage location of said cache memory is allocated to another pending thread having a lower priority than said pending thread in said cache requesting stage, and
if said unavailable cache storage location is allocated to another pending thread having a lower priority than said pending thread in said cache requesting stage, to re-allocate said unavailable cache storage location to said current pending thread and trigger a memory access request for said data or instructions requested by said cache access request.

### Claim 18 (depends on 17)

The data processing apparatus according to claim 17, comprising circuitry configured to control said cache memory, when a pending thread for which said cache requesting stage has allocated a cache storage location is forwarded from said pipeline, to prevent re-allocation of the cache storage location allocated to said pending thread until processing of said pending thread is complete.

### Claim 19

A data processing apparatus comprising:
processing means for processing threads using resources accessible to said processing means;
pipeline means for handling at least two pending threads awaiting processing by said processing means, said pipeline means comprising at least one pipeline stage means including at least one resource-requesting pipeline stage means for requesting access to said resources for said pending threads;
pipeline control means for determining whether requested resources are available for a pending thread in a final pipeline stage means of said pipeline means, for returning said pending thread to a first pipeline stage means of said pipeline means if said requested resources are not yet available for said pending thread, and for forwarding said pending thread from said pipeline means if said requested resources are available for said pending thread;
priority control means for controlling priority levels of said pending threads, said priority levels defining a priority with which respective pending threads are granted access to resources, pending threads being assigned a base priority level when entering said pipeline means for the first time;
wherein said priority control means is arranged to selectively raise the current priority level of a pending thread in said final pipeline stage means if said pipeline control means returns said pending thread to said first pipeline stage means.

### Claim 20

A data processing method for an apparatus comprising processing circuitry for processing threads using resources accessible to said processing circuitry and a pipeline for handling at least two pending threads awaiting processing by said processing circuitry, said pipeline comprising at least one pipeline stage including at least one resource-requesting pipeline stage for requesting access to resources for said pending threads, wherein said pending threads are associated with priority levels defining a priority with which respective pending threads are granted access to resources, pending threads being assigned a base priority level when entering said pipeline means for the first time; the method comprising the steps of:
(a) determining whether requested resources are available for a pending thread in a final pipeline stage of said pipeline;
(b) if said requested resources are not yet available for said pending thread in said final pipeline stage, returning said pending thread to a first pipeline stage of said pipeline and selectively raising the current priority level of said pending thread; and
(c) if said requested resources are available for said pending thread in said final pipeline stage, forwarding said pending thread from said pipeline.

### Claim 21 (depends on 20)

The method according to claim 20, wherein step (b) comprises re-evaluating said current priority level of said pending thread in said final pipeline stage if said requested resources are not yet available, such that said pending thread has a re-evaluated priority level when returned to said first pipeline stage;
said re-evaluated priority level is higher than said current priority level if said current priority level is lower than a priority cap level; and
said re-evaluated priority level is equal to said current priority level if said current priority level is equal to or higher than said priority cap level.

### Claim 22 (depends on 21)

The data processing apparatus according to claim 21, wherein step (b) further comprises lowering said priority cap level if said re-evaluated priority level equals said priority cap level.

### Claim 23 (depends on 22)

The data processing apparatus according to claim 22, wherein step (c) further comprises setting said priority cap level to said current priority level of said pending thread forwarded from said pipeline if said current priority level of said pending thread is greater than said priority cap level.
