Method and apparatus for ensuring fairness and forward progress when executing multiple threads of execution

• US 8,024,735 B2
• Filed: 06/14/2002
• Issued: 09/20/2011
• Est. Priority Date: 06/14/2002
• Status: Expired due to Fees

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Rudd, Kevin W., Walterscheidt, Udo
• Primary Examiner(s): Sough; H.
• Assistant Examiner(s): JORDAN, KIMBERLY L
• Application Number:
  US10/173,334
• Publication Number:
  US 20030233394A1
• Time in Patent Office: 3,385 Days
• Field of Search: 718/103, 718/108, 718/102
• US Class Current: 718/102
• CPC Class Codes: G06F 9/3851 from multiple instruction streams, e.g. multistreaming
• CPC Class Codes: G06F 9/485 Task life-cycle, e.g. stopping, restarting, resuming execution G06F9/4881 takes precedence
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues

Abstract

A system and method for determine which threads to execute at a given time in a multi-threaded computer system. A thread prioritizer determines execution fairness between pairs of potentially executing threads. A switch enabler determines forward progress of each executing thread. The resulting indicators from the thread prioritizer and switch enabler may aid in the determination of whether or not to switch a particular potentially executing thread into execution resources.

Claims

1. An apparatus comprising:

logic circuitry to determine fairness of execution of a first thread relative to execution of a second thread based on a single value stored in a fairness counter, wherein the fairness counter is to be incremented in response to execution of one of the first thread or second thread and is to be decremented in response to execution of another one of the first thread or second thread, wherein the fairness counter is to be incremented or decremented in response to an execution event corresponding to the first thread or second thread, the event comprising;

processor cycles, weighted processor cycles, or weighted instruction counts,

logic circuitry to identify a next thread for execution based on the determined fairness and an execution information signal that indicates information about currently executing threads, wherein the logic circuitry to identify the next thread is to cause generation of a next thread signal to cause a processor to execute the next thread; and

logic to determine forward progress of a plurality of executing threads based on values stored in respective forward progress counters and a switch stimulus type from a plurality of switch stimulus types, wherein a value of a forward progress counter is to indicate whether to permit a voluntary switching out of a corresponding thread, and wherein the first thread and the second thread are distinct.

2. The apparatus of claim 1, wherein the logic to determine fairness is to determine fairness of execution of the first thread relative to execution of a third thread;

and

wherein the logic to identify the next thread for execution is to identify the next thread for execution based on the determined fairness of execution of the first thread relative to execution of the second thread and based on the determined fairness of execution of the first thread relative to execution of the third thread.

3. The apparatus of claim 1, wherein the logic to identify the next thread is to identify the next thread based on an execution signal that is to indicate a number of threads which may be concurrently executed by the processor.

4. The apparatus of claim 1, wherein the logic to determine fairness is to modify content of the fairness counter in response to a first thread event and in response to a second thread event.

5. The apparatus of claim 1, wherein the logic to determine fairness is to determine an unfair bias to the first thread if content of the fairness counter exceeds a threshold.

6. The apparatus of claim 5, wherein the logic to determine fairness is to determine an unfair bias to the second thread if content of the fairness counter exceeds another threshold.

7. The apparatus of claim 1, wherein the logic to determine fairness is to limit modification of content of the fairness counter in response to a first thread event.

8. The apparatus of claim 7 wherein the logic to determine fairness is to limit modification of content of the fairness counter in response to a second thread event.

9. The apparatus of claim 1, comprising:

logic to switch execution to the next thread in response to the determined forward progress.

10. The apparatus of claim 9, wherein the logic to determine forward progress includes the forward progress counter.

11. The apparatus of claim 10, wherein the logic to determine forward progress is to modify content of the forward progress counter in response to an executing thread event.

12. The apparatus of claim 10, wherein the logic to switch execution to the next thread is to switch execution to the next thread in response to content of the forward progress counter exceeding a threshold.

13. The apparatus of claim 10, wherein the logic to switch execution to the next thread is to switch execution to the next thread in response to content of the forward progress counter exceeding one of a plurality of switch stimulus event thresholds.

14. The apparatus of claim 10, wherein the logic to determine forward progress is to reset content of the forward progress counter when thread execution is switched.

15. The apparatus of claim 1, wherein the logic circuitry to determine fairness of execution determines the fairness of execution of the first thread relative to execution of the second thread based on the value stored in the fairness counter and an absolute thread priority signal that indicates priorities of the first thread, the second thread, and at least a third thread.

16. The apparatus of claim 1, wherein the event further comprises an instruction count or any other repetitive event corresponding to execution.

17. A method comprising:

determining fairness of execution of a first thread relative to execution of a second thread based on a single value stored in a fairness counter, wherein the fairness counter is to be incremented in response to execution of one of the first thread or second thread and is to be decremented in response to execution of another one of the first thread or second thread, wherein the fairness counter is to be incremented or decremented in response to an execution event corresponding to the first thread or second thread, the event comprising;

processor cycles, weighted processor cycles, or weighted instruction counts;

identifying a next thread for execution based on the determined fairness and an execution information signal that indicates information about currently executing threads;

causing generation of a next thread signal to cause a processor to execute the next thread; and

