System and method of scheduling computing threads

• US 20060059485A1
• Filed: 09/13/2004
• Published: 03/16/2006
• Est. Priority Date: 09/13/2004
• Status: Active Grant

• Current Assignee: Integrated Device Technology Incorporated (Renesas Electronics Corporation)
• Original Assignee: Integrated Device Technology Incorporated (Renesas Electronics Corporation)
• Inventors: Onufryk, Peter Zenon, Levit, Inna
• Granted Patent: US 7,634,774 B2
• Time in Patent Office: Days
• US Class Current: 718/100
• 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 thread of a plurality of threads, the method comprising:

identifying a lead thread index of a runnable thread based on a plurality of precycle signals;

identifying an alternative thread index of another runnable thread based on the plurality of precycle signals; and

selecting either the lead thread index or the alternative thread index during a scheduling cycle, based on a same cycle signal.

2. The method of claim 1, wherein identifying a lead thread index of a runnable thread based on a plurality of precycle signals occurs before the start of the scheduling cycle.

3. The method of claim 1, wherein identifying an alternative thread index of another runnable thread based on the plurality of precycle signals occurs before the start of the scheduling cycle.

4. The method of claim 1, wherein at least one precycle signal of the plurality of precycle signals is a thread priority, a thread state, a thread index, or a selected thread index.

5. The method of claim 1, wherein the same cycle signal occurs during the scheduling cycle.

6. The method of claim 1, wherein the same cycle signal is a data cache miss, an instruction cache miss, an instruction exception, a wait on arithmetic operation, or an instruction synchronization.

7. The method of claim 1, wherein identifying a lead thread index of a runnable thread based on a plurality of precycle signals comprises:

identifying at least one runnable thread in the plurality of threads, each runnable thread having a thread priority, each runnable thread having a thread index of a predetermined circular sequence;

grouping the thread index of each runnable thread into a priority group according to the thread priority of the runnable thread, each priority group having a priority that is the same as the thread priority of any runnable thread having a thread index in the priority group;

determining a first priority group having a highest priority; and

identifying a thread index in the first priority group as the lead thread index, the lead thread index being the thread index in the first priority group that first follows a most recently selected thread index in the predetermined circular sequence.

8. The method of claim 7, wherein identifying an alternative thread index of another runnable thread based on the plurality of precycle signals comprises:

determining a second priority group containing at least one thread index other than the lead thread index; and

identifying a thread index in the second priority group other than the lead thread index as the alternative thread index, the alternative thread index being a thread index in the second priority group other than the lead thread index that first follows the most recently selected lead thread index in the predetermined circular sequence.

9. The method of claim 8, wherein the alternative thread index is the thread index in the second priority group that first follows the lead thread index in the predetermined circular sequence.

10. The method of claim 8, wherein the first priority group and the second priority group are the same priority group.

11. The method of claim 1, wherein identifying a lead thread index of a runnable thread based on a plurality of precycle signals comprises:

identifying at least one runnable thread in the plurality of threads, each runnable thread having a thread priority and a thread index;

grouping the thread index of each runnable thread into a priority group according to the thread priority of the runnable thread, each priority group having a priority that is the same as the thread priority of any runnable thread having a thread index in the priority group;

determining a first priority group having a highest priority; and

identifying a thread index in the first priority group as the lead thread index, the lead thread index being the thread index in the first priority group that first follows a most recently selected thread index based on a ranking algorithm.

12. The method of claim 11, wherein identifying an alternative thread index of another runnable thread based on the plurality of precycle signals comprises:

determining a second priority group containing at least one thread index other than the lead thread index; and

identifying a thread index in the second priority group other than the lead thread index as the alternative thread index, the alternative thread index being a thread index in the second priority group other than the lead thread index that first follows the most recently selected thread index based on the ranking algorithm.

13. The method of claim 12, wherein the alternative thread index is the thread index in the second priority group that first follows the lead thread index based on the ranking algorithm.

14. The method of claim 12, wherein the first priority group and the second priority group are the same priority group.

15. The method of claim 11, wherein the ranking algorithm is a round robin algorithm.

16. A system for scheduling a thread of a plurality of threads, the system comprising:

a thread ranking module configured to identify both a lead thread index of a runnable thread and an alternative thread index of another runnable thread, based on a plurality of precycle signals; and

a thread selector configured to select either the lead thread index or the alternative thread index during a scheduling cycle, based on a same cycle signal.

17. The system of claim 16, wherein each precycle signal of the plurality of precycle signals occurs before the start of the scheduling cycle.

18. The system of claim 16, wherein at least one precycle signal of the plurality of precycle signals is a thread priority, a thread state, a thread index, or a selected thread index.

19. The system of claim 16, wherein the same cycle signal occurs during the scheduling cycle.

20. The system of claim 16, wherein the same cycle signal is a data cache miss, an instruction cache miss, an instruction exception, a wait on arithmetic operation, or an instruction synchronization.

21. The system of claim 16, wherein the thread ranking module is further configured to:

identify at least one runnable thread in the plurality of threads, each runnable thread having a thread priority, each runnable thread having a thread index of a predetermined circular sequence;

group the thread index of each runnable thread into a priority group according to the thread priority of the runnable thread, each priority group having a priority that is the same as the thread priority of any runnable thread having a thread index in the priority group;

determine a first priority group having a highest priority; and

identify a thread index in the first priority group as the lead thread index, the lead thread index being the thread index in the first priority group that first follows a most recently selected thread index in the predetermined circular sequence.

22. The system of claim 21, wherein the thread ranking module is further configured to:

