# US 2017/0371653 A1 · System and method for scheduling instructions in a multithread simd architecture with a fixed number of registers

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2017/0371653 A1
- Document ID: US20170371653A1
- Status: Published application
- Kind: A1
- Application number: 15/191,374
- Filed: 2016-06-23
- Published: 2017-12-28
- Earliest claimed: 2016-06-23
- Assignees: Advanced Micro Devices, Inc.
- Applicants: Advanced Micro Devices, Inc.
- Inventors: Robert A. Gottlieb; Christopher L. Reeve; Michael John Bedy
- Web page: https://patentgrep.com/patent/US20170371653A1

## CPC

- G06F 15/8007: {single instruction multiple data [SIMD] multiprocessors}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A method and apparatus for scheduling instructions of a shader program for a graphics processing unit (GPU) with a fixed number of registers. The method and apparatus include computing, via a processing unit (PU), a liveness-based register usage across all basic blocks in the shader program, computing, via the PU, the range of numbers of waves of a plurality of registers for the shader program, assessing the impact of available post-register allocation optimizations, computing, via the PU, the scoring data based on number of waves of the plurality of registers, and computing, via the PU, the number of waves for execution for the plurality of registers.

## Claims

### Claim 1

A method for scheduling instructions of a shader program for a graphics processing unit (GPU) with a fixed number of registers, the method comprising:
computing, via a processing unit (PU), a live variable analysis of the registers used by a shader program;
computing, via the PU, a range of waves of the analyzed registers based on the live variable analysis of the registers;
assessing, via the PU, an impact of the computed range of waves based on the computed range of wave of the analyzed registers;
computing, via the PU, a score for the assessed impact of the computed range of waves; and
computing, via the PU, the number of waves to execute for the registers used by the shader program based on the computed score.

### Claim 2 (depends on 1)

The method of claim 1, wherein the live variable analysis of the registers used by a shader program includes a liveness-based register usage across all basic blocks in the shader program.

### Claim 3 (depends on 2)

The method of claim 2, wherein the computing a liveness-based register usage across all basic blocks in the shader program includes computing a minimum and maximum number of registers of the plurality of registers estimated for the shader program.

### Claim 4 (depends on 1)

The method of claim 1, wherein the range of waves of the analyzed registers includes a range of numbers of waves of a plurality of registers for the shader program based on the live variable analysis of the registers used by a shader program.

### Claim 5 (depends on 4)

The method of claim 4, wherein the computing the range of numbers of waves of the plurality of registers for the shader program includes computing a minimum number of waves of the plurality of registers and a maximum numbers of waves of the plurality of registers for the shader program.

### Claim 6 (depends on 1)

The method of claim 1, wherein the impact of the computed range of waves includes an impact of available post-register allocation optimizations based on the range of waves of the analyzed registers.

### Claim 7 (depends on 6)

The method of claim 6, wherein the assessing the impact of available post-register allocation optimizations includes computing a minimum number of waves of the plurality of registers for the shader program from the computed maximum number of registers of the plurality of registers.

### Claim 8 (depends on 1)

The method of claim 1, wherein the score for the assessed impact of the computed range of waves includes a scoring data based on the assessed impact of available post-register allocation optimizations.

### Claim 9 (depends on 8)

The method of claim 8, wherein the computing the scoring data based on number of waves of the plurality of registers includes choosing a best scheduling algorithm based on the scores including post-register allocation optimization and accumulate the information with the information for the number of waves of the plurality of registers for all blocks in the shader program.

### Claim 10 (depends on 1)

The method of claim 1, wherein the number of waves to execute for the registers used by the shader program based on the computed score includes a number of waves for the plurality of registers based on the computed scoring data.

### Claim 11 (depends on 10)

The method of claim 10, wherein the computing the number of waves of the plurality of registers includes choosing the number of waves, based on a best score for the accumulated data for the number of waves, and the best score for the accumulated data with post-register allocation optimizations, and choosing the number of registers of the plurality of registers used by the shader program based on the number of waves chosen.

### Claim 12 (depends on 1)

The method of claim 1, wherein the PU is one of a central processing unit (CPU) and a GPU.

### Claim 13

A graphics processor with optimized scheduling of instructions of a shader program, the scheduling of instructions optimized by:
computing, via a processing unit (PU), a live variable analysis of the registers used by a shader program;
computing, via the PU, a range of waves of the analyzed registers based on the computed live variable analysis;
assessing, via the PU, an impact of the computed range of waves based on the computed range of numbers of waves of the plurality of registers;
computing, via the PU, a score for the assessed impact of the computed range of waves; and
computing, via the PU, the number of waves to execute for the registers used by the shader program based on the computed score.

### Claim 14 (depends on 13)

The graphics processor of claim 13, wherein the computing a live variable analysis of the registers used by a shader program includes computing a minimum and maximum number of registers of the plurality of registers estimated for the shader program.

### Claim 15 (depends on 13)

The graphics processor of claim 13, wherein the a range of waves of the analyzed registers includes computing a minimum number of waves of the plurality of registers and a maximum numbers of waves of the plurality of registers for the shader program.

### Claim 16 (depends on 13)

The graphics processor of claim 13, wherein the assessing the impact of the computed range of waves includes computing a minimum number of waves of the plurality of registers for the shader program from the computed maximum number of registers of the plurality of registers.

### Claim 17 (depends on 13)

The graphics processor of claim 13, wherein the computing a score for the assessed impact of the computed range of waves includes choosing a best scheduling algorithm based on the scores including post-register allocation optimization and accumulate the information with the information for the number of waves of the plurality of registers for all basic blocks in the shader program.

### Claim 18 (depends on 13)

The graphics processor of claim 13, wherein the computing the number of waves to execute for the registers used by the shader program based on the computed score includes choosing the number of waves, based on a best score for the accumulated data for the number of waves, and the best score for the accumulated data with post-register allocation optimizations, and choosing the number of registers of the plurality of registers used by the shader program based on the number of waves chosen.

### Claim 19 (depends on 13)

The graphics processor of claim 13, wherein the PU is one of a central processing unit (CPU) and a GPU.
