Abstract:
The disclosed invention provides a solution for the problem of blending colors in a graphics processing unit. The plurality of blending equations used in various graphics layers is performed with a programmable streaming processor. Multiple simultaneous threads are used to eliminate pipeline latency and memory stalls. Overlays of predefined blending modes are used to minimize the time instruction memory is updated. 
     The processing unit includes: (a) an instruction memory (b) hardware context registers for each executing stream (c) pipelined arithmetic units of predefined precision, including support for floating point (d) units that convert multi-format data to and from floating point precision (e) Look-up tables for quick color space transformations.

Description:
BACKGROUND OF THE INVENTION 
     The disclosed invention is related to graphics display technology, and more specifically to methods for blending colors in a graphics processing unit. Color blending is a process which combines color channels and alpha channels from sources of image information in order to generate modified image information. One such method has been described by Thomas Porter and Tom Duff in “Compositing Digital Images”,  Computer Graphics,  18(3), July 1984, 253-259. 
     Blending is required in systems like computer-generated graphics, image fusion for visualisation, graphical user interfaces etc. and is usually part of a Graphics Processing Unit (GPU), i.e. of a device that can render graphic images to be displayed on computer screens. 
     Image blending was used from the start of motion picture generations (U.S. Pat. No. 1,262,954). Blending was part of computer-based image processing since its origins (U.S. Pat. Nos. 4,384,338, 4,679,040, 4,827,344). 
     Original blender implementations were based on image multiplexing at the output to a screen via analog circuitry or on software programmes running on standard processors. This method is suitable for applications where high-speed software processing resources are available or where there is no high-speed requirement for the generation of the output images, as is the case with photograph editing. 
     In order to be able to process blending in real time systems, a hardware blender is required. Methods that implement blending in hardware have been proposed as described in the following paragraphs: 
     One of the first architectures of a blending apparatus was suggested in U.S. Pat. No. 5,592,196. This apparatus includes instructions for implementing the blending functions. These instructions are included in tables which form a blending mode, making the method fast but not as flexible as a full programmable approach. 
     A hardware implementation of blending targeted explicitly to 3D graphics has been disclosed in U.S. Pat. No. 5,754,185. This method did not include any programmability mechanism but rather defined blending mode via control signals. 
     Another hardware implementation is described in U.S. Pat. No. 5,896,136. This description mentions a unit that implements blending equations by using an alpha channel of lower resolution than the RGB channels. 
     In a structure described in U.S. Pat. No. 7,397,479 a method for providing programmable combination of pixel characteristics is disclosed. 
     Methods for implementing programmable blending were disclosed with patent application US 2006/192788 and U.S. Pat. No. 7,973,797. In both cases, the instructions for blending are provided by a processing unit loading formula or operation descriptors as a sequence to be executed by the blending hardware. 
     Blending in the above referenced cases is defined as the process of generating a target pixel fragment value (T) by combining various inputs: a said source pixel fragment (S), a said destination pixel fragment (D) and corresponding alpha values (A s , A d ) for the source and destination pixels. Depending on the blending mode a different function (f) is applied in order to calculate the target. 
     For calculating the target (T=f(S, A s , D, A d )), an arithmetic and logical unit (ALU) is employed that uses the said inputs and the blending mode in order to produce the target value. For many blending modes, computing the formula in a single operation requires complex hardware. In order to minimize hardware using simpler operators, the outputs can re-enter the ALU a second time or more until the formula is calculated. 
     During this iterative process the blender cannot receive new inputs, thus complex blending modes result in lower overall throughput of the GPU. One method to achieve higher throughput is to implement the ALU as a pipeline of at least two threads. If the input pixel fragments can be provided in a continuous flow, the pipeline can produce one output per each clock cycle. 
     The current state of the art in color blending devices as described above provides fast and programmable functionality. Many different operations—from a predefined set—can be performed on sequences of pixel fragments, where each pixel is represented as a color (c, usually R,G,B) and alpha (α) combination. 
     One shortcoming of current implementations is that they are best fit for systems where the locations of subsequent pixel fragments are more or less continuous. In a modern GPU system like the one shown in  FIG. 2 , Shader  206  processing and communication to the main memory for reading and writing pixel fragments is a bottleneck. Thus, the system cannot generate a steady flow of continuous pixel fragments. 
     Another limitation is that most current implementations operate on integer or fixed-point representations. This makes it harder to interface with floating-point pixel sources and frame buffers. Furthermore, this limits the dynamic range of color representation for each pixel fragment. 
     Another limitation of most current solutions is that the programmability is constrained by a few predefined operators. In one case only (U.S. Pat. No. 7,973,797), the operation is guided by two instructions which can be configured by other entities in the GPU. A more flexible approach is required for full programmability, where any sequence of instructions including flow control can be provided as input in the form of a small program for the blender core. 
     All existing implementations support the RGBA color scheme that is very common in computer graphics; each pixel fragment is represented by three color channels of Red, Green and Blue (RGB) and an Alpha channel (A). However, if one has to blend non-RGBA pixel fragments (for example pixels in YUVA representation commonly used in video and photography), there needs to be another step of color space conversion, consuming time and bandwidth. 
     SUMMARY OF THE INVENTION 
     The disclosed apparatus provides color blending functionality with fully programmable sequences of operations on the source and destination pixel fragments. The architecture of the device is based on the observation that modern graphics systems do not generate steady flow of pixel fragments, leaving the blender with unused processing capability. 
     The disclosed blender takes advantage of this fact in order to multiplex in time many blending functions on different fragments of pixels. This is achieved by the multithreading capability of the blender core. 
     The disclosed device is a blender which is build around arithmetic and logic units (ALUs) that implement a plurality of blending functions as defined by a sequence of instructions. The core of the said blender is capable of pipelining the instructions in order to achieve high throughput of results. Furthermore, the said blending core can handle instructions from a plurality of sequences and operate on a plurality of input streams. This feature of the said blending core provides for multithreaded operations, thus minimizing the time a blender has to wait for non-continuous pixel fragments to be fetched from a memory. 
     The disclosed blending device consists of (a) circuitry that reads, reformats and aligns pixel fragments from two inputs, (b) a blending core that can execute threads of instruction sequences in order to generate a result and (c) an output selection and reformatting circuitry that produces the final output pixel fragments. 
     In one embodiment, the disclosed apparatus will be able to run the following operations:
         Blending of source &amp; destination pixel fragments according to alpha values and a chosen mode.   Concurrent multithreaded processing of a plurality of pixel fragments with different blending functions applied to each pixel fragment.   Implementation of a wide variety of blending modes including the ones defined in the Khronos group standards OpenGL and OpenVG, regardless if the input or output streams are premultiplied or non-premultiplied.   Conversion from RGB to YUV color space and vice versa.   Gamma/degamma color correction.       

    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  shows a typical minimal embedded system-on-chip with a graphics processing unit. 
         FIG. 2  shows a top level block diagram of a graphical processing unit (GPU) that is implemented using the disclosed blending device. 
         FIG. 3  shows a possible structure of the disclosed blending device. 
         FIG. 4  contains a block diagram of a possible embodiment of the core multi-threaded blender. 
         FIG. 5  shows the internal structure of the ALU blocks of  FIG. 4 . 
         FIG. 6  presents the structure of a possible embodiment of an operations pipeline. 
         FIG. 7  presents some blending mode examples. 
         FIG. 8  shows a possible structure for the instructions used by the blender. 
     
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
     Usage 
     Graphics Processing Units (GPUs) are increasingly required to perform a plurality of blending functions. When projecting glyphs or user interface items like icons, buttons or window frames over an image, or when combining images from different sources, or when drawing a 3D scene with items on the foreground and items on the background, or when translucent items are displayed, in all those cases a target pixel value on the display is the result of the combination of two input pixel fragments weighted by a value called the alpha of that pixel fragment. 
     Some examples of blending modes are described in table 1, which are defined in the Qt application framework: 
     
       
         
               
             
               
               
             
           
               
                 TABLE 1 
               
             
             
               
                   
               
               
                 Blending mode examples 
               
             
          
           
               
                 Name 
                 Description 
               
               
                   
               
               
                 Source Over/ 
                 The alpha of the source is used to blend the pixel on top of the 
               
               
                 Destination Over 
                 destination. Destination Over is the inverse of Source Over. 
               
               
                 Clear 
                 The pixels in the destination are cleared (set to fully 
               
               
                   
                 transparent) independent of the source. 
               
               
                 Source/ 
                 The output is the source/destination pixel. 
               
               
                 Destination 
               
               
                 Source In/ 
                 The output is the source, where the alpha is reduced by that of 
               
               
                 Destination In 
                 the destination. Destination In is the inverse of Source In. 
               
               
                 Source Out/ 
                 The output is the source, where alpha is reduced by the inverse 
               
               
                 Destination Out 
                 of destination. Destination Out is the inverse of Source Out. 
               
               
                 Source Atop/ 
                 The source pixel is blended on top of the destination, with the 
               
               
                 Destination Atop 
                 alpha of the source pixel reduced by the alpha of the 
               
               
                   
                 destination pixel. Destination Atop is the inverse of Source 
               
               
                   
                 Atop. 
               
               
                 Xor 
                 The source, whose alpha is reduced with the inverse of the 
               
               
                   
                 destination alpha, is merged with the destination, whose alpha 
               
               
                   
                 is reduced by the inverse of the source alpha. 
               
               
                 Plus 
                 Both the alpha and color of the source and destination pixels 
               
               
                   
                 are added together. 
               
               
                 Multiply 
                 The output is the source color multiplied by the destination.. 
               
               
                 Screen 
                 The source and destination colors are inverted and then 
               
               
                   
                 multiplied. 
               
               
                 Overlay 
                 Multiplies or screens the colors depending on the destination 
               
               
                   
                 color. The destination color is mixed with the source color to 
               
               
                   
                 reflect the lightness or darkness of the destination. 
               
               
                 Darken 
                 The darker of the source and destination colors is selected. 
               
               
                 Lighten 
                 The lighter of the source and destination colors is selected. 
               
               
                 Color Dodge 
                 The destination color is brightened to reflect the source color. A 
               
               
                   
                 black source color leaves the destination color unchanged. 
               
               
                 Color Burn 
                 The destination color is darkened to reflect the source color. A 
               
               
                   
                 white source color leaves the destination color unchanged. 
               
               
                 Hard Light 
                 Multiplies or screens the colors depending on the source color. 
               
               
                   
                 A light source color will lighten the destination color, whereas a 
               
               
                   
                 dark source color will darken the destination color. 
               
               
                 Soft Light 
                 Darkens or lightens the colors depending on the source color. 
               
               
                   
                 Similar to HardLight. 
               
               
                 Difference 
                 Subtracts the darker of the colors from the lighter. Painting with 
               
               
                   
                 white inverts the destination color, whereas painting with black 
               
               
                   
                 leaves the destination color unchanged. 
               
               
                 Exclusion 
                 Similar to Difference, but with a lower contrast. Painting with 
               
               
                   
                 white inverts the destination color, whereas painting with black 
               
               
                   
                 leaves the destination color unchanged. 
               
               
                 Source Or/And/ 
                 Does a bitwise OR/AND/XOR operation on the source and 
               
               
                 Xor Destination 
                 destination pixels (src OR dst). 
               
               
                 Not Source And 
                 Does a bitwise NOR operation on the source and destination 
               
               
                 Not Destination 
                 pixels ((NOT src) AND (NOT dst)). Other similar modes are also 
               
               
                   
                 defined: ((NOT src) OR (NOT dst)), ((NOT src) XOR dst), (NOT 
               
               
                   
                 src), ((NOT src) AND dst), (src AND (NOT dst)). 
               
               
                   
               
             
          
         
       
     
     The example diagram of  FIG. 1  shows a typical system that performs graphics processing. The system connects all devices through a Bus Fabric  110  and is controlled by a Central Processing Unit (CPU)  102 . Graphics and Imaging functionality is performed in a Graphics Processing Unit (GPU)  200 . The program for the CPU and the GPU as well as the images handled by them are stored in a Memory  104 . The display of the system is updated through a Display Controller  106 . 
     In one embodiment of the disclosed invention, the GPU and the display controller are connected through a direct link  108  for frame synchronization and bandwidth shaping. 
     An abstract diagram of the GPU  200  from  FIG. 1  is given in  FIG. 2 . Connections to the CPU  212  and the Memory  214  are shown as direct links for simplicity, although they are typically implemented through a bus fabric. A Primitive Generator  204  block is used to create vectors, polygons, triangles, curves etc. as described in documents like U.S. Pat. No. 5,303,321. The core of the GPU is a processing unit, the Shader  206 , which calculates graphics functions in order to determine pixel fragment color and transparency values. One or more of said Shaders can exist in a GPU, each one dealing in parallel to the others with separate primitives or fragments. The output of the said Shader can be processed by units  208  that accelerate the generation of texture elements. Pixel fragments from the Shader are provided as input to a Blender  300 , which implements color/alpha blending. The Blender interfaces with the memory  214  for reading background image fragments and in order to store the blended output. 
     Structure 
     The disclosed apparatus is hereby described by reference to the block diagram of  FIG. 3 . This block diagram shows the units that constitute the said blending device ( 300  in  FIG. 2 ). The block diagram also shows connections between the units. 
     The disclosed blending device operates on input streams of pixel fragments. One input is the stream of source fragments  302  which is typically provided by a Shader. If the blending mode requires that the output solely depends on the said incoming fragments, then the data simply enters the Source Reformat and clamping circuit  308 . If the decision is made  304  that a Destination Fragment is also required, then a request to the memory is issued  318 , and the operation waits until the said destination fragment is received  320 , and reformatted and clamped  306 . 
     The two input streams come from different sources and need alignment  310  in order to be processed while maintaining spatial coherency. Processing is performed by the core  400  of the said blending device. The output of the core may have to be reformatted  312  if the target frame buffer uses a different pixel format. The same block  312  also performs color dithering in order to enhance the visual experience. When multiple outputs are generated, other circuitry  314  re-orders and aligns the pixel data so that they can be stored in the memory&#39;s frame buffer  316 . 
     The core of the disclosed blending device is a Blender Core  400  which is multi-threaded. By allocating processing resources to more than one thread of execution, the blender core can multiplex in time a number of parallel blending operations, hiding the latency of arithmetic units, hiding the latency of reading fragments and sustaining throughput. 
       FIG. 4  shows a possible embodiment of the said multi-threaded blender core. A brief description of the structure follows. The said blender core reads two aligned and appropriately preformatted pixel fragments, the source  404  and the destination  402 , consisting of color and alpha information for each input including possible stencil information in the alpha channel. The two inputs are maintained  406  until a processing slot in the arithmetic logic units becomes available. There are two arithmetic logic units ALUs, one for performing operations with the Alpha channel  430  and one for performing SIMD operations with the color channels  420 . 
     The ALUs perform operations by reading a sequence of instructions from the Instruction Memory Contexts  410 . Multiple contexts exist in order to support multithreading. Each instruction sequence forms a small program that is executed by the disclosed blender core utilizing the operators in the said ALUs. The ALUs can also employ temporary data storage and look-up tables  408  to perform certain operations. 
     The results from the blender core ALUs are selected  412  as defined in the instructions by the output circuitry and appropriately converted  414  to a suitable output pixel format, for example floating point (GL_RGBA32F, GL_RGBA16F), fixed point, RGB888, RGB565 etc. 
     The output from the said blender core can be stalled based on a signal  108  from the display controller  106 , indicating high risk of data starvation which might lead to loss of visible frames. 
     The internal structure of the ALUs of the disclosed blander core is shown in  FIG. 5 . As stated, the inputs are pixel fragments formatted for blending. One is the source pixel fragment that consists of source color  502  and source alpha  504 . The second is the destination pixel fragment which consists of destination color  506  and destination alpha  508 . The output is a pixel fragment represented by its color channels  516  and its alpha  518 . 
     The color ALU  420  in the diagram contains three parallel operation pipeline blocks  522 ,  524 ,  526  so that it can support up to three color channels. Other embodiments with less or more color channels are also possible. The output of each operation pipeline block can be fed back  510  to the ALU for a subsequent processing step or can be forwarded to one of a multitude of intermediate registers  528 ,  529 . 
     The Alpha ALU  430  contains one operation pipeline block  432  similar to the said operation pipeline blocks of the color ALU. The result is stored in a couple of intermediate registers  538 ,  539  or fed back  510  to the inputs of the ALUs for the next step in the blending sequence. 
     The output of the said color ALU is generated by combining or selecting  512  from the said two or more intermediate registers  528 ,  529  and storing the result in the target pixel color  516 . The output of the said alpha ALU is generated by combining or selecting  514  from the said two intermediate registers  538 ,  539  and storing the result in the target pixel alpha  518 . 
     The detail of each ALU operation pipeline block is shown in a possible embodiment in  FIG. 6 . The instructions are fetched for multiple threads from the instruction memory contexts  410 . A dedicated fetch logic circuitry  418  chooses one instruction from each active thread per clock and feeds them  660  to the internal pipeline stages of the ALU operation. The figure shows an example with four threads A, B, C and D. The first instruction from each thread —instr0— is already in the pipeline, the second instruction from each thread —instr1— is ready to be executed, and the following instructions—inst2, instr3, instr4—wait in the memory contexts. 
     The first stage is instruction decode  622  which determines the type of instruction and the corresponding operator  632  that must be used. It is possible that the instruction op-code affects directly the next instruction that needs to be fetched, thus executing a non-conditional branch. This branch request  642  is reported to the instruction fetch logic  418 . 
     Data are fetched  624  at the same clock cycle with instruction decode from the input port  610  of the ALU which can be connected to a previous output of the same or another ALU operations pipeline or to a temporary location in memory or to a look-up table. Fetched data are fed to the next pipeline stage via registers  634 . 
     The core operators of each currently processed instruction are in the subsequent pipeline stages  626 ,  628 ,  630 . Operators include multiplication, addition, subtraction, logical operators, reciprocal and floor/ceiling. The result is stored in pipeline registers  636 ,  638 ,  640  and the flags  644  generated by the operation are reported to the instruction fetch logic. The described embodiment uses three pipeline stages for the operators; alternative implementations can include more or less stages to achieve an optimum trade-off between complexity, throughput, latency and number of threads that can be supported. 
     The output from the last stage of the pipeline  640  is directly placed on the port of the ALU operations pipeline  650 . Depending on the op-code, the output can be fed back for a next instruction through the ALU or placed on the output register if processing of the specific data has finished. 
     A possible embodiment of the disclosed invention will include an instruction code structured as: 
     [OC: Op-code][DS: Destination][(S1: Source of input A][S2: Source of input B] 
     and four or more such instructions will constitute a very long instruction word (VLIW) instruction for the entire blending core. This is further illustrated in  FIG. 8 . 
     The entire VLIW instruction  820  that goes through the operating units consists of three or more instructions for the color channel pipelines and one instruction for the alpha pipeline. In each VLIW instruction, operations for reading inputs, storing outputs, performing SIMD processing of the RGB channels and branching are combined. Each instruction consists of an op-code  810 , a destination descriptor  812  and two source descriptors  814 ,  816 . The op-code  810  can be related to a set of mnemonics  830  for the supported operations. 
     The disclosed blender device is fully programmable, supporting any possible blending function. Some basic blending operations that are supported are shown in  FIG. 7 . The source  710  and the destination  720  are two input pixel fragments that can be blended in any of the shown manners. 
     The disclosed blending device also supports the blending modes defined by OpenVG: 
     
       
         
               
             
               
               
             
           
               
                 TABLE 2 
               
             
             
               
                   
               
               
                 OpenVG Blending Modes 
               
             
          
           
               
                 Name 
                 color Function 
               
               
                   
               
               
                 Source 
                 c src   
               
               
                 Source over Destination 
                 c src  + (1 − α src )*c dst   
               
               
                 Destination over Source 
                 c src *(1 − α dst ) + c dst   
               
               
                 Source in Destination 
                 c src *a dst   
               
               
                 Destination in Source 
                 c dst *a src   
               
               
                 Multiply 
                 α src *c src  *(1 − α dst ) + α dst *c dst *(1 − 
               
               
                   
                 α src ) + α src *c src *α dst *c dst   
               
               
                 Screen 
                 α src *c src  + α dst *c dst  − α src *c src *α dst *c dst   
               
               
                 Darken 
                 min(α src *c src  + α dst *c dst  *(1 − α src ), 
               
               
                   
                 α dst *c dst  + α src *c src  *(1 − α dst )) 
               
               
                 Lighten 
                 max(α src *c src  + α dst *c dst  *(1 − α src ), 
               
               
                   
                 α dst *c dst  + α src *c Src  *(1 − α dst )) 
               
               
                   
               
             
          
         
       
     
     The disclosed blending device also supports the OpenGL blending modes, where the function is c=c src *F src +c dst *F dst : 
     
       
         
               
             
               
               
               
             
           
               
                 TABLE 3 
               
             
             
               
                   
               
               
                 Blending modes defined for OpenGL 
               
             
          
           
               
                   
                 Name 
                 F src , F dst   
               
               
                   
                   
               
               
                   
                 Zero 
                 (0, 0) 
               
               
                   
                 One 
                 (1, 1) 
               
               
                   
                 Source color 
                 (C src  , α src ) 
               
               
                   
                 One Minus Source color 
                 (1 − C src  , 1 − α src ) 
               
               
                   
                 Destination color 
                 (C dst  , α dst ) 
               
               
                   
                 One Minus Destination color 
                 (1 − C dst , 1 − α dst ) 
               
               
                   
                 Source Alpha 
                 (α src  , α src ) 
               
               
                   
                 One Minus Source Alpha 
                 (1 − α src , 1 − α src ) 
               
               
                   
                 Destination Alpha 
                 (α dst , α dst ) 
               
               
                   
                 One Minus Destination Alpha 
                 (1 − α dst  , 1 − α dst ) 
               
               
                   
                 Source Alpha Saturate 
                 min(α src , 1 − α dst ) 
               
               
                   
                   
               
             
          
         
       
     
     To illustrate the functionality of the said blending device, an example of a specific operation is presented. The example shows the instruction sequence for implementing a “Source Over” blending operation with non-premultiplied inputs, as defined by the formula: 
                   c   src     *     α   src       +       (     1   -     α   src       )     *     c   dst     *     α   dst             α   src     +       (     1   -     α   src       )     *     α   dst               
The corresponding VLIW instructions are shown in the following listing.
 
     
       
         
               
               
               
               
             
           
               
                   
               
             
             
               
                 1: MUL P0, Cs, As 
                 NOP 
                 LDR Pa, As 
                 MUL Pb, Ad, 
               
               
                   
                   
                   
                 (1 − As) 
               
               
                 2: MUL P1, Cd, 
                 ADD Pc, Pa, Pb 
                 NOP 
                 NOP 
               
               
                 (1 − As) 
               
               
                 3: MUL P2, P1, Ad 
                 ADD P3, P0, P2 
                 NOP 
                 RCP Pd, Pc 
               
               
                 4: MUL P1, P3, Pd 
                 NOP 
                 OUT P1, Pa 
                 NOP 
               
               
                   
               
             
          
         
       
     
     The first VLIW instruction multiplies source color with source alpha c src *α src  storing the result in an intermediate register P 0 , multiplies destination alpha with the inverse of source alpha (1−α src )*α dst  and prepares the denominator α src +(1−α src )*α dst  in a register Pc. The second instruction finds the reciprocal of Pc into a register Pd, and multiplies destination color c dst  with (1−α src ) storing this in register P 1 . The third instruction multiplies P 1  with the destination alpha and adds P 0  and P 2 , the two parts of the nominator. The fourth VLIW line finalizes calculation by multiplying the nominator P 3  with the reciprocal of the denominator Pd. It also sends a command to the output selection blocks  512 ,  514  to provide the results (P 1  and Pa) to the output of the blender on the following clock cycle. *Work that led to the development of this invention, was co-financed by Hellenic Funds and by the European Regional Development Fund (ERDF) under the Hellenic National Strategic Reference Framework (NSRF) 2007-2013, according to Contract no. MICRO2-035 of the Project “TSi-ThinkVG” within the Programme “Hellenic Technology Clusters in Microelectronics—Phase-2 Aid Measure”.