# US 2025/0094219 A1 · Building and scheduling tasks for parallel processing

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

- Number: US 2025/0094219 A1
- Document ID: US20250094219A1
- Status: Published application
- Kind: A1
- Application number: 18/968,479
- Filed: 2024-12-04
- Published: 2025-03-20
- Earliest claimed: 2020-09-30
- Assignees: Imagination Technologies Limited
- Applicants: Imagination Technologies Limited
- Inventors: Alistair Goudie; Panagiotis Velentzas
- Web page: https://patentgrep.com/patent/US20250094219A1

## CPC

- G06F 9/4881: {Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues}
- 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 12/0802: Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches
- G06T 1/20: Processor architectures; Processor configuration, e.g. pipelining
- G06T 15/005: {General purpose rendering architectures}
- G06T 15/06: Ray-tracing
- G06F 2209/509: Offload
- G06F 2212/60: Details of cache memory
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL

## Abstract

Task building logic builds a plurality of tasks each comprising a group of rays. When a new ray is received into ray storage, if an existing task exists for the new ray, the new ray is added to an existing respective list. The task building logic indicates when any of the tasks is ready for scheduling, and task scheduling logic identifies a task ready for scheduling based on the indication from the task building logic, and in response traverses the respective list in order to schedule at least some of the rays of the respective task for processing in parallel.

## Claims

### Claim 1

A processor comprising:
task building logic for building a plurality of tasks, each task comprising a group of rays;
ray storage arranged to hold a respective identifier for each of the rays; and
one or more storage modules configured to store a list for each task
wherein the task building logic is configured to, when a new ray is received into the ray storage, determine whether an existing task exists for the new ray, and if so, add the new ray to an existing respective list;
wherein the task building logic is further configured to indicate when any of the tasks is ready for scheduling; and
task scheduling logic arranged to identify a task ready for scheduling based on the indication from the task building logic, and in response, traverse the respective list in order to schedule at least some of the rays of the respective task for processing in parallel.

### Claim 2 (depends on 1)

The processor of claim 1, wherein the task building logic is configured to perform said indicating by asserting a respective flag in the one or more storage modules to flag when any of the tasks is ready for scheduling; and
wherein the task scheduling logic is arranged to perform said identifying by monitoring the one or more storage modules for asserted flags, and to detect that one of the tasks is ready when the respective flag is asserted.

### Claim 3 (depends on 1)

The processor of claim 1, wherein the task building logic comprises temporary storage arranged to store one or more indications of tasks being built, and the task building logic is configured to remove the indication of a selected task from the temporary storage based on one or more predetermined criteria and indicate that the selected task is ready for scheduling.

### Claim 4 (depends on 3)

The processor of claim 3, wherein the temporary storage comprises a cache comprising a plurality of bins, each operable to cache one of the tasks by temporarily recording an indication of the task, wherein when a new task is created it is cached in one of the bins, wherein the one or more predetermined criteria comprise an eviction policy and the cache is configured to evict tasks from the bins according to the eviction policy, and
wherein the task building logic is configured to indicate that the selected task is ready for scheduling when the selected task is evicted from the cache.

### Claim 5 (depends on 4)

The processor of claim 4, wherein the eviction policy comprises: when a new task is created and a set of bins suitable for caching the new task is full, an existing task is evicted from one of the bins of the set to accommodate the new task.

### Claim 6 (depends on 5)

The processor of claim 5, wherein:
the cache is arranged into sets and ways, each set comprising one or more of the ways, and the ways being the bins, wherein each set is mapped to a subset of the tasks, and the cache is configured so as when a new task is created, the new task is added to one of the ways of the set mapped to the new task; and
wherein said eviction policy comprises: when a new task is created and all the ways of the set mapped to the new task are full, an existing task is evicted from one of the ways of this set in order to accommodate the new task.

### Claim 7 (depends on 5)

The processor of claim 5, wherein either:
(i) each task has an associated priority recorded in the cache, being indicative of a priority for scheduling the respective task, and wherein the existing task selected for eviction is that with the highest priority for scheduling amongst the set; or
(ii) the existing task selected for eviction is that with the largest number of rays in the in the respective list; or
(iii) each task has an associated age recorded in the cached, being indicative of a time since the task was created, and the existing task selected for eviction is that with the oldest age.

### Claim 8 (depends on 4)

