Method and apparatus for controlling the processing priority between multiple threads in a multithreaded processor
AssigneeIntel Corporation
InventorDavid J. Sager
Life of this patent
Estimating the term…
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.
Claims33
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
Dependencies are inferred from the claim text.