Method and apparatus for controlling the processing priority between multiple threads in a multithreaded processor
First Claim
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:
- setting a first duration and a second duration to a first initial period of time and a second initial period of time, respectively, the first duration representing a period of priority during which the first thread is assigned the processing priority and the second duration representing a period of priority during which the processing priority is assigned to the second thread; and
assigning alternately the processing priority to the first thread for the first duration and to the second thread for the second duration, the first duration being dynamically adjusted each time the processing priority is assigned to the first thread based on whether the first thread has made progress, and the second duration being dynamically adjusted each time the processing priority is assigned to the second thread based on whether the second thread has made progress.
1 Assignment
0 Petitions
Accused Products
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.
-
Citations
33 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:
-
setting a first duration and a second duration to a first initial period of time and a second initial period of time, respectively, the first duration representing a period of priority during which the first thread is assigned the processing priority and the second duration representing a period of priority during which the processing priority is assigned to the second thread; and
assigning alternately the processing priority to the first thread for the first duration and to the second thread for the second duration, the first duration being dynamically adjusted each time the processing priority is assigned to the first thread based on whether the first thread has made progress, and the second duration being dynamically adjusted each time the processing priority is assigned to the second thread based on whether the second thread has made progress. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14)
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 further comprising:
-
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.
-
-
11. The method of claim 10 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.
-
-
12. The method of claim 11 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.
-
13. The method of claim 10 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.
-
-
14. The method of claim 10 wherein setting the first duration to the first starting value comprises:
setting a first counter to the first starting value.
-
15. 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, the first duration being set to a predetermined restart period of time in response to a specified event selected from a group consisting of a nuke event and a reset event;
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.
-
-
16. 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:
-
determining a first duration, including;
updating the first duration periodically, including;
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;
assigning the processing priority to the first thread for the 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. - View Dependent Claims (18, 19, 20, 21, 22)
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.
-
-
21. The method of claim 16 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.
-
22. The method of claim 16 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.
-
17. The method of clam 16 wherein the predetermined time period comprises a time period during which the processing priority was last assigned to the first thread.
-
23. An apparatus for arbitrating a processing priority given alternately to a first thread and a second thread in a multithreaded processor, the apparatus comprising:
-
logic to set a first priority duration to a first initial period of time and a second priority duration to a second initial period of time, respectively, the first priority duration corresponding to a period during which the first thread is given the processing priority and the second priority duration corresponding to a period during which the second thread is given the processing priority; and
logic to alternately give the processing priority to the first thread for the first priority duration and to the second thread for the second priority duration, the first priority duration being dynamically updated each time the processing priority is given to the first thread based on whether the first thread has made progress, and the second priority duration being dynamically updated each time the processing priority is given to the second thread based on whether the second thread has made progress. - View Dependent Claims (25, 26, 27)
-
-
24. 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, the first circuit comprising;
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;
a second circuit to invert the processing priority in response to the change signal;
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, wherein the first thread counter is set to a first starting value in response to a specified event selected from the group consisting of a nuke event and a reset event.
-
-
28. 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, the first circuit comprising;
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;
a second circuit to invert the processing priority in response to the change signal;
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, 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. - View Dependent Claims (29, 30)
-
-
31. 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;
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;
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, wherein the first starting number and the second starting number are updated periodically, 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.
-
-
32. 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.
-
-
33. 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, the second circuit comprising;
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, the invert device comprising;
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.
-
Specification