Patent Description:
Many kernels, particularly kernels corresponding to encoded display data contain dependencies between threads in the kernel. Said differently, execution of some of the threads in the kernel must wait for the threads from which they depend to be executed before their own execution can be started. As such, only a subset of the total number of threads in a kernel can be executed by a GPU in parallel.

Conventionally, a GPU executes a kernel by dispatching those threads without any dependencies first and those with dependencies last. This is sometimes referred to as wavefront dispatching. However, as will be appreciated kernels that have a substantial amount of spatial thread dependency will often experience reduced parallelism when dispatched according to wavefront dispatch methodologies. It is with respect to the above, that the present disclosure is provided.

<CIT> refers to a scoreboard for a video processor that keeps track of dependencies between threads. Dependent threads are collected in a FIFO buffer and the execution of a dependent thread depends on the execution of another potentially active thread. An arbiter looks at independent threads when the depended threads are stalled.

<CIT> refers to a data processing system that determines for a stream of instructions to be executed, whether there are any instructions that can be re-ordered in an instruction stream and assigns each such instructions to an instruction completion tracker. For each instruction in the instruction stream, an indication to the instruction completion tracker is provided to which other instruction the first instruction is dependent. Before executing an instruction, the status of the relevant instruction completion tracker is checked.

<CIT> refers to methods and apparatus for providing a weak dependency linking two tasks of a workflow of task. From a user interface, an indication is received representing a link between a first task and a second task. The link represents a weak dependency between the first and second task. The weak dependency represents that one or more tasks may be inserted between the first and second tasks.

<CIT> refers to a data processor with an instruction pipeline for executing instruction streams having branch instructions. The choices of a branch instruction, the next inline instruction or a target instruction, are made available for selection by a control bypass signal that is generated during decode of the branch instruction.

<CIT> B <NUM> refers to an apparatus including a processor, a graphics processing unit and a memory, wherein the graphics processing unit executes a motion estimation kernel which performs a motion estimation on a current frame using a reference frame.

Advantageous embodiments are subject to the dependent claims.

Various embodiments are generally directed to techniques to dispatch threads of a graphics kernel encoded according to a V9 graphics encoding standard for execution. The threads of the graphics kernel are <NUM> vertical edge threads and <NUM> horizontal edge threads corresponding to a <NUM> x <NUM> pixel area of a superblock. The invention allows for increasing the interval between dependent threads and the associated (e.g., threads upon which execution depends) threads. As such, the present disclosure may dispatch threads to reduce the computing penalty (e.g., reduced parallelism, or the like) caused by waiting for associated threads to finish execution before dependent threads can start execution using the associated threads' results.

According to the embodiments of the invention, the dispatch interval is increased by dispatching associated threads (e.g., those threads upon which other threads execution depends), followed by threads without any dependencies, followed by threads dependent on the earlier dispatched associated threads. As such, the interval between dependent threads and their associated threads can be increased, leading to increased parallelism.

Reference is now made to the drawings, wherein like reference numerals are used to refer to like elements throughout. It may be evident, however, that the novel embodiments can be practiced without these specific details. In other instances, well known structures and devices are shown in block diagram form in order to facilitate a description thereof.

<FIG> is a block diagram of a thread dispatch system <NUM>, according to an embodiment. In general, the system <NUM> is configured to optimize the dispatch of threads for execution by a graphics processor. In particular, the system <NUM> is configured to dispatch the threads to increase the interval between execution of associated threads and corresponding dependent threads. The thread dispatch system <NUM> includes one or more processors <NUM> and one or more graphics processors <NUM>, and may be a single processor desktop system, a multiprocessor workstation system, or a server system having a large number of processors <NUM> or processor cores <NUM>. In on embodiment, the thread dispatch system <NUM> is a system on a chip integrated circuit (SOC) for use in mobile, handheld, or embedded devices.

An embodiment of the thread dispatch system <NUM> can include, or be incorporated within a server-based gaming platform, a game console, including a game and media console, a mobile gaming console, a handheld game console, or an online game console. In one embodiment, the thread dispatch system <NUM> is a mobile phone, smart phone, tablet computing device or mobile Internet device. The thread dispatch system <NUM> can also include, couple with, or be integrated within a wearable device, such as a smart watch wearable device, smart eyewear device, augmented reality device, or virtual reality device. In one embodiment, the thread dispatch system <NUM> is a television or set top box device having one or more processors <NUM> and a graphical interface generated by one or more graphics processors <NUM>.

The one or more processors <NUM> each include one or more processor cores <NUM> to process instructions which, when executed, perform operations for system and user software. In one embodiment, each of the one or more processor cores <NUM> is configured to process a specific instruction set <NUM>. The instruction set <NUM> may facilitate complex instruction set computing (CISC), reduced instruction set computing (RISC), or computing via a very long instruction word (VLIW). Multiple processor cores <NUM> may each process a different instruction set <NUM> that may include instructions to facilitate the emulation of other instruction sets. A processor core <NUM> may also include other processing devices, such a digital signal processor (DSP).

