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

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.

What is claimed is:  
     
         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.