Data processing systems

• US 9,535,700 B2
• Filed: 06/14/2013
• Issued: 01/03/2017
• Est. Priority Date: 06/14/2013
• Status: Active Grant

• Current Assignee: Arm Ltd. (United Kingdom) (SoftBank Group Corp.)
• Original Assignee: Arm Ltd. (United Kingdom) (SoftBank Group Corp.)
• Inventors: Nystad, Jorn, Engh-Halstvedt, Andreas
• Primary Examiner(s): Tseng, Cheng-Yuan
• Application Number:
  US13/918,664
• Publication Number:
  US 20140372731A1
• Time in Patent Office: 1,299 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 9/3802 Instruction prefetching
• CPC Class Codes: G06F 9/3851 from multiple instruction streams, e.g. multistreaming
• CPC Class Codes: G06F 9/3888 controlled by a single instruction for multiple threads [SIMT] in parallel

Abstract

A data processing system includes an execution pipeline that includes one or more programmable execution stages which execute execution threads to execute instructions to perform data processing operations. Instructions to be executed by a group of execution threads are first fetched into an instruction cache and then read from the instruction cache for execution by the thread group. When an instruction to be executed by a thread group is present in a cache line in the instruction cache, or is to be fetched into an allocated cache line in the instruction cache, a pointer to the location of the instruction in the instruction cache is stored for the thread group. This stored pointer is then used to retrieve the instruction for execution by the thread group from the instruction cache.

Claims

1. A method of operating a data processing system which includes an execution pipeline that includes one or more programmable execution stages which execute execution threads to execute instructions to perform data processing operations, and in which instructions to be executed for an execution thread are first fetched into an instruction cache and then read from the instruction cache for execution by a thread, the method comprising:

storing in the instruction cache for one or more of the cache lines in the instruction cache an indication of where in the instruction cache the instructions that immediately precede the instructions in the cache line and the instructions that immediately follow the instructions in the cache line are stored;

storing for a thread for which an instruction to be executed by the thread is present in a cache line in the instruction cache, or is to be fetched into an allocated cache line in the instruction cache, a pointer to the location of the instruction in the instruction cache;

using the stored pointer to the location of the instruction in the instruction cache to retrieve the instruction to be executed by the thread from the instruction cache; and

executing the instruction for the thread;

the method further comprising locking a cache line in the instruction cache when a pointer to the cache line has been stored for a thread or thread group.

4. The method of claim 1, further comprising, if following the execution of an instruction by a thread or thread group, the next instruction in the program flow lies within the same cache line in the instruction cache:

updating the instruction cache pointer for the thread or thread group to indicate the new instruction in the cache line;

using the updated pointer to retrieve the next instruction to be executed by the thread or thread group from the instruction cache; and

executing the instruction for the thread or thread group.

5. The method of claim 1, further comprising, if the instruction flow crosses the current cache line'"'"'s boundary:

checking whether the current cache line has a valid indication of where in the instruction cache the instructions that immediately precede the instructions in the cache line or the instructions that immediately follow the instructions in the cache line are stored as appropriate, and if so, updating the cache line pointer associated with the thread or thread group in question to point to the appropriate new cache line; and

using the updated cache line pointer for the thread or thread group to continue the instruction execution.

6. The method of claim 5, further comprising when the instruction flow crosses a cache line boundary:

unlocking the previous cache line in respect of the thread or thread group in question, and locking the new cache line for the thread or thread group in question.

7. The method of claim 1, wherein the data processing system is a data processing system in which execution threads may be grouped together into thread groups, in which the threads of the group are executed in lock step, one instruction at a time, and further comprising:

storing an instruction cache pointer for each respective thread group that the active threads for an execution stage are divided into.

8. The method of claim 1, further comprising storing a set of program counters for a set of active threads in the data processing system.

9. The method of claim 1, wherein the data processing system is a data processing system in which execution threads may be grouped together into thread groups, in which the threads of the group are executed in lock step, one instruction at a time, and further comprising:

storing a program counter for each respective thread group that the active threads for an execution stage are divided into.

10. The method of claim 1, further comprising, when a thread or thread group is to execute or is executing a sequence of instructions:

reading a program counter for the thread or thread group;

performing an instruction cache lookup using the program counter value for the thread or thread group; and

if there is a hit in the instruction cache, storing a pointer to the instruction in the instruction cache for the thread or thread group;

or

if there is a miss in the instruction cache, but a cache line can be allocated for the thread or thread group, allocating a cache line in the instruction cache for the thread or thread group, and storing a pointer to the instruction in the instruction cache for the thread or thread group.

