System and method of scheduling computing threads

• US 7,634,774 B2
• Filed: 09/13/2004
• Issued: 12/15/2009
• Est. Priority Date: 09/13/2004
• Status: Expired due to Fees

• Current Assignee: Integrated Device Technology Incorporated (Renesas Electronics Corporation)
• Original Assignee: Integrated Device Technology Incorporated (Renesas Electronics Corporation)
• Inventors: Onufryk, Peter Zenon, Levit, Inna
• Primary Examiner(s): An, Meng-Ai
• Assistant Examiner(s): Arcos, Caroline
• Application Number:
  US10/940,201
• Publication Number:
  US 20060059485A1
• Time in Patent Office: 1,919 Days
• Field of Search: 718/100, 718/102, 718/103, 709/240, 712/206, 712/245
• US Class Current: 718/103
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues

Abstract

A system and method for scheduling a thread identifies runnable threads based on precycle signals determined before the scheduling cycle. The thread indexes of the runnable threads are grouped according to the thread priorities of the runnable threads, and the thread indexes are ranked within each group. The runnable threads that will be runnable in the next scheduling cycle are identified based on same cycle signals determined during the scheduling cycle. The highest ranked thread index of the runnable threads that will also be runnable in the next scheduling cycle is selected as the scheduled thread.

Claims

1. A method of scheduling a computing thread, the method comprising:

identifying a lead thread index of a thread from a plurality of threads before a start of a scheduling cycle based on a plurality of precycle signals that indicate thread states of the plurality of threads, the precycle signals indicating whether each thread of the plurality of threads will be runnable at the start of the scheduling cycle, the thread identified by the lead thread index being runnable at the start of the scheduling cycles, wherein the scheduling cycle is a clock cycle of a clock signal and the start of the scheduling cycle is established by an edge of the clock signal;

identifying an alternative thread index of another thread from the plurality of threads before the start of the scheduling cycle based on the plurality of precycle signals, the thread identified by the alternative thread index being runnable at the staff of the scheduling cycle, the lead thread index being ranked higher than the alternative thread index; and

selecting either the lead thread index or the alternative thread index as a selected thread index in the scheduling cycle, based on a same cycle signal received in the scheduling cycle indicating whether the thread identified by the lead thread index has become unrunnable in the scheduling cycle, the thread identified by the selected thread index being a highest ranked thread index being runnable at an end of the scheduling cycle, wherein the same cycle signal indicates a cache miss occurring in a pipelined processor or an instruction exception occurring in the pipelined processor or a wait on arithmetic operation occurring in the pipelined processor or an instruction synchronization occurring in the pipelined processor.

5. The method of claim 1, further comprising:

storing the lead thread index and the alternative thread index in the scheduling cycle in response to the edge of the clock signal; and

outputting the selected thread index in the scheduling cycle in response to the edge of the clock signal.

6. The method of claim 1, further comprising a pipelined processor coupled to the thread selector, wherein the thread selector is further configured to issue the selected thread index to the pipelined processor for processing the thread identified by the selected thread index.

7. The method of claim 1, wherein identifying the lead thread index is performed in a thread ranking module, identifying the alternative thread index is performed in the thread ranking module, selecting either the lead thread index or the alternative thread index as the selected thread index is performed in a thread selector coupled to the thread ranking module, the thread ranking module is a hardware module, and the thread selector is a hardware module.

2. A system for scheduling a computing thread, the system comprising:

a pipelined processor;

a thread ranking module configured to identify both a lead thread index of a thread and an alternative thread index of another thread from a plurality of threads before a start of a scheduling cycle, based on a plurality of precycle signals that indicate thread states of the plurality of threads, the precycle signals indicating whether each thread of the plurality of threads will be runnable at the staff of the scheduling cycle, both the thread identified by the lead thread index and the thread identified by the alternative thread index being runnable at the start of the scheduling cycle, the lead thread index being ranked higher than the alternative thread index, wherein the scheduling cycle is a clock cycle of a clock signal and the start of the scheduling cycle is established by an edge of the clock signal; and

a thread selector configured to select either the lead thread index or the alternative thread index as a selected thread index in the scheduling cycle, based on a same cycle signal received in the scheduling cycle indicating whether the thread identified by the lead thread index has become unrunnable in the scheduling cycle, the thread identified by the selected thread index being a highest ranked thread index being runnable at an end of the scheduling cycle, wherein the same cycle signal indicates a cache miss occurring in the pipelined processor or an instruction exception occurring in the pipelined processor or a wait on arithmetic operation occurring in the pipelined processor or an instruction synchronization occurring in the pipelined processor.

