Patent Description:
Single-instruction multiple-data ("SIMD") processors achieve parallelization of execution by using a single control flow module with multiple items of data. It is possible for control flow to diverge when the control flow is dependent on the data, since different threads of execution can have different values for the data on which control flow depends. In such situations, the different control flow paths are serialized, resulting in a slowdown. <NPL>" and <CIT> relate to methods for reducing divergence of control flow in a single-instruction-multiple-data processor.

Described herein are techniques for reducing divergence of control flow in a single-instruction-multiple-data processor. The method includes, at a point of divergent control flow, identifying control flow targets for different execution items, sorting the execution items based on the control flow targets, reorganizing the execution items based on the sorting, and executing after the point of divergent control flow, with the reorganized execution items.

<FIG> is a block diagram of an example device <NUM> in which one or more features of the disclosure can be implemented. The device <NUM> includes, for example, a computer, a gaming device, a handheld device, a set-top box, a television, a mobile phone, or a tablet computer. The device <NUM> includes a processor <NUM>, a memory <NUM>, a storage <NUM>, one or more input devices <NUM>, and one or more output devices <NUM>. The device <NUM> also optionally includes an input driver <NUM> and an output driver <NUM>. It is understood that the device <NUM> includes additional components not shown in <FIG>.

In various alternatives, the processor <NUM> includes a central processing unit (CPU), a graphics processing unit (GPU), a CPU and GPU located on the same die, or one or more processor cores, wherein each processor core can be a CPU or a GPU. In various alternatives, the memory <NUM> is located on the same die as the processor <NUM>, or is located separately from the processor <NUM>. The memory <NUM> includes a volatile or non-volatile memory, for example, random access memory (RAM), dynamic RAM, or a cache.

The storage <NUM> includes a fixed or removable storage, for example, a hard disk drive, a solid state drive, an optical disk, or a flash drive. The input devices <NUM> include, without limitation, a keyboard, a keypad, a touch screen, a touch pad, a detector, a microphone, an accelerometer, a gyroscope, a biometric scanner, or a network connection (e.g., a wireless local area network card for transmission and/or reception of wireless IEEE <NUM> signals). The output devices <NUM> include, without limitation, a display device <NUM>, a speaker, a printer, a haptic feedback device, one or more lights, an antenna, or a network connection (e.g., a wireless local area network card for transmission and/or reception of wireless IEEE <NUM> signals).

The input driver <NUM> communicates with the processor <NUM> and the input devices <NUM>, and permits the processor <NUM> to receive input from the input devices <NUM>. The output driver <NUM> communicates with the processor <NUM> and the output devices <NUM>, and permits the processor <NUM> to send output to the output devices <NUM>. It is noted that the input driver <NUM> and the output driver <NUM> are optional components, and that the device <NUM> will operate in the same manner if the input driver <NUM> and the output driver <NUM> are not present. The output driver <NUM> includes an accelerated processing device ("APD") <NUM> which is coupled to a display device <NUM>. The APD <NUM> is configured to accept compute commands and graphics rendering commands from processor <NUM>, to process those compute and graphics rendering commands, and to provide pixel output to display device <NUM> for display. As described in further detail below, the APD <NUM> includes one or more parallel processing units configured to perform computations in accordance with a single-instruction-multiple-data ("SIMD") paradigm. Thus, although various functionality is described herein as being performed by or in conjunction with the APD <NUM>, in various alternatives, the functionality described as being performed by the APD <NUM> is additionally or alternatively performed by other computing devices having similar capabilities that are not driven by a host processor (e.g., processor <NUM>) and configured to provide (graphical) output to a display device <NUM>. For example, it is contemplated that any processing system that performs processing tasks in accordance with a SIMD paradigm can be configured to perform the functionality described herein.

<FIG> is a block diagram of the device <NUM>, illustrating additional details related to execution of processing tasks on the APD <NUM>, according to an example. The processor <NUM> maintains, in system memory <NUM>, one or more control logic modules for execution by the processor <NUM>. The control logic modules include an operating system <NUM>, a driver <NUM>, and applications <NUM>. These control logic modules control various features of the operation of the processor <NUM> and the APD <NUM>. For example, the operating system <NUM> directly communicates with hardware and provides an interface to the hardware for other software executing on the processor <NUM>. The driver <NUM> controls operation of the APD <NUM> by, for example, providing an application programming interface ("API") to software (e.g., applications <NUM>) executing on the processor <NUM> to access various functionality of the APD <NUM>. In some implementations, the driver <NUM> includes a just-in-time compiler that compiles programs for execution by processing components (such as the SIMD units <NUM> discussed in further detail below) of the APD <NUM>. In other implementations, no just-in-time compiler is used to compile the programs, and a normal application compiler compiles shader programs for execution on the APD <NUM>.

The APD <NUM> executes commands and programs for selected functions, such as graphics operations and non-graphics operations that are suited for parallel processing and/or non-ordered processing. The APD <NUM> is used for executing graphics pipeline operations such as pixel operations, geometric computations, and rendering an image to display device <NUM> based on commands received from the processor <NUM>. The APD <NUM> also executes compute processing operations that are not related, or not directly related to graphics operations, such as operations related to video, physics simulations, computational fluid dynamics, or other tasks, based on commands received from the processor <NUM>. The APD <NUM> also executes compute processing operations that are related to ray tracing-based graphics rendering.

