Method and apparatus for controlling the processing priority between multiple threads in a multithreaded processor

• US 20030158885A1
• Filed: 02/13/2003
• Published: 08/21/2003
• Est. Priority Date: 07/08/1999
• Status: Active Grant

• Current Assignee: David J. Sager
• Original Assignee: David J. Sager
• Inventors: Sager, David J.
• Granted Patent: US 6,928,647 B2
• Time in Patent Office: Days
• US Class Current: 718/108
• CPC Class Codes: G06F 9/4831 with variable priority
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues

Abstract

The present invention provides a method and apparatus for controlling a processing priority assigned alternately to a first thread and a second thread in a multithreaded processor to prevent deadlock and livelock problems between the first thread and the second thread. In one embodiment, the processing priority is initially assigned to the first thread for a first duration. It is then determined whether the first duration has expired in a given processing cycle. If the first duration has expired, the processing priority is assigned to the second thread for a second duration.

Claims

1. A method of controlling a processing priority assigned alternately to a first thread and a second thread in a multithreaded processor, the processing priority being used to prevent deadlock and livelock problems between the first thread and the second thread, the method comprising:

assigning the processing priority to the first thread for a first duration;

determining whether the first duration has expired; and

if the first duration has expired, assigning the processing priority to the second thread for a second duration.

2. The method of claim 1 wherein assigning the processing priority to the first thread comprises:

setting a thread priority signal to a first value indicating that the first thread has the processing priority over the second thread.

3. The method of claim 2 wherein the thread priority signal comprises a thread priority bit, the thread priority bit being set to a first bit value to indicate that the first thread has the processing priority and being set to a second bit value to indicate that the second thread has the processing priority.

4. The method of claim 2 further including:

setting a priority time period to indicate that the first duration during which the first thread has the processing priority has started.

5. The method of claim 4 wherein setting the priority time period comprises:

loading a priority time counter with a first number corresponding to the first duration.

6. The method of claim 1 wherein assigning the processing priority to the second thread comprises:

setting a thread priority signal to a second value indicating that the second thread has the processing priority over the first thread.

7. The method of claim 6 wherein the thread priority signal comprises a thread priority bit, the thread priority bit being set to a first bit value to indicate that the first thread has the processing priority and being set to a second bit value to indicate that the second thread has the processing priority.

8. The method of claim 6 further including:

setting a priority time period to indicate that the second duration during which the second thread has the processing priority has started.

9. The method of claim 8 wherein setting the priority time period comprises:

loading a priority time counter with a second number corresponding to the second duration.

10. The method of claim 1 wherein determining whether the first duration has expired comprises:

keeping track of an amount of time that has elapsed since the first duration starts;

checking whether the amount of time that has elapsed since the first duration starts exceeds a predetermined threshold value; and

indicating that the first duration has expired if the amount of time that has elapsed since the first duration starts exceeds the predetermined threshold value.

11. The method of claim 10 wherein keeping track of the amount of time that has elapsed comprises:

setting a priority time period to a first number that corresponds to the length of the first duration when the first duration starts; and

decrementing the priority time period by a predetermined count periodically to reflect the amount of time that has elapsed since the first duration starts.

12. The method of claim 11 wherein checking whether the amount of time that has elapsed since the first duration starts comprises:

checking whether the priority time period exceeds the predetermined threshold value.

13. The method of claim 12 wherein the predetermined threshold value is zero.

14. The method of claim 11 wherein setting the priority time period comprises loading a priority time counter with the first number corresponding to the length of the first duration when the first duration starts and decrementing the priority time period comprises decrementing the priority time counter by the predetermined count periodically.

15. The method of claim 11 wherein decrementing the priority time period periodically comprises:

decrementing the priority time period by the predetermined count once per a processing period.

16. The method of claim 15 wherein the processing period comprises a predetermined number of processing cycles.

17. The method of claim 16 wherein the predetermined number of processing cycles corresponds to a predetermined number of the processor clock periods.

18. The method of claim 16 wherein the predetermined number of processing cycles is one and the predetermined number of the processor clock periods is one.

19. The method of claim 10 wherein keeping track of the amount of time that has elapsed comprises:

setting a priority time period to a first number that corresponds to a starting point of the first duration when the first duration starts; and

incrementing the priority time period by a predetermined count periodically to reflect the amount of time that has elapsed since the first duration starts.

20. The method of claim 19 wherein checking whether the amount of time that has elapsed since the first duration starts comprises:

checking whether the priority time period exceeds the predetermined threshold value.

21. The method of claim 20 wherein the predetermined threshold value equals the length of the first duration.

22. The method of claim 17 wherein setting the priority time period comprises loading a priority time counter with the first number corresponding to the starting point of the first duration when the first duration starts and incrementing the priority time period comprises incrementing the priority time counter by the predetermined count periodically.

23. The method of claim 1 further comprising:

determining the first duration.

24. The method of claim 23 wherein determining the first duration comprises:

initializing the first duration to a first initial period of time at the start of the first thread execution.

25. The method of claim 24 wherein initializing the first duration to the first initial period comprises:

loading a first counter with a first number corresponding to the first initial period.

26. The method of claim 24 wherein the first initial period of time corresponds to a predetermined number of processing periods.

27. The method of claim 26 wherein each processing period corresponds to a predetermined number of processing cycles and each processing cycle corresponds to a predetermined number of processor clock periods.

28. The method of claim 23 wherein determining the first duration further comprises:

setting the first duration to a predetermined restart period of time in response to a specified event.

29. The method of claim 28 wherein setting the first duration to the predetermined restart period comprises:

loading a first counter with a first restart number corresponding to the predetermined restart period.

30. The method of claim 28 wherein the predetermined restart period corresponds to a predetermined number of processing periods.

31. The method of claim 28 wherein the specified event is selected from a group consisting of a nuke event and a reset event.

32. The method of claim 23 wherein determining the first duration further comprises:

updating the first duration periodically.

33. The method of claim 32 wherein updating the first duration comprises:

determining whether the first thread has made progress in a current processing period; and

setting the first duration to a first starting value if the first thread has made progress in the current processing period.

34. The method of claim 33 wherein determining whether the first thread has made progress in the current processing period comprises:

checking whether there is any instruction in the first thread waiting for retirement; and

indicating that the first thread has made progress if there is no instruction in the first thread waiting for retirement in the current processing period.

35. The method of claim 34 wherein checking whether there is any instruction in the first thread waiting for retirement comprises:

examining a queue used to store instructions from the first thread that are waiting to be retired.

36. The method of claim 33 wherein determining whether the first thread has made progress in the current processing period comprises:

determining whether the first thread has retired at least one instruction in the current processing period; and

indicating that the first thread has made progress if the first thread has retired at least one instruction in the current processing period.

37. The method of claim 33 wherein setting the first duration to the first starting value comprises:

setting a first counter to the first starting value.

38. The method of claim 32 wherein updating the first duration comprises:

increasing the first duration by a predetermined amount based upon at least one factor selected from the group consisting of a first factor indicating whether the first thread has made progress within a predetermined time period and a second factor indicating whether the processing priority has been inverted in a current processing period.

39. The method of claim 38 wherein the predetermined time period comprises a time period during which the processing priority was last assigned to the first thread.

40. The method of claim 38 wherein the predetermined time period comprises a time period during which the processing priority was last assigned to the second thread.

41. The method of claim 38 wherein the predetermined time period comprises a time period during which the processing priority was last assigned to the first thread and a time period during which the processing priority was last assigned to the second thread.

42. The method of claim 38 wherein increasing comprises:

increasing the first duration by the predetermined amount if the first thread has not made progress since the last time it had the processing priority and the processing priority has been switched from the first thread to the second thread in the current processing period.

43. The method of claim 38 wherein increasing comprises:

increasing the first duration by the predetermined amount if the first thread has not made progress since the last time it had the processing priority and the processing priority has been switched from the second thread to the first thread in the current processing period.

44. The method of claim 38 wherein increasing the first duration comprises:

incrementing a first counter by the predetermined count, the predetermined count corresponding to a predetermined number of processing periods.

45. An apparatus for arbitrating a processing priority given alternately to a first thread and a second thread in a multithreaded processor in a current processing period, the apparatus comprising:

a first circuit to determine whether a current priority period has expired and generate a change signal if the current priority period has expired; and

a second circuit to invert the processing priority in response to the change signal.

46. The apparatus of claim 45 wherein the first circuit comprises:

a priority counter to store a value indicating an amount of time that has elapsed since the current priority period starts; and

a comparator to compare the value stored in the priority counter with a predetermined threshold value and to generate the change signal indicating that the current priority period has expired when the value stored in the priority counter exceeds the predetermined threshold value.

47. The apparatus of claim 46 wherein the value stored in the priority counter is set to correspond to the length of the current priority period at the start of the current priority period and is decremented by a predetermined count periodically thereafter to reflect the amount of time that has elapsed since the current priority period starts.

48. The apparatus of claim 47 wherein the priority counter is decremented by the predetermined count once every processing period after the current priority starts.

49. The apparatus of claim 48 wherein each processing period corresponds to a predetermined number of processing cycles.

50. The apparatus of claim 49 wherein each processing cycle corresponds to a predetermined number of processor clock periods.

51. The apparatus of claim 47 wherein the predetermined threshold value equals zero.

52. The apparatus of claim 46 wherein the value stored in the priority counter is set to correspond to a starting point of the current priority period at the start of the current priority period and is incremented by a predetermined count periodically thereafter to reflect the amount of time that has elapsed since the current priority period starts.

53. The apparatus of claim 52 wherein the priority counter is incremented by the predetermined count once every processing period after the current priority starts.

54. The apparatus of claim 53 wherein each processing period corresponds to a predetermined number of processing cycles.

55. The apparatus of claim 54 wherein each processing cycle corresponds to a predetermined number of processor clock periods.

56. The apparatus of claim 52 wherein the predetermined threshold value equals the length of the current priority period.

57. The apparatus of claim 46 further comprising:

a first thread counter to hold a first value corresponding to a first duration during which the processing priority is to be given to the first thread;

a second thread counter to hold a second value corresponding to a second duration during which the processing priority is to be given to the second thread; and

a selector to select either the output of the first thread counter or the output of the second thread counter as the length of a next priority period, the output of the selector is to be loaded into the priority counter in response to the change signal generated from the comparator indicating that the current priority period has expired.

58. The apparatus of claim 57 wherein the first thread counter is set to a first starting value at the start of the first thread execution.

59. The apparatus of claim 57 wherein the first thread counter is set to a first starting value in response to a specified event.

60. The apparatus of claim 59 wherein the specified event is selected from the group consisting of a nuke event and a reset event.

61. The apparatus of claim 57 wherein the first thread counter is reset to a first starting value in response to a signal indicating that the first thread has made progress in the current processing period.

62. The apparatus of claim 61 wherein the first thread has made progress in the current processing period if the first thread has no instructions waiting to be retired in the current processing period.

63. The apparatus of claim 61 wherein the first thread has made progress in the current processing period if the first thread has retired at least one instruction in the current processing period.

64. The apparatus of claim 57 wherein the first thread counter is incremented by a predetermined number based upon at least one factor selected from the group consisting of a first factor indicating whether the first thread has made progress after a predetermined time period has passed and a second factor indicating whether the processing priority has been alternated in the current processing period.

65. The apparatus of claim 64 wherein the first thread counter is incremented by the predetermined number if the first thread has not made progress in the current processing period and the processing priority has been alternated from the second thread to the first thread in the current processing period.

66. The apparatus of claim 64 wherein the first thread counter is incremented by the predetermined number if the first thread has not made progress in the current processing period and the processing priority has been alternated from the first thread to the second thread in the current processing period.

67. An apparatus for managing a processing priority between a first thread and a second thread in a multithreaded processor in a current processing period, the apparatus comprising:

a first counter to store a first value corresponding to a first duration during which the first thread is to be given the processing priority;

a second counter to store a second value corresponding to a second duration during which the second thread is to be given the processing priority;

a selector to select either the first value or the second value based upon a thread priority signal indicating whether the processing priority is to be given to the first thread or the second thread;

a priority counter coupled to the selector and to store a third value indicating how much time has elapsed since the start of a current priority period, the priority counter further stores a fourth value derived from the output of the selector in response to a priority change signal;