determine a second priority group containing at least one thread index other than the lead thread index; and

identify a thread index in the second priority group other than the lead thread index as the alternative thread index, the alternative thread index being a thread index in the second priority group other than the lead thread index that first follows the most recently selected thread index in the predetermined circular sequence.

23. The system of claim 22, wherein the alternative thread index is the thread index in the second priority group that first follows the lead thread index in the predetermined circular sequence.

24. The system of claim 22, wherein the first priority group and the second priority group are the same priority group.

25. The system of claim 16, wherein the thread ranking module is further configured to:

identify at least one runnable thread in the plurality of threads, each runnable thread having a thread priority and a thread index;

group the thread index of each runnable thread into a priority group according to the thread priority of the runnable thread, each priority group having a priority that is the same as the thread priority of any runnable thread having a thread index in the priority group;

determine a first priority group having a highest priority; and

identify a thread index in the first priority group as the lead thread index, the lead thread index being the thread index in the first priority group that first follows a most recently selected thread index based on a ranking algorithm.

26. The system of claim 25, wherein the thread ranking module is further configured to:

determine a second priority group containing at least one thread index other than the lead thread index; and

identify a thread index in the second priority group other than the lead thread index as the alternative thread index, the alternative thread index being a thread index in the second priority group other than the lead thread index that first follows the most recently selected thread index based on the ranking algorithm.

27. The method of claim 26, wherein the alternative thread index is the thread index in the second priority group that first follows the lead thread index based on the ranking algorithm.

28. The system of claim 26, wherein the first priority group and the second priority group are the same priority group.

29. The system of claim 25, wherein the ranking algorithm is a round robin algorithm.

30. A computer program product including computer program code for performing the steps of:

identifying a lead thread index of a runnable thread based on a plurality of precycle signals;

identifying an alternative thread index of another runnable thread based on the plurality of precycle signals; and

selecting either the lead thread index or the alternative thread index during a scheduling cycle, based on a same cycle signal.

31. The computer program product of claim 30, wherein identifying a lead thread index of a runnable thread based on a plurality of precycle signals occurs before the start of the scheduling cycle.

32. The computer program product of claim 30, wherein identifying an alternative thread index of another runnable thread based on the plurality of precycle signals occurs before the start of the scheduling cycle.

33. The computer program product of claim 30, wherein at least one precycle signal of the plurality of precycle, signals is a thread index, a thread state, a thread priority, or a selected thread index.

34. The computer program product of claim 30, wherein the same cycle signal occurs during the scheduling cycle.

35. The computer program product of claim 30, wherein the same cycle signal is a data cache miss, an instruction cache miss, a wait on arithmetic operation, an instruction exception, or an instruction synchronization.

36. A system for scheduling a thread during a scheduling cycle, the system comprising:

means for identifying a lead thread index of a runnable thread based on a plurality of precycle signals;

means for identifying an alternative thread index of another runnable thread based on the plurality of precycle signals; and

means for selecting either the lead thread index or the alternative thread index during a scheduling cycle, based on a same cycle signal.

37. The system of claim 36, wherein each precycle signal of the plurality of precycle signals occurs before the start of the scheduling cycle.

38. The system of claim 36, wherein at least one precycle signal of the plurality of precycle signals is a thread index, a thread state, a thread priority, or a selected thread index.

39. The system of claim 36, wherein the same cycle signal occurs during the scheduling cycle.

40. The system of claim 36, wherein the same cycle signal is a data cache miss, an instruction cache miss, a wait on arithmetic operation, an instruction exception, or an instruction synchronization.

41. A method of scheduling a thread of a plurality of threads, the method comprising:

identifying at least one runnable thread index based on at least one precycle signal in a plurality of precycle signals, each runnable thread index identifying a thread being runnable at the start of a scheduling cycle;

ranking each of the at least one runnable thread index based on at least one precycle signal in the plurality of precycle signals and a ranking algorithm; and

selecting a highest ranked runnable thread index identifying a thread being runnable in a next scheduling cycle, based on at least one same cycle signal occurring during the scheduling cycle.

42. The method of claim 41, wherein ranking each of the at least one runnable thread index based on at least one precycle signal in the plurality of precycle signals and a ranking algorithm further comprises establishing an order among each of the at least one runnable thread index identifying a thread having the same thread priority, based on the ranking algorithm.

43. The method of claim 41, wherein the ranking algorithm is a round robin algorithm.

44. A system for scheduling a thread of a plurality of threads, the system comprising:

a runnable thread identification module configured to identify at least one runnable thread index based on at least one precycle signal in a plurality of precycle signals, each runnable thread index identifying a thread being runnable at the start of a scheduling cycle;

a runnable thread ranking module configured to rank each of the at least one runnable thread index based on at least one precycle signal in the plurality of precycle signals and a ranking algorithm; and

a thread selector configured to select a highest ranked runnable thread index identifying a thread being runnable in a next scheduling cycle, based on at least one same cycle signal determined during a scheduling cycle.

45. The system of claim 44, wherein the thread selector comprises a thread queue configured to store at least two ranked runnable thread indexes.

46. The system of claim 44, wherein the thread selector comprises a thread queue configured to store a ranked runnable thread index for each thread.

47. The system of claim 44, further comprising a pipelined processor having a predetermined number of stages, the pipelined processor configured to process the plurality of threads, wherein the thread selector comprises a thread queue configured to store a predetermined number of ranked runnable thread indexes, the predetermined number of ranked runnable thread indexes being the same as the predetermined number of stages in the pipelined processor.