In one embodiment, the processor <NUM> includes cache memory <NUM>. In one embodiment, the cache memory is shared among various components of the processor <NUM>. In one embodiment, the processor <NUM> also uses an external cache (e.g., a Level <NUM> (L3) cache or last level cache (LLC)) (not shown) that may be shared among the processor cores <NUM> using known cache coherency techniques. A register file <NUM> is additionally included in the processor <NUM> which may include different types of registers for storing different types of data (e.g., integer registers, floating point registers, status registers, and an instruction pointer register).

The processor <NUM> is coupled to a processor bus <NUM> to transmit data signals between the processor <NUM> and other components in the system <NUM>. The system <NUM> uses an exemplary 'hub' system architecture, including a memory controller hub <NUM> and an input output (I/O) controller hub <NUM>. The memory controller hub <NUM> facilitates communication between a memory device and other components of the system <NUM>, while the I/O controller hub (ICH) <NUM> provides connections to I/O devices via a local I/O bus.

The memory device <NUM>, can be a dynamic random access memory (DRAM) device, a static random access memory (SRAM) device, flash memory device, or some other memory device having suitable performance to serve as process memory. The memory controller hub <NUM> also couples with an optional external graphics processor <NUM>, which may communicate with the one or more graphics processors <NUM> in the processors <NUM> to perform graphics and media operations. The memory <NUM> can store data <NUM> and instructions <NUM> for use when the processor <NUM> executes a process. The instructions <NUM> can be a sequence of instructions operative on the processors <NUM> and/or the external graphics processor <NUM> to implement logic to perform various functions.

The ICH <NUM> enables peripherals to connect to the memory <NUM> and processor <NUM> via a high-speed I/O bus. The I/O peripherals include an audio controller <NUM>, a firmware interface <NUM>, a wireless transceiver <NUM> (e.g., Wi-Fi, Bluetooth), a data storage device <NUM> (e.g., hard disk drive, flash memory, etc.), and a legacy I/O controller for coupling legacy (e.g., Personal System <NUM> (PS/<NUM>)) devices to the system. One or more Universal Serial Bus (USB) controllers <NUM> connect input devices, such as keyboard and mouse <NUM> combinations. A network controller <NUM> may also couple to the ICH <NUM>. In one embodiment, a high-performance network controller (not shown) couples to the processor bus <NUM>.

In various embodiments, the memory <NUM> stores (e.g., as data <NUM>) one or more of a kernel <NUM> including threads <NUM>-a. It is important to note, that the kernel <NUM> can include any number of threads. For example, the kernel <NUM> is depicted in this figure as including the threads <NUM>-<NUM>, <NUM>-<NUM>, and <NUM>-<NUM>. However, it is to be appreciated, that in practice the kernel <NUM> may include many more threads than depicted. Examples are not intended to be limiting in this context.

In general, the system <NUM> dispatches the threads <NUM>-a to increase an interval between execution of dependent threads and associated threads. As used herein, a dependent thread is a thread that depends upon, or consumes results of, another thread. The thread whose results the dependent thread consumes is referred to herein as the associated thread. A dependent thread may have multiple associated threads. Said differently, a dependent thread may consume results from multiple threads. For example, in some common graphics encoding standards, a thread may depend upon the results of <NUM> other threads. However, it is to be appreciated, that some threads do not have any dependency. More particularly, they are not dependent thread or associated threads. As used herein, such threads are referred to as independent.

For example, assume that the thread <NUM>-<NUM> depends upon the thread <NUM>-<NUM>, while the thread <NUM>-<NUM> is independent. As such, the thread <NUM>-<NUM> is dependent while the thread <NUM>-<NUM> is its associated thread. The system <NUM> can dispatch the threads <NUM>-<NUM>, <NUM>-<NUM>, and <NUM>-<NUM> to increase the interval between the threads <NUM>-<NUM> and <NUM>-<NUM>. As such, in some examples, the system <NUM> can dispatch the thread <NUM>-<NUM> for execution (e.g., by the graphics processor <NUM> and/or <NUM>). Subsequently, the system <NUM> can dispatch the thread <NUM>-<NUM> for execution. Subsequently, the system <NUM> can dispatch the thread <NUM>-<NUM> for execution. As such, the interval between execution of the dependent thread (e.g., <NUM>-<NUM>) and its associated thread (e.g., <NUM>-<NUM>) is increased.

In some examples, the processor <NUM> may determine the order to dispatch the threads <NUM>-a (e.g., the execution order). More particularly, the processor may execution instructions (e.g., instruction set <NUM>) to determine the order in which the threads are to be dispatched (the "dispatch order"). With some examples, the graphics processor (e.g., the graphics processor <NUM> and/or <NUM>) may determine the dispatch order.

<FIG> is a block diagram of an embodiment of a graphics processor <NUM>. In some examples, the graphics processor <NUM> may be the graphics processor <NUM> and/or the graphics processor <NUM> of the system <NUM> shown in <FIG>. In general, the graphics processor <NUM> may be configured to execute threads to increase an interval between execution of dependent and associated threads.

In one embodiment, the graphics processor includes a ring interconnect <NUM>, a pipeline front-end <NUM>, a media engine <NUM>, and graphics cores 280A-N. The ring interconnect <NUM> couples the graphics processor to other processing units, including other graphics processors or one or more general-purpose processor cores. In one embodiment, the graphics processor is one of many processors integrated within a multi-core processing system.

