Two-level scheduler for multi-threaded processing
One embodiment of the present invention sets forth a technique for scheduling thread execution in a multi-threaded processing environment. A two-level scheduler maintains a small set of active threads called strands to hide function unit pipeline latency and local memory access latency. The strands are a sub-set of a larger set of pending threads that is also maintained by the two-leveler scheduler. Pending threads are promoted to strands and strands are demoted to pending threads based on latency characteristics. The two-level scheduler selects strands for execution based on strand state. The longer latency of the pending threads is hidden by selecting strands for execution. When the latency for a pending thread is expired, the pending thread may be promoted to a strand and begin (or resume) execution. When a strand encounters a latency event, the strand may be demoted to a pending thread while the latency is incurred.
1. A method for executing a program in a multi-threaded processing environment, the method comprising:
receiving, for execution by a multi-threaded execution unit, a plurality of threads that each include a portion of the program;
storing state specific to each thread of the plurality of threads in thread entries;
promoting, based on a latency characteristic, a sub-set of threads from the plurality of threads to occupy strand slots, wherein the sub-set of threads that occupy the strand slots are considered for execution and remaining threads in the plurality of threads that do not occupy the strand slots are not considered for execution;
selecting a first thread from a first strand slot of the strand slots for execution by the multi-threaded execution unit;
issuing the first thread for execution by the multi-threaded execution unit;
determining that a second thread occupying a second strand slot of the strand slots has encountered a latency event; and
demoting the second thread by removing the second thread from the second strand slot.
2. The method of claim 1 , further comprising copying state associated with the second thread from the second strand slot to an entry in the thread entries.
3. The method of claim 1 , further comprising copying state associated with the first thread from an entry in the thread entries to the first strand slot that is allocated to the first thread.
4. The method of claim 1 , further comprising:
determining that a third thread that is stored in a third strand slot of the strand slots will be unable to execute for a number of clock cycles; and
retaining the third thread in the third strand slot.
5. The method of claim 1 , wherein the selecting comprises identifying one or more threads occupying the strand slots that are eligible to issue.
6. The method of claim 1 , further comprising:
determining that execution of the first thread is complete; and
deallocating the first strand slot assigned to the first thread.
7. The method of claim 1 , further comprising dividing the program into a plurality of code segments having a limited number of instructions to generate the plurality of threads.
8. The method of claim 1 , wherein the latency characteristic indicates presence of instructions corresponding to a thread in an instruction cache.
9. A non-transitory computer-readable storage medium storing instructions that, when executed by a processor, cause the processor to execute the program in a multi-threaded processing environment, by performing the steps of:
receiving a plurality of threads for execution that each include a portion of the program;
storing state specific to each thread of the plurality of threads in thread entries;
promoting, based on a latency characteristic, a sub-set of threads from the plurality of threads to occupy strand slots, wherein the sub-set of threads that occupy the strand slots are considered for execution and remaining threads in the plurality of threads that do not occupy the strand slots are not considered for execution;
selecting a first thread from a first strand slot of the strand slots for execution;
issuing the first thread for execution;
determining that a second thread occupying a second strand slot of the strand slots has encountered a latency event; and
demoting the second thread by removing the second thread from the second strand slot.
10. A system for executing a program in a multi-threaded processing environment, the system comprising:
an instruction memory that stores instructions for the program; and
a scheduler that is coupled to the instruction memory and:
receives a plurality of threads for execution that each include a portion of the program;
stores state specific to each thread of the plurality of threads in thread entries;
promotes, based on a latency characteristic, a sub-set of threads from the plurality of threads to occupy strand slots, wherein the sub-set of threads that occupy the strand slots are considered for execution and remaining threads in the plurality of threads that do not occupy the strand slots are not considered for execution;
selects a first thread from a first strand slot of the strand slots for execution;
issues the first thread for execution;
determines that a second thread that occupies a second strand slot of the strand slots has encountered a latency event; and
demotes the second thread by removing the second strand from the second strand slot.
11. The system of claim 10 , wherein the scheduler copies state associated with the second thread from the second strand slot to an entry in the thread entries.
12. The system of claim 10 , wherein the scheduler copies state associated with the first thread from an entry in the thread entries to the first strand slot that is allocated to the first strand.
13. The system of claim 10 , wherein the scheduler:
determines that a third thread occupying a third strand slot of the strand slots is unable to execute for a number of clock cycles; and
retains the third strand in the third strand slot.
14. The system of claim 10 , wherein the scheduler identifies one or more threads occupying the strand slots that are eligible to issue to select the first strand.
15. The system of claim 10 , wherein the scheduler:
determines that an instruction of the first thread and an instruction of a second strand use different function units; and
simultaneously issues the first thread and the second thread for execution.
16. The system of claim 10 , wherein the program is divided into a plurality of code segments having a limited number of instructions to generate the plurality of threads.
17. The system of claim 10 , wherein the instruction memory comprises an instruction cache and a backing memory and the latency characteristic indicates presence of instructions corresponding to a thread in the instruction cache.
18. The system of claim 10 , further comprising:
a main register file that stores data associated with the plurality of threads; and
a register file cache that is coupled between the scheduler and the main register file and that stores data associated with the strand slots.
19. The system of claim 18 , wherein management of the register file cache is controlled by hardware.