Register allocation for clustered multi-level register files

Patent metadata

Field	Value
Publication number	US-9229717-B2
Application number	US-201213710909-A
Country	US
Kind code	B2
Filing date	Dec 11, 2012
Priority date	Dec 11, 2012
Publication date	Jan 5, 2016
Grant date	Jan 5, 2016

Abstract

A method for allocating registers within a processing unit. A compiler assigns a plurality of instructions to a plurality of processing clusters. Each instruction is configured to access a first virtual register within a live range. The compiler determines which processing cluster in the plurality of processing clusters is an owner cluster for the first virtual register within the live range. The compiler configures a first instruction included in the plurality of instructions to access a first global virtual register.

First claim

The claimed invention is:

1. A method of allocating registers within a processing unit, the method comprising:
assigning a plurality of instructions to a plurality of processing clusters, wherein each instruction is configured to access a first virtual register within a live range;
determining which processing cluster in the plurality of processing clusters is an owner cluster for the first virtual register within the live range; and
configuring a first instruction included in the plurality of instructions to access a first global virtual register, wherein the first instruction is assigned to the owner cluster.

2. The method of claim 1 , wherein the first instruction is configured to implement a write operation to the first virtual register.

3. The method of claim 2 , wherein:
the first instruction has a corresponding location in a program control flow; and
configuring the first instruction comprises:
determining that an instruction assigned to a non-owner cluster is configured to implement a read operation from the first virtual register; and
inserting a copy instruction after the corresponding location in the program control flow of the first instruction, wherein the copy instruction is configured to implement a copy operation that copies a value in the first virtual register to the first global virtual register.

4. The method of claim 1 , wherein the first instruction is configured to implement a write operation to the first virtual register and is assigned to a non-owner cluster.

5. The method of claim 4 , wherein:
the first instruction has a corresponding location in a program control flow; and
configuring the first instruction comprises:
configuring the first instruction to implement a write operation to a second virtual register;
inserting a first copy instruction after the corresponding location in the program control flow of the first instruction, wherein the first copy instruction is configured to implement a copy operation that copies a value in the second virtual register to the first global virtual register; and
inserting a second copy instruction, after the first copy instruction, wherein the second copy instruction is configured to implement a copy operation that copies a value in the first global virtual register to the first virtual register.

6. The method of claim 1 , wherein the first instruction is configured to implement a read operation from the first virtual register and is assigned to a non-owner cluster.

7. The method of claim 6 , wherein configuring the first instruction comprises:
determining that there is only one read instruction that is configured to implement a read operation from the first virtual register and that is assigned to the non-owner cluster in the live range; and
configuring the first instruction to implement a read operation from the first global virtual register.

8. The method of claim 6 , wherein:
the first instruction has a corresponding location in a program control flow; and
configuring the first instruction comprises:
determining that there is a plurality of read instructions that are configured to read from the first virtual register in the live range and that are assigned to the non-owner cluster;
inserting a first copy instruction before the corresponding location in the program control flow of the first instruction, wherein the first copy instruction is configured to copy a value in the first global register to a second virtual register; and
configuring the plurality of read instructions to implement a read operation from the second virtual register.

9. The method of claim 1 , further comprising allocating the first virtual register to a physical register in the owner cluster.

10. A non-transitory computer-readable medium storing instructions, that when executed by a processor, cause a computer system to allocate registers within a processing unit, by performing the steps of:
assigning a plurality of instructions to a plurality of processing clusters, wherein each instruction is configured to access a first virtual register within a live range;
determining which processing cluster in the plurality of processing clusters is an owner cluster for the first virtual register within the live range; and
configuring a first instruction included in the plurality of instructions to access a first global virtual register, wherein the first instruction is assigned to the owner cluster.

11. The non-transitory computer-readable medium of claim 10 , wherein the first instruction is configured to implement a write operation to the first virtual register.

12. The non-transitory computer-readable medium of claim 11 , wherein:
the first instruction has a corresponding location in a program control flow; and
configuring the first instruction comprises:
determining that an instruction assigned to a non-owner cluster is configured to implement a read operation from the first virtual register; and
inserting a copy instruction after the corresponding location in the program control flow of the first instruction, wherein the copy instruction is configured to implement a copy operation that copies a value in the first virtual register to the first global virtual register.

13. The non-transitory computer-readable medium of claim 10 , wherein the first instruction is configured to implement a write operation to the first virtual register and is assigned to a non-owner cluster.

14. The non-transitory computer-readable medium of claim 13 , wherein:
the first instruction has a corresponding location in a program control flow; and
configuring the first instruction comprises:
configuring the first instruction to implement a write operation to a second virtual register;
inserting a first copy instruction after the corresponding location in the program control flow of the first instruction, wherein the first copy instruction is configured to implement a copy operation that copies a value in the second virtual register to the first global virtual register; and
inserting a second copy instruction, after the first copy instruction, wherein the second copy instruction is configured to implement a copy operation that copies a value in the first global virtual register to the first virtual register.

15. The non-transitory computer-readable medium of claim 10 , wherein the first instruction is configured to implement a read operation from the first virtual register and is assigned to a non-owner cluster.

16. The non-transitory computer-readable medium of claim 15 , wherein configuring the first instruction comprises:
determining that there is only one read instruction that is configured to implement a read operation from the first virtual register and that is assigned to the non-owner cluster in the live range; and
configuring the first instruction to implement a read operation from the first global virtual register.

17. The non-transitory computer-readable medium of claim 15 , wherein:
the first instruction has a corresponding location in a program control flow; and
configuring the first instruction comprises:
determining that there is a plurality of read instructions that are configured to read from the first virtual register in the live range and that are assigned to the non-owner cluster;
inserting a first copy instruction before the corresponding location in the program control flow of the first instruction, wherein the first copy instruction is configured to copy a value in the first global register to a second virtual register; and
configuring the plurality of read instructions to implement a read ope

Assignees

• Nvidia Corp

Inventors

• Mehrara Mojtaba
• Diamos Gregory

Classifications

• G06F9/3012 Primary

  Organisation of register space, e.g. banked or distributed register file · CPC title

• G06F9/3891

  organised in groups of units sharing resources, e.g. clusters · CPC title

• G06F9/30138

  Extension of register space, e.g. register cache · CPC title

• G06F9/30098 Primary

  Register arrangements · CPC title