The graphics processor receives batches of commands via the ring interconnect <NUM>. The incoming commands are interpreted by a command streamer <NUM> in the pipeline front-end <NUM>. For example, the ring interconnect <NUM> can receive the kernel <NUM> and threads <NUM>-a. The graphics processor includes scalable execution logic to perform 3D geometry processing and media processing via the graphics core(s) 280A-N. For 3D geometry processing commands, the command streamer <NUM> supplies the commands to the geometry pipeline <NUM>. For at least some media processing commands, the command streamer <NUM> supplies the commands to a video front end <NUM>, which couples with a media engine <NUM>. The media engine <NUM> includes a video quality engine (VQE) <NUM> for video and image post processing and a multi-format encode/decode (MFX) <NUM> engine to provide hardware-accelerated media data encode and decode. The geometry pipeline <NUM> and media engine <NUM> each generate execution threads for the thread execution resources provided by at least one graphics core 280A.

The graphics processor includes scalable thread execution resources featuring modular cores 280A-N (sometime referred to as core slices), each having multiple sub-cores 250A-N, 260A-N (sometimes referred to as core sub-slices). The graphics processor can have any number of graphics cores 280A through 280N. In one embodiment, the graphics processor includes a graphics core 280A having at least a first sub-core 250A and a second core sub-core 260A. In another embodiment, the graphics processor is a low power processor with a single sub-core (e.g., 250A). In one embodiment, the graphics processor includes multiple graphics cores 280A-N, each including a set of first sub-cores 250A-N and a set of second sub-cores 260A-N. Each sub-core in the set of first sub-cores 250A-N includes at least a first set of execution units 252A-N and media/texture samplers 254A-N. Each sub-core in the set of second sub-cores 260A-N includes at least a second set of execution units 262A-N and samplers 264A-N. In one embodiment, each sub-core 250A-N, 260A-N shares a set of shared resources 270A-N. In one embodiment, the shared resources include shared cache memory and pixel operation logic. Other shared resources may also be included in the various embodiments of the graphics processor.

<FIG> illustrate embodiments of logic flows that may be implemented to increase the interval between execution of associated threads and a dependent thread. The logic flows may be representative of some or all of the operations executed by one or more embodiments described herein. In some examples, the logic flows may be executed by components of the system <NUM>. More specifically, the logic flows may illustrate operations performed by the processor <NUM> in dispatching the threads <NUM>-a to the graphics processor <NUM>. Additionally, or alternatively, the logic flows may illustrate operations performed by the graphics processor <NUM> in executing the threads <NUM>-a to increase an interval between dependent and associated threads.

Although reference to the system <NUM> and component of the system <NUM> are made in describing the logic flows, the logic flows may be implemented using component other than those shown or component in alternative configuration. Examples are not limited in this context.

Turning more specifically to <FIG>, a logic flow <NUM> is depicted. The logic flow <NUM> may begin at block <NUM>. At block <NUM> "identify a first thread and a second thread, the first thread dependent upon the second thread," a first thread (e.g., dependent thread) and a second thread (e.g., associated thread) from a number of threads are identified. For example, assuming the thread <NUM>-<NUM> was dependent upon the thread <NUM>-<NUM>, the threads <NUM>-<NUM> and <NUM>-<NUM> may be identified. In some examples, the processor <NUM> may identify the threads <NUM>-<NUM> and <NUM>-<NUM> from the threads <NUM>-a. In some examples, the graphics processor <NUM> may identify the threads <NUM>-<NUM> and <NUM>-<NUM> from the threads <NUM>-a.

Continuing to block <NUM> "determine an order of execution for a number of threads to increase an interval between execution of the first and second threads," an order of execution or dispatch order for the threads <NUM>-a may be determined in order to increase the interval between execution of the thread <NUM>-<NUM> and <NUM>-<NUM>. In some examples, the processor <NUM> may determine the dispatch order. With some examples, the graphics processor <NUM> may determine the dispatch order.

Continuing to block <NUM> "identify a third thread independent thread," a third thread that is independent is identified from the number of threads. For example, assuming the thread <NUM>-<NUM> is independent, the thread <NUM>-<NUM> may be identified. In some examples, the processor <NUM> may identify the threads <NUM>-<NUM> and <NUM>-<NUM> from the threads <NUM>-a. In some examples, the graphics processor <NUM> may identify the threads <NUM>-<NUM> and <NUM>-<NUM> from the threads <NUM>-a.

Continuing to blocks <NUM>-<NUM>, the threads may be dispatched in a particular order to increase an interval between execution of the dependent and associated threads. In particular, at block <NUM> "dispatch the second thread" the second thread is dispatched for execution before either the first or third threads. For example, using the threads <NUM>-<NUM>, <NUM>-<NUM>, and <NUM>-<NUM> as laid out above, the second thread <NUM>-<NUM> can be dispatched for execution before the threads first and third threads <NUM>-<NUM> and <NUM>-<NUM>. In some examples, the processor <NUM> may dispatch the thread <NUM>-<NUM>. In some examples, the graphics processor <NUM> may dispatch the thread <NUM>-<NUM>.