8. The system of claim 2, wherein the thread selector is further configured to store the lead thread index and the alternative thread index in the scheduling cycle in response to the edge of the clock signal and output the selected thread index in the scheduling cycle in response to the edge of the clock signal.

9. The system of claim 2, wherein the pipelined processor is coupled to the thread selector, wherein the thread selector is further configured to issue the selected thread index to the pipelined processor for processing the thread identified by the selected thread index.

3. A storage device storing a computer program product including computer program code for performing a method comprising:

identifying a lead thread index of a thread from a plurality of threads before a start of a scheduling cycle based on a plurality of precycle signals that indicate thread states of the plurality of threads, the precycle signals indicating whether each thread of the plurality of threads will be runnable at the start of the scheduling cycle, the thread identified by the lead thread index being runnable at the start of the scheduling cycles wherein the scheduling cycle is a clock cycle of a clock signal and the start of the scheduling cycle is established by an edge of the clock signal;

identifying an alternative thread index of another thread from the plurality of threads before the start of the scheduling cycle based on the plurality of precycle signals, the thread identified by the alternative thread index being runnable at the start of the scheduling cycle, the lead thread index being ranked higher than the alternative thread index; and

selecting either the lead thread index or the alternative thread index as a selected thread index in the scheduling cycle, based on a same cycle signal received in the scheduling cycle indicating whether the thread identified by the lead thread index has become unrunnable in the scheduling cycle, the thread identified by the selected thread index being a highest ranked thread index being runnable at an end of the scheduling cycle, wherein the same cycle signal indicates a cache miss occurring in a pipelined processor or an instruction exception occurring in the pipelined processor or a wait on arithmetic operation occurring in the pipelined processor or an instruction synchronization occurring in the pipelined processor.

10. The storage device of claim 3, wherein the method further comprises:

storing the lead thread index and the alternative thread index in the scheduling cycle in response to the edge of the clock signal; and

outputting the selected thread index in the scheduling cycle in response to the edge of the clock signal.

11. The storage device of claim 3, wherein the method further comprises issuing the selected thread index to the pipelined processor for processing the thread identified by the selected thread index.

12. The storage device of claim 3, wherein identifying the lead thread index is performed in a thread ranking module, identifying the alternative thread index is performed in the thread ranking module, selecting either the lead thread index or the alternative thread index as the selected thread index is performed in a thread selector, the thread ranking module is a software module, and the thread selector is a software module.

4. A system for scheduling a computing thread, the system comprising:

a pipelined processor;

means for identifying a lead thread index of a thread from a plurality of threads before a start of a scheduling cycle based on a plurality of precycle signals that indicate thread states of the plurality of threads, the precycle signals indicating whether each thread of the plurality of threads will be runnable at the start of the scheduling cycle, the thread identified by the lead thread index being runnable at the start of the scheduling cycle, wherein the scheduling cycle is a clock cycle of a clock signal and the start of the scheduling cycle is established by an edge of the clock signal;

means for identifying an alternative thread index of another thread from the plurality of threads before the start of the scheduling cycle based on the plurality of precycle signals, the thread identified by the alternative thread index being runnable at the start of the scheduling cycle, the lead thread index being ranked higher than the alternative thread index; and

means for selecting either the lead thread index or the alternative thread index as a selected thread index in the scheduling cycle, based on a same cycle signal received in the scheduling cycle indicating whether the thread identified by the lead thread index has become unrunnable in the scheduling cycle, the thread identified by the selected thread index being a highest ranked thread index being runnable at an end of the scheduling cycle, wherein the same cycle signal indicates a cache miss occurring in the pipelined processor or an instruction exception occurring in the pipelined processor or a wait on arithmetic operation occurring in the pipelined processor or an instruction synchronization occurring in the pipelined processor.

13. The system of claim 4, further comprising:

means for storing the lead thread index and the alternative thread index in the scheduling cycle in response to the edge of the clock signal; and

means for outputting the selected thread index in the scheduling cycle in response to the edge of the clock signal.

14. The system of claim 4, wherein the pipelined processor is coupled to the thread selector, the system further comprising:

means for issuing the selected thread index to the pipelined processor for processing the thread identified by the selected thread index.