The APD <NUM> includes compute units <NUM> that include one or more SIMD units <NUM> that perform operations at the request of the processor <NUM> in a parallel manner according to a SIMD paradigm. The SIMD paradigm is one in which multiple processing elements share a single program control flow unit and program counter and thus execute the same program but are able to execute that program with different data. In one example, each SIMD unit <NUM> includes sixteen lanes, where each lane executes the same instruction at the same time as the other lanes in the SIMD unit <NUM> but executes that instruction with different data. Lanes can be switched off with predication if not all lanes need to execute a given instruction. Predication can also be used to execute programs with divergent control flow. More specifically, for programs with conditional branches or other instructions where control flow is based on calculations performed by an individual lane, predication of lanes corresponding to control flow paths not currently being executed, and serial execution of different control flow paths allows for arbitrary control flow. In an implementation, each of the compute units <NUM> can have a local L1 cache. In an implementation, multiple compute units <NUM> share a L2 cache.

The basic unit of execution in compute units <NUM> is a work-item. Each work-item represents a single instantiation of a program that is to be executed in parallel in a particular lane. Work-items can be executed together as a "wavefront" on a single SIMD processing unit <NUM>. The SIMD nature of the SIMD processing unit <NUM> means that multiple work-items may execute in parallel simultaneously. Work-items that are executed together in this manner on a single SIMD unit are part of the same wavefront. In some implementations or modes of operation, a SIMD unit <NUM> executes a wavefront by executing each of the work-items of the wavefront simultaneously. In other implementations or modes of operation, a SIMD unit <NUM> executes different sub-sets of the work-items in a wavefront in parallel. In an example, a wavefront includes <NUM> work-items and the SIMD unit <NUM> has <NUM> lanes (where each lane is a unit of the hardware sized to execute a single work-item). In this example, the SIMD unit <NUM> executes the wavefront by executing <NUM> work-items simultaneously, <NUM> times.

One or more wavefronts are included in a "workgroup," which includes a collection of work-items designated to execute the same program. An application or other entity (a "host") requests that shader programs be executed by the accelerated processing device <NUM>, specifying a "size" (number of work-items), and the command processor <NUM> generates one or more workgroups to execute that work. The number of workgroups, number of wavefronts in each workgroup, and number of work-items in each wavefront correlates to the size of work requested by the host. In some implementations, the host may specify the number of work-items in each workgroup for a particular request to perform work, and this specification dictates the number of workgroups generated by the command processor <NUM> to perform the work. As stated above, the command processor <NUM> dispatches workgroups to one or more compute units <NUM>, which execute the appropriate number of wavefronts to complete the workgroups.

The parallelism afforded by the compute units <NUM> is suitable for graphics related operations such as pixel value calculations, vertex transformations, and other graphics operations. Thus in some instances, a graphics pipeline <NUM>, which accepts graphics processing commands from the processor <NUM>, provides computation tasks to the compute units <NUM> for execution in parallel.

In some implementations, the accelerated processing device <NUM> implements ray tracing, which is a technique that renders a 3D scene by testing for intersection between simulated light rays and objects in a scene. Much of the work involved in ray tracing is performed by programmable shader programs, executed on the SIMD units <NUM> in the compute units <NUM>. Although some of the teachings presented herein are described in the context of ray tracing work being performed on the APD <NUM>, it should be understood that various teachings presented herein may be applied in workloads other than ray tracing workloads.

<FIG> illustrates a ray tracing pipeline <NUM> for rendering graphics using a ray tracing technique, according to an example. The ray tracing pipeline <NUM> provides an overview of operations and entities involved in rendering a scene utilizing ray tracing. A ray generation shader <NUM>, any hit shader <NUM>, closest hit shader <NUM>, and miss shader <NUM> are shader-implemented stages that represent ray tracing pipeline stages whose functionality is performed by shader programs executing in the SIMD units <NUM>. Any of the specific shader programs at each particular shader-implemented stage are defined by application-provided code (i.e., by code provided by an application developer that is pre-compiled by an application compiler and/or compiled by the driver <NUM>). The ray trace stage <NUM> performs a ray intersection test to determine whether a ray hits a triangle. The ray trace stage <NUM> may be performed by a shader program executing in the SIMD units <NUM> or by fixed function hardware configured to perform ray intersection tests.

The various programmable shader stages (ray generation shader <NUM>, any hit shader <NUM>, closest hit shader <NUM>, miss shader <NUM>) are implemented as shader programs that execute on the SIMD units <NUM>. The command processor <NUM> orchestrates execution of the ray tracing pipeline <NUM>. Specifically, the command processor <NUM> is a programmable unit that executes instructions to cause the various stages of the ray tracing pipeline <NUM> to be performed on the APD <NUM>. Additional details are provided elsewhere herein.

The ray tracing pipeline <NUM> operates in the following manner. One or more compute units <NUM> execute a ray generation shader <NUM>. The ray generation shader <NUM> requests the ray trace stage <NUM> to perform one or more ray intersection tests. Each ray intersection test defines an origin and direction for a ray trace operation, which determines whether the ray hits one or more triangles or whether the ray does not hit any triangle.

