Register allocation for message sends in graphics processing pipelines

• US 8,237,726 B2
• Filed: 06/26/2009
• Issued: 08/07/2012
• Est. Priority Date: 06/26/2009
• Status: Active Grant

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Chen, Wei-Yu, Lueh, Guei-Yuan
• Primary Examiner(s): Hsu, Joni
• Application Number:
  US12/492,500
• Publication Number:
  US 20100328334A1
• Time in Patent Office: 1,138 Days
• Field of Search: 345/426, 345/440, 345/501, 345/506, 345/522, 345/530, 345/543, 345/559
• US Class Current: 345/559
• CPC Class Codes: G06T 1/20 Processor architectures; Processor configuration, e.g. pipelining

Abstract

Message sends may be implemented in a graphics pipeline using biased graph coloring. Registers may be allocated by shaders for message sends using biased graph coloring.

Claims

1. A method comprising:

identifying live ranges of variables used in message sends for graphics processing;

modeling a plurality of physical registers and the live ranges in an interference graph;

bias coloring the interference graph based on preferred colors of the live ranges;

allocating the plurality of physical registers to the message sends based on the interference graph after bias coloring; and

identifying live ranges of variables used in message sends from shaders in a graphics pipeline.

2. The method of claim 1 including coalescing message sources with actual sources of a send instruction.

3. The method of claim 2 including favoring sources to be assigned to the same physical register as a corresponding message source.

4. The method of claim 1 including assigning the preferred colors to the live ranges without checking for interferences.

5. The method of claim 4 including resolving conflicts during the bias coloring.

6. The method of claim 1 including using heuristics to pick one of the plurality of physical registers to be a preferred color.

7. The method of claim 6 including using heuristics to pick the physical register with the most number of message sends.

8. The method of claim 1 including assigning colors to nodes with a preferred color first.

9. The method of claim 1 including avoiding the use of physical registers assigned to send sources for live ranges without a preferred color.

10. The method of claim 1 including avoiding assigning to a live range the preferred color of its neighbors.

11. An apparatus comprising:

a plurality of registers for message sends in a graphics pipeline; and

a shader to;

identify live ranges of variables used in the message sends,

model the plurality of physical registers and the live ranges in an interference graph,

bias coloring the interference graph based on preferred colors of the live ranges, and

allocate the plurality of physical registers to the message sends based on the interference graph after bias coloring.

12. The apparatus of claim 11, said shader to avoid the use of physical registers assigned to send sources for live ranges without a preferred color.

13. The apparatus of claim 11, said shader to coalesce message sources with actual sources of a send instruction.

14. The apparatus of claim 13, said shader to favor sources to be assigned to the same physical register as a corresponding message source.

15. The apparatus of claim 11, said shader to assign the preferred colors to the live ranges without checking for interferences.

16. The apparatus of claim 15, said shader to resolve conflicts during the bias coloring.

17. The apparatus of claim 11, said shader to use heuristics to pick one of the plurality of physical registers to be a preferred color.

18. The apparatus of claim 17, said shader to use heuristics to pick the physical register with the most number of message sends.

19. The apparatus of claim 11, said shader to assign colors to nodes with the preferred color first.