Patent Publication Number: US-2010123717-A1

Title: Dynamic Scheduling in a Graphics Processor

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS 
     This application is related to copending U.S. patent application Ser. No. 12/019,741, filed on Jan. 25, 2008, and entitled “Graphics Processor Having Unified Shader Unit,” which is incorporated by reference in its entirety into the present disclosure. 
    
    
     TECHNICAL FIELD 
     The present disclosure generally relates to three-dimensional computer graphics systems. More particularly, the disclosure relates to dynamically scheduling parallel shader units in graphics processing systems. 
     BACKGROUND 
     Three-dimensional (3D) computer graphics systems, which can render objects from a 3D world (real or imaginary) onto a two-dimensional (2D) display screen, are currently used in a wide variety of applications. For example, 3D computer graphics can be used for real-time interactive applications, such as computer games, virtual reality, scientific research, etc., as well as off-line applications, such as the creation of high resolution movies, graphic art, etc. Because of a growing interest in 3D computer graphics, this field of technology has been developed and improved significantly over the past several years. 
     In order to render 3D objects onto a 2D display, objects to be displayed are defined in a 3D “world space” using space coordinates and color characteristics. The coordinates of points on the surface of an object are determined and the points, or vertices, are used to create a wireframe connecting the points to define the general shape of the object. In some cases, these objects may have “bones” and “joints” that can pivot, rotate, etc., or may have characteristics allowing the objects to bend, compress, deform, etc. A graphics processing system can gather the vertices of the wireframe of the object to create triangles or polygons. For instance, an object having a simple structure, such as a wall or a side of a building, may be defined by four planar vertices forming a rectangular polygon or two triangles. A more complex object, such as a tree or sphere, may be defined by hundreds of vertices forming hundreds of triangles. 
     In addition to defining vertices of an object, the graphics processor may also perform other tasks such as determining how the 3D objects will appear on a 2D screen. This process includes determining, from a single “camera view” pointed in a particular direction, a window frame view of this 3D world. From this view, the graphics processor can clip portions of an object that may be outside the frame, hidden by other objects, or facing away from the “camera” and hidden by other portions of the object. Also, the graphics processor can determine the color of the vertices of the triangles or polygons and make certain adjustments based on lighting effects, reflectivity characteristics, transparency characteristics, etc. Using texture mapping, textures or colors of a flat picture can be applied onto the surface of the 3D objects as if putting skin on the object. In some cases, the color values of the pixels located between two vertices, or on the face of a polygon formed by three or more vertices, can be interpolated if the color values of the vertices are known. Other graphics processing techniques can be used to render these objects onto a flat screen. 
     As is known, the graphics processors include components referred to as “shaders”. Software developers or artists can utilize these shaders to create images and control frame-by-frame video as desired. For example, vertex shaders, geometry shaders, and pixel shaders are commonly included in graphics processors to perform many of the tasks mentioned above. Also, some tasks are performed by fixed function units, such as rasterizers, pixel interpolators, triangle setup units, etc. By creating a graphics processor having these individual components, a manufacturer can provide a basic tool for creating realistic 3D images or video. 
     However, different software developers or artists may have different needs, depending on their particular application. Because of this, it can be difficult to determine up front what proportion of each of the shader units or fixed function units of the total processing core should be included in the graphics processor. Thus, a need exists in the art of graphics processors to address the accumulation and proportioning of separate types of shaders and fixed function units based on application. It would therefore be desirable to provide a graphics processing system capable of overcoming these and other inadequacies and deficiencies in the 3D graphics technology. 
     SUMMARY 
     Systems and methods for processing graphical data are disclosed herein. In one embodiment among others, a graphics processing unit (GPU) comprises a shader device configured to perform multiple graphics shading functions. The shader device has a plurality of execution units configured to operate in parallel, each execution unit having a plurality of threads. The threads are also configured to operate in parallel, where each thread configured to perform multiple graphics shading functions. The GPU further includes a control device in communication with the shader device. The control device is configured to receive vertex data and allocate portions of the vertex data to at least one thread of at least one execution unit. The control device is further configured to dynamically reallocate the vertex data from threads that are determined to be busy to threads that are determined to be less busy. 
     In another embodiment, an execution unit is described having a plurality of thread processing paths, a memory device, and a thread control device. The thread processing paths, which are configured to process vertex data, each have logic for performing vertex shading functionality, logic for performing geometry shading functionality, and logic for performing pixel shading functionality. The memory device is configured to store vertex data being processed. The thread control device is configured to control an allocation of the vertex data to the plurality of thread processing paths based on an initial assignment. The thread control device is further configured to control a reallocation of the vertex data to the plurality of thread processing paths based on the availability of the thread processing paths. 
     Other systems, methods, features, and advantages of the present disclosure will be apparent to one having skill in the art upon examination of the following drawings and detailed description. It is intended that all such additional systems, methods, features, and advantages be included within this description and protected by the accompanying claims. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       Many aspects of the embodiments disclosed herein can be better understood with reference to the following drawings. Like reference numerals designate corresponding parts throughout the several views. 
         FIG. 1  is a block diagram of a graphics processing system according to one embodiment of the present disclosure. 
         FIG. 2  is a block diagram of an embodiment of the graphics processing unit shown in  FIG. 1 . 
         FIG. 3A  is a block diagram of another embodiment of the graphics processing unit shown in  FIG. 1 . 
         FIG. 3B  is a block diagram of another embodiment of the graphics processing unit shown in  FIG. 1 . 
         FIG. 3C  is a block diagram of yet another embodiment of the graphics processing unit shown in  FIG. 1 . 
         FIG. 4  is a block diagram of an embodiment of an execution unit according to the execution units shown in  FIGS. 3A-3C . 
         FIG. 5  is a block diagram of another embodiment of an execution unit according to the execution units shown in  FIGS. 3A-3C . 
         FIG. 6  is a block diagram of yet another embodiment of an execution unit according to the execution units shown in  FIGS. 3A-3C . 
         FIG. 7  is a diagram of an embodiment of a thread controller and related signal flow. 
         FIG. 8  is a block diagram of another embodiment of a thread controller. 
         FIG. 9  is a block diagram of an embodiment of a thread queue. 
         FIG. 10  is a flow chart illustrating an embodiment of a method for managing tasks within a graphics processing unit. 
     
    
    
     DETAILED DESCRIPTION 
     Conventionally, graphics processors or graphics processing units (GPUs) are incorporated into a computer system for specifically performing computer graphics. With the greater use of three-dimensional (3D) computer graphics, GPUs have become more advanced and more powerful. Some tasks normally handled by a central processing unit (CPU) are now handled by GPUs to accomplish graphics processing having great complexity. Typically, GPUs may be embodied on a graphics card attached to or in communication with a motherboard of a computer processing system. 
     GPUs contain a number of separate units for performing different tasks to ultimately render a 3D scene onto a two-dimensional (2D) display screen, such as a television, computer monitor, video screen, or other suitable display device. These separate processing units are usually referred to as “shaders” and may include, for example, vertex shaders, geometry shaders, and pixel shaders. Also, other processing units referred to as fixed function units, such as pixel interpolators and rasterizers, are also included in the GPUs. When designing a GPU, the combination of each of these components is taken into consideration to allow various tasks to be performed. Based on the combination, the GPU may have a greater ability to perform one task while lacking full ability for another task. Because of this, hardware developers have attempted to place some shader units together into one component. However, the extent to which separate units have been combined has been limited. 
     The present disclosure discusses the combining of the shader units and fixed function units into a single unit, referred to herein as a unified shader. The unified shader has the ability to perform the functions of vertex shading, geometry shading, and pixel shader, as well as perform the functions of rasterization, pixel interpolation, etc. Also, by including a device for determining allocation, the rendering of 3D can be dynamically adjusted based on the particular need at the time. By observing the current and past needs of individual functions, the allocation mechanism can adjust the allocation of the processing facilities appropriately to efficiently and quickly process the graphics data. 
     As an example, when the unified shader determines that many objects defined within the 3D world space have a simple structure, such as a scene inside a room having many planar walls, floors, ceilings, and doors, a vertex shader in this case is not utilized to its fullest extent. Therefore, more processing power can be allocated to the pixel shader, which may need to process complex textures. On the other hand, if a scene includes many complex shapes, such as a scene within a forest, more processing power may be needed by the vertex shader and less for the pixel shader. Even if a scene changes, such as moving from an outside scene to an indoor scene or vice versa, the unified shader can dynamically adjust the allocation of the shaders to meet the particular demand. 
     Furthermore, the unified shader may be configured having several parallel units, referred to herein as “execution units,” where each execution unit is capable of the full range of graphics processing shading tasks and fixed function tasks. In this way, the allocation mechanism may dynamically configure each execution unit or portions thereof to process a particular graphics function. The unified shader, having a number of similarly functioning execution units, can be flexible enough to allow a software developer to allocate as needed, depending on the particular scene or object. In this way, the GPU can operate more efficiently by allocating the processing resources as needed. This on-demand resource allocation scheme can provide faster processing speeds and allow for more complex rendering. 
     Another advantage of the unified shader described herein is that the capability or size of each execution unit can be relatively simple. By combining the execution units in parallel, the performance of the GPU can be changed simply by adding or subtracting execution units. Since the number of execution units can be changed, a GPU having a lower level of execution capacity can be developed for simple inexpensive graphics processing. Also, the number of execution units can be increased or scaled up to cater to higher level users. Because of the versatility of the execution units to perform a great number of graphics processing functions, the performance of the GPU can be determined simply by the number of execution units included. The scaling up or scaling down of the execution units can be relatively simple and does not require complex re-engineering designs to satisfy a range of low level or high level users. 
     Each of the parallel execution units, as defined herein, may comprise a number of “threads”. A thread described herein refers to a task or a basic task unit in the execution unit. In this respect, several parallel tasks or threads can be executed simultaneously in the same cycle. In the present disclosure, not only can the execution units themselves be arbitrated to resolve which ones are to be used for different shading functions, but also the individual threads may be arbitrated as well to provide a finer granularity with respect to scheduling the pool of execution units. This dynamic scheduling is therefore performed on a thread level as opposed to an execution unit level, which results in a greater level of flexibility. 
     The GPUs, unified shaders, and execution units described herein are designed to meet DirectX and OpenGL specifications. A more detailed description of the embodiments of these components will now be discussed in the following. 
       FIG. 1  is a block diagram of an embodiment of a computer graphics system  10 . The computer graphics system  10  includes a computing system  12 , a graphics software module  14 , and a display device  16 . The computing system  12  includes, among other things, a graphics processing unit (GPU)  18  for processing at least a portion of the graphical data handled by the computing system  12 . In some embodiments, the GPU  18  may be configured on a graphics card within the computing system  12 . The GPU  18  processes the graphics data to generate color values and luminance values for each pixel of a frame for display on the display device  16 , normally at a rate of 30 frames per second. The graphics software module  14  includes an application programming interface (API)  20  and a software program application  22 . The API  20 , in this embodiment, adheres to the latest OpenGL and/or DirectX specifications. 
     In recent years, a need has arisen to utilize a GPU having more programmable logic. In this embodiment, the GPU  18  is configured with greater programmability. A user can control a number of input/output devices to interactively enter data and/or commands via the graphics software module  14 . The API  20 , based on logic in the application  22 , controls the hardware of the GPU  18  to create the available graphics functions of the GPU  18 . In the present disclosure, the user may be unaware of the GPU  18  and its functionality, particularly if the graphics software module  14  is a video game console and the user is simply someone playing the video game. If the graphics software module  14  is a device for creating 3D graphic videos, computer games, or other real-time or off-line rendering and the user is a software developer or artist, this user may typically be more aware of the functionality of the GPU  18 . It should be understood that the GPU  18  may be utilized in many different applications. However, in order to simplify the explanations herein, the present disclosure focuses particularly on real-time rendering of images onto the 2D display device  16 . 
       FIG. 2  is a block diagram of an embodiment of the GPU  18  shown in  FIG. 1 . In this embodiment, the GPU  18  includes a graphics processing pipeline  24  separated from a cache system  26  by a bus interface  28 . The pipeline  24  includes a vertex shader  30 , a geometry shader  32 , a rasterizer  34 , and a pixel shader  36 . An output of the pipeline  24  may be sent to a write back unit (not shown). The cache system  26  includes a vertex stream cache  40 , a level one (L1) cache  42 , a level two (L2) cache  44 , a Z cache  46 , and a texture cache  48 . 
     The vertex stream cache  40  receives commands and graphics data and transfers the commands and data to the vertex shader  30 , which performs vertex shading operations on the data. The vertex shader  30  uses vertex information to create triangles and polygons of objects to be displayed. From the vertex shader  30 , the vertex data is transmitted to geometry shader  32  and to the L1 cache  42 . If necessary, some data can be shared between the L1 cache  42  and the L2 cache  44 . The L1 cache can also send data to the geometry shader  32 . The geometry shader  32  performs certain functions such as tessellation, shadow calculations, creating point sprites, etc. The geometry shader  32  can also provide a smoothing operation by creating a triangle from a single vertex or creating multiple triangles from a single triangle. 
     After this stage, the pipeline  24  includes a rasterizer  34 , operating on data from the geometry shader  32  and L2 cache  44 . Also, the rasterizer  34  may utilize the Z cache  46  for depth analysis and the texture cache  48  for processing based on color characteristics. The rasterizer  34  may include fixed function operations such as triangle setup, span tile operations, a depth test (Z test), pre-packing, pixel interpolation, packing, etc. The rasterizer  34  may also include a transformation matrix for converting the vertices of an object in the world space to the coordinates on the screen space. 
     After rasterization, the rasterizer  34  sends the data to the pixel shader  36  for determining the final pixel values. The pixel shader  36  includes processing each individual pixel and altering the color values based on various color characteristics. For example, the pixel shader  36  may include functionality to determine reflection or specular color values and transparency values based on position of light sources and the normals of the vertices. The completed video frame is then output from the pipeline  24 . As is evident from this drawing, the shader units and fixed function units utilize the cache system  26  at a number of stages. Communication between the pipeline  24  and cache system  26  may include further buffering if the bus interface is an asynchronous interface. 
     In this embodiment, the components of the pipeline  24  are configured as separate units accessing the different cache components when needed. However, in other embodiments described herein, the pipeline  24  can be configured in a simpler fashion while providing the same functionality. In this way, the shader components can be pooled together into a unified shader. The data flow can be mapped onto a physical device, referred to herein as an execution unit, for executing a range of shader functions. In this respect, the pipeline is consolidation into at least one execution unit capable of performing the functions of the pipeline  24 . Also, some cache units of the cache system  26  may be incorporated in the execution units. By combining these components into a single unit, the graphics processing flow can be simplified and can include switching across the asynchronous interface. As a result, the processing can be kept local, thereby allowing for quicker execution. 
       FIG. 3A  is a block diagram of an embodiment of the GPU  18  shown in  FIG. 1  or other graphics processing device. The GPU  18  includes a unified shader unit  50 , which has multiple execution units (EUs)  52 , and a cache/control device  54 . The EUs  52  are oriented in parallel and accessed via the cache/control device  54 . The unified shader unit  50  may include any number of EUs  52  to adequately perform a desired amount of graphics processing depending on various specifications. When more graphics processing is needed in a design, more EUs can be added. In this respect, the unified shader unit  50  can be defined as being scalable. 
     In this embodiment, the unified shader unit  50  has a simplified design having more flexibility than the conventional graphics processing pipeline. In other embodiments, each shader unit needed a greater amount of resources, e.g. caches and control devices, for operation. In this embodiment, the resources can be shared. Also, each EU  52  can be manufactured similarly and can be accessed depending on its current workload. Based on the workload, each EU  52  can be allocated as needed to perform one or more functions of the graphics processing pipeline  24 . As a result, the unified shader unit  50  provides a more cost-effective solution for graphics processing. 
     Furthermore, when the design and specifications of the API  20  changes, which is common, the unified shader unit  50  is designed such that it does not require a complete re-design to conform to the API changes. As a non-limiting example, another shader can be added to the graphics pipeline, which is a change of the specifications of the API  20 . Instead, the unified shader unit  50  can dynamically adjust in order to provide the particular shading functions according to need. The cache/control device  54  includes a dynamic scheduling device to balance the processing load according to the objects or scenes being processed. More EUs  52  can be allocated to provide greater processing power to specific graphics processing, such as shader functions or fixed functions, as determined by the scheduling device. In this way, the latency can be reduced. Also, the EUs  52  can operate on the same instruction set for all shader functions, thereby simplifying the processing. 
     In particular, the cache/control device  54  may comprise a scheduler  55 , which allocates the EUs  52  as needed. The scheduler  55  stores an initial assignment of EUs  52  based on a predetermined allocation. When certain shading functions begin to bottleneck due to processing of a certain type of shading, the scheduler  55  determines the bottleneck and also determines resources that are the least busy or “starving” for additional work. The starving EU resources are reallocated to the bottleneck functions to relieve the bottleneck situation. This reallocation is performed by the scheduler  55  dynamically based on current needs. As processing needs change over time, the scheduler  55  continues to make proper allocation adjustments to properly balance the processing load. This approach can be considered as coarse granularity level scheduling of EUs  52  resources. 
     In addition, the EUs  52  can be divided into a number of “threads,” which represent tasks that can be performed in parallel in the EUs  52 . In some embodiments, the resources of EUs  52  are divided into  32  threads, for example. The scheduler  55  is capable of storing an initial allocation for the threads of the EUs  52  and adjusting the allocation on a higher degree of granularity. Again, this reallocation is dynamic and is based on current need as determined by the scheduler  55 . This second approach can be considered as fine granularity level scheduling. 
     The scheduler  55 , in general, is a dynamic scheduling device that operates on the thread level, but can also operate on the EU level. When finer granularity is needed, the scheduler  55  allocates one or more threads of an EU to one shading stage while allocating one or more threads of the EU to another shading stage. The allocation involves switching the threads to operate as needed. This greater resolution of allocation or switching is particularly useful with respect to lower end processors having fewer EUs  52 . Otherwise, if a device with few EUs is incapable of thread level scheduling control, a ping-pong scenario may result where an EU is switched from one stage to another in a futile attempt to reduce bottlenecks in more than one shading stages. 
     The scheduler  55  can be implemented, for example, to calculate a projected instruction throughput based on past and current demand. Based on the projected throughput, the scheduler  55  attempts to optimize, or at least reduce any bottleneck situations, by switching the thread resources to perform needed shading functions. The scheduler  55  thus analyzes the threads that are bottlenecked and those that are starving. By comparing the projected throughput with the current condition, the scheduler  55  can dynamically switch the functions of threads if it is determined that such a switching operation can improve the throughput. 
       FIG. 3B  is a block diagram of another embodiment of the GPU  18 . Pairs of EU devices  56  and texture units  58  are included in parallel and connected to a cache/control device  60 . In this embodiment, the texture units  58  are part of the pool of execution units. The EU devices  56  and texture units  58  can therefore share the cache in the cache/control device  60 , allowing the texture unit  58  access to instructions quicker than conventional texture units. The cache/control device  60  in this embodiment include a read-only cache  62 , a data cache  64 , a vertex shader control device (VS control)  66 , and a raster interface  68 . The GPU  18  also includes a command stream processor (CSP)  70 , a memory access unit (MXU)  72 , a raster  74 , and a write back unit (WBU)  76 . 
     Since the data cache  64  is a read/write cache and is more expensive than the read-only cache  62 , these caches are kept separate. The read-only cache  62  may include about 32 cachelines, but the number may be reduced and the size of each cacheline may be increased in order to reduce the number of comparisons needed. The hit/miss test for the read-only cache  62  may be different than a hit/miss test of a regular CPU, since graphics data is streamed continually. For a miss, the cache simply updates and keeps going without storing in external memory. For a hit, the read is slightly delayed to receive the data from cache. The read-only cache  62  and data cache  64  may be level one (L1) cache devices to reduce the delay, which is an improvement over conventional GPU cache systems that use L2 cache. 
     The VS control  66  receives commands and data from the CSP  70 . The EUs  56  and TEXs  58  receive a stream of texture information, instructions, and constants from the cache  62 . The EUs  56  and TEXs  58  also receive data from the data cache  64  and, after processing, provide the processed data back to the data cache  64 . The cache  62  and data cache  64  communicate with the MXU  72 . The raster interface  68  and VS control  66  provide signals to the EUs  56  and receive processed signals back from the EUs  56 . The raster interface  68  communicates with a raster device  74 . The output of the EUs  56  is also communicated to the WBU  76 . 
     The cache/control device  60  may further include a scheduler (not shown), such as one which is similar to the scheduler  55  shown in  FIG. 3A , for scheduling tasks of the EUs  56 . The scheduler in this embodiment also handles the assignment of tasks to different EUs  56  and to individual threads of the EUs  56 . As the tasks are completed, the scheduler removes or drops the task from cache  62  and indicates that certain thread slots are not occupied. When empty thread slots are available, the scheduler assigns additional tasks to these threads. 
       FIG. 3C  is a block diagram of another embodiment of the GPU  18 . In this embodiment, the GPU  18  includes a packer  78 , an input crossbar, also known as asynchronous input interface,  80 , a plurality of pairs of EU devices  82 , an output crossbar, also known as asynchronous output interface,  84 , a write back unit (WBU)  86 , a texture address generator (TAG)  88 , a level  2  (L2) cache  90 , a cache/control device  92 , a memory interface (MIF)  94 , a memory access unit (MXU)  96 , a triangle setup unit (TSU)  98 , and a command stream processor (CSP)  100 . 
     The CSP  100  provides a stream of indices to the cache/control device  92 , where the indices pertain to an identification of a vertex. For example, the cache/control  92  may be configured to identify  256  indices at once in a FIFO. The packer  78 , which is preferably a fixed function unit, sends a request to the cache/control device  92  requesting information to perform pixel shading functionality. The cache/control device  92  returns pixel shader information along with an assignment of the particular EU number and thread number. The EU number pertains to one of the multiple EU devices  82  and the thread number pertains to one of a number of parallel threads in each EU for processing data. The packer  78  then transmits texel and color information, related to pixel shading operations, to the input crossbar  80 . For example, two inputs to the input crossbar  80  may be designated for texel information and two inputs may be designated for color information. Also, each input may be capable of transmitting 512 bits, for example. 
     The input crossbar  80 , which can be a bus interface, routes the pixel shader data to the particular EU and thread slot according to the assignment allocation defined by the cache/control device  92 . The assignment allocation may be based on the availability of EUs and empty threads, or other factors, and can be changed as needed. With several EUs  82  connected in parallel and with each EU capable of handling several parallel tasks (or threads), a greater amount of the graphics processing can be performed simultaneously. Also, with the easy accessibility of the cache, the data traffic remains local without requiring fetching from a less-accessible cache. In addition, the traffic through the input crossbar  80  and output crossbar  84  can be reduced as compared with conventional graphics systems, thereby reducing processing time. 
     Each EU  82  processes the data using vertex shading and geometry shading functions according to the manner in which it is assigned. The EUs  82  can be assigned, in addition, to process data to perform pixel shading functions based on the texel and color information from the packer  78 . As illustrated in this embodiment, five EUs  82  are included and each EU  82  is divided into two divisions, each division representing a number of threads. Each division can be represented as illustrated in the embodiments of  FIGS. 4-6 , for example. The output of the EU devices  82  is transmitted to the output crossbar  84 . 
     When graphics signals are completed, the signals are transmitted from the output crossbar  84  to the WBU  86 , which leads to a frame buffer for displaying the frame on the display device  16 . The WBU  86  receives completed frames after one or more EU devices  82  process the data using pixel shading functions, which is the last stage of graphics processing. Before completion of pixel shading functions of each frame, however, the processing flow may loop through the cache/control  92  one or more times due to dependent texture reads. During intermediate processing, the TAG  88  receives dependent texture coordinates from the output crossbar  84  to determine addresses to be sampled. The TAG  88  may operate in a pre-fetch mode or a dependency read mode. A texture number load request is sent from the TAG  88  to the L2 cache  90  and load data can be returned to the TAG  88 . 
     Also output from the output crossbar  84  is vertex data, which is directed to the cache/control device  92 . In response, the cache/control device  92  may send data input related to vertex shader or geometry shader operations to the input crossbar  80 . Also, read requests are sent from the output crossbar  84  to the L2 cache  90 . In response, the L2 cache  90  may send data to the input crossbar  80  as well. The L2 cache  90  performs a hit/miss test to determine whether data is stored in the cache. If not in cache, the MIF  94  can access memory through the MXU  96  to retrieve the needed data. The L2 cache  90  updates its memory with the retrieved data and drops old data as needed. The cache/control device  92  also includes an output for transmitting vertex shader and geometry shader data to the TSU  98  for triangle setup processing. 
     The cache/control device  92  may also include a scheduling device (not shown), such as one similar to the scheduler  55  shown in  FIG. 3A , for scheduling various shader stages of the EUs  56 . The scheduling device is able to assign tasks to different EUs  56  and even can assign different types of shading tasks to individual threads of the EUs  56 , based on the particular processing need at the time. In this respect, the assignment and allocation of resources is performed dynamically to reallocate in such as way as to substantially balance the processing load. By balancing the load, potential bottleneck situations involving overly busy EUs and/or threads can be minimized. 
     As each task is completed, the scheduling device removes the task from a resource table in cache  62  and indicates the availability of the thread slots that are not presently occupied or busy. When thread slots are available, the scheduler can assign additional tasks to these threads. 
       FIG. 4  is a block diagram of an embodiment of a general execution unit (EU)  102 . The EU  102  may be embodied as the EU  52  shown in  FIG. 3A , the EU  56  shown in  FIG. 3B , a half of the EU device  82  shown in  FIG. 3C , or other suitable execution unit capable of parallel processing of multiple shader and fixed function operations. In this embodiment, the EU  102  includes a thread control device  104 , a cache system  106 , and a thread processing path  108 . These elements are communicated with other parts of the GPU  18  via input crossbar  110  and output crossbar  112 . The input crossbar  110  and output crossbar  112  may correspond, for example, with the input crossbar  80  and output crossbar  84 , respectively, shown in  FIG. 3C . 
     The thread control device  104  includes control hardware to determine an appropriate allocation of the EU data path resources, i.e. thread processing path  108 . An advantage of the compact processing pipeline defined by the thread processing path  108  is to reduce the data flow, which may require fewer clock cycles and fewer cache misses. Also, the reduced data flow puts less pressure on the asynchronous interfaces, thus potentially reducing a bottleneck situation at these components. By adopting the EU  102  or other EUs disclosed herein, a reduction in processing time with respect to conventional graphics processors may result. 
     The thread control device  104  controls the data flow within the EU. By managing the status of each thread, the thread control  104  can determine how each thread will be executed. Also, the thread control  104  determines an allocation to utilize EUs and threads that are available and decrease the load on processing resources that may be overly busy or bottlenecked. By dynamically reallocating the resources, the thread control  104  can maximize data throughput to allow for greater shading functionality and increased speed. 
     The thread processing path  108  is the core of the graphics processing pipeline and can be programmable. Because of the flexibility of the thread processing path  108 , a user can program the EU to perform a greater number of graphics operations than conventional real-time graphics processors. The thread processing path  108  includes vertex shading processing, geometry shading processing, triangle setup, interpolation, pixel shading processing, etc. Because of the compactness of the EU  102 , the need to send data out to memory and later retrieve the data is reduced. For example, if the thread processing path  108  is processing a triangle strip, several vertices of the triangle strip can be handled by one EU while another EU simultaneously handles several other vertices. Also, for triangle rejection, the thread processing path  108  can more quickly determine whether or not a triangle is rejected, thereby reducing delay and unnecessary computations. 
     In some embodiments, the input crossbar  110  and output crossbar  112  are asynchronous interfaces allowing the EU to operate at a clock speed different from the remaining portions of the GPU. For example, the EU may operate at a clock speed that is twice the speed of the GPU clock. Also, the thread processing path  108  may further operate at a clock speed that is twice the speed of the thread control  104  and cache system  106 . Because of the difference in clock speeds, the crossbars  110  and  112  may be configured with buffers to synchronize processing between the internal EU components and the external components. These or other similar buffers are shown, for example, in  FIG. 5 . 
       FIG. 5  is a block diagram of an embodiment of the EU  102  of  FIG. 4  illustrated in greater detail. In this embodiment, the cache system  106  as illustrated includes an instruction cache  114 , a constant cache  116 , and a vertex and attribute cache  117 . The thread processing path  108  as illustrated includes a common register file (CRF)  118  and an EU data path  120 . The CRF  118  includes even and odd paths. The EU data path  120  includes arithmetic logic units (ALUs)  122 ,  123  and an interpolator  124 . The input crossbar  110  includes an execution unit pool control (EUP control)  126 , cache  128 , texture buffer  130 , and data cache  132 . The output crossbar  112  includes an EUP control  134 , cache  136 , and an output buffer  138 . The embodiment of  FIG. 5  also includes an indexing input fetch unit (IFU)  140  and a predicate register file (PRF)  142 . 
     Because of the asynchronous nature of the input crossbar  110  and output crossbar  112 , the asynchronous interfaces include buffers to coordinate processing with external components of the GPU. Signals from the EUP control  126  are transmitted to the thread control  104  to maintain multiple threads of the thread processing path  108 . The cache  128  sends instructions and constants to the instruction cache  114  and constant cache  116 , respectively. Texture coordinates are transmitted from the texture buffer  130  to the CRF  118 . Data is transmitted from the data cache  132  to the CRF  118  and VAC  117 . 
     The instruction cache  114  sends an instruction fetch to the thread control  104 . In this embodiment, a large portion of the fetches will be hits, and a small portion of fetches that are misses are sent from the instruction cache  114  to the cache  136  for retrieval from memory. Also, the constant cache  116  sends misses to the cache  136  for data retrieval. The processing of the thread processing path  108  includes loading the CRF  118  with data according to an even or odd designation. Data on the even side is transmitted to ALU  0  ( 122 ) and data on the odd side is transmitted to ALU  1  ( 123 ). The ALUs  122 ,  123  may include shader processing hardware to process the data as needed, depending on the assignment from the thread control device  104 . Also in the EU data path  120 , the data is sent to interpolator  124 . 
       FIG. 6  is a block diagram of another embodiment of the EU  102  of  FIG. 4  showing greater detail. In this embodiment, the EU  102  may include one-half of an EU device  82  as depicted in  FIG. 3C . The EU half  102  (EU  0  or EU  1 ) includes Xin interface logic  144 , an instruction cache  146 , a thread cache  148 , a constant buffer  150 , and a common register file  152 . The EU half  102  further includes an execution unit data path  154 , a request FIFO  156 , a predicate register file  158 , a scalar register file  160 , a data out control  162 , Xout interface logic  164 , and a thread task interface  166 . 
     The instruction cache  146  can be an L1 cache and may include, for example, about 8 Kbytes of static random access memory (SRAM). The instruction cache  146  receives instructions from the Xin interface logic  144 . Instruction misses are sent as requests to the Xout interface logic  164 . The thread cache  148  receives assignment threads and issues instructions to the execution unit data path  154 . In some embodiments, the thread cache  148  includes 32 threads. The constant buffer  150  receives constants from the Xin interface logic  144  and loads the constant data into the execution unit data path  154 . The constant buffer in some embodiments includes 4 Kbytes of memory. The CRF  152  receives texel data, which is transmitted to the execution unit data path  154 . The CRF  152  may include 16 Kbytes of memory, for example. 
     The execution unit data path  154  decodes the instructions, fetches operands, and performs branch computations. The execution unit data path  154  further performs floating point or integer calculation of the data and shift/logic, deal/shuffle, and load/store operations. Texel data and misses are transmitted from the execution unit data path  154  via the request FIFO  156  to the Xout interface logic  164 . The PRF  158  and SRF  160  may be 1 Kbyte each, for example, and provide data to the execution unit data path  154  as needed. 
     Control signals are input from outside the EU  102  to the data out control device  162 . The data out control  162  also receives signals from the execution unit data path  154  and data from the Xin interface logic  144 . The data out control  162  may also request data from the CRF  152  as needed. The data out control device  162  outputs data to the Xout interface logic  164  and to the thread task interface for determining the future task assignment of threads according to the completed or in-progress data. 
     The data flow through the execution unit data path  154  may be classified into three levels, including a context level, a thread level and an instruction (execution) level. At any given time, there are two contexts in each EU. The context information is passed from the execution unit data path  154  before a task of this context is started. Context level information, for example, includes shader type, number of input/output registers, instruction starting address, output mapping table, horizontal swizzle table, vertex identification, and constants in the constant buffer  150 . 
     Each EU can contain up to 32 threads, for example, in the thread cache  148 . Threads correspond to functions similar to a vertex shader, geometry shader, or pixel shader. One bit is used to distinguish between the two contexts to be used in the thread. The threads are assigned to one of the thread slots in the execution unit data path that is not completely full. The thread slot can be empty or partially used. The threads are divided into even and odd groups, each containing a queue of 16 threads, for example. After the thread has started, the thread will be put into an eight-thread buffer, for example. The thread fetches instructions according to a program counter to fetch up to 256 bits, for example, of instruction data in each cycle. The thread will stay inactive if waiting for some incoming data. Otherwise, the thread will be in an active mode. 
     The arbitration of thread execution pairs two active threads together from the eight-thread buffer, depending on the age of the threads and other resource conflicts, such as ALU or CRF conflicts. Since some of the thread may enter inactive mode during execution, better pairing of the eight threads can be achieved. At the end of execution, the thread is moved from the working buffer and an end-of-program token is issued down stream. The token enters the data out control device  162  to move the data out to the Xout interface logic  164 . Once all data is moved out, the thread will be removed from the thread slot and the execution unit data path  154  is notified. The data out control  162  also moves data from the CRF  152  according to a mapping table. Once the registers are clear, the execution unit data path  154  can load the CRF  152  for the next thread. 
     Regarding the instruction data flow, the thread execution generates an instruction fetch. For example, there may be 64 bits of data in each compressed instruction. The thread control can decompress the instruction, if necessary, and perform a scoreboard test and then proceed to an arbitration stage. In order to increase efficiency, the hardware can pair the instructions from different threads. 
     The instruction fetch scheme between thread control and instruction cache may include a miss, which returns a four-bit set address plus a two-bit way address. A broadcast signal of the incoming data from the Xin interface logic  144  may be received. The instruction fetch may also include a hit, in which the data is received on the next clock cycle. A hit-on-miss may be similar to a miss result. Miss-on-miss may return a four-bit set address and the broadcast signal from the Xin interface logic can be received on a second request. In order to keep the thread running, the scoreboard maintains requested data that comes back. A thread can be stalled if the incoming instruction needs this data to proceed. 
       FIG. 7  is a block diagram of an embodiment of a thread controller  170  of an exemplary execution unit. In this embodiment, the thread controller  170  includes a thread status device  172 , an age comparison device  174 , a number of valid select devices  176 , a thread instruction queue  178 , multiplexers  180 , conflict checking devices  182 , and an arbiter  184 . This embodiment includes four valid select devices  176  and 28 sets of multiplexer  180  pairs and conflict checking devices  182 , particularly for a system where the execution unit includes 32 threads. In other embodiments where the execution units include a different number of threads, one of ordinary skill will appreciate that the number of components in the thread controller  170  may be changed accordingly. 
     With 32 threads within the execution unit, the threads can be divided into two equal even and odd groups, where each group contains 16 threads. The age of the thread, availability, and arbitration is managed separately for each group. Control of the threads is provided in two stages. In the first stage, the 16 threads are divided into four sets with four threads within each set. The four threads of each set are provided to a respective valid select device  176 . In this example of an even grouped division, the thread numbers for the first valid select device  176 , for example, include threads 0, 2, 4, and 6. In every cycle, up to two valid threads are selected from each set and provided at the output of the valid select devices  176 . These outputs are referred to herein as “slots” or “instruction select slots”, where the first valid select device  176  outputs slots  0  and  1  (s 0 , s 1 ). The instructions of the selected threads are stored in the thread instruction queue  178  for later use, as explained below. In the same cycle, the ages of the 16 threads are compared by the age comparison device  174  to determine the oldest thread that is available. The oldest thread is selected and provided to the arbiter  184  for the next cycle. 
     In the second stage of thread control, which is performed in the next cycle, the next instructions of the eight selected threads are output from the thread instruction queue  178  to the multiplexers  180 . These instructions are provided to the multiplexers  180  in such a way that comparisons between instructions of each possible pairings of the eight selected threads can be made. For example, instructions for slot  0  and slot  1  provided to the first pair of multiplexers  180  and corresponding instructions of each slot are compared by the first conflict checking device  182 . Each slot is therefore compared with the other seven slots at other multiplexer pairings. In this respect, there are  28  total combinations of pairings for comparison, where each comparison can be performed in parallel by the multiple conflict checking devices  182 . 
     Each of the conflict checking devices  182  compares the instructions of the respective slots and determines any conflict with respect to several different criteria. First, the conflict checking devices  182  check for any source and destination memory and ALU access conflicts, such as a CRF bank read/write conflict, a constant buffer read conflict, a scalar register file and predicate register file conflict. The conflict checking devices  182  can also check for floating-point, integer, logical, or L/S ALU access conflicts. 
     The result of the 28 combinations of conflict checks is multiplexed by the arbiter  184  with the oldest thread selected from the previous cycle. If a pair that includes the oldest thread is found to be matched (no conflict), the two instructions are issued simultaneously at the output of the arbiter  184  and sent to the execution unit datapath for execution. If none of the pairs that include the oldest thread is found to be matched, then other matched pairs, if any, can be issued from the arbiter  184 . If none of the pairs matches, the oldest thread is issued. With the combination of the even and odd groups of threads, up to four instructions can be issued for execution during the same cycle. 
     Controlling the threads as described therefore includes receiving the threads from the pool of execution units. In the example where each EU comprises 32 threads, the information for the threads is buffered and 16 of the 32 active threads are assigned. The threads are then handled to determine the status of each, including, for example, determining an empty, ready, sleep, wakeup, or inactive status. The control then includes arbitrating the threads in the queue to select one thread with the highest priority, i.e. oldest thread, to be issued if an empty slot in the active thread unit is available. 
       FIG. 8  is a block diagram illustrating another embodiment of a thread controller  186 , which may be configured to have several similarities to the thread control device  104  shown in  FIGS. 4 and 5  and/or the thread controller  170  of  FIG. 7 . In the embodiment of  FIG. 8 , the thread controller  186  includes an EU pool load thread device  188 , a thread buffer  190 , a number of thread queues  192 , a L1 cache interface  194 , an L1 cache  196 , a thread arbitration devices  198  and  200 , and execution unit data paths  202  and  204 . 
     In operation, a new thread to be processed is accepted from the EU pool by the EU pool load thread device  188  and loaded into the thread buffer  190 . When the thread buffer  190  is loaded with 32 new threads, 16 of these threads are assigned through an even channel to a first respective set of thread queues  192  and 16 of the threads are assigned through an odd channel to a second respective set of thread queues  192 . From the first set of thread queues  192 , the even threads are supplied to the L1 cache interface  194  and are also supplied to the even thread arbitration device  198 . From the second set of thread queues  192 , the odd threads are also supplied to the L1 cache interface  194  and in addition are supplied to the odd thread arbitration device  200 . The L1 cache interface  194  supplies thread data to the L1 cache  196  and can determine from the data stored in the L1 cache  196  whether requests for data result in a hit or miss in the L1 cache  196 . 
     The even thread arbitration device  198  performs an arbitration algorithm to choose one or two of the 16 even threads for processing. The selected threads are passed on to the even execution unit data path  202  to undergo specific shading processing functions as designated for the threads. In addition, the odd thread arbitration device  200  arbitrates among the 16 odd threads to choose the one or two threads to be processed. These odd threads are passed to the odd EUDP  204  to undergo the shading functions as determined for the threads. 
     The arbitration algorithms used by the thread arbitration devices  198  and  200  may include any suitable technique for arbitrating the threads. In some embodiments, the arbitration algorithms may include handling the status of the threads. For example, each thread may be determined to include a status such as empty, ready, sleeping, awake, active, inactive, etc. In some embodiments, the arbitration algorithm includes selecting the threads having the highest priority with regard to a certain characteristic. The priority may be based, for example, on age of the thread, where the oldest thread is given the highest priority. The selected threads are made active when an empty slot in the active thread unit is available. 
       FIG. 9  is a block diagram of an embodiment of a thread queue  206 . In some embodiments, the thread queue  206  of  FIG. 9  may represent one or more of the thread queues  192  shown in  FIG. 8 . According to this implementation as illustrated in  FIG. 9 , the thread queue  206  includes a thread buffer  208 , an L1 cache interface  210 , an instruction fetch device  212 , a decompressed queue device  214 , a thread control device  216 , a scoreboarding device  218 , and a thread arbitrator  220 . For illustrative purposes, some of the components of  FIG. 9  may be similar in function and design with the corresponding components of  FIG. 8 . For example, the thread buffer  208  may be similar to the thread buffer  190 ; the L1 cache interface  210  may be similar to the interface  194 ; and the thread arbitrator  220  may be similar to the even and odd thread arbitration devices  198  and  200 . 
     Threads stored in the thread buffer  208  are loaded in the queue to await processing. The thread control device  216  receives a request for performing a particular function on a selected thread. In particular, the thread control device  216  receives a program count from the data path (EUDP) and provides the program count to the instruction fetch device  212 . Essentially, the thread control  216  commands the instruction fetch device  212  to fetch a processing instruction to be performed on the thread if the instruction is presently stored in the cache. The instruction is retrieved from cache via the L1 cache interface  210  on a hit, but may receive an indication that the request missed the cache. 
     In parallel, the scoreboarding device  218  performs functions as described with respect to the scheduling devices disclosed herein. Also, the scoreboarding device  218  receives an address from the common register file (CRF)  152  shown in  FIG. 6 . The scoreboarding device  218  provides a scoreboard or data dependency test for the decompressed queue  214 , which also receives instruction data from the cache via the cache interface  210 . The matched instruction data is then provided to the thread arbitrator  220 . In this way, the correct instruction can be matched with the respective thread for processing. 
       FIG. 10  is directed to a flow chart showing an embodiment of a method or process for managing tasks in a graphics processing unit. The method of  FIG. 10  includes buffering new threads (tasks or task units) to be processed, as indicated in block  222 . In block  224 , the threads are divided into two equal groups, an even group and an odd group. As an example, when 32 threads are buffered during block  222 , the dividing procedure of block  224  includes dividing the threads into two groups of 16. In block  225 , a scoreboard test can be completed as described above in reference to  FIG. 9 . In block  226 , the method includes fetching instructions, such as from cache or other suitable memory. Fetching the instructions is performed based on a current program counter to synchronize instruction data with respective tasks to be performed. Each instruction may be 256 bits, for example. However, the instructions can be compressed before storage in memory. In this respect, fetching the instruction, as indicated in block  226 , further includes decompressing any compressed instructions. 
     In block  227 , either thread or instruction level arbitration can be completed. Then, in block  228 , two threads are paired together to improve efficiency by allowing two threads having the same instruction to be processed together. The pairing in this respect includes matching those threads having the same task to be performed, which thereby reduces the number of instruction fetches to memory. The pairing of threads can also be based on age of the threads and any conflicts that may exist, such as ALU access conflicts, CRF bank read/write conflicts, constant buffer read conflicts, scalar register file and predicate register file conflicts, and floating-point/integer/logical/ALU access conflicts. Pairing the threads may further include assigning each thread or task unit to an empty slot of an execution unit. 
     The unified shaders and execution units of the present disclosure can be implemented in hardware, software, firmware, or a combination thereof. In the disclosed embodiments, portions of the unified shades and execution units implemented in software or firmware, for example, can be stored in a memory and can be executed by a suitable instruction execution system. Portions of the unified shaders and execution units implemented in hardware, for example, can be implemented with any or a combination discrete logic circuitry having logic gates, an application specific integrated circuit (ASIC), a programmable gate array (PGA), a field programmable gate array (FPGA), etc. 
     The functionality of the unified shaders and execution units described herein, as well as the method of  FIG. 10 , can include an ordered listing of executable instructions for implementing logical functions. The executable instructions can be embodied in any computer-readable medium for use by an instruction execution system, apparatus, or device, such as a computer-based system, processor-controlled system, or other system. A “computer-readable medium” can be any medium that can contain, store, communicate, propagate, or transport the program for use by the instruction execution system, apparatus, or device. The computer-readable medium can be, for example, an electronic, magnetic, optical, electromagnetic, infrared, or semiconductor system, apparatus, device, or propagation medium. 
     It should be emphasized that the above-described embodiments are merely examples of possible implementations. Many variations and modifications may be made to the above-described embodiments without departing from the principles of the present disclosure. All such modifications and variations are intended to be included herein within the scope of this disclosure and protected by the following claims.