determining forward progress of a plurality of executing threads based on values stored in respective forward progress counters and a switch stimulus type from a plurality of switch stimulus types, wherein a value of a forward progress counter is to indicate whether to permit a voluntary switching out of a corresponding thread, and wherein the first thread and the second thread are distinct.

18. The method of claim 17, comprising:

determining fairness of execution of the first thread relative to execution of a third thread;

wherein the identifying includes identifying the next thread for execution based on the determined fairness of execution of the first thread relative to execution of the second thread and based on the determined fairness of execution of the first thread relative to execution of the third thread.

19. The method of claim 17, wherein determining fairness includes modifying content of the fairness counter in response to a first thread event and in response to a second thread event.

20. The method of claim 17, wherein determining fairness includes determining an unfair bias to the first thread if content of the fairness counter exceeds a threshold.

21. The method of claim 17, wherein determining fairness includes limiting modification of content of the fairness counter in response to a first thread event.

22. The method of claim 17, comprising:

determining forward progress of an executing thread; and

switching execution to the next thread in response to the determined forward progress.

23. The method of claim 22, wherein determining forward progress includes modifying content of a forward progress counter in response to an executing thread event.

24. The method of claim 22, wherein switching execution to the next thread includes switching execution to the next thread in response to content of the forward progress counter exceeding a threshold.

25. The method of claim 17, wherein the event further comprises an instruction count or any other repetitive event corresponding to execution.

26. A non-transitory computer readable media containing a program executable by a machine to perform operations that result in:

determining fairness of execution of a first thread relative to execution of a second thread based on a single value stored in a fairness counter, wherein the fairness counter is to be incremented in response to execution of one of the first thread or second thread and is to be decremented in response to execution of another one of the first thread or second thread, wherein the fairness counter is to be incremented or decremented in response to an execution event corresponding to the first thread or second thread, the event comprising;

processor cycles, weighted processor cycles, or weighted instruction counts;

identifying a next thread for execution based on the determined fairness and an execution information signal that indicates information about currently executing threads;

causing generation of a next thread signal to cause a processor to execute the next thread; and

determining forward progress of a plurality of executing threads based on values stored in respective forward progress counters and a switch stimulus type from a plurality of switch stimulus types, wherein a value of a forward progress counter is to indicate whether to permit a voluntary switching out of a corresponding thread, and wherein the first thread and the second thread are distinct.

27. The non-transitory computer readable media of claim 26, wherein the program is executable by a machine to perform operations that result in:

determining fairness of execution of the first thread relative to execution of a third thread;

wherein the identifying includes identifying the next thread for execution based on the determined fairness of execution of the first thread relative to execution of the second thread and based on the determined fairness of execution of the first thread relative to execution of the third thread.

28. The non-transitory computer readable media of claim 26, wherein determining fairness includes modifying content of the fairness counter in response to a first thread event and in response to a second thread event.

29. The non-transitory computer readable media of claim 26, wherein determining fairness includes determining an unfair bias to the first thread if content of the fairness counter exceeds a threshold.

30. The non-transitory computer readable media of claim 26, wherein determining fairness includes limiting modification of content of the fairness counter in response to a first thread event.

31. The non-transitory computer readable media of claim 26, wherein the program is executable by a machine to perform operations that result in:

determining forward progress of an executing thread; and

switching execution to the next thread in response to the determined forward progress.

32. The non-transitory computer readable media of claim 31, wherein determining forward progress includes modifying content of the forward progress counter in response to an executing thread event.

33. The non-transitory computer readable media of claim 31, wherein switching execution to the next thread includes switching execution to the next thread in response to content of the forward progress counter exceeding a threshold.

34. The medium of claim 26, wherein the event further comprises an instruction count or any other repetitive event corresponding to execution.

35. A system comprising:

a processor including logic to determine fairness of execution of a first thread relative to execution of a second thread based on a single value stored in a fairness counter, wherein the fairness counter is to be incremented in response to execution of one of the first thread or second thread and is to be decremented in response to execution of another one of the first thread or second thread, and logic to identify a next thread for execution based on the determined fairness and an execution information signal that indicates information about currently executing threads, wherein the logic circuitry to identify the next thread is to cause generation of a next thread signal to cause the processor to execute the next thread, wherein the fairness counter is to be incremented or decremented in response to an execution event corresponding to the first thread or second thread, the event comprising;

processor cycles, weighted processor cycles, or weighted instruction counts;

a fixed disk; and

logic to determine forward progress of a plurality of executing threads based on values stored in respective forward progress counters and a switch stimulus type from a plurality of switch stimulus types, wherein a value of a forward progress counter is to indicate whether to permit a voluntary switching out of a corresponding thread, and wherein the first thread and the second thread are distinct.

36. The system of claim 35, wherein the logic to determine fairness is to determine fairness of execution of the first thread relative to execution of a third thread;

and

wherein the logic to identify the next thread for execution is to identify the next thread for execution based on the determined fairness of execution of the first thread relative to execution of the second thread and based on the determined fairness of execution of the first thread relative to execution of the third thread.

37. The system of claim 35, wherein the logic to determine fairness includes the fairness counter.

38. The system of claim 35, wherein the processor includes logic to determine forward progress of an executing thread and logic to switch execution to the next thread in response to the determined forward progress.

39. The system of claim 38, wherein the logic to determine forward progress includes the forward progress counter.

40. The system of claim 35, wherein the event further comprises an instruction count or any other repetitive event corresponding to execution.