a comparator coupled to the priority counter and to generate the priority change signal if the third value stored in the priority counter exceeds a predetermined threshold number; and

invert logic coupled to the comparator and to invert the thread priority signal to alternate the processing priority in response to the priority change signal from the comparator.

68. An apparatus for controlling a processing priority in a multithreaded processor capable of processing a first thread and a second thread concurrently, the apparatus comprising:

a first circuit to determine whether a first duration during which the first thread has the processing priority has expired and to generate a priority change signal if the first duration has expired; and

a second circuit to invert the processing priority from the first thread to the second thread for a second duration if the first duration has expired.

69. The apparatus of claim 68 wherein the first circuit comprises:

a priority counter to maintain a first count corresponding to a time that has elapsed since the first duration starts; and

a comparator to generate the priority change signal based upon the first count and a predetermined threshold value.

70. The apparatus of claim 69 wherein the first count is initialized to a first value corresponding to the length of the first duration at the start of the first duration and decremented by a predetermined decrementing value periodically thereafter.

71. The apparatus of claim 69 wherein the first count is initialized to a first value corresponding to a starting point of the first duration at the start of the first duration and incremented by a predetermined incrementing value periodically thereafter.

72. The apparatus of claim 69 wherein the predetermined threshold value is stored in a programmable storage unit.

73. The apparatus of claim 70 wherein the predetermined threshold value is set to a value corresponding to a starting point of the first duration.

74. The apparatus of claim 71 wherein the predetermined threshold value is set to a value corresponding to the length of the first duration.

75. The apparatus of claim 69 wherein the comparator performs a comparison operation with respect to the first count and the predetermined threshold value and generates the priority change signal if the first count exceeds the predetermined threshold value.

76. The apparatus of claim 68 wherein the second circuit comprises:

an invert device coupled to invert a thread precedence signal to alternate the processing priority in response to the priority change signal from the first circuit.

77. The apparatus of claim 76 wherein the thread precedence signal comprises a thread precedence bit, the thread precedence bit is set to a first bit value to indicate that the first thread has the processing priority and set to a second bit value to indicate that the second thread has the processing priority.

78. The apparatus of claim 76 wherein the invert device comprises an exclusive OR gate coupled to receive as inputs the priority change signal and the thread precedence signal and to generate the invert of the thread precedence signal.

79. The apparatus of claim 76 wherein the thread precedence signal is stored in a programmable storage unit.

80. The apparatus of claim 68 further comprising:

a first counter to maintain a first starting number, the first starting number specifying a next priority duration for the first thread; and

a second counter to maintain a second starting number, the second starting number specifying a next priority duration for the second thread.

81. The apparatus of claim 80 wherein the first starting number is initialized to a first initial duration at the start of the first thread execution and the second starting number is initialized to a second initial duration at the start of the second thread execution.

82. The apparatus of claim 80 wherein the first starting number and the second starting number are initialized to a first restart duration and a second restart duration, respectively, in response to a specified event.

83. The apparatus of claim 80 wherein the first starting number and the second starting number are updated periodically.

84. The apparatus of claim 83 wherein the first starting number is reset to a first value in response to a signal indicating that the first thread has made progress in the current processing period.

85. The apparatus of claim 84 wherein the first thread has made progress in the current processing period if there is no instruction from the first thread waiting for retirement or if the first thread retires at least one instruction in the current processing period.

86. The apparatus of claim 83 wherein the first starting number is incremented by a predetermined number if the first thread has not made progress in the current processing period.

87. The apparatus of claim 83 wherein the first starting number is incremented by a predetermined number if the first thread has not made progress in the current processing period and the processing priority has alternated in the current processing period.

88. A method of controlling a processing priority alternately given to a first thread and a second thread in a multithreaded processor, the method comprising:

determining whether a previous priority period has expired in a current processing period;

generating a priority change signal if the previous priority period has expired in the current processing period; and

alternating the processing priority in response to the priority change signal.

89. The method of claim 88 wherein determining whether the previous priority period has expired in the current processing period comprises:

keeping track of an amount of time that has elapsed since the previous priority period starts; and

comparing the amount of time that has elapsed with a predetermined threshold value.