At block <NUM> "dispatch the third thread" the third thread is dispatched for execution before the first thread. For example, using the threads <NUM>-<NUM>, <NUM>-<NUM>, and <NUM>-<NUM> as laid out above, the third thread <NUM>-<NUM> can be dispatched for execution before the first thread <NUM>-<NUM>. In some examples, the processor <NUM> may dispatch the thread <NUM>-<NUM>. In some examples, the graphics processor <NUM> may dispatch the thread <NUM>-<NUM>.

At block <NUM> "dispatch the first thread" the first thread is dispatched for execution. For example, using the threads <NUM>-<NUM>, <NUM>-<NUM>, and <NUM>-<NUM> as laid out above, the first thread <NUM>-<NUM> can be dispatched for execution. As such, the interval between execution of the first thread <NUM>-<NUM> (dependent thread) and the second thread <NUM>-<NUM> (associated thread) is increased. In some examples, the processor <NUM> may dispatch the thread <NUM>-<NUM>. In some examples, the graphics processor <NUM> may dispatch the thread <NUM>-<NUM>.

<FIG> illustrates an embodiment of a storage medium <NUM>. The storage medium <NUM> may comprise an article of manufacture. In some examples, the storage medium <NUM> may include any non-transitory computer readable medium or machine readable medium, such as an optical, magnetic or semiconductor storage. The storage medium <NUM> may store various types of computer executable instructions, such as instructions to implement logic flows <NUM> and/or <NUM>. Examples of a computer readable or machine readable storage medium may include any tangible media capable of storing electronic data, including volatile memory or non-volatile memory, removable or non-removable memory, erasable or non-erasable memory, writeable or re-writeable memory, and so forth. Examples of computer executable instructions may include any suitable type of code, such as source code, compiled code, interpreted code, executable code, static code, dynamic code, object-oriented code, visual code, and the like. The examples are not limited in this context.

In embodiments of the invention, the system <NUM> and the logic flows <NUM> and <NUM> may be implemented to dispatch threads from a graphics kernel (e.g., the kernel <NUM>) to increase an interval between execution of a dependent thread and its associated threads. In general, the kernel can be encoded based on any of a variety of graphics encoding standards, including WMV, MPEG-<NUM>, H. <NUM>/MPEG-<NUM>, VC1, VP8, VP9, and HEVC. In the embodiments of the invention, the kernel <NUM> is encoded according to the VP9 standard.

The present invention is thus applied to dispatch threads from a kernel encoded using the VP9 standard, and particularly, the embodiments of the invention are applicable to dispatching of threads using a VP9 Deblock GPU approach. In general, <FIG> illustrate threads of a VP9 encoded graphics kernel and corresponding dispatch order that can be generated based on the present disclosure. In particular, <FIG> is a table illustrating a superblock (e.g., 64x64 pixels) of the VP9 kernel; <FIG> is a table illustrating dependency relationships for the threads in the superblock; <FIG> and 9A-9D are tables illustrating dependency relationships for various threads; <FIG> is a table illustrating a dispatch order for the threads of the superblock, dispatched according to embodiments of the present disclosure; and <FIG> is a table illustrating a dispatch order for the threads of the superblock, dispatched according to a conventional technique.

Turning more specifically to <FIG>, the table <NUM> is shown. It is to be appreciated, that the threads of a graphics kernel (e.g., the threads <NUM>-a of the graphics kernel <NUM>) are split into multiple superblocks (e.g., see <FIG>). For example, the graphics kernel can be split into superblocks of <NUM> threads that cover a 64x64 pixel area. In particular, the table <NUM> shows threads <NUM>-<NUM> to <NUM>-<NUM> from a superblock <NUM>. It is important to note, that not all the threads are called out with numeric identifiers in <FIG> for purposes of clarity. However, as can be seen the <NUM> threads <NUM>-<NUM> to <NUM>-<NUM> are formed by interleaving <NUM> vertical edge threads from an 8x8 pixel space and <NUM> horizontal edge threads from an 8x8 pixel space into the threadspace of the superblock <NUM>. It is to be appreciated, that the threads are mapped as depicted to have enough parallel software threads for processing.

Turning more specifically to <FIG>, the table <NUM> is shown. It is to be appreciated, that a dependent thread in a VP9 encoded graphics kernels can have up to <NUM> associated threads. Table <NUM> depicts the dependency for a particular thread based on the VP9 standard. In particular, table <NUM> shows a dependent thread <NUM> and associated threads <NUM>-<NUM> to <NUM>-<NUM>. As can be seen, for a dependent thread <NUM>, with coordinates (<NUM>,<NUM>), the associated threads' coordinates in relation to the dependent thread <NUM> can be: associated thread <NUM>-<NUM> having coordinates (-<NUM>, <NUM>); associated thread <NUM>-<NUM> having coordinates (-<NUM>, <NUM>); associated thread <NUM>-<NUM> having coordinates (-<NUM>, <NUM>); associated thread <NUM>-<NUM> having coordinates (-<NUM>, -<NUM>); associated thread <NUM>-<NUM> having coordinates (<NUM>, -<NUM>); associated thread <NUM>-<NUM> having coordinates (<NUM>, -<NUM>); and associated thread <NUM>-<NUM> having coordinates (<NUM>, <NUM>).

