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

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.

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.