Abstract:
A method for memory management in video decoding systems that avoids some of the costs and disadvantages with video decoding systems in the prior art. Some embodiments of the present invention are especially well-suited for use with the H.264 video decoding standard. The illustrative embodiment is a memory management technique that controls which data is in the fastest memory available to a processor performing video decoding. In particular, the technique seeks to ensure that the data the processor will need is in the primary memory and expunges data that the processor will not need. The technique is based upon an analysis of predictive video decoding standards, such as H.264. By employing this technique, the illustrative embodiment ensures the expedient decoding of video frames.

Description:
FIELD OF THE INVENTION 
     The present invention relates to information technology in general, and, more particularly, to video decoding and memory management in video decoding systems. 
     BACKGROUND OF THE INVENTION 
       FIG. 1  depicts a video frame that comprises an image of a person in the prior art. The video frame comprises a two-dimensional array of 720 by 480 8-bit pixels. In some cases, all 345,600 pixels are transmitted when the frame is transmitted, but that requires that 345,600 bytes of data be transmitted for each frame. 
     There are techniques, however, for reducing, on average, the number of bytes that must be transmitted. One such technique is known as H.264. In accordance with H.264, some of the pixels in a frame are transmitted explicitly while others are not, but instead are derived or extrapolated from those that are. 
     To accomplish this, the pixels in the video frame are organized in a hierarchy of data structures. First, the frame is partitioned into a two-dimensional array of 45 by 30 macroblocks, as shown in  FIG. 2 . In turn, and as shown in  FIG. 3 , each macroblock is partitioned into a two-dimensional array of 4 by 4 luma blocks, and each luma block is partitioned into a two-dimensional array of 8-bit pixels. 
     All 1350 macroblocks in the frame are established in row-column order, as depicted in  FIG. 4 , so that each row is established, left to right, before the row before it is established. The 16 luma blocks within each macroblock are established in a specific pattern, as depicted in  FIG. 5 , to preserve the relationship that each luma block is established only after the luma blocks (if any) above it and to its left have been established. The reason is that the pixels in each luma block are either transmitted explicitly, or they are derived from the pixels in the luma blocks above it and to its left. 
     The pixels in a luma block are designated p[x,y] through p[x+3, y+3] as depicted in  FIG. 6 , wherein x ε{x: x=4n} and n ε{n: n is a non-negative integer}; and wherein y ε{y: y=4m} and m ε{m: m is a non-negative integer} (i.e., the values of x and y are restricted to positive multiples of 4). When the pixels in a luma block are predicted based on the pixels above it and to its left, those pixels are designated p[x−1, y−1] through p[x+7, y−1] and p[x−1,y] through p[x−1,y+3], as depicted in  FIG. 7 . There are a variety of formulas for predicting the pixels in the luma block, as graphically depicted in  FIGS. 8   a  through  8   h , but the receiver is not able predict which formula will be used before it is told which formula to use. 
     This can wreak havoc on the speed with which the video frame can be decoded, and, therefore, the need exists for a technique for ensuring the expedient decoding of a video frame. 
     SUMMARY OF THE INVENTION 
     The present invention presents a method for memory management in video decoding systems that avoids some of the costs and disadvantages with video decoding systems in the prior art. Some embodiments of the present invention are especially well-suited for use with the H.264 video decoding standard. 
     The illustrative embodiment is a memory management technique that controls which data is in the fastest memory available to a processor performing video decoding. In particular, the technique seeks to ensure that the data the processor will need is in the primary memory and expunges data that the processor will not need. The technique is based upon an analysis of predictive video decoding standards, such as H.264. By employing this technique, the illustrative embodiment ensures the expedient decoding of video frames. 
     The illustrative embodiment comprises: retaining pixel[x−1, y−1] in a first memory until pixel[x, y] has been established; and expunging pixel[x, y] from the first memory before pixel[x+3, y+3] is expunged from the first memory; wherein x ε{x: x=4n} and n ε{n: n is a non-negative integer}; and wherein y ε{y: y=4m} and m ε{m: m is a non-negative integer}. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  depicts a video frame that comprises an image of a person in the prior art. 
         FIG. 2  depicts a video frame that is partitioned into a two-dimensional array of 45 by 30 macroblocks. 
         FIG. 3  depicts a macroblock as it is partitioned into luma blocks and pixels. 
         FIG. 4  depicts the order in which the macroblocks in a video frame are established. 
         FIG. 5  depicts the order in which the luma blocks in a macroblock are established. 
         FIG. 6  depicts the designation of the pixels in a luma block. 
         FIG. 7  depicts the designation of the pixels in the luma block with regard to the pixels from which they can be derived. 
         FIG. 8   a  depicts a graphical illustration of the H.264 Intra — 4×4_Horizontal_Up prediction mode. 
         FIG. 8   b  depicts a graphical illustration of the H.264 Intra — 4×4_Horizontal prediction mode. 
         FIG. 8   c  depicts a graphical illustration of the H.264 Intra — 4×4_Horizontal_Down prediction mode. 
         FIG. 8   d  depicts a graphical illustration of the H.264 Intra — 4×4_Diagonal_Down_Right prediction mode. 
         FIG. 8   e  depicts a graphical illustration of the H.264 Intra — 4×4_Vertical_Right prediction mode. 
         FIG. 8   f  depicts a graphical illustration of the H.264 Intra — 4×4_Vertical prediction mode. 
         FIG. 8   g  depicts a graphical illustration of the H.264 Intra — 4×4_Vertical_Left prediction mode. 
         FIG. 8   h  depicts a graphical illustration of the H.264 Intra — 4×4 Diagonal_Down_Left prediction mode. 
         FIG. 9  depicts a block diagram of the salient components of the illustrative embodiment of the present invention, which is the architecture of a video decoding system. 
         FIG. 10  depicts the designation of the pixels in each luma block and the designation of the pixels that surround the luma block. 
         FIG. 11  depicts the pseudocode for controlling when pixels are retained in primary memory  911  and when pixels are expunged from primary memory. 
     
    
    
     DETAILED DESCRIPTION 
       FIG. 9  depicts a block diagram of the salient components of the illustrative embodiment of the present invention, which is the architecture of a video decoding system. 
     Video decoding system  900  comprises: processor  901 , primary memory  911 , secondary memory  912 , tertiary memory  913 , and memory management unit  902 , interconnected as shown. 
     Processor  901  is a general-purpose processor that can read and write to primary memory  911  and that perform the functionality described herein. 
     Primary memory  911  is the fastest addressable memory and processor  901  can access data within primary memory  911  in one clock cycle. Primary memory  911  is not a content-addressable memory with a hardwired cache-retention discipline—or a cache that is invisible to the system programmer. In accordance with the illustrative embodiment, processor  901  and primary memory  911  are on the same monolithic die. In accordance with the illustrative embodiment, primary memory  911  has its own address space, which is distinct from the address space of secondary memory  912 . It will be clear to those skilled in the art, however, how to make and use alternative embodiments of the present invention in which primary memory  911  and secondary memory  912  are in the same address space. 
     Secondary memory  912  is the second-fastest addressable memory in the system. Processor  901  can access data within secondary memory  912  in approximately 100 clock cycles. In accordance with the illustrative embodiment, secondary memory  912  is semiconductor memory but secondary memory  912  is not on the same die as processor  901 . This accounts for the substantial difference in speed between secondary memory  912  and primary memory  911 . 
     Tertiary memory  913  is the slowest addressable memory. Processor  901  can access data within tertiary memory  913  in approximately 10,000 clock cycles. In accordance with the illustrative embodiment, tertiary memory  913  is a mass storage device, such as a hard drive, and this accounts for the substantial difference in speed between tertiary memory  913  and secondary memory  912 . 
     Primary memory  911  costs substantially more, per bit, than does secondary memory  912 , and secondary memory  912  costs substantially more, per bit, than does tertiary memory  913 . For this reason, primary memory  911  comprises substantially fewer bytes than secondary memory  912 , and secondary memory  912  comprises substantially fewer bytes than tertiary memory  913 . 
     When processor  901  seeks a word of data and the word is in primary memory  911 , processor  901  can continue processing very quickly. In contrast, when processor  901  seeks a word of data and the word is not in primary memory  911 , processor  901  waits until the word can be retrieved. Given that secondary memory  912  is 1/100 th  of the speed of primary memory  911 , processing can become very slow if processor  901  must regularly wait for data to be retrieved from secondary memory  912 . 
     One solution is to ensure that the size of primary memory  911  is large because this reduces, probabilistically, the frequency with which a desired word is not in primary memory  911 . This approach is problematic, however, because it is expensive and because some applications, such as video decoding, use such large quantities of data that any reasonably-sized primary memory would be ineffective. 
     To overcome this problem, the illustrative embodiment employs memory management unit  902  which controls what data is in primary memory  911  and what is not. In other words, memory management unit  902  retains in primary memory  911  data that will be needed by processor  901  soon and expunges from primary memory  911  data that will not be needed by processor  901  again soon. By retaining in primary memory  911  data that will be needed soon, the illustrative embodiment reduces the frequency and likelihood that processor  901  must wait until data can be retrieved from secondary memory  912 , and by expunging from primary memory  911  data that will not be needed by processor  901  again soon, the illustrative embodiment frees up space in primary memory  911  for data that will be needed by processor  901  soon. 
     In many cases, a memory management unit cannot predict what data the processor will need again soon and what data it will not, but there are applications, such as video decoding, when reasonable predictions can be made. 
       FIG. 10  depicts the designation of the pixels in each luma block and the designation of the pixels that surround the luma block. At the beginning of the decoding of a video frame, none of the pixels are established. At the end of the decoding of the video frame, 345,600 pixels have been established by processor  901  and—at one time or another—stored within primary memory  911 . All 345,600 8-bit pixels cannot be kept in primary memory  911  forever, and so, in accordance with the illustrative embodiment, each established pixel is expunged from primary memory  911  as soon as it is no longer needed. In principal, this sounds simple, but there are a lot of pixels and, without more, the overhead associated with determining which pixels are needed and for how long and when they can and should be expunged can create a computational and memory problem that is worse than the problem to be addressed. The illustrative embodiment, however, incorporates computationally simple rules that retain and expunge the pixels at times that make the maximum use of primary memory  911 . 
       FIG. 11  depicts the pseudocode for controlling when pixels are retained in primary memory  911  and when pixels are expunged from primary memory. By following this procedure, memory management unit  902  ensures that pixels that will be needed soon by processor  901  are, in fact, in primary memory  911  and that pixels that will not be needed soon by processor  901  are expunged from primary memory  911 . 
     As can be seen in  FIG. 11 , there are five (5) treatments for various groups of pixels. Each of the treatments comes from the relative position of the pixels and their potential use in predicting other pixels.
         i. pixel[x−1, y−1], pixel[x, y−1], pixel[x+1, y−1], pixel[x+2, y−1], pixel[x−1, y], pixel[x−1, y+1], pixel[x−1, y+1] are retained in primary memory until pixel[x, y], pixel[x+1, y], pixel[x+2, y], pixel[x+3, y], pixel[x, y+1], pixel[x+1, y+1], pixel[x+2, y+1], pixel[x+3, y+1], pixel[x, y+2], pixel[x+1, y+2], pixel[x+2, y+2], pixel[x+3, y+2], pixel[x, y+3], pixel[x+1, y+3], pixel[x+2, y+3], and pixel[x+3, y+3] are established;   ii. pixel[x+3, y−1], pixel[x+3, y], pixel[x+3, y+1], and pixel[x+3, y+2] are retained in primary memory until pixel[x+4, y], pixel[x+4, y+1], pixel[x+4, y+2], and pixel[x+4, y+3] are established;   iii. pixel[x−1, y+3], pixel[x, y+3], pixel[x+1, y+3], and pixel[x+2, y+3] are retained in primary memory until pixel[x, y+4], pixel[x+1, y+4], pixel[x+2, y+4], and pixel[x+3, y+4] are established;   iv. pixel[x+3, y+3] is retained until pixel[x+4,y+4] is established; and   v. pixel[x, y], pixel[x+1, y], pixel[x+2, y], pixel[x, y+1], pixel[x+1, y+1], pixel[x+2, y+1], pixel[x, y+2], pixel[x+1, y+2], and pixel[x+2, y+2] are expunged from primary memory before pixel[x+3, y], pixel[x+3, y+1], pixel[x+3, y+2], pixel[x, y+3], pixel[x+1, y+3], pixel[x+2, y+3], and pixel[x+3, y+3] are expunged from primary memory and before pixel[x+4, y], pixel[x+4, y+1], pixel[x+4, y+2], pixel[x+4, y+3], pixel[x, y+4], pixel[x+1, y+4], pixel[x+2, y+4], pixel[x+3, y+4], and pixel[x+4, y+4] are established.
 
It will be clear to those skilled in the art, after reading this specification, how to make and use embodiments of the present invention that retain and expunge pixels from primary memory  911 .
       

     It is to be understood that the above-described embodiments are merely illustrative of the present invention and that many variations of the above-described embodiments can be devised by those skilled in the art without departing from the scope of the invention. It is therefore intended that such variations be included within the scope of the following claims and their equivalents.