Depending on the specific dependent thread's location, only some of the <NUM> associated threads need to be enforced. Said differently, the output of some of the associated threads may not be required to process the dependent thread. This concept can be reflected in a dependency ranking that includes an indication of the likelihood the dependency will not need to be enforced. In particular, the likelihood that each dependency relationship (e.g., between the dependent thread <NUM> and each associated thread <NUM>) can be measured. In some examples, this measurement is binary (e.g., <NUM> = yes likely, <NUM> = no not likely, or the like). Said differently, some of the dependency relationships are considered "weak" while the other are considered "strong. " With run time data (i.e., transform size, tile boundary, picture boundary, or the like), the "weak" dependencies may not need to be enforced.

For example, <FIG> illustrate tables <NUM>, <NUM>, <NUM>, and <NUM>, respectively. These tables depict location specific dependency patterns for vertical threads <NUM> in the superblock <NUM>. <FIG> illustrate tables <NUM>, <NUM>, <NUM>, and <NUM>, respectively. These tables depict location specific dependency patterns for horizontal threads in the superblock <NUM>. It is important to note, that these tables refer to various dependent threads and corresponding associated threads. In particular, the associated threads are referenced based on the table <NUM> shown in <FIG>. More specifically, similar numeric identifiers for the associated threads are used in these tables such that referencing the table <NUM> can identify the relative location of the associated thread to the dependent thread.

Furthermore, these tables highlight associated thread where a dependency ranking including an indication of the likelihood the dependency will need to be enforced during runtime. More specifically, these tables indicate some threads where the dependency may not need to be enforced. In some examples, if there exists a <NUM>% or greater chance that the dependency on an associated thread will not be necessary and can be cleared (e.g., not enforced at runtime) there is a greater priority to increase the interval between execution of the other associated thread and the dependent thread first. As such, the present disclosure provides for determining a dependency ranking and dispatching the associated threads based on the dependent ranking. In particular, the associated threads are dispatched to increase the interval of execution between associated threads that are likely to need to be enforced and the dependent thread to a greater interval than the interval between the associated threads that are unlikely to need to be enforced.

Turning more particularly to <FIG>, the table <NUM> is shown. The table <NUM> depicts a dependent thread <NUM> and corresponding associated threads <NUM>-a. It is important to note that the table <NUM> depicts a dependency pattern for a vertical edge thread where the coordinates are [y > <NUM>, x = <NUM>]. As depicted the dependent thread <NUM> has three associated threads <NUM>-a. In particular, the threads <NUM>-<NUM>, <NUM>-<NUM>, and <NUM>-<NUM> are associated with the dependent thread <NUM>.

Turning more particularly to <FIG>, the table <NUM> is shown. The table <NUM> depicts a dependent thread <NUM> and corresponding associated threads <NUM>-a. It is important to note that the table <NUM> depicts a dependency pattern for a vertical edge thread where the coordinates are [y = <NUM>, x = <NUM>]. As depicted the dependent thread <NUM> has three associated threads <NUM>-a. In particular, the threads <NUM>-<NUM>, <NUM>-<NUM>, and <NUM>-<NUM> are associated with the dependent thread <NUM>.

It is important to note, that for the dependency patterns depicted in tables <NUM> and <NUM>, the dependency of the associated thread <NUM>-<NUM> is guaranteed by the associated thread <NUM>-<NUM>.

Turning more particularly to <FIG>, the table <NUM> is shown. The table <NUM> depicts a dependent thread <NUM> and corresponding associated threads <NUM>-a. It is important to note that the table <NUM> depicts a dependency pattern for a vertical edge thread where the coordinates are [y < <NUM>, x > <NUM>]. As depicted the dependent thread <NUM> has two associated threads <NUM>-a. In particular, the threads <NUM>-<NUM> and <NUM>-<NUM> are associated with the dependent thread <NUM>.

Turning more particularly to <FIG>, the table <NUM> is shown. The table <NUM> depicts a dependent thread <NUM> and corresponding associated threads <NUM>-a. It is important to note that the table <NUM> depicts a dependency pattern for a vertical edge thread where the coordinates are [y = <NUM>, x > <NUM>]. As depicted the dependent thread <NUM> has two associated threads <NUM>-a. In particular, the threads <NUM>-<NUM> and <NUM>-<NUM> are associated with the dependent thread <NUM>.

With respect to the vertical edge threads depicted in tables <NUM>, <NUM>, <NUM>, and <NUM>, the dependency of each thread upon the associated thread <NUM>-<NUM> is "weak. " More specifically, the dependency of each dependent thread upon the associated thread <NUM>-<NUM> can be ranked as likely to not be enforced during runtime. As such, a dependency ranking may be determined (e.g., low, weak, unlikely, <NUM>, <NUM>, or the like) to include an indication that the dependency upon the associated thread <NUM>-<NUM> may not need to be enforced. Furthermore, it is important to note, that the associated threads depicted in tables <NUM> and <NUM> cross superblocks and as such, may be a special case.

