Method and apparatus for scheduling multiple threads for execution in a shared microprocessor pipeline

• US 20060136915A1
• Filed: 12/17/2004
• Published: 06/22/2006
• Est. Priority Date: 12/17/2004
• Status: Active Grant

• Current Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Aingaran, Kathirgamar, Su, Hong-Men
• Granted Patent: US 8,756,605 B2
• Time in Patent Office: Days
• US Class Current: 718/100
• CPC Class Codes: G06F 2209/483 Multiproc
• CPC Class Codes: G06F 9/3842 Speculative instruction execution
• CPC Class Codes: G06F 9/3851 from multiple instruction streams, e.g. multistreaming
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues

Abstract

An apparatus and method for scheduling execution of multiple threads on a shared processor resource is described in connection with a multithreaded multiprocessor chip. Using a thread selection policy that switches between available threads every cycle to give priority to the least recently executed or scheduled threads, different threads are able to operate in a way that ensures no deadlocks or livelocks while maximizing aggregate performance and fairness between threads. Prioritization is accomplished by monitoring and sorting thread status information for each thread, including speculative states in which a thread may be speculatively scheduled, thereby improving usage of the execution pipeline by switching a thread in with a lower priority.

Claims

1. A multithreaded processor comprising:

an instruction buffer for storing instructions for a plurality of threads;

at least one processor core for executing instructions stored in the instruction buffer; and

a scheduler for selecting which of the plurality of threads will have an instruction scheduled for execution by monitoring a current thread state for each of the plurality of threads to determine whether each thread is ready to be scheduled for execution, whether each thread is currently executing and what condition is preventing each thread from executing, where the scheduler selects a first thread having a current thread state indicating that the first thread was least recently scheduled.

2. The multithreaded processor of claim 1, where the instruction buffer stores up to a plurality of instructions for each of four threads as part of an instruction fetch unit for the multithreaded processor.

3. The multithreaded processor of claim 1, where the scheduler comprises:

a thread state register for tracking a run state, ready state, speculative run state, and speculative ready state for each thread; and

a wait mask register for tracking a plurality of wait states for each thread.

4. The multithreaded processor of claim 1, where the scheduler comprises a thread order register for tracking which thread has been least recently executed.

5. The multithreaded processor of claim 1, where the scheduler updates a current thread state when conditions causing a thread to be stalled clear.

6. The multithreaded processor of claim 1, where the scheduler selects which of the plurality of threads will have an instruction scheduled for execution by applying a priority rule that gives a higher priority to a thread that is in a ready state, a lower priority to a thread that is in a speculative ready state, and a lowest priority to a thread that is in a run state.

7. The multithreaded processor of claim 6, where the scheduler selects which of the plurality of threads will have an instruction scheduled for execution by applying a priority rule that gives a highest priority to a thread that is in an idle state with an interrupt pending.

8. The multithreaded processor of claim 1, where the scheduler monitors a current thread state for each of the plurality of threads to determine whether each thread is in an idle state or a halt state.

9. The multithreaded processor of claim 1, where the scheduler monitors a current thread state for each of the plurality of threads to determine whether each thread is in any of a plurality of wait states.

10. The multithreaded processor of claim 1, where the plurality of wait states comprise a first state for waiting for an instruction fill operation, a second state for waiting for room in a store buffer and a third state for waiting for a long latency operation.

11. The multithreaded processor of claim 1, where the scheduler monitors a current thread state to detect a speculative thread state where completion is being predicted whereby a thread having a speculative thread state is scheduled for execution assuming completion.

12. A method for scheduling multiple threads for execution on a shared processor pipeline, comprising:

maintaining at least one thread status register to keep track of thread states for each of a plurality of threads, said thread states comprising a ready state, a run state and at least one wait state;

maintaining a thread order register for the plurality of threads to track a thread execution order defining which thread was least recently executed;

scheduling any one or more of the plurality of threads for execution that are in the ready state or the run state by assigning a higher priority to a thread that is in a ready state and a lower priority to a thread that is in a run state, with priority between any two or more threads in a ready state being given to whichever thread was least recently executed.

13. The method of claim 12, wherein the thread states tracked in the thread status register further comprise a speculative ready state and wherein priority between any two or more threads in a speculative ready state is given to whichever thread was least recently executed.

14. The method of claim 12, wherein the thread states tracked in the thread status register further comprise a predetermined idle state, such that the scheduling of any one or more of the plurality of threads for execution that are in the predetermined idle state, ready state or the run state is determined by assigning a highest priority to the thread that is in a predetermined idle state, a higher priority to a thread that is in a ready state and a lowest priority to a thread that is in a run state.

15. The method of claim 14, where priority between any two or more threads in the predetermined idle state is given based on thread identifier information for each thread.

16. The method of claim 12, further comprising updating the thread status register when a condition causing a wait state clears.

17. The method of claim 12, wherein the at least one wait state comprises a first state for waiting for an instruction fill operation, a second state for waiting for room in a store buffer and a third state for waiting for a long latency operation.

18. The method of claim 12, wherein the thread states tracked in the thread status register comprise a ready state, a speculative ready state, a run state, a speculative run state and at least one wait state, such that the scheduling of any one or more of the plurality of threads for execution that are in the ready state, the speculative ready state, the run state, or the speculative run state is determined by assigning a higher priority to a thread that is in a ready state, a lower priority to a thread that is in a speculative ready state, and a lowest priority to a thread that is in either a run state or a speculative run state, with priority between any two or more threads in a ready state or in the speculative ready state being given to whichever thread was least recently executed.

19. An article of manufacture having at least one recordable medium having stored thereon one or more executable instructions which, when executed by at least one shared processing device, cause the at least one processing device to schedule execution of multiple threads on said processing device by:

tracking a thread state for each of a plurality of threads, where said thread state may comprise a ready state, a speculative ready state, a run state and a speculative run state;

scheduling for execution any one or more of the plurality of threads by assigning a higher priority to a thread that is in a ready state, a lower priority to a thread that is in a speculative ready state, and a lowest priority to a thread that is in either a run state or a speculative run state, with priority between any two or more threads in a ready state or in the speculative ready state being given to whichever thread was least recently executed.

20. The article of manufacture defined in claim 19, wherein the instructions cause the shared processing device to track at least one wait state for each of the plurality of threads in a wait register.