Round-Robin Apparatus and Instruction Dispatch Scheduler Employing Same For Use In Multithreading Microprocessor

Abstract

An apparatus for selecting one of N requesters of a shared resource in a round-robin fashion is disclosed. One or more of the N requestors may be disabled from being selected in a selection cycle. The apparatus includes a first input that receives a first value specifying which of the N requestors was last selected. A second input receives a second value specifying which of the N requestors is enabled to be selected. A barrel incrementer, coupled to receive the first and second inputs, 1-bit left-rotatively increments the second value by the first value to generate a sum. Combinational logic, coupled to the barrel incrementer, generates a third value specifying which of the N requestors is selected next.

1 . An apparatus for selecting one of N requestors of a shared resource in a round-robin fashion, wherein one or more of the N requesters may be disabled from being selected in a selection cycle, the apparatus comprising:
 a first input, for receiving a first value specifying which of the N requestors was last selected;   a second input, for receiving a second value specifying which of the N requesters is enabled to be selected;   one or more registers to hold N bits, each bit corresponding to one of the N requestors and each bit enabled in accordance with an enabled state of the corresponding requestor and a selected state of the corresponding requestor; and   logic, coupled to the one or more registers, to generate a third value specifying which of the N requesters is selected next.   
   
   
       2 . The apparatus as recited in  claim 1 , wherein the first value comprises N bits corresponding to the N requestors and wherein only one of the N bits corresponding to the last selected requester has a value of true. 
   
   
       3 . The apparatus as recited in  claim 1 , wherein the second value comprises N bits corresponding to the N requesters and wherein each of the N bits whose corresponding requester is enabled has a value of false. 
   
   
       4 . The apparatus as recited in  claim 1 , wherein the logic is configured to set each of the N bits in the one or more registers corresponding to each requestor that is not enabled and was not last selected. 
   
   
       5 . The apparatus as recited in  claim 4 , wherein the logic is configured to generate the third value based upon the Boolean AND of the second value and a sum of a 1-bit left-rotated version of the first value and the enabled N bits in the one or more registers. 
   
   
       6 . The apparatus as recited in  claim 1 , wherein the logic is configured to generate the third value based upon the Boolean AND of the second value and a sum of an inverted version of the second value and a 1-bit left-rotated version of the first value. 
   
   
       7 . The apparatus as recited in  claim 1 , wherein the third value comprises N bits corresponding to the N requestors and wherein only one of the N bits corresponding to the next selected one of the N requesters is true. 
   
   
       8 . The apparatus as recited in  claim 1 , further comprising:
 a plurality of adders, coupled to the one or more registers, configured to add an inverted version of the first value to an inverted version of the second value, wherein the carryout of each adder is added to a 1-bit left-rotated version of the first value and wherein the resulting carryout of each last used adder is added to the second value to generate the third value.   
   
   
       9 . The apparatus as recited in  claim 1 , wherein the N requestors comprise N thread contexts in a multithreading microprocessor each requesting a dispatch scheduler to dispatch an instruction of the thread context to at least one execution pipeline of the microprocessor. 
   
   
       10 . A method for selecting one of N requestors of a shared resource in a round-robin fashion, wherein one or more of the N requesters may be disabled from being selected in a selection cycle, the method comprising:
 receiving a first value specifying which of the N requesters was last selected;   receiving a second value specifying which of the N requesters is enabled to be selected;   storing N bit values in one or more registers, each bit corresponding to one of the N requestors and each bit enabled in accordance with an enabled state of the corresponding requestor and a selected state of the corresponding requester; and   generating a third value based on the N bit values in the one or more registers, specifying which of the N requesters is selected next.   
   
   
       11 . The method as recited in  claim 10 , wherein the first value comprises N bits corresponding to the N requesters and wherein only one of the N bits corresponding to the last selected requester has a value of true. 
   
   
       12 . The method as recited in  claim 10 , wherein the second value comprises N bits corresponding to the N requesters and wherein each of the N bits whose corresponding requestor is enabled has a value of false. 
   
   
       13 . The method as recited in  claim 10 , further comprising:
 setting each of the N bits in the one or more registers to enabled for each corresponding N requester that is not enabled and was not last selected.   
   
   
       14 . The method as recited in  claim 13 , further comprising:
 generating the third value based upon the Boolean AND of the second value and a sum of a 1-bit left-rotated version of the first value and the enabled N bits in the one or more registers.   
   
   
       15 . The method as recited in  claim 10 , further comprising:
 generating the third value based upon the Boolean AND of the second value and a sum of an inverted version of the second value and a 1-bit left-rotated version of the first value.   
   
   
       16 . The method as recited in  claim 10 , wherein the third value comprises N bits corresponding to the N requestors and wherein only one of the N bits corresponding to the next selected one of the N requesters is true. 
   
   
       17 . The method as recited in  claim 10 , wherein the N requestors comprise N thread contexts in a multithreading microprocessor each requesting a dispatch scheduler to dispatch an instruction of the thread context to at least one execution pipeline of the microprocessor. 
   
   
       18 . A computer-readable storage medium having computer program code embodied thereon that generates a microprocessor having N requesters of a shared resource that selects one of the N requestors of the shared resource in a round-robin fashion, wherein one or more of the N requestors may be disabled from being selected in a selection cycle, the computer program code comprising:
 first program code for providing a first input, for receiving a first value specifying which of the N requestors was last selected;   second program code for providing a second input, for receiving a second value specifying which of the N requesters is enabled to be selected;   third program code for storing N bit values in one or more registers, each bit corresponding to one of the N requestors and each bit enabled in accordance with an enabled state of the corresponding requester and a selected state of the corresponding requestor; and   fourth program code for generating a third value based on the N bit values in the one or more registers, specifying which of the N requestors is selected next.   
   
   
       19 . The computer program code embodied on a computer-readable storage medium as recited in  claim 18 , wherein the first value comprises N bits corresponding to the N requesters and wherein only one of the N bits corresponding to the last selected requestor has a value of true. 
   
   
       20 . The computer program code embodied on a computer-readable storage medium as recited in  claim 18 , wherein the second value comprises N bits corresponding to the N requesters and wherein each of the N bits whose corresponding requestor is enabled has a value of false. 
   
   
       21 . The computer program code embodied on a computer-readable storage medium as recited in  claim 18 , further comprising fifth program code for setting each of the N bits in the one or more registers to enabled for each corresponding N requestor that is not enabled and was not last selected. 
   
   
       22 . The fifth program code as recited in  claim 21 , further comprising code for generating the third value based upon the Boolean AND of the second value and a sum of a 1-bit left-rotated version of the first value and the enabled N bits in the one or more registers. 
   
   
       23 . The computer program code embodied on a computer-readable storage medium as recited in  claim 18 , further comprising fifth program code for generating the third value based upon the Boolean AND of the second value and a sum of an inverted version of the second value and a 1-bit left-rotated version of the first value. 
   
   
       24 . The computer program code embodied on a computer-readable storage medium as recited in  claim 18 , wherein the third value comprises N bits corresponding to the N requesters and wherein only one of the N bits corresponding to the next selected one of the N requesters has a value of true. 
   
   
       25 . The computer program code embodied on a computer-readable storage medium as recited in  claim 18 , wherein the N requesters comprise N thread contexts in a multithreading microprocessor each requesting a dispatch scheduler to dispatch an instruction of the thread context to at least one execution pipeline of the microprocessor.