Turning more particularly to <FIG>, the table <NUM> is shown. The table <NUM> depicts a dependent thread <NUM> and corresponding associated threads <NUM>-a. It is important to note that the table <NUM> depicts a dependency pattern for a horizontal edge thread where the coordinates are [y = <NUM>, x < <NUM>]. As depicted the dependent thread <NUM> has five associated threads <NUM>-a. In particular, the threads <NUM>-<NUM>, <NUM>-<NUM>, <NUM>-<NUM>, <NUM>-<NUM>, and <NUM>-<NUM> are associated with the dependent thread <NUM>.

Turning more particularly to <FIG>, the table <NUM> is shown. The table <NUM> depicts a dependent thread <NUM> and corresponding associated threads <NUM>-a. It is important to note that the table <NUM> depicts a dependency pattern for a horizontal edge thread where the coordinates are [y = <NUM>, x = <NUM>]. As depicted the dependent thread <NUM> has four associated threads <NUM>-a. In particular, the threads <NUM>-<NUM>, <NUM>-<NUM>, <NUM>-<NUM> and <NUM>-<NUM> are associated with the dependent thread <NUM>.

Turning more particularly to <FIG>, the table <NUM> is shown. The table <NUM> depicts a dependent thread <NUM> and corresponding associated threads <NUM>-a. It is important to note that the table <NUM> depicts a dependency pattern for a horizontal edge thread where the coordinates are [y > <NUM>, x < <NUM>]. As depicted the dependent thread <NUM> has five associated threads <NUM>-a. In particular, the threads <NUM>-<NUM>, <NUM>-<NUM>, <NUM>-<NUM>, <NUM>-<NUM>, and <NUM>-<NUM> are associated with the dependent thread <NUM>.

Turning more particularly to <FIG>, the table <NUM> is shown. The table <NUM> depicts a dependent thread <NUM> and corresponding associated threads <NUM>-a. It is important to note that the table <NUM> depicts a dependency pattern for a horizontal edge thread where the coordinates are [y > <NUM>, x = <NUM>]. As depicted the dependent thread <NUM> has three associated threads <NUM>-a. In particular, the threads <NUM>-<NUM>, <NUM>-<NUM> and <NUM>-<NUM> are associated with the dependent thread <NUM>.

With respect to the horizontal edge threads depicted in tables <NUM>, <NUM>, <NUM>, and <NUM>, the dependency of each thread upon the associated thread <NUM>-<NUM> is "weak. " More specifically, the dependency of each dependent thread upon the associated thread <NUM>-<NUM> can be ranked as likely to not be enforced during runtime. As such, a dependency ranking may be determined (e.g., low, weak, unlikely, <NUM>, <NUM>, or the like) to include an indication that the dependency upon the associated thread <NUM>-<NUM> may not need to be enforced. Furthermore, it is important to note, that the associated thread <NUM>-<NUM> depicted in tables <NUM> and <NUM> cross superblocks and as such, may be a special case.

Returning to the table <NUM> shown in <FIG>, the threads <NUM>-a can be dispatched in a particular order to increase the interval between execution of associated threads (e.g., refer to <FIG>, <FIG>, <FIG>) and corresponding dependent threads. In particular, the present disclosure provides for dispatching the threads to increase the execution interval based on the dependency ranking (e.g., likelihood the dependency will be enforced). <FIG> illustrates a table <NUM> that shows dispatch ordering for each of the threads <NUM> depicted in the table <NUM>. In particular, the dispatch ordering depicted in table <NUM> is based on embodiments of the present disclosure. For comparison purposes, <FIG> illustrates a table <NUM> that shows dispatch ordering for each of the threads <NUM> depicted in the table <NUM> based on a conventional (e.g., WAVEFRONT) dispatching method.

An example of increasing the interval between executions of associated threads and their corresponding dependent thread is described with reference to <FIG> and <FIG>. In particular, with reference to the horizontal edge dependent thread <NUM> at coordinate H[<NUM>, <NUM>]. This thread and its dispatch order are indicated in the tables <NUM> and <NUM>. This particular thread has five dependencies. Said differently, this particular thread has five associated threads, four of which are "strong," that is likely to be enforced at runtime and one is "weak," that is unlikely to be enforced at runtime (e.g., refer to <FIG> and <FIG>9D). The associated threads that are likely to be enforced at runtime are the vertical edge threads V[<NUM>, <NUM>], V[<NUM>, <NUM>], V[<NUM>, <NUM>], and V[<NUM>, <NUM>] while the associated thread that is unlikely to be enforced at runtime is H[<NUM>, <NUM>].

In accordance with an embodiment of the invention, applying the dispatching scheme of the invention will cause that the dependent thread H[<NUM>, <NUM>] is dispatched <NUM>th. Its associated threads where the dependency ranking indicates the dependency is likely to be enforced (e.g., > <NUM>%, or the like) are dispatched <NUM>th, <NUM>th, <NUM>th and <NUM>th,respectively. Its associated thread where the dependency ranking indicates the dependency is unlikely to be enforced at runtime is dispatched <NUM>th.

Conversely, using a conventional dispatching technique, the dependent thread H[<NUM>, <NUM>] is dispatched <NUM>th. Its associated threads where the dependency ranking indicates the dependency is likely to be enforced (e.g., > <NUM>%, or the like) are dispatched <NUM>th, <NUM>th, <NUM>th and <NUM>th, respectively. Its associated thread where the dependency ranking indicates the dependency is unlikely to be enforced at runtime is dispatched <NUM>th.