90. The method of claim 89 wherein keeping track of the amount of time comprises:

maintaining a priority time count to indicate the amount of time that has elapsed since the previous priority period starts.

91. The method of claim 90 wherein maintaining the priority time count comprises:

initializing the priority time count to a first value at the start of the previous priority period; and

periodically updating the priority time count to specify how much time has passed since the start of the previous priority period.

92. The method of claim 91 wherein the first value corresponds to the length of the previous priority period and wherein periodically updating the priority time count comprises decrementing the first value by a predetermined amount once every processing period.

93. The method of claim 91 wherein the first value corresponds to a starting point of the previous priority period and wherein periodically updating the priority period comprises incrementing the first value by a predetermined amount once every processing period.

94. The method of claim 88 wherein alternating the processing priority comprises:

inverting a thread precedence signal, the thread precedence signal being set to a first state to indicate that the first thread has processing priority and being set to a second state to indicate that the second thread has processing priority.

95. The method of claim 88 further comprising:

setting a new priority period in response to the priority change signal.

96. The method of claim 95 wherein setting the new priority period comprises:

setting the new priority period to a first duration if the first thread is to have processing priority in the new priority period and to a second duration if the second thread is to have processing priority in the new priority period.

97. An apparatus for arbitrating a processing priority given alternately to a first thread and a second thread in a multithreaded processor, the apparatus comprising:

means for determining whether a current priority duration has expired in a current processing period; and

means for alternating the processing priority if the current priority duration has expired in the current processing period.

98. The apparatus of claim 97 wherein means for determining whether the current priority duration has expired comprises:

means for keeping track of an amount of time that has elapsed since the current priority duration starts; and

means for generating a priority change signal to indicate that the current priority duration has expired if the amount of time that has elapsed since the current priority duration starts exceeds a predetermined threshold value.

99. The apparatus of claim 98 further comprising:

means for comparing the amount of time that has elapsed since the current priority duration starts with the predetermined threshold value.

100. The apparatus of claim 97 further comprising:

means for determining a next priority duration for the first thread and a next priority duration for the second thread.

101. The apparatus of claim 100 further comprising:

means for selecting either the next priority duration for the first thread or the next priority duration for the second thread based upon a signal indicating whether the first thread or the second thread is to be given the processing priority.

102. The apparatus of claim 100 including:

means for resetting the next priority duration for the first thread to a first predetermined duration and for setting the next priority duration for the second thread to a second predetermined duration, in response to detecting a specified event.

103. The apparatus of claim 100 including:

means for resetting the next priority duration for the first thread to a first predetermined duration in response to a signal indicating that the first thread has made progress in the current processing period and for resetting the next priority duration for the second thread to a second predetermined duration in response to a signal indicating that the second thread has made progress in the current processing period.

104. The apparatus of claim 100 including:

means for increasing the next priority duration for the first thread and the next priority duration for the second thread based upon at least one factor selected from the group consisting of a first factor indicating whether the first thread or the second thread has made progress within a predetermined time period and a second factor indicating whether the processing priority has been alternated in the current processing period.

105. A method for controlling a processing priority between a first thread and a second thread in a multithreaded processor to prevent deadlock and livelock problems, the method comprising:

assigning alternately the processing priority to the first thread for a first priority duration and to the second thread for a second priority duration;

increasing the first priority duration by a first predetermined amount if the first thread has not made progress after a first period of time has passed since the last time the processing priority is assigned to the first thread; and

increasing the second priority duration by a second predetermined amount if the second thread has not made progress after a second period of time has passed since the last time the processing priority is assigned to the second thread.

106. The method of claim 105 wherein the first priority duration is initialized to a first starting number at the start of the first thread and the second priority duration is initialized to a second starting number at the start of the second thread.

107. The method of claim 105 wherein the first priority duration is reset to a first reset value if the first thread has made progress in a current processing period and the second priority duration is reset to a second reset value if the second thread has made progress in the current processing period.

108. The method of claim 105 wherein the first thread has made progress if the first thread has no instructions waiting for retirement in a current processing period.

109. The method of claim 105 wherein the first thread has made progress if the first thread has retired at least one instruction in a current processing period.