Abstract:
A method and apparatus to improve motion prediction in video processing systems is introduced. When a motion prediction cache completes requesting data for a current macroblock and enters an into idle state, data comprising one or more reference frames is speculatively requested, with the hope that the requested data are will be needed in a subsequent macroblock. If the speculative data is needed, then it is consumed. However, if the speculative data is not needed, then the correct data must be requested and a price is paid for an extra memory read bandwidth. In case the speculative data is the correct data for the subsequent macroblock, the effective memory read latency is reduced and the decode performance increases. The video decoder becomes more immune to memory read latency.

Description:
FIELD OF INVENTION 
     This invention is generally related to video data caches. 
     BACKGROUND 
     Contemporary video compression algorithms require significant memory bandwidth for referencing previously decoded images. A decoder memory buffer is used to maintain a number of previously decoded image frames, termed reference frames, ready for display so these frames may be used as references in decoding other image frames. Due to the development and availability of high definition video, the rate at which the data in the decoder memory buffers are transferred has substantially increased. In addition, the decoder memory buffer may provide data blocks that are substantially larger than that required by the decoder to process a particular image block, thereby increasing the memory bandwidth without benefit. 
     Motion prediction is a commonly used technique for encoding video images. According to conventional video encoding techniques employing motion prediction, successive images are compared and the motion of a particular area in one image relative to another image is determined to generate motion vectors. A “macroblock” is a term used in video compression for such an area; typically a macroblock represents a block of 16×16 pixels. Different picture formats utilize different numbers of pixels and macroblocks. For example, a 1920×1088 HDTV pixel format includes 120×68 macroblocks. To decode a video bitstream, a decoder shifts blocks in a previous picture according to the respective motion vectors to generate the next image. This process is based on the use of intracoded frames, forward predicted frames and bi-directional coded frames as is known in the art. 
     In some video decoder systems, motion prediction (MP) caches are used to limit the data transfer rate from the memory buffer. An MP cache stores image pixel values for previously decoded macroblocks that may be useful for subsequent macroblocks to be decoded. An MP cache is typically limited in capacity and expensive in comparison to an external memory buffer. An MP cache typically includes only a small portion of the pixel data necessary for a single video frame. Consequently, data in an MP cache is quickly replaced as new macroblocks or parts of macroblocks are written to the cache. 
     In video decoders, for every macroblock, a set of motion vectors are decoded from a video bitstream and translated into addresses of pixels in the reference frame memory buffers. The pixels are then requested from the memory when they are needed, and are expected to return within a macroblock time period. The time elapsed between the request and the return of the imaging information is called the latency. The latency of a memory system from which the pixels are requested can often be quite high. In such a case the reference image data return slows down the video decoding process, which may cause some frames to be unable to be completed on time for display and, as a result, the frames are dropped. This can lead to a choppy playback. The motion prediction operation is well known to be a major source of the memory read latency bottleneck of a decoder memory system. Accordingly, improvements in memory use and reducing the bottleneck of the system are desired. 
     SUMMARY 
     A method and apparatus to improve motion prediction in video processing systems is introduced. When a motion prediction cache completes requesting data for a current macroblock and would typically enter into an idle state, data comprising one or more reference frames is speculatively requested, with the hope that the requested data will be needed in a subsequent macroblock. If the speculative data is needed, then it is immediately consumed. However, if the speculative data is not needed, then the correct data must be requested and a price is paid for an extra memory read bandwidth. In case the speculative data is the correct data for the subsequent macroblock, the effective memory read latency is reduced and the decode performance increases. Thus, the video decoder becomes more immune to memory read latency. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       A more detailed understanding may be had from the following description, given by way of example and to be understood in conjunction with the accompanying drawings wherein: 
         FIG. 1  is block diagram of a system for implementing a speculative motion prediction cache (MPC); 
         FIG. 2  is a block diagram of the speculative motion vector block of  FIG. 1 ; 
         FIG. 3  is a more detailed block diagram of the MPC block of  FIG. 1 ; 
         FIG. 4  is a process of reducing the memory read latency of a motion prediction system; 
         FIG. 5  is diagram of a memory cache of an MPC using direct mapping; and 
         FIG. 6  is a diagram of a cache tag identifying a speculatively tagged data. 
     
    
    
     DETAILED DESCRIPTION 
     A motion prediction cache (MPC) enables the use of reference image pixel data, (i.e., data which is stored in reference macroblocks), to build other macroblocks. As aforementioned, MPC may be expensive as compared to other types of memories. Preferably, the size of the MPC is sufficient for storage of at least one reference macroblock of prediction pixels, which will enable the MPC to rapidly accommodate all data requests for a current reference macroblock. The size of an MPC may be determined by application specific criteria including various modes of operation and different tile configurations. 
     During the course of the video decoding process, the MPC would typically experience idle periods. A method to reduce the latency by speculatively requesting data during the idle periods is hereby introduced to take advantage of those idle periods. 
       FIG. 1  shows a system  100  for implementing speculative motion prediction. The system  100  includes a bitstream entropy decoder  210 , a motion predictor (MP)  220 , a motion prediction cache (MPC)  230 , a memory block  240 , and a speculative motion vectors (SMV) block  250 . The bitstream entropy decoder  210  receives a video bitstream and converts the received bitstream into intermediate symbols, quantized coefficients, and motion vector information, (e.g. motion vectors, reference image identifier and macroblock identifier). 
     The MP  220  receives the motion vector information from the bitstream entropy decoder  210  and transmits a request for reference image data to the MPC  230 . The MP  220  then receives the reference image data and outputs a predicted macroblock. 
     The MPC  230  receives requests from the MP  220  and the SMV block  250  for reference image data for a macroblock, sends data requests to the memory block  240 , and receives and stores the requested reference image data for use in building subsequent macroblocks. The MPC  230  also is configured to output a state identifier, which may notify other blocks of its present state for scheduling purposes. 
     The SMV block  250  receives motion vector information from the bitstream entropy decoder  210 , as well as the state identifier from the MPC  230 , and outputs data requests for reference image data from the memory block  240  when it determines the MPC  230  has entered, or will enter, on idle period. 
     The memory block  240  receives memory requests, retrieves the requested reference image data and outputs the requested reference image data. 
     The aforementioned components of the system  100  will now be discussed in greater detail hereinafter. The bitstream entropy decoder  210  receives a video bitstream and converts it into intermediate symbols, quantized coefficients, and motion vector information, (e.g. motion vectors, reference image identifier, and macroblock identifier.) The particular implementation of the bitstream entropy decoder  210  may vary depending on the application in which it is used. For example, a context-based adaptive binary arithmetic coding (CABAC) bitstream entropy decoder generates intermediate symbols, quantized coefficients, and motion vector information produced by transform-decoding. CABAC decoders may be implemented in an integrated circuit or software for execution on general purpose processors. 
     The MP  220  predicts motion by using motion vector information of a current macroblock and a reference frame that is typically stored in memory, (in this case the memory block  240 ). The MP  220  receives a multiplexed data signal including intermediate symbols, quantized coefficients, and motion vector information. An MP  220  may comprise a demultiplexer receiving multiplexed intermediate symbols, quantized coefficients, and motion vector information and outputting demultiplexed motion vector information components, (i.e. include motion vectors, reference image identifiers, and macroblock identifiers). The MP  220  uses the motion vector information components to calculate a memory address. The calculated memory address may contain a cache address, a reference frame number, a macroblock number, or any other type of identification of the location or address of reference image data stored in the memory block  240 . 
     Once the memory address is calculated, a request is generated for the reference image data stored at the particular memory address in the memory block  240 . The MP  220  then transmits the request and waits for the requested reference image data to return. When the MP  220  receives the reference image data, it filters the reference image data and reconstructs a macroblock. The reconstructed macroblock is then output to the system for further decoding. The MP  220  output represents a block position on the basis of a predictive error with respect to an appropriate range for the reference image corresponding to the motion prediction reference image. 
     Referring to  FIG. 3 , the MPC  230  of system  100  is shown in greater detail. The MPC  230  enables the MP  220  to use the reference image data to build a macroblock. The MPC  230  may include a control module  331 , a motion prediction cache buffer  332  having a tag memory  333  and a data cache memory  334 , an external data request module  335 , a request queue  336  and a state machine  337 . The MPC  230  will respond to a request for reference image data for a current macroblock by requesting the data from the memory block  240  shown in  FIG. 1 . The request may be received from the MP  220  or the SMV block  250 . Optionally, the MPC  230  may be further configured to include a priority for requesting reference image data, wherein the MP  220  requests would have a higher priority, and consequently, a request from the MP  220  would terminate any pending requests from the SMV block  250 . 
     In operation, a request including the calculated address is received at the control module  331 . The control module  331  provides overall control of the MPC  230 . The data cache memory  334  stores any reference image data that is retrieved from the memory block to  240 . The tag memory  333  stores a “tag” or listing of the reference image data blocks that are stored in the data cache memory  334 . Any requests for external data from the memory block  240  are handled by the external data request module  335 . These requests are also placed into the request queue  336  and monitored by the state machine  337 . If the state machine  337  observes that a request including a particular address for reference image data was previously requested and is stored in the data cache memory  334 , the state machine  337  enables the data cache memory  334  to forward the previously retrieved data to the control module  331 . This process will be described in greater detail hereinafter. The control module  331  examines the request and searches the tag memory  333  to determine if the address associated with the request is stored in the tag memory  333 . If so, it means that the associated reference image data is stored in the data cache memory  334 . If the search of the tag memory is unsuccessful, meaning the requested reference image data is not stored in the MPC  230 , a request to the memory block  240  is made by the external data request module  335 . 
     The tag memory  333  is written with at least some of the parameters in the request. If the search was successful, meaning the requested reference image data is already stored in the data cache memory  334 , the data is read from the data cache memory  334  to the control module  331  and then to the MP  220 . 
     Regardless of whether or not the search of the tag memory  333  was successful, the search parameters are written to the request queue  336  and, if the request queue  336  is not full, the next request received is serviced. When the MPC  230  has completed requesting data for a current data block, which may be indicated by an empty request queue  336 , the state machine  337  transmits a signal indicating that it has entered into an idle state. If the MPC  230  receives a request from the SMV block  250  during the idle state, the MPC  230  can speculatively request reference image data from the memory block  240 . This request is processed in the same manner as the request from the MP  220 . The requested reference image data will be stored in the data cache memory  334  and the associated tag will also be stored in the tag memory  333  with the hope that the reference image data will be needed for a subsequent macroblock. 
     Referring to  FIG. 2 , the SMV block  250  of  FIG. 1  is shown in greater detail. The SMV block  250  generates “speculative” data requests for the MPC  230 , when the MP  220  to MPC  230  data flow is idle. A speculative data request is not a request for reference image data that is needed, (as is the case with a request from the MP  220 ), rather it is a request for reference image data that might be needed. 
     Ideally, when the MP  220  is ready to request data for a subsequent macroblock, the MPC  230  will have already requested the reference image data from the memory block  240  based on the requests that originate from the SMV block  250  during a period where the MPC  230  would otherwise be in an idle state. 
     The SMV block  250  includes a motion vector calculator  253 , a register  254 , and a motion vector memory to address translator (MVMAT)  256 . The motion vector calculator  253  receives motion vector information, (e.g. macroblock information, motion vectors, mode, and reference image information, and a frame start data field), from the bitstream entropy decoder  210 . A register  254  is provided to store the trend of the motion vector direction based on the past motion vectors. A moving window average of recent trends in the motion vector direction is calculated based on the received information, using extrapolation techniques. This average is used to generate a speculatively predicted motion vector for a subsequent macroblock. The speculatively predicted motion vector is sent to the MVMAT  256 , which translates the vector into a corresponding memory address in the memory block  240 . The MVMAT  256  then generates a data request for the data located at the selected memory address. 
     It should be understood that the SMV block  250  may employ a number of methods to speculate the motion vectors for a subsequent macroblock. For example, if a video decoder is operating in a horizontal scan mode, (e.g. the HD resolutions in H.264 and VC-1 standards), the speculative motion vectors may be the same as the current vectors, or the average of vectors from the left macroblock, the top-left macroblock and top macroblock. Alternatively, the SMV block  250  could maintain a running average of the motion per macroblock and extrapolate from the running average. There are many other similar methods that may be implemented. The particular method may be chosen adaptively based on the decoding performance, which is measurable. 
     Referring back to  FIG. 1 , the system  100  also includes a memory block  240 . As aforementioned, the memory block  240  receives requests for reference data from the MPC  230 , and additionally from other parts of the system  100 . The memory block  240  may include a memory control interface (MCI)  242  and a reference frame memory buffer  244 . The MCI  242  manages the control and timing of data transfers, bus arbitration, and memory access. Additionally, the MCI  242  may provide a dedicated channel to transfer image data that may be stored in the memory block  240 . The memory block  240  stores reference image data for later retrieval upon request. In the present embodiment, the reference frame memory buffer  244  comprises dynamic random access memory (DRAM). Alternatively, the reference frame memory buffer  244  may comprise an SRAM, virtual memory, flash memory, or any other accepted memory buffer. 
     The process of reducing the memory read latency of a motion prediction system is shown in  FIG. 4 . A video bitstream is received (step  410 ). The video bitstream is used to calculate motion vectors which are then used to calculate the addresses of reference image data for a current macroblock. The MP  220  requests reference image data corresponding to the calculated reference frame addresses. The MPC  230  receives the data requests, and requests the reference image data from the memory block  240 . After the requested reference image data has been received by the MPC  230  (step  420 ), a determination is made as to whether reference image data for a new macroblock is ready to be requested (step  425 ). If the reference image data for the new macroblock is not ready to be requested, (i.e. the MP  220  has not calculated the addresses of reference image data for a new macroblock), and the MPC  230  would otherwise enter an idle state, reference image data in the memory block  240  is speculatively requested (step  430 ). The speculative data request can be for a full macroblock of data or less than a full macroblock. The actual amount of data that is speculatively received is dynamically adjusted based on the decoding status of the present macroblock. Thereafter, the MP  220  is ready to request reference image data for a new macroblock (steps  435 ). 
     A determination is then made as to whether the reference image data that has been speculatively requested is the reference image data that corresponds with the data that is requested by the MP  220  for the subsequent image (step  440 ). If the data is needed, the data is immediately consumed (step  460 ). However, if the speculatively requested data is not needed, then the correct reference image data must be requested (step  450 ) and the speculatively requested data must be purged. 
     In the event the speculatively requested data is not used, it may be preferable to purge the tag memory  333  of the unused speculative data in a more efficient manner.  FIG. 5  shows a motion prediction cache buffer  332  of the MPC  230  in greater detail. Each location in each memory has a datum, called a cache line, which may range in size in depending upon the system design. Each location in each memory also has an index, (usually the lower order digits of the address), which is used to address a word in the cache. The remaining high-order bits in the address, called the tag, are stored in the motion prediction cache buffer  332  along with the data. When a request is received at the control module  331 , the control module  331  examines the request and searches the tag memory  333  associated with the request. In the event that the control module  331  searches the tag memory  333  and determines that the reference image data is not found in the motion prediction cache buffer  332 , the search will be deemed unsuccessful. In the event the cache tags searched were speculatively requested, they will then be purged to make room for additional memory requests. In order to further streamline the above process, the cache tags may be modified to include an “s-flag”, as shown in  FIG. 6 , so the cache lines that were speculatively requested, if not used in the current macroblock could be easily identified by the 5-flag and, thus, purged first. 
     The potential advantages offered as compared to known art include enabling the Blu-ray, HD-DVD support of high-definition video on low-end chips. Additionally it could enable dual HD video support. 
     Although the features and elements are described in particular combinations, each feature or element can be used alone without the other features and elements or in various combinations with or without other features. The methods or flow charts provided may be implemented in a computer program, software, or firmware tangibly embodied in a computer-readable storage medium for execution by a general purpose computer or a processor. Examples of computer-readable storage mediums include a read only memory (ROM), a random access memory (RAM), a register, cache memory, semiconductor memory devices, magnetic media such as internal hard disks and removable disks, magneto-optical media, and optical media such as CD-ROM disks, and digital versatile disks (DVDs). 
     Suitable processors include, by way of example, a general purpose processor, a special purpose processor, a conventional processor, a digital signal processor (DSP), a plurality of microprocessors, one or more microprocessors in association with a DSP core, a controller, a microcontroller, Application Specific Integrated Circuits (ASICs), Field Programmable Gate Arrays (FPGAs) circuits, any other type of integrated circuit (IC), and/or a state machine.