11. The method of claim 1, wherein the data processing system comprises a graphics processing system that includes a graphics processing pipeline that includes one or more programmable shader stages which execute graphics shader programs to perform graphics processing operations.

2. A data processing system comprising:

an execution pipeline that includes one or more programmable execution stages which execute execution threads to execute instructions to perform data processing operations; and

an instruction cache into which instructions to be executed for an execution thread are fetched and then read from for execution by a thread; and

in which;

the instruction caches stores for one or more of the cache lines in the instruction cache an indication of where in the instruction cache the instructions that immediately precede the instructions in the cache line and the instructions that immediately follow the instructions in the cache line are stored;

wherein the data processing system;

stores for a thread for which an instruction to be executed by the thread is present in a cache line in the instruction cache, or is to be fetched into an allocated cache line in the instruction cache, a pointer to the location of the instruction in the instruction cache; and

uses the stored pointer to the location of the instruction in the instruction cache to retrieve the instruction to be executed by the thread from the instruction cache; and

wherein the data processing system is configured to lock a cache line in the instruction cache when a pointer to the cache line has been stored for a thread or thread group.

12. The system of claim 2, wherein the data processing system is configured to, if following the execution of an instruction by a thread or thread group, the next instruction in the program flow lies within the same cache line in the instruction cache:

update the instruction cache pointer for the thread or thread group to indicate the new instruction in the cache line;

use the updated pointer to retrieve the next instruction to be executed by the thread or thread group from the instruction cache; and

execute the instruction for the thread or thread group.

13. The system of claim 2, wherein the data processing system is configured to, if the instruction flow crosses the current cache line boundary:

check whether the current cache line has a valid indication of where in the instruction cache the instructions that immediately precede the instructions in the cache line or the instructions that immediately follow the instructions in the cache line are stored, as appropriate, and if so, update the cache line pointer associated with the thread or thread group in question to point to the appropriate new cache line; and

use the updated cache line pointer for the thread or thread group to continue the instruction execution.

14. The system of claim 13, wherein the data processing system is configured to, when the instruction flow crosses a cache line boundary:

unlock the previous cache line in respect of the thread or thread group in question, and lock the new cache line for the thread or thread group in question.

15. The system of claim 2, wherein the data processing system is a data processing system in which execution threads may be grouped together into thread groups, in which the threads of the group are executed in lock step, one instruction at a time;

and wherein;

an instruction cache pointer is stored for each respective thread group that the active threads for an execution stage are divided into.

16. The system of claim 2, wherein a set of program counters for a set of active threads in the data processing system is also stored.

17. The system of claim 2, wherein the data processing system is a data processing system in which execution threads may be grouped together into thread groups, in which the threads of the group are executed in lock step, one instruction at a time;

and wherein

a program counter for each respective thread group that the active threads for an execution stage are divided into is also stored.

18. The system of claim 2, wherein the data processing system is configured to, when a thread or thread group is to execute or is executing a sequence of instructions:

read a program counter for the thread or thread group;

perform an instruction cache lookup using the program counter value for the thread or thread group; and

if there is a hit in the instruction cache, store a pointer to the instruction in the instruction cache for the thread or thread group;

or

if there is a miss in the instruction cache, but a cache line can be allocated for the thread or thread group, allocate a cache line in the instruction cache for the thread or thread group, and store a pointer to the instruction in the instruction cache for the thread or thread group.

19. The system of claim 2, wherein the data processing system comprises a graphics processing system that includes a graphics processing pipeline that includes one or more programmable shader stages which execute graphics shader programs to perform graphics processing operations.

3. A computer readable storage medium storing computer software code which when executing on a processor performs a method of operating a data processing system which includes an execution pipeline that includes one or more programmable execution stages which execute execution threads to execute instructions to perform data processing operations, and in which instructions to be executed for an execution thread are first fetched into an instruction cache and then read from the instruction cache for execution by a thread, the method comprising:

storing in the instruction cache for one or more of the cache lines in the instruction cache an indication of where in the instruction cache the instructions that immediately precede the instructions in the cache line and the instructions that immediately follow the instructions in the cache line are stored;

storing for a thread for which an instruction to be executed by the thread is present in a cache line in the instruction cache, or is to be fetched into an allocated cache line in the instruction cache, a pointer to the location of the instruction in the instruction cache;

using the stored pointer to the location of the instruction in the instruction cache to retrieve the instruction to be executed by the thread from the instruction cache; and

executing the instruction for the thread;

the method further comprising locking a cache line in the instruction cache when a pointer to the cache line has been stored for a thread or thread group.