Circuit and method for dynamic register allocation for a graphics processing unit

1 . A dynamic register allocation circuit for a graphics processing unit, comprising:

receiving circuitry for receiving a binary vector having a length of M bits, the binary vector indicating one or more available blocks of memory in a register file memory;

performing circuitry to perform a parallel prefix scanning method to identify positions of high bits in-order within the binary vector to search for the one or more available blocks of memory in the register file memory and generate an allocation state for a warp; and

decoding circuitry to decode the allocation state into entries for a lookup table used to generate memory addresses of available blocks of register file memory.

2 . The dynamic register allocation circuit of claim 1 , further comprising:

searching circuitry to search the binary vector for N available blocks of memory from the one or more available blocks of memory in the register file memory to generate an allocation state for a warp.

3 . The dynamic register allocation circuit of claim 1 , wherein the allocation state is a bitmask comprising an encoded vector indicating positions of high bits in-order within the bitmask from least significant to most significant.

4 . The dynamic register allocation circuit of claim 1 , wherein the length of M bits is in a range of 16-64 bits.

5 . The dynamic register allocation circuit of claim 1 , wherein the performing circuitry comprises:

scanning circuitry to scan the binary vector for high bits in-order by performing group functions on a corresponding group of bits of the binary vector for groups of bits in the binary vector using logic of a parallel prefix tree to produce a group result for each group function performed;

combining circuitry to combine the group result for each group function to produce a parallel prefix tree output; and

encoded vector generation circuitry to combine the parallel prefix tree output with the binary vector to generate an encoded vector indicating positions of the high bits in-order with the binary vector.

6 . The dynamic register allocation circuit of claim 5 , wherein each group function includes a Boolean expression implemented with logical operators to calculate a number of high bits in the group of bits.

7 . The dynamic register allocation circuit of claim 5 , wherein the parallel prefix tree is a Sklansky tree.

8 . A method for dynamic register allocation for a graphics processing unit, comprising:

receiving a binary vector having a length of M bits, the binary vector indicating one or more available blocks of memory in a register file memory;

performing a parallel prefix scanning method to identify positions of high bits in-order within the binary vector to search for the one or more available blocks of memory in the register file memory and generate an allocation state for a warp; and

decoding the allocation state into entries for a lookup table used to generate memory addresses of available blocks of register file memory.

9 . The method of claim 8 , wherein performing the parallel prefix scanning method to identify positions of high bits in-order with the binary vector comprises:

scanning the binary vector for high bits in order by performing a group function on a corresponding group of bits of the binary vector for groups of bits of the binary vector using logic of a parallel prefix tree to produce a group result for each group function performed,

combining the group result for each group function to produce a parallel prefix tree output, and

combining the parallel prefix tree output with the binary vector to generate the allocation state indicating positions of the high bits in-order.

10 . The method of claim 9 , wherein performing a group function on a corresponding group of bits of the binary vector for groups of bits includes:

performing calculations on the received binary vector to obtain a vector including a calculation of exactly 0 and exactly 1 (EX0, EX1) bits high for a single bit group, for all the bits of the binary vector;

distributing all of the bits of the binary vector into groups of bits; and

calculating group functions on the groups of bits to produce corresponding group results, each group result including a number of high bits in the corresponding group of bits.

11 . The method of claim 9 , wherein performing a group function on a corresponding group of bits of the binary vector for groups of bits includes:

performing calculations on the received binary vector to obtain a vector including a calculation of exactly 0, exactly 1, exactly 2, and exactly 3 (EX0, EX1, EX 2, EX3) bits high for a single bit group, for all the bits of the binary vector;

distributing all of the bits of the binary vector into groups of bits; and

calculating group functions on the groups of bits to produce corresponding group results, each group result including a number of high bits in the corresponding group of bits.

12 . The method of claim 9 , wherein combining the parallel prefix tree output with the binary vector comprises utilizing a bitwise AND.

13 . The method of claim 8 , wherein the allocation state is a bitmask comprising an encoded vector indicating positions of high bits in-order within the bitmask from least significant to most significant.

14 . The method of claim 13 , wherein decoding the allocation state into entries for the lookup table comprises populating the lookup table with a decoded value indicating a base address for a register block determined by a location of a high bit in the encoded vector from least significant to most significant starting at a lookup table row 0 up to row N−1.

15 . The method of claim 14 , wherein the decoding is performed in two or more cycles of execution by combining the decoded value for a first N entries with the binary vector to produce an output and processing the output in subsequent cycles.

16 . The method of claim 8 , wherein the method is performed in one cycle of execution when the warp is created.

17 . A parallel prefix circuit, comprising:

logic circuitry structured to form a parallel prefix tree that performs a plurality of group functions that each calculate a number of high bits of an input to produce an output, said logic circuitry further comprising:

receiving circuitry for receiving a binary vector having a length of M bits, the binary vector indicating one or more available blocks of memory in a register file memory;

performing circuitry to perform a parallel prefix scanning method to identify positions of high bits in-order within the binary vector to search for the one or more available blocks of memory in the register file memory and generate an allocation state for a warp; and

decoding circuitry to decode the allocation state into entries for a lookup table used to generate memory addresses of available blocks of register file memory.

18 . The parallel prefix circuit of claim 17 , the logic circuitry further comprising:

encoded vector generation circuitry to combine the output with the binary vector to generate an encoded vector indicating positions of the high bits in-order with the binary vector.

19 . The parallel prefix circuit of claim 17 , wherein the logic circuitry comprises AND gates and OR gates.

20 . The parallel prefix circuit of claim 17 , wherein the output is structured to be combined with the input and processed over subsequent cycles of execution.