The processor of claim 4, wherein:
(i) each task has an associated age recorded in the cache, being indicative of a time since the task was created, and wherein the eviction policy comprises: evicting task if the age exceeds a threshold; and/or
(ii) the eviction policy comprises: evicting a task if the respective list exceeds a threshold number of rays in length; and/or
(iii) the eviction policy comprises evicting tasks randomly.

### Claim 9 (depends on 3)

The processor of claim 3, wherein the indication of each task in the cache comprises a pointer to a ray ID of a head and/or tail ray in the respective list.

### Claim 10 (depends on 1)

The processor of claim 1, wherein the one or more storage modules comprise an entry for each ray in each list, and
each entry in the one or more storage modules further comprise an entry point marker, wherein the task building logic is configured, for each task ready for scheduling, to assert one of the entry point markers to indicate which ray in the list is to act as an entry point to the list; and the task scheduling logic is configured so as, traversing the respective list to perform said scheduling, to start from the ray in the entry with the entry point marker asserted.

### Claim 11 (depends on 1)

The processor of claim 1, wherein the one or more storage modules comprise an entry for each ray in each list, and
the entry for a tail ray in each list records a pointer to a head ray of the respective list; and
the task scheduling logic is operable to schedule any selected individual one of the rays for processing from one of the lists, and to stitch together a remainder of that list for future scheduling, by setting the pointer of an adjacent entry preceding that of the individual ray to point to the ray of an adjacent entry following that of the individual ray.

### Claim 12 (depends on 4)

The processor of claim 4, wherein the one or more storage modules comprise an entry for each ray in each list, and
the task building logic is operable to set the entry for a tail ray in the list of at least one of the tasks to point to the cache bin of the respective task in the cache;
and wherein task scheduling logic is configured so as, if starved of work, to schedule the respective task from the cache bin pointed to by the tail ray before indicated as ready by the task building logic.

### Claim 13 (depends on 1)

The processor of claim 1, wherein the task scheduling logic is operable to schedule only a contiguous subgroup of the rays from the beginning or end of one of the tasks, and to leave the remainder of the task for future scheduling by making one of the remaining rays the new head or tail ray, respectively.

### Claim 14

A method comprising:
building a plurality of tasks, each comprising a respective group of rays to be processed;
scheduling each of the tasks to be processed, whereby for each task, at least some of the rays of the respective group are processed in parallel;
holding, in ray storage, respective data content of each ray; and
in one or more storage modules, providing a respective entry for each of the rays;
wherein the building of the tasks comprises: when a new ray is received into the ray storage, determining whether an existing task exists for the new ray, and if so adding the new ray to an existing respective list of entries in the one or more storage modules;
the building of the tasks further comprising indicating when any of the tasks is ready for scheduling; and
the scheduling comprising, based on said indication from the building, identifying a task ready for scheduling, and in response traversing the respective list in order to schedule the rays of the respective task for the processing.

### Claim 15 (depends on 1)

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

### Claim 16 (depends on 1)

A method of manufacturing an integrated circuit embodying the processor as set forth in claim 1 using an integrated circuit manufacturing system, comprising inputting a computer readable dataset description of said processor into said integrated circuit manufacturing system, and causing the integrated circuit manufacturing system to manufacture an integrated circuit embodying the processor.

### Claim 17 (depends on 1)

An integrated circuit manufacturing system configured to manufacture an integrated circuit embodying the processor as set forth in claim 1.

### Claim 18 (depends on 14)

A graphics processing system configured to perform the method as set forth in claim 14.

### Claim 19

A non-transitory computer readable storage medium having stored thereon computer readable code configured to, when the code is run on at least one processor, cause the at least one processor to:
build a plurality of tasks, each comprising a respective group of rays to be processed;
schedule each of the tasks to be processed, whereby for each task, at least some of the rays of the respective group are processed in parallel;
hold, in ray storage, respective data content of each ray; and
in one or more storage modules, provide a respective entry for each of the rays;
wherein the building of the tasks comprises: when a new ray is received into the ray storage, determining whether an existing task exists for the new ray, and if so adding the new ray to an existing respective list of the a subset of the entries in the one or more storage modules;
the building of the tasks further comprises indicating when any of the tasks is ready for scheduling; and
the scheduling comprises, based on said indication from the building, identifying a task ready for scheduling, and in response traversing the respective list in order to schedule the rays of the respective task for the processing.