Accordingly, the present invention can ensure that the associated threads are dispatched significantly sooner providing greater time for the execution of the associated threads to finish as compared to conventional techniques. As a result, memory pressure and parallelism can be increased when the present disclosure is implemented to dispatch threads.

An actual bit stream (e.g., kernel <NUM>) includes multiple superblocks (e.g., the superblock <NUM>). For example, <FIG> illustrates a table <NUM> showing multiple superblocks <NUM>-a, where each superblock includes <NUM> threads corresponding to a 64x64 pixel area. Each of the superblocks <NUM>-a are typically dispatched in a <NUM> degree pattern, as illustrated in this figure. In some examples, all the superblocks <NUM>-a in the same wavefront (e.g., <NUM>-<NUM>/<NUM>-<NUM>, <NUM>-<NUM>/<NUM>-<NUM>, <NUM>-<NUM>/<NUM>-<NUM>/<NUM>-<NUM>, or the like) and can be dispatched together. In some examples, the threads in each superblock are dispatched individually, for example as illustrated in <FIG>. With some examples, with each wavefront of superblocks (e.g., <NUM>-<NUM> and <NUM>-<NUM>) the vertical threads from all the superblocks <NUM>-a can be dispatched, followed by the horizontal threads. This is illustrated in <FIG>. In general, <FIG> depict logic flows for dispatching threads within superblocks of a wavefront while <FIG> depict tables showing the dispatch order of thread within superblocks of a number of consecutive wavefronts. It is important to note, that the superblocks depicted in <FIG> only show <NUM> threads for purposes of clarity.

Turning more specifically to <FIG>, the logic flow <NUM> is depicted, the logic flow <NUM> can be used to increase the interval between execution of associated threads and corresponding dependent threads across multiple superblocks in a wavefront. The logic flow <NUM> may begin at block <NUM>. At block <NUM> "receive threads from superblocks in a wavefront" the threads of superblocks (e.g., superblocks <NUM>-a) for a particular wavefront of superblocks may be received. In some examples, the processor <NUM> may receive the threads.

Continuing to block <NUM> "dispatch all vertical edge threads in each superblock" the columns of vertical threads in each superblock may be dispatched. In some examples, the processor <NUM> and/or the graphics processor <NUM> may dispatch the vertical edge threads column by column for each superblock in the wavefront. Continuing to block <NUM> "dispatch all horizontal edge threads in each superblock" the columns of horizontal threads in each superblock may be dispatched. In some examples, the processor <NUM> and/or the graphics processor <NUM> may dispatch the horizontal edge threads column by column for each superblock in the wavefront.

For example, <FIG> illustrates a table <NUM> showing three wavefronts of superblocks <NUM>, <NUM>, and <NUM>. As depicted, the third wavefront includes two superblocks <NUM> and <NUM>. Furthermore, as noted, the table <NUM> shows the dispatch order for the threads within the superblocks. As can be seen, the columns of vertical edge threads from both superblocks <NUM> and <NUM> are dispatched prior to the horizontal edge threads being dispatched. In particular, the vertical edge threads from the first superblock are dispatched, followed by the vertical edge threads of the second superblock.

Turning more specifically to <FIG>, the logic flow <NUM> according to an embodiment of the invention is depicted. The logic flow <NUM> can be used to increase the interval between execution of associated threads and corresponding dependent threads across multiple superblocks in a wavefront. The logic flow <NUM> may begin at block <NUM>. At block <NUM> "receive threads from superblocks in a wavefront" the threads of superblocks (e.g., superblocks <NUM>-a) for a particular wavefront of superblocks may be received. In some examples, the processor <NUM> may receive the threads.

Continuing to block <NUM> "dispatch the first column of vertical threads in each superblock" the first column of vertical threads in each superblock may be dispatched. In some examples, the processor <NUM> and/or the graphics processor <NUM> may dispatch the first column of vertical edge threads in each superblock in the wavefront. Continuing to block <NUM> "dispatch the second column of vertical edge threads in each superblock" the second column of vertical threads in each superblock may be dispatched. In some examples, the processor <NUM> and/or the graphics processor <NUM> may dispatch the second column of vertical edge threads in each superblock in the wavefront.

Continuing to block <NUM> "all columns of vertical edge threads in each superblock dispatched?" a determination of whether all the columns of vertical edge threads in each superblock have been dispatched is made. In some examples, the processor <NUM> and/or the graphics processor <NUM> may determine whether all columns of vertical edge threads in each superblock in the wavefront have been dispatched.

Based on the determination at block <NUM> the logic flow <NUM> may continue to block <NUM> or to block <NUM>. In particular, if not all columns of vertical edge threads in each superblock have been dispatched, the logic flow may continue to block <NUM> "dispatch the next column of vertical edge threads in each superblock" the next column of vertical threads in each superblock may be dispatched. In some examples, the processor <NUM> and/or the graphics processor <NUM> may dispatch the next column of vertical edge threads in each superblock in the wavefront.