The ray trace stage <NUM> identifies one or more triangles intersected by a ray for a ray intersection test, or, if no triangles are intersected by the ray up to a given distance, determines that the ray does not hit any triangles (i.e., that the ray "misses"). The ray trace stage <NUM> may be implemented in any technically feasible manner. In one example, the ray trace stage <NUM> is implemented as a shader program executing on one or more compute units <NUM>. In another example, the ray trace stage <NUM> is implemented as fixed function hardware.

Ray trace stage <NUM> triggers execution of a closest hit shader <NUM> for the triangle closest to the origin of the ray that the ray hits, or, if no triangles were hit, triggers a miss shader. A typical use for the closest hit shader <NUM> is to color a material based on a texture for the material. A typical use for the miss shader <NUM> is to color a pixel with a color set by a skybox. It should be understood that the shader programs defined for the closest hit shader <NUM> and miss shader <NUM> may implement a wide variety of techniques for coloring pixels and/or performing other operations.

A typical way in which ray generation shaders <NUM> generate rays is with a technique referred to as backwards ray tracing. In backwards ray tracing, the ray generation shader <NUM> generates a ray having an origin at the point corresponding to a camera. The point at which the ray intersects a plane defined to correspond to the screen defines the pixel on the screen whose color the ray is being used to determine. If the ray hits an object, that pixel is colored based on the closest hit shader <NUM>. If the ray does not hit an object, the pixel is colored based on the miss shader <NUM>. Multiple rays may be cast per pixel, with the final color of the pixel being determined by some combination (e.g., an average) of the colors determined for each of the rays of the pixel. Any particular ray generation shader <NUM> (or any other shader) may also specify that an any hit shader <NUM> is to be executed for any of the hits between a ray and a triangle, even if such hits are not the closest hit.

It is possible for the closest hit shader <NUM> and/or miss shader <NUM> to spawn their own rays, which enter the ray tracing pipeline <NUM> at the ray test point. These rays can be used for any purpose. One common use is to implement environmental lighting or reflections. In an example, when a closest hit shader <NUM> is invoked, the closest hit shader <NUM> spawns rays in various directions. For each object, or a light, hit by the spawned rays, the closest hit shader <NUM> adds the lighting intensity and color at the hit location to the pixel corresponding to the closest hit shader <NUM> that spawned the rays. It should be understood that although some examples of ways in which the various components of the ray tracing pipeline <NUM> can be used to render a scene have been described, any of a wide variety of techniques may alternatively be used.

It should be understood that any shader program written for the closest hit shader stage <NUM>, miss shader stage <NUM>, or any hit shader stage <NUM>, may implement any of the operations described elsewhere herein as being performed by shader programs written for the ray generation stage <NUM>. For example, in addition to spawning new rays to be provided to the ray test point for testing at the ray trace stage <NUM>, such shader programs may specify whether misses or hits should spawn additional rays to trace (starting again at the ray test point), what shader programs to execute for any such additional rays, how to combine the color and/or luminosity values generated by such additional shader program executions, and any other operations that could be performed by a ray generation shader <NUM>.

Shader programs are launched as "kernels" on the APD <NUM>. A kernel specifies a particular shader program (e.g., a stitched shader program), as well as a number of work-items that will be executed as part of the kernel. The scheduler <NUM> breaks the kernel up into workgroups and assigns workgroups to one or more compute units <NUM> for execution. The workgroups of a kernel begin execution, execute their instructions, and then terminate execution. A workgroup executes as one or more wavefronts within a compute unit <NUM>. A wavefront executes on a SIMD unit <NUM>, as a plurality of work-items executing concurrently.

Each wavefront includes work-items that execute simultaneously in a single-instruction-multiple-data ("SIMD") manner. More specifically, the SIMD units <NUM> execute shader programs in a manner in which a single instruction pointer is used to control program execution for multiple work-items, and therefore multiple instructions can execute simultaneously. In an example, four work-items of a wavefront execute on a SIMD unit. Part of the execution control flow begins at a section shown in pseudo code below:.

The first instruction adds the value in r2 to the value in r3 and stores the result in r1. The second instruction adds the value in r1 to r5 and stores the result in r4. The third instruction stores the value in r4 to the address specified in r6. Lanes of the wavefront executing this psuedo-code execute simultaneously, so that multiple adds, multiplies, and stores are executed simultaneously, once for each lane. "r1" through "r6" represent register names.

It is possible for control flow to diverge among lanes in a SIMD unit <NUM> and thus among work-items of a wavefront. More specifically, some instructions modify the instruction pointer based on the value of a particular variable. In an example, a conditional branch is an instruction whose jump target is based on the results of evaluation of a conditional. In another example, a jump may target an address specified in a variable. When control flow is divergent in this manner, the SIMD unit <NUM> serializes each of the possible paths that at least one lane is to execute. The following example pseudo-code illustrates a situation that can result in divergent control flow.

In table <NUM>, each lane executes the instruction add r1, r2, <NUM>, which adds the value of <NUM> to r2 and stores the result in r1. The blz instruction is a conditional branch that branches if the value in r1 is less than zero. If the value in r1 is greater than zero, the control flow falls through to section <NUM>, which includes some instructions and then a jump instruction to the "reconverge" label. Referring back to the conditional branch, if the value in r1 is not greater than zero, the control flow proceeds to the label LESS_THAN_ZERO, and section <NUM> is executed. At label "RECONVERGE," the control flow reconverges.

If a first lane executing in a wavefront had the value -<NUM> stored in r2 when the first instruction shown were executed, then register r1 for that lane would store the value -<NUM> after that first instruction, which would cause the first lane to execute section <NUM> at "LESS_THAN_ZERO. " If a second lane executing in the same wavefront had the value <NUM> in r2 when the first instruction were executed, then the register r1 for that lane would store the value <NUM>, which would cause that lane to not branch and execution section <NUM>. The execution of section <NUM> and section <NUM> by different lanes would be accomplished by executing each section sequentially, with the lanes not executing a particular section switched off. More specifically, the divergence would cause SIMD unit <NUM> to execute section <NUM> for the second lane, with the first lane switched off, and then to execute section <NUM> for the first lane, with the second lane switched off, which reduces the efficiency of processing because multiple lanes that might otherwise execute simultaneously are now serialized.

Another example of divergent control flow is presented with respect to Table <NUM>.

In the example of Table <NUM>, each lane performs a trace ray to detect a triangle intersection. Then each lane identifies the material of the intersected triangle and stores the address of the material shader for the identified material in register r1. Then each lane jumps to the address stored in r1. These addresses may be the various material shaders ("MATERIAL_SHADER_1," "MATERIAL_SHADER_2, etc.) illustrated. After executing a material shader, the lane jumps to "end_material_shaders. " If each lane hit a triangle with a different material shader, then each of those material shaders would be serialized, resulting in a slowdown equal to the number of lanes in a wavefront - which would represent total deparallelization. Note, a material shader is a section of code used for ray tracing that is executed to provide a color for a ray that intersects a triangle (e.g., at the closest hit shader stage) or that misses a triangle and is thus colored by the skybox (e.g., at the miss stage).

In some examples, on a SIMD processor, the point at which a branch instruction exists is a "branch point. " Branches at branch points point to one or more branch targets. Branches that have a fixed target have a single branch target and branches that have a variable target may have more than one branch target. There are also reconvergence points, which are points where lanes that have diverged due to taking different branch paths necessarily reconverge. The sequence of instructions that begins at a branch target is referred to herein as a "taken path. " The sequence of instructions that begins at the instruction immediately following a conditional branch (the "not-taken point") is referred to herein as a "not-taken path. " Collectively, taken paths and not-taken paths are referred to herein as "code paths. " Each code path extends from a branch target or a not-taken point to a reconvergence point or a branch point. Essentially, each code path defines a sequence of instructions within which the combination of lanes that execute that code path cannot change (which change would occur due to a branch or a reconvergence).

To execute a sequence of instructions that includes a branch, the SIMD processor evaluates the branch instruction for each lane and, based on the results, sets the bit values within an execution bitmask for each code path that could be reached from the branch. Each bit in the bitmask is associated with one lane of the wavefront being executed. One bit value in the bitmask (such as "<NUM>") indicates that a corresponding lane will execute that code path. The other bit value in the bitmask (such as "<NUM>") indicates that a corresponding lane will not execute that code path.

After determining bitmasks for the different code paths, the SIMD processor advances or modifies the instruction pointer as necessary until all code paths that at least one lane is to execute have in fact been executed. For code paths whose bitmask indicates that no lanes execute that code path, the SIMD processor modifies the instruction pointer to skip that code path. In general, modifying the instruction pointer as necessary involves modifying the instruction pointer from the address of the last instruction of one code path that is executed by at least one lane to the address of another code path that is executed by at least one lane. Such modifying may include simply incrementing the instruction pointer if two code paths to be executed are laid out sequentially in memory, or may involve a "true branch," meaning that the instruction pointer is modified in a way other than simply incrementing the instruction pointer, by setting the instruction pointer to the address of the first instruction of a code path to be executed.

<FIG> illustrates serialization resulting from divergent control flow, according to an example. A table <NUM> illustrates several sections of code, listed as "convergent section," "F1," "F2," "F3," and "F4. " Time proceeds downwards in the figure. A mark "O" in a given box indicates that the lane executes the section of code in a given section of time. In the convergent section, it is assumed that each of lanes <NUM> through <NUM> execute that section together. Thus there is a mark "O" for each lane in the convergent section. Due to the results of the convergent section, it is determined that lane <NUM> will execute F1 and not F2, F3, or F4, that lane <NUM> will execute F2 and not F1, F3, or F4, that lane <NUM> will execute F3 and not F1, F2, or F4, and that lane <NUM> will execute F4 and not F1, F2, or F3. As can be seen, each of F1, F2, F3, and F4 executes in a different section of time, and thus execution of the wavefront including lanes <NUM> through <NUM> is deparallelized. More specifically, in a first section of time, lane <NUM> executes function F1 with lanes <NUM>-<NUM> switched off. In a second section of time, lane <NUM> executes function F2 with lanes <NUM> and <NUM>-<NUM> switched off. In a third section of time, lane <NUM> executes function F3, with lanes <NUM>-<NUM> and <NUM> switched off. In a fourth section of time, lane <NUM> executes function F4, with lanes <NUM>-<NUM> switched off.

To reduce control flow divergence, a compute unit <NUM> reorganizes execution items at a control flow divergence point. In some implementations, the term "execution item" refers to a work-item. In other implementations, the term "execution item" refers to a thread of execution that is more granular than a work-item. More specifically, it is possible to execute multiple logical threads of execution in a single work-item, by executing such multiple logical threads sequentially. In such an example, each of the multiple logical threads of execution is the execution item. Two techniques for reorganizing execution items at a divergence point include a technique in which the compute unit <NUM> reorganizes execution items across different wavefronts of a workgroup and a technique in which the compute unit <NUM> reorganizes execution items within a wavefront.

<FIG> illustrates a technique for reducing control flow divergence by reorganizing execution items across wavefronts of a workgroup, according to an example. In this example, there is a one-to-one correspondence between work-items and execution items -- each work-item executes one execution item. In the scenario of <FIG>, one workgroup <NUM> includes two wavefronts - wavefront <NUM><NUM>(<NUM>) and wavefront <NUM><NUM>(<NUM>). A workgroup <NUM> is a collection of work-items that execute together in a single compute unit <NUM>. Work-items of a workgroup <NUM> are executed together as wavefronts. Wavefronts include work-items that execute simultaneously on a SIMD unit <NUM> as described, for example, with respect to <FIG>. It is possible for all of the work-items of a wavefront to execute simultaneously in a SIMD unit <NUM>, but it is also possible for a wavefront to include a number of work-items that is greater than the number of data lanes in a SIMD unit <NUM>. Typically, such wavefronts would include a number of work-items equal to an integer multiple of the number of data lanes in a SIMD unit <NUM>. Execution of such wavefronts would occur by sequentially executing the sub-sets of the work-items of a wavefront. In an example, a wavefront includes <NUM> work-items and a SIMD unit <NUM> includes <NUM> data lanes. In this example, the wavefront is executed by executing work-items <NUM>-<NUM>, then <NUM>-<NUM>, then <NUM>-<NUM>, then <NUM>-<NUM>.

Different wavefronts of a single workgroup do not execute in the simultaneous SIMD manner described herein, although such wavefronts can execute concurrently on different SIMD units <NUM> of a single compute unit <NUM>. One characteristic of a workgroup, though, is that the compute unit <NUM> supports synchronization among different workgroups. "Synchronization" refers to the ability for wavefronts to execute a barrier that halts execution of all wavefronts that participate in the barrier until some condition is met. Wavefronts in a workgroup also have the ability to communicate during execution via local memory in a compute unit <NUM>.

In <FIG>, a table <NUM> illustrates execution by the workgroup <NUM>. The workgroup <NUM> illustrated includes two wavefronts <NUM>. Wavefront <NUM><NUM>(<NUM>) includes work-items <NUM>-<NUM> and wavefront <NUM><NUM>(<NUM>) includes work-items <NUM>-<NUM>. An instruction pointer indicates the sections of code that each wavefront <NUM> executes at a given point of time. Time progresses forward from top to bottom. Some of the entries in the table correspond to portions of code that either may or may not be executed by particular work-items. These portions include functions F1-F4, which are executed by one or more work-items. A convergent portion is executed by all work-items of the wavefronts <NUM>. A mark of "O" indicates that a particular work-item executes one of these portions of code and a blank rectangle indicates that a particular work-item does not execute one of these portions of code.

In the convergent portion, each work-item determines which of functions F1-F4 that work-item is to execute. Note, the term "function" refers to a portion of the shader program being executed by the workgroup <NUM>. A barrier and reorganize stage executes after the convergent portion. The barrier and reorganize stage halts execution of each wavefront <NUM> until the barrier and reorganize stage has completed for each wavefront <NUM> for which the reorganize is occurring. These wavefronts <NUM> include wavefront <NUM><NUM>(<NUM>) and wavefront <NUM><NUM>(<NUM>) in the example of <FIG>. The barrier and reorganize stage reorganizes work-items across different wavefronts <NUM> based on the results of the convergent portion indicating which of the functions F1-F4 the work-items are to execute. In general, the goal of the reorganization is to reduce the divergence (in the example, a higher divergence is associated with a higher total number of functions to be executed) for the wavefronts by swapping work-items between wavefronts. In general, reducing divergence is accomplished by reducing the number of control flow targets in at least one wavefront.

In the example illustrated, the work-items in both wavefront <NUM><NUM>(<NUM>) and wavefront <NUM><NUM>(<NUM>) execute all of functions F1-F4. This is considered <NUM>-times divergence, since the compute unit <NUM> executing those work-items would have to serialize each of functions F1-F4. A reorganization reduces the total number of functions to execute in the wavefronts by grouping together work-items that branch to the same control flow target. The example reorganization results in wavefront <NUM><NUM>(<NUM>) having work-items designated to perform functions F1 and F2 and not F3 and F4 and wavefront <NUM><NUM>(<NUM>) having work-items designated to perform functions F3 and F4 and not F1 and F2. Specifically, wavefront <NUM><NUM>(<NUM>) includes work-items <NUM>, <NUM>, <NUM>, and <NUM>, each of which is designated to execute either F1 or F2, and not F3 or F4, and wavefront <NUM><NUM>(<NUM>) includes work-items <NUM>, <NUM>, <NUM>, and <NUM>, each of which is designated to execute either F3 or F4, and not F1 or F2. With this reorganization, each wavefront <NUM> is only two-times divergent. Note that the code executed by each wavefront <NUM> still includes functions not performed by particular work-items, but this code is skipped, resulting in little or no execution time devoted to those functions for the wavefronts <NUM> having work-items that do not execute those functions.

Although a specific example sequence of instructions is shown, where this specific sequence includes determining a function to execute for each work-item, and executing the function by the work-item, it should be understood that the technique described with respect to <FIG> can be applied to any sequence of instructions that results in divergent control flow. In any situation, the barrier and reorganize stage would examine the total number of divergent control flow targets in a workgroup <NUM> and attempt to assign as few as possible to each wavefront <NUM>. A control flow target may be identified by the instruction pointer address that is targeted by a branch instruction, by the decision of whether or not a conditional branch is taken, or through any other technically feasible means. Assigning as few as possible divergent control flow targets to each wavefront <NUM> can be accomplished by sorting the wavefronts based on the targets, dividing up the sorted list by the number of work-items in each wavefront <NUM>, and assigning the divided up work-items to different wavefronts <NUM>. Moving a work-item from one wavefront <NUM> to another wavefront can be accomplished in any technically feasible manner, such as by modifying lists of work-items assigned to each wavefront <NUM> and by copying execution state data, such as register values, flag values, and the like, from the location where the work-item was previously executing to the location where the work-item is to be moved.

The barrier and reorganize stage may be implemented completely in software, for example with instructions inserted by a runtime or offline compiler, or may be implemented with special hardware support. In an example, either or both of sorting by destination and reorganization of execution items may be accomplished by fixed-function hardware triggered by execution of a special instruction by each wavefront <NUM> of the workgroup <NUM>.

<FIG> illustrates execution that would occur without the reorganization illustrate in <FIG>. As described above, each wavefront <NUM> includes a work item that executes functions F1- F4. Thus, execution of these functions without the reorganization is 4x divergent, as each function is executed in turn.

<FIG> illustrates a technique for reducing control flow divergence by reorganizing execution items within a wavefront, according to an example. In the example shown, each work-item executes two execution items. More specifically, the shader program executed by the wavefront is configured such that two instances of a particular workload - two execution items - are performed sequentially. Each execution item, executing as part of a particular work-item, is executed in a particular time slot. Note that multiple different work-items can of course execute simultaneously. Thus, multiple work-items can execute their slot <NUM> simultaneously, and then execute their slot <NUM> simultaneously. In the example of ray tracing, each slot may correspond to a different ray. In the example, a shader program determines the triangles that rays intersect. The shader program executes a material shader based on the material of the intersected triangle. Each slot for a work-item corresponds to a different ray and thus it is possible to execute a different material shader in different slots of a single work-item.

The sequential performance of two execution items allows for swapping to occur between time slots in order to reduce divergence. The example in <FIG> illustrates such swapping. In the example, four lanes of a wavefront <NUM> are executing two execution items each. Lane <NUM> executes execution items <NUM> and <NUM>, lane <NUM> executes execution items <NUM> and <NUM>, lane <NUM> executes execution items <NUM> and <NUM>, and lane <NUM> executes execution items <NUM> and <NUM>. The lanes execute the convergent portion to identify which of functions F1, F2, F3, and F4 each execution item should execute. Although not shown, the convergent portion may be executed once for each execution item.

The results of the convergent portion are shown: execution item <NUM> is to execute function F1, execution item <NUM> is to execute function F2, execution item <NUM> is to execute function F2, execution item <NUM> is to execute function F3, execution item <NUM> is to execute function F1, execution item <NUM> is to execute function F4, execution item <NUM> is to execute function F3, execution item <NUM> is to execute function F4. In slot <NUM> there would be a total of three functions that would execute and in slot <NUM>, there would be a total of three functions that would execute. This means that in each slot, there would be a divergence factor of <NUM>. At the reorganization stage, the compute unit <NUM> reorganizes execution items among the different lanes to reduce divergence. Specifically, the reorganization stage sorts the execution items by the targets for the execution items, divides the sorted execution items, and assigns the divided, sorted execution items to the slots. In the example shown, the sorted targets are F1 (Item <NUM>), F1 (Item <NUM>), F2 (Item <NUM>), F2 (Item <NUM>), F3 (Item <NUM>), F3 (Item <NUM>, F4 (Item <NUM>), and F4 (Item <NUM>). The reorganization stage assigns the execution items executing functions F1 and F3 to slot one and assigns the execution items executing functions F2 and F4 to slot two. Slot one executes and then slot two executes, with each getting two functions - a divergence factor of <NUM>. Specifically, the functions F1-F4 are to execute sequentially as shown. This sequence occurs twice - once for each slot. In slot one, items <NUM> and <NUM> execute function F1 simultaneously and items <NUM> and <NUM> execute function F3 simultaneously. In slot one, functions F2 and F4 are skipped because no lanes execute those functions. In slot two, items <NUM> and <NUM> execute F2 simultaneously and items <NUM> and <NUM> execute function F4 simultaneously, with functions F1 and F3 being skipped.

Although a specific example sequence of instructions is shown, in general, the intra-wavefront technique is performed as follows. A compiler generates a shader program having two or more time slots, each time slot being a duplicate of a particular work-load to be executed for a different execution item. At a point of divergent control flow, the compiler inserts reorganization code to reorganize execution items across the time slots. The reorganization code sorts the execution items by control flow destinations, into execution item groups. The reorganization code attempts to assign as few groups as possible to each time slot. This reorganization reduces the divergence in at least one time slot, thereby reducing total execution time.

The reorganization stage may be implemented by software (e.g., by instructions inserted into a shader program by a runtime or offline compiler) or with at least partial hardware support. In an example, the shader program executes a special instruction that causes fixed function hardware to reorganize execution items across time slots as described.

Note that although the functions in the time slots are shown as executing sequentially in each time slot, it is possible that each function is repeated for each time slot. In an example, time slot <NUM> performs function <NUM> and then time slot <NUM> performs function <NUM>, then time slot <NUM> performs function <NUM> and time slot <NUM> performs function <NUM>, and so on. The teachings herein apply to any technique for performing multiple iterations of particular sections of divergent control flow. In various examples, a runtime or offline compiler transforms a shader program so that the multiple iterations of sections of divergent control flow are executed as described.

<FIG> illustrates execution that would occur without the reorganization of <FIG>. Specifically, because lanes that execute three different functions are present in each time slot, each time slot executes with 3x divergence, which is a slow-down as compared with the execution that occurs in <FIG>.

<FIG> is a flow diagram of a method <NUM> for reorganizing execution items in an APD <NUM>, according to an example. Although described with respect to the system of <FIG>, it should be understood that any system, configured to perform the steps of the method <NUM> in any technically feasible order, would fall within the scope of the present disclosure.

The method <NUM> begins at step <NUM>, where a compute unit <NUM> identifies control flow targets for different execution items at a point of divergent control flow. As described elsewhere herein, two techniques are disclosed for reorganizing execution items. In a first technique, execution items are reorganized between time slots within a single wavefront. This first technique may be referred to herein as the "intra-wavefront technique. " In a second technique, execution items are reorganized across wavefronts of a wavegroup. This second technique may be referred to herein as the "inter-wavefront technique. " In either technique, the shader program that is executing reaches a point of divergent control flow, which is a point where different execution items execute different portions of the shader program due to having different branch targets (e. due to a different conditional result or due to a different address target for a variable target jump instruction). At step <NUM>, these different branch targets are identified for the different execution items. In some examples, a branch target for a particular execution item includes the address of the destination for that execution item. In other examples, a branch target includes an indication of whether a conditional branch is taken or not (i.e., whether the conditional is met).

In an example, each execution item executes a trace ray operation to identify the material of a triangle intersected by a ray. At this point, different execution items have encountered different triangles with different materials and thus execute different material shaders. Note that the different material shaders are inlined into the shader program being executed, so that executing a particular material shader is accomplished by jumping to the appropriate inlined function, rather than by stopping execution of the current shader and launching the material shader. In other words, at least a part of the ray tracing pipeline is implemented by a single "monolithic" shader program that includes the shaders at different stages of the ray tracing pipeline, as well as instructions for controlling execution flow between the different stages and for moving data between the different stages.

At step <NUM>, the compute unit <NUM> sorts the execution items based on the control flow targets. In an example where the divergence is based on a jump to a variable target, the control flow target is the target of the jump. In an example where the divergence is based on a conditional branch, the control flow target is the result of the condition. Sorting based on the control flow targets comprises sorting the execution items such that execution items having the same control flow targets are grouped together. The result of the sorting is data indicating the sorted order of the execution items. In an example, execution items <NUM> through <NUM> exist and execute a conditional branch. Execution items <NUM>, <NUM>, <NUM>, and <NUM> take the branch and execution items <NUM>, <NUM>, <NUM>, and <NUM> do not take the branch. The data indicating the sorted order indicate that execution items <NUM>, <NUM>, <NUM>, and <NUM> are in a first group and that execution items <NUM>, <NUM>, <NUM>, and <NUM> are in a second group.

At step <NUM>, the compute unit <NUM> reorganizes the execution items based on the sort operation. In the intra-wavelength technique, where execution items are reorganized across time slots, reorganizing the execution items includes assigning each group of sorted execution items to a particular time slot. In the above example, execution items <NUM>, <NUM>, <NUM>, and <NUM> would be assigned to a first time slot and execution items <NUM>, <NUM>, <NUM>, and <NUM> would be assigned to a second time slot. As described elsewhere herein, a time slot is an iteration of a sequentially repeated portion of a shader program. More specifically, to enable reorganization of execution items within a wavefront, at least some portions of a shader program are configured to execute in two or two or more iterations, where each iteration corresponds to a different time slot. Because divergence is related to the number of different segments of code executed at a particular time, having multiple time slots allows reorganization of execution items between time slots so that more execution items having the same control flow target are executed in the same time slot. It is of course possible that the number of execution items in each sorted group is not the same as the number of execution items in the wavefront. Even in this scenario, however, where two or more groups are assigned to a particular time slot, the sorting reduces divergence, which reduces total execution time.

In some implementations, a compiler introduces the time slot construct into a shader program. One example of a compiler is a runtime compiler that executes, for example as part of the driver <NUM>. Another example of a compiler is an offline compiler that executes as part of an application compiler that compiles the application that triggers execution of the shader program. The compiler introduces the time slot construct by causing at least a portion of a shader program to execute for two or more iterations - one iteration for each time slot. In each iteration, a different execution item executes the portion of the shader program. In addition, because the purpose of the time slots is to allow reduction of control flow divergence that results from different execution items taking different control flow paths, each iteration is able to select any of the possible divergent paths (even though each execution item may only take one such path). In an example, if there are four different segments of code that could be executed in a given portion of the shader program, with a variable jump targeting one of the possible segments of code, then in each time slot, an execution item could execute any of the possible segments of code. Divergent control flow can still happen within a given time slot, and this is implemented by a SIMD unit <NUM> serializing each of the different possible control flow paths, as is normal for divergent control flow.

In the inter-wavefront technique, the reorganization of execution items occurs across wavefronts. More specifically, the sorting data described above is still used to group execution items. However, instead of reorganizing the execution items across time slots in a single wavefront, the groups are assigned together to particular wavefronts. In the above example, where each wavefront has a width of four work-items, execution items <NUM>, <NUM>, <NUM>, and <NUM> would be assigned to a first wavefront and execution items <NUM>, <NUM>, <NUM>, and <NUM> would be assigned to a second wavefront. As with the intra-wavefront technique, multiple groups may be assigned to each wavefront, but divergence would still be reduced. At step <NUM>, the shader program executes past the point of divergent control flow, with the reorganized execution items.

It should be understood that many variations are possible based on the disclosure herein. Although features and elements are described above in particular combinations, each feature or element can be used alone without the other features and elements or in various combinations with or without other features and elements. In one example, although the techniques have been described in the context of SIMD processors, the techniques may also be used for multiple-instruction-multiple-data ("MIMD") processors. In another example, although sorting is stated as being done based on the code section to be executed, it is alternatively possible to sort based on other criteria such as the texture that a lane is to fetch or the direction of the ray associated with the lane. Sorting based on such criteria is not directly related to sorting based on what code sections will be executed by the lanes. However, such sorting would be more likely to cause lanes having similar execution flow to be grouped together. In an example, it is somewhat likely that lanes having a similar ray direction will hit the same triangles and will thus execute the same material shader. It is also somewhat likely that lanes that fetch the same texture will execute a similar sequence of instructions because fetching the same texture may indicate that the lanes execute the same shaders (e.g., material shaders).

The various functional units illustrated in the figures and/or described herein (including, but not limited to, the processor <NUM>, the input driver <NUM>, the input devices <NUM>, the output driver <NUM>, the output devices <NUM>, the accelerated processing device <NUM>, the scheduler <NUM>, the graphics processing pipeline <NUM>, the compute units <NUM>, the SIMD units <NUM>, the ray tracing pipeline <NUM>, the ray generation shader <NUM>, the ray trace stage <NUM>, the any hit shader <NUM>, the miss shader <NUM>, or the closest hit shader <NUM>) may be implemented as a general purpose computer, a processor, or a processor core, or as a program, software, or firmware, stored in a non-transitory computer readable medium or in another medium, executable by a general purpose computer, a processor, or a processor core. The methods provided can be implemented in a general purpose computer, a processor, or a processor core. Suitable processors include, by way of example, a general purpose processor, a special purpose processor, a conventional processor, a digital signal processor (DSP), a plurality of microprocessors, one or more microprocessors in association with a DSP core, a controller, a microcontroller, Application Specific Integrated Circuits (ASICs), Field Programmable Gate Arrays (FPGAs) circuits, any other type of integrated circuit (IC), and/or a state machine. Such processors can be manufactured by configuring a manufacturing process using the results of processed hardware description language (HDL) instructions and other intermediary data including netlists (such instructions capable of being stored on a computer readable media). The results of such processing can be maskworks that are then used in a semiconductor manufacturing process to manufacture a processor which implements aspects of the embodiments.

Claim 1:
A method for reducing divergence of control flow in a single-instruction-multiple-data processor, the method comprising:
at a point of divergent control flow, identifying (<NUM>) control flow targets for different execution items of a wavefront, wherein the wavefront is temporally divided into a plurality of time slots for execution;
sorting (<NUM>) the execution items based on the identified control flow targets to generate sorted execution item groups;
reorganizing (<NUM>) the execution items of the wavefront (<NUM>) by swapping the execution items of the wavefront (<NUM>) between the time slots based on the sorted execution item groups such that within a time slot of the time slots more execution items have the same control flow target than without the reorganizing, wherein execution items of the same group are reorganized into the same time slot; and
executing (<NUM>) the wavefront after the point of divergent control flow based on the reorganized execution items.