Thread instruction fetch based on prioritized selection from plural round-robin outputs for different thread states
View Patent ↗A fetch director in a multithreaded microprocessor that concurrently executes instructions of N threads is disclosed. The N threads request to fetch instructions from an instruction cache. In a given selection cycle, some of the threads may not be requesting to fetch instructions. The fetch director includes a circuit for selecting one of threads in a round-robin fashion to provide its fetch address to the instruction cache. The circuit 1-bit left rotatively increments a first addend by a second addend to generate a sum that is ANDed with the inverse of the first addend to generate a 1-hot vector indicating which of the threads is selected next. The first addend is an N-bit vector where each bit is false if the corresponding thread is requesting to fetch instructions from the instruction cache. The second addend is a 1-hot vector indicating the last selected thread. In one embodiment threads with an empty instruction buffer are selected at highest priority; a last dispatched but not fetched thread at middle priority; all other threads at lowest priority. The threads are selected round-robin within the highest and lowest priorities.
1. An apparatus for selecting one of N threads for fetching instructions into N respective instruction buffers from an instruction cache in a multithreading microprocessor that concurrently executes the N threads, the apparatus comprising:
a first round-robin generator, having a circuit configured to
receive a first N-bit value specifying which of the N threads was last selected to fetch instructions and a second N-bit value specifying if a corresponding one of the N threads is enabled for fetching and has an empty instruction buffer; and
generate a first round-robin indicator indicating a next one of the N threads in round-robin order which is enabled for fetching and has an empty instruction buffer;
a second round-robin generator, having a circuit configured to
receive a first N-bit value specifying which of the N threads was last selected to fetch instructions and a second N-bit value specifying if a corresponding one of the N threads is enabled for fetching; and
generate a second round-robin indicator indicating a next one of the N threads in round-robin order which is enabled for fetching; and
a multiplexer, coupled to receive said first and second indicators and a selection control fetch priority signal generated by control logic, and configured:
to output said first indicator if at least one of the N threads is enabled for fetching and has an empty instruction buffer; and
to output said second indicator otherwise;
wherein said output indicates which of the N threads is selected for fetching instructions.
2. The apparatus as recited in claim 1 , further comprising:
a third indicator, for indicating one of the N threads, if any, which is enabled for fetching, was last selected for dispatching an instruction for execution, and was not last selected for fetching;
wherein said multiplexer is further coupled to receive said third indicator, and configured:
to output said first indicator if at least one of the N threads is enabled for fetching and has an empty instruction buffer;
to output said third indicator if none of the N threads is enabled for fetching and has an empty instruction buffer, and one of the N threads is enabled for fetching, was last selected for dispatching an instruction for execution, and was not last selected for fetching; and
to output said second indicator otherwise.
3. The apparatus as recited in claim 1 , further comprising:
a second multiplexer, coupled to receive said output of said first multiplexer as a select control input, further coupled to receive N fetch addresses of the respect N threads, and to select one of said N fetch addresses indicated by said output for provision as a fetch address to an instruction cache of the microprocessor for fetching instructions there from.
4. The apparatus as recited in claim 1 , wherein one of the N threads is disabled for fetching if its respective instruction buffer is full.
5. The apparatus as recited in claim 1 , wherein one of the N threads is disabled for fetching if the thread is disabled for execution.
6. The apparatus as recited in claim 1 , wherein one of the N threads is disabled for fetching if the thread caused a miss in the instruction cache and the missing data has not yet been filled in the instruction cache.
7. The apparatus as recited in claim 1 , wherein said first round-robin generator comprises:
a first input, for receiving said first corresponding N-bit value specifying which of the N threads was last selected to fetch instructions, wherein only one of said N bits corresponding to said last selected thread is true;
a second input, for receiving said second corresponding N-bit value, each of said N bits being false if said corresponding one of the N threads is enabled for fetching and has an empty instruction buffer;
a barrel incrementer, coupled to receive said first and second inputs, configured to 1-bit left-rotatively increment said second value by said first value to generate a sum; and
combinational logic, coupled to said barrel incrementer, configured to generate said first round-robin indicator, said first round-robin indicator comprising a Boolean AND of said sum and an inverted version of said second value, wherein only one of said N bits is true.
8. The apparatus as recited in claim 1 , wherein said second round-robin generator comprises:
a first input, for receiving said first corresponding N-bit value specifying which of the N threads was last selected to fetch instructions, wherein only one of said N bits corresponding to said last selected thread is true;
a second input, for receiving said second corresponding N-bit value, each of said N bits being false if said corresponding one of the N threads is enabled for fetching;
a barrel incrementer, coupled to receive said first and second inputs, configured to 1-bit left-rotatively increment said second value by said first value to generate a sum; and
combinational logic, coupled to said barrel incrementer, configured to generate said second round-robin indicator, said second round-robin indicator comprising a Boolean AND of said sum and an inverted version of said second value, wherein only one of said N bits is true.
9. A method for selecting one of N threads for fetching instructions into N respective instruction buffers from an instruction cache in a multithreading microprocessor that concurrently executes the N threads, the method comprising:
generating a first round-robin indicator based on a first N-bit value specifying which of the N threads was last selected to fetch instructions and a second N-bit value specifying if a corresponding one of the N threads is enabled for fetching and has an empty instruction buffer, the first round-robin indicator indicating a next one of the N threads in round-robin order which is enabled for fetching and has an empty instruction buffer;
generating a second round-robin indicator based on a first N-bit value specifying which of the N threads was last selected to fetch instructions and a second N-bit value specifying if a corresponding one of the N threads is enabled for fetching, the second round-robin indicator indicating a next one of the N threads in round-robin order which is enabled for fetching;
receiving a selection control fetch priority signal generated by control logic; and
outputting the first indicator if at least one of the N threads is enabled for fetching and has an empty instruction buffer, and otherwise outputting the second indicator, to indicate which of the N threads is selected for fetching instructions.
10. The method as recited in claim 9 , further comprising:
generating a third indicator indicating one of the N threads, if any, which is enabled for fetching, was last selected for dispatching an instruction for execution, and was not last selected for fetching; and
outputting the first indicator if at least one of the N threads is enabled for fetching and has an empty instruction buffer;
outputting the third indicator if none of the N threads is enabled for fetching and has an empty instruction buffer, and one of the N threads is enabled for fetching, was last selected for dispatching an instruction for execution, and was not last selected for fetching; and
outputting the second indicator otherwise.
11. The method as recited in claim 9 , further comprising:
selecting one of N fetch addresses of the respective N threads indicated by said outputting for provision as a fetch address to an instruction cache of the microprocessor for fetching instructions therefrom.
12. A computer program product for use with a computing device, the computer program product comprising:
a computer usable medium, having computer readable program code embodied in said medium, for causing an apparatus for selecting one of N threads for fetching instructions into N respective instruction buffers from an instruction cache in a multithreading microprocessor that concurrently executes the N threads, said computer readable program code comprising:
first program code for providing a first round-robin generator, configured to generate a first round-robin indicator based on a first N-bit value specifying which of the N threads was last selected to fetch instructions and a second N-bit value specifying if a corresponding one of the N threads is enabled for fetching and has an empty instruction buffer, the first round-robin indicator indicating a next one of the N threads in round-robin order which is enabled for fetching and has an empty instruction buffer;
second program code for providing a second round-robin generator, configured to generate a second round-robin indicator based on a first N-bit value specifying which of the N threads was last selected to fetch instructions and a second N-bit value specifying if a corresponding one of the N threads is enabled for fetching, the second round-robin indicator indicating a next one of the N threads in round-robin order which is enabled for fetching; and
third program code for providing a multiplexer, coupled to receive said first and second indicators and a selection control fetch priority signal generated by control logic, and configured to output said first indicator if at least one of the N threads is enabled for fetching and has an empty instruction buffer, and to output said second indicator otherwise, wherein said output indicates which of the N threads is selected for fetching instructions.
13. The computer program product of claim 12 , wherein said computer readable program code further comprises:
fourth program code for providing a third indicator, for indicating one of the N threads, if any, which is enabled for fetching, was last selected for dispatching an instruction for execution, and was not last selected for fetching;
wherein said multiplexer is further coupled to receive said third indicator, and configured to output said first indicator if at least one of the N threads is enabled for fetching and has an empty instruction buffer; to output said third indicator if none of the N threads is enabled for fetching and has an empty instruction buffer, and one of the N threads is enabled execution, and was not last selected for fetching; and to output said second indicator otherwise.