Alternatively, if all columns of vertical edge threads have been dispatched the logic flow <NUM> may continue to block <NUM> "dispatch the first column of horizontal edge threads in each superblock" the first column of horizontal edge threads in each superblock may be dispatched. In some examples, the processor <NUM> and/or the graphics processor <NUM> may dispatch the first column of horizontal edge threads in each superblock in the wavefront. Continuing to block <NUM> "dispatch the second column of horizontal edge threads in each superblock" the second column of horizontal edge threads in each superblock may be dispatched. In some examples, the processor <NUM> and/or the graphics processor <NUM> may dispatch the second column of horizontal edge threads in each superblock in the wavefront.

Continuing to block <NUM> "all columns of horizontal edge threads in each superblock dispatched?" a determination of whether all the columns of horizontal edge threads in each superblock have been dispatched is made. In some examples, the processor <NUM> and/or the graphics processor <NUM> may determine whether all columns of horizontal edge threads in each superblock in the wavefront have been dispatched.

Based on the determination at block <NUM> the logic flow <NUM> may continue to block <NUM> or the logic flow may end. In particular, if not all columns of horizontal edge threads in each superblock have been dispatched, the logic flow may continue to block <NUM> "dispatch the next column of horizontal edge threads in each superblock" the next column of horizontal threads in each superblock may be dispatched. In some examples, the processor <NUM> and/or the graphics processor <NUM> may dispatch the next column of horizontal edge threads in each superblock in the wavefront.

For example, <FIG> illustrates a table <NUM> showing three wavefronts of superblocks <NUM>, <NUM>, and <NUM>. As depicted, the third wavefront includes two superblocks <NUM> and <NUM>. Furthermore, as noted, the table <NUM> shows the dispatch order for the threads within the superblocks. As can be seen, the first columns of vertical edge threads from both superblocks <NUM> and <NUM> are dispatched, followed by the second columns of vertical edge threads, etc. After the vertical edge threads are dispatched, the first columns of horizontal edge threads are dispatched, followed by the second columns of vertical edge threads, etc..

To the extent various operations or functions are described herein, they can be described or defined as hardware circuitry, software code, instructions, configuration, and/or data. The content can be embodied in hardware logic, or as directly executable software ("object" or "executable" form), source code, high level shader code designed for execution on a graphics engine, or low level assembly language code in an instruction set for a specific processor or graphics core. The software content of the embodiments described herein can be provided via an article of manufacture with the content stored thereon, or via a method of operating a communication interface to send data via the communication interface.

A non-transitory machine readable storage medium can cause a machine to perform the functions or operations described, and includes any mechanism that stores information in a form accessible by a machine (e.g., computing device, electronic system, etc.), such as recordable/non-recordable media (e.g., read only memory (ROM), random access memory (RAM), magnetic disk storage media, optical storage media, flash memory devices, etc.). A communication interface includes any mechanism that interfaces to any of a hardwired, wireless, optical, etc., medium to communicate to another device, such as a memory bus interface, a processor bus interface, an Internet connection, a disk controller, etc. The communication interface is configured by providing configuration parameters or sending signals to prepare the communication interface to provide a data signal describing the software content. The communication interface can be accessed via one or more commands or signals sent to the communication interface.

Various components described can be a means for performing the operations or functions described. Each component described herein includes software, hardware, or a combination of these. The components can be implemented as software modules, hardware modules, special-purpose hardware (e.g., application specific hardware, application specific integrated circuits (ASICs), digital signal processors (DSPs), etc.), embedded controllers, hardwired circuitry, etc..

Some embodiments may be described using the expression "one embodiment" or "an embodiment" along with their derivatives. These terms mean that a particular feature, structure, or characteristic described in connection with the embodiment is included in at least one embodiment. Further, some embodiments may be described using the expression "coupled" and "connected" along with their derivatives. The term "coupled," however, may also mean that two or more elements are not in direct contact with each other, but yet still cooperate or interact with each other. Furthermore, aspects or elements from different embodiments may be combined.

Claim 1:
An apparatus for dispatching a plurality of threads (<NUM>-<NUM> - <NUM>-<NUM>) of a graphics kernel (<NUM>) encoded according to a V9 graphics encoding standard, the threads (<NUM>-<NUM> - <NUM>-<NUM>) of the graphics kernel (<NUM>) are <NUM> vertical edge threads and <NUM> horizontal edge threads corresponding to a <NUM> × <NUM> pixel area of a superblock (<NUM>), the apparatus comprising:
a graphics processor (<NUM>) configured to execute the plurality of threads; and
a thread dispatcher configured to determine an order of execution of the plurality of threads (<NUM>-<NUM> - <NUM>-<NUM>) based upon whether a respective one of the threads (<NUM>-<NUM> - <NUM>-<NUM>) is a vertical edge thread or a horizontal edge thread of the graphics kernel (<NUM>) to increase an interval between execution of horizontal edge threads and vertical edge threads, the horizontal edge threads dependent upon the vertical edge threads;
wherein the thread dispatcher is further configured to dispatch the threads (<NUM>-<NUM>, <NUM>-<NUM>, <NUM>-<NUM>, ...) that are vertical edge threads prior to dispatching the threads (<NUM>-<NUM>, <NUM>-<NUM>, <NUM>-<NUM>, ...) that are horizontal edge threads.