Fetch director employing barrel-incrementer-based round-robin apparatus for use in multithreading microprocessor
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 adds a first addend to a 1-bit left-rotated version of a second addend to generate a sum and a carry-out bit. The circuit includes the carry-out bit as a carry-in bit of the add to generate the sum. The sum 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 fetch addresses associated with N corresponding threads for providing to an instruction cache for fetching instructions therefrom in a multithreading microprocessor that concurrently executes the N threads, wherein a subset of the N threads may request to fetch instructions in a selection cycle, the apparatus comprising:
a first input, for receiving a first corresponding N-bit value specifying which of the N threads was last selected to fetch instructions, wherein only one of said N bits of said first value corresponding to said last selected thread is true;
a second input, for receiving a second corresponding N-bit value, each of said N bits of said second value being false if said corresponding one of the N threads is requesting to fetch instructions;
a barrel incrementer, coupled to said first and second inputs, configured to add said second value to a 1-bit left-rotated version of said first value to generate a sum and a carry-out bit, wherein said barrel incrementer includes said carry-out bit as a carry-in bit of the add to generate the sum; and
combinational logic, coupled to said barrel incrementer, configured to generate a third corresponding N-bit value specifying which of the N threads is selected next to fetch instructions, said third value comprising a Boolean AND of said sum and an inverted version of said second value, wherein only one of said N bits of said third value corresponding to said next selected one of the N threads is true.
2. The apparatus as recited in claim 1 , wherein a thread refrains from requesting to fetch instructions if an instruction buffer into which the instructions are to be written is full.
3. The apparatus as recited in claim 1 , wherein thread refrains from requesting to fetch instructions if the thread is not enabled for execution.
4. The apparatus as recited in claim 1 , wherein thread refrains from requesting to fetch instructions if the thread caused a miss in the instruction cache and the missing data has not yet been filled in the instruction cache.
5. The apparatus as recited in claim 1 , wherein the N fetch addresses are provided by N program counter registers associated with corresponding ones of the N threads.
6. The apparatus as recited in claim 5 , further comprising:
a 1-hot mux, having a first N inputs coupled to receive the N fetch addresses from the respective N program counter registers, and having a second N control inputs for receiving said N bits of said third value, wherein said 1-hot mux selects for output one of said first N inputs corresponding to said true one of said N bits of said third value.
7. The apparatus as recited in claim 1 , further comprising:
an N-bit storage element, coupled to receive from said combinational logic said third value at a first time, and configured to store said third value, and coupled to provide said third value on said first input at a second time subsequent to said first time.
8. The apparatus as recited in claim 7 , wherein said storage element is updated only when instructions are actually fetched from the instruction cache for execution in response to one of said N fetch addresses.
9. The apparatus as recited in claim 1 , wherein said barrel incrementer comprises:
a plurality of adders, rotatively coupled in series, configured to add said second value to said 1-bit left-rotated version of said first value to generate said sum.
10. The apparatus as recited in claim 9 , wherein said plurality of adders are configured to add said 1-bit left-rotated version of said first value to said second value Boolean ANDed with an inverted version of said first value.
11. The apparatus as recited in claim 10 , wherein said plurality of adders comprises N 1-bit adders corresponding to the N threads, rotatively coupled in series, each having first and second addend inputs, a carry-in input, a sum output, and a carry-out output, wherein said first addend input is coupled to receive said corresponding one of said N bits of said first value left rotated 1-bit, wherein said second addend input is coupled to receive said corresponding one of said N bits of said second value Boolean ANDed with an inverted version of said corresponding one of said N bits of said first value, wherein said carry-in input is coupled to receive said carry-out output of a rotatively right adjacent one of said N 1-bit adders in said series.
12. The apparatus as recited in claim 11 , wherein each of said N 1-bit adders comprises:
an OR gate, having first and second inputs and an output, said OR gate first input comprising said first addend input of said 1-bit adder, said OR gate second input comprising said carry-in input of said 1-bit adder; and
a half-adder, having an addend input, a carry-in input, a sum output, and a carry-out output, said addend input comprising said second addend input of said 1-bit adder, said carry-in input coupled to receive said OR gate output, said sum output comprising said sum output of said 1-bit adder, and said carry-out output comprising said carry-out output of said 1-bit adder.
13. The apparatus as recited in claim 1 , wherein said barrel incrementer 1-bit left-rotatively increments said second value by said first value to generate said sum according to the following equation:
{ Cout.i, Sum.i}=A.i +( B.i OR Cin.i ),
wherein said A.i comprises one of said N bits of said second value,
wherein said B.i comprises a 1-bit left rotated corresponding one of said N bits of said first value,
wherein said Sum.i comprises a binary sum of said A.i+(B.i OR Cin.i),
wherein said Cout.i comprises a carry out of said A.i+(B.i OR Cin.i),
wherein said Cin.i=said Cout.i−1,
wherein Cin.0=Cout.N−1.
14. The apparatus as recited in claim 1 , wherein said barrel incrementer 1-bit left-rotatively increments said second value by said first value to generate said sum according to the following equation:
{ Cout.i, Sum.i}=A.i+B.i+Cin.i,
wherein said A.i comprises one of said N bits of said second value,
wherein said B.i comprises a 1-bit left rotated corresponding one of said N bits of said first value,
wherein said Sum.i comprises a binary sum of said A.i+B.i+Cin.i,
wherein said Cout.i comprises a carry out of said A.i+B.i+Cin.i,
wherein said Cin.i=said Cout.i−1,
wherein Cin.0=Cout.N−1.
15. The apparatus as recited in claim 1 , wherein said barrel incrementer comprises:
first and second rows of adders, coupled in series, said first row configured to add said second value to a 1-bit left-shifted version of said first value to generate an intermediate sum, said second row configured to add said intermediate sum and a carry-out bit thereof to a left-most bit of said first value.
16. The apparatus as recited claim 15 , wherein a zero bit is shifted into a right-most bit of said 1-bit left-shifted version of said first value.
17. The apparatus as recited in claim 15 ,
wherein said first row of adders comprises N 1-bit adders coupled in series, each having first and second addend inputs, a carry-in input, a sum output, and a carry-out output, wherein said first addend input is coupled to receive said corresponding one of said N bits of said first value left-shifted 1-bit, wherein said second addend input is coupled to receive said corresponding one of said N bits of said second value, wherein said carry-in input is coupled to receive said carry-out output of a right adjacent one of said first row 1-bit adders, wherein said carry-in input and said first addend input of a right-most one of said first row 1-bit adders are configured to receive a zero bit, wherein said sum output is configured to convey a corresponding bit of said intermediate sum;
wherein said second row of adders comprises N 1-bit adders coupled in series, each having first and second addend inputs, a carry-in input, a sum output, and a carry-out output, wherein said first addend input is coupled to receive a zero bit except for a right-most one of said second row 1-bit adders that is coupled to receive a left-most bit of said first value, wherein said second addend input is coupled to receive said corresponding bit of said intermediate sum, wherein said carry-in input is coupled to receive said carry-out output of a right adjacent one of said second row 1-bit adders except a right-most one of said second row 1-bit adders that is coupled to receive said carry-out output of a left-most one of said first row 1-bit adders, wherein said sum output is configured to convey a corresponding bit of said sum of said barrel incrementer.
18. The apparatus as recited in claim 17 , wherein each of said first row N 1-bit adders comprises:
an OR gate, having first and second inputs and an output, said OR gate first input comprising said first addend input of said 1-bit adder, said OR gate second input comprising said carry-in input of said 1-bit adder; and
a half-adder, having an addend input, a carry-in input, a sum output, and a carry-out output, said addend input comprising said second addend input of said 1-bit adder, said carry-in input coupled to receive said OR gate output, said sum output comprising said sum output of said 1-bit adder, and said carry-out output comprising said carry-out output of said 1-bit adder.
19. The apparatus as recited in claim 18 , wherein each of said second row N 1-bit adders comprises:
a half-adder, having an addend input, a carry-in input, a sum output, and a carry-out output, said addend input coupled to receive said sum output of a corresponding one of said first row 1-bit adders, said carry-in input comprising said carry-in input of said 1-bit adder, said sum output comprising said sum output of said 1-bit adder, and said carry-out output comprising said carry-out output of said 1-bit adder;
wherein a right-most one of said second row N 1-bit adders further comprises an OR gate, coupled to receive said left-most bit of said second value and said carry-out bit of a left-most one of said first row of half-adders and to provide its output on said carry-in input of a right-most one of said second row of half-adders.
20. The apparatus as recited in claim 1 , wherein a computer program product comprising a computer usable medium having computer readable program code causes the apparatus, wherein said computer program product is for use with a computing device.
21. The apparatus as recited in claim 1 , wherein a computer data signal embodied in a transmission medium comprising computer-readable program code provides the apparatus.
22. A method for selecting one of N fetch addresses associated with N corresponding threads for providing to an instruction cache for fetching instructions therefrom in a multithreading microprocessor that concurrently executes the N threads, wherein a subset of the N threads may request to fetch instructions in a selection cycle, the method comprising:
receiving a first corresponding N-bit value specifying which of the N threads was last selected to fetch instructions, wherein only one of the N bits of the first value corresponding to the last selected thread is true;
receiving a second corresponding N-bit value, each of the N bits of the second value being false if the corresponding one of the N threads is requesting to fetch instructions;
adding the second value to a 1-bit left-rotated version of the first value to generate a sum and a carry-out bit, wherein said adding includes the carry-out bit as a carry-in bit to generate the sum; and
generating a third corresponding N-bit value specifying which of the N threads is selected next to fetch instructions, the third value comprising a Boolean AND of the sum and an inverted version of the second value, wherein only one of the N bits of the third value corresponding to the next selected one of the N threads is true.
23. The method as recited in claim 22 , further comprising:
for each of the N threads, requesting to fetch instructions only if an instruction buffer into which the instructions are to be written is non-full.
24. The method as recited in claim 22 , further comprising:
for each of the N threads, requesting to fetch instructions only if the thread is enabled for execution.
25. The method as recited in claim 22 , further comprising:
selecting one of the N fetch addresses corresponding to a true one of the N bits of the third value for providing to the instruction cache for fetching instructions therefrom.
26. The method as recited in claim 22 , further comprising:
storing the third value at a first time; and
providing the stored third value as the first value for generating a new third value specifying which of the N threads is selected next at a second time subsequent to said first time.
27. 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 fetch addresses associated with N corresponding threads for providing to an instruction cache for fetching instructions therefrom in a multithreading microprocessor that concurrently executes the N threads, wherein a subset of the N threads may request to fetch instructions in a selection cycle, said computer readable program code comprising:
first program code for providing a first input, for receiving a first corresponding N-bit value specifying which of the N threads was last selected to fetch instructions;
second program code for providing a second input, for receiving a second corresponding N-bit value, wherein each of said N bits of said second value is false if said corresponding one of the N threads is requesting to fetch instructions;
third program code for providing a barrel incrementer, coupled to said first and second inputs, configured to add said second value to a 1-bit left-rotated version of said first value to generate a sum and a carry-out bit, wherein said barrel incrementer includes said carry-out bit as a carry-in bit of the add to generate the sum; and
fourth program code for providing combinational logic, coupled to said barrel incrementer, configured to generate from said sum and said second value a third corresponding N-bit value specifying which of the N threads is selected next to fetch instructions, wherein said third value comprises a Boolean AND of said sum and an inverted version of said second value.
28. The computer program product of claim 27 , wherein said computer readable program code further comprises:
fifth program code for providing a 1-hot mux, having a first N inputs coupled to receive the N fetch addresses from N respective program counter registers, and having a second N control inputs for receiving said N bits of said third value, wherein said 1-hot mux selects for output one of said first N inputs corresponding to said true one of said N bits of said third value.
29. The computer program product of claim 27 , wherein said computer readable program code further comprises:
fifth program code for providing an N-bit storage element, coupled to receive from said combinational logic said third value at a first time, and configured to store said third value, and coupled to provide said third value on said first input at a second time subsequent to said first time.
30. The computer program product of claim 27 , wherein only one of said N bits of said first value corresponding to said last selected thread is true.
31. The computer program product of claim 27 , wherein only one of said N bits of said third value corresponding to said next selected one of the N threads is true.
32. An apparatus for selecting one of N fetch addresses associated with N corresponding threads for providing to an instruction cache for fetching instructions therefrom in a multithreading microprocessor that concurrently executes the N threads, wherein a subset of the N threads may request to fetch instructions in a selection cycle, the apparatus comprising:
a first input, for receiving a first corresponding N-bit value specifying which of the N threads was last selected to fetch instructions;
a second input, for receiving a second corresponding N-bit value, wherein each of said N bits of said second value is false if said corresponding one of the N threads is requesting to fetch instructions;
a barrel incrementer, coupled to said first and second inputs, configured to add said second value to a 1-bit left-rotated version of said first value to generate a sum and a carry-out bit, wherein said barrel incrementer includes said carry-out bit as a carry-in bit of the add to generate the sum; and
combinational logic, coupled to said barrel incrementer, configured to generate from said sum and said second value a third corresponding N-bit value specifying which of the N threads is selected next to fetch instructions, wherein said third value comprises a Boolean AND of said sum and an inverted version of said second value.
33. The apparatus of claim 32 , wherein only one of said N bits of said first value corresponding to said last selected thread is true.
34. The apparatus of claim 32 , wherein only one of said N bits of said third value corresponding to said next selected one of the N threads is true.
35. A method for selecting one of N fetch addresses associated with N corresponding threads for providing to an instruction cache for fetching instructions therefrom in a multithreading microprocessor that concurrently executes the N threads, wherein a subset of the N threads may request to fetch instructions in a selection cycle, the method comprising:
receiving a first corresponding N-bit value specifying which of the N threads was last selected to fetch instructions;
receiving a second corresponding N-bit value, wherein each of the N bits of said second value is false if the corresponding one of the N threads is requesting to fetch instructions;
adding the second value to a 1-bit left-rotated version of the first value to generate a sum and a carry-out bit, wherein said adding includes the carry-out bit as a carry-in bit to generate the sum; and
generating from the sum and the second value a third corresponding N-bit value specifying which of the N threads is selected next to fetch instructions, wherein the third value comprises a Boolean AND of the sum and an inverted version of the second value.
36. The method of claim 35 , wherein only one of the N bits of said first value corresponding to the last selected thread is true.
37. The method of claim 35 , wherein only one of the N bits of said third value corresponding to the next selected one of the N threads is true.