System, method, and apparatus for efficiently storing macroblocks

Presented herein is a system for storing macroblocks for such that all vertically, horizontally, and diagonally adjacent macroblock are stored in different banks. When fetching a block from a reference frame that overlaps four macroblocks, each of the overlapped macroblocks can be fetched substantially concurrently.

FEDERALLY SPONSORED RESEARCH OR DEVELOPMENT

BACKGROUND OF THE INVENTION

One of the major challenges in designing a memory subsystem is organizing data in such a way, as to enable efficient memory access that would increase the system throughput. Data organization in the memory becomes even more of a bigger challenge in a UMA (Unified Memory Architecture) subsystem, where it has a direct impact on the efficiency of the system as a whole. Therefore data in the memory should be organized in such a way that, a high bandwidth client (a client is an agent that initiates data transfer between itself and the memory subsystem) benefits the most without compromising the access efficiency of the other low bandwidth clients. In other words, the data organization in the memory should help reduce the DDR-SDRAM overheads for high bandwidth clients, which in turn would improve the efficiency of the memory subsystem as a whole.

In a video decompression-engine (a.k.a video decoder) a substantial portion of the system bandwidth is utilized in transacting video pixel data. The video decoder uses the neighboring macro-block (a macro block is a 16×16 pixel block) data from the previous and future frames of the video to predict the current macro-block information. Thus the right choice would be to have a memory subsystem that is macro-block oriented.

However the current column sizes in the DDR-SDRAM technology do not allow the packing of a full macro-block row of information in one bank of the DRAM for a SD size picture. At the same time, a very simple linear arrangement of macro-block continuously in the same bank of the DDR-SDRAM would increase the SDRAM overheads, as an adjacent or vertical neighbor macro-block fetch would require a different row of the same bank to be activated. In such a case, the current row of the current bank needs to be precharged and a new row of the same bank needs to be activated, thus resulting in roughly 6-clocks overhead per row change. In the worst case, a particular video decode fetch could involve four macro-blocks worth data, lying in four different rows of the same bank, resulting in as high as 18 (three row switching) clocks overhead. On the other hand, if the adjacent or vertical macro-block were to exist in different banks of the DRAM, it would be possible to reduce the SDRAM overhead to zero in the best case and the worst case numbers will be much less that 18 clocks.

Conventionally, four macro blocks worth of data are packed into one bank, before switching to the next bank of the DDR-SDRAM. This packing would be efficient for images, whose number of horizontal macro-block (NMBX) follows the equation,
NMBX=16*N+8(where N is any positive integer)

The above equation ensures efficient data fetching and packing for a HD size picture (NMBX=120). However for a SD size picture (NMBX=45), the closest value of N, that satisfies the above equation=4, resulting in NMBX required=56. This means we have 11 macro-blocks, wasted for every macro-block row of the image. For a SD size picture this would be roughly 75 Kbytes of wasted memory per frame storage (roughly 20% wastage per frame).

BRIEF SUMMARY OF THE INVENTION

System(s), method(s), and apparatus for efficiently storing macroblocks are presented herein.

In one embodiment, there is presented a method for storing a plurality of blocks representing portions of a frame. The method comprises storing the plurality of blocks in a plurality of banks, wherein every two vertically adjacent blocks are stored in different ones of the banks from one another.

In another embodiment, there is presented a method for storing a plurality of rows of blocks. The method comprises storing each of a first sequence of blocks of a first row in particular ones of a plurality of banks according to a particular order, starting at a first and then a second of the plurality of banks, and storing each of the blocks of a next row in particular ones of the plurality of banks according to the particular order, starting at a third and then a fourth of the plurality of banks.

In another embodiment, there is presented a method for decoding a macroblock. The method comprises displacing a position associated with the macroblock with one or more motion vectors, resulting in a displaced region for a reference frame, retrieving a first macroblock of the reference frame that overlaps the displaced region, retrieving a second macroblock of the reference frame that overlaps the displaced region, while retrieving the first macroblock, retrieving a third macroblock of the reference frame that overlaps the displaced region, while retrieving the first macroblock, and retrieving a fourth macroblock of the reference frame that overlaps the displaced region, while retrieving the first macroblock.

In another embodiment, there is presented a system for storing a plurality of blocks representing portions of a frame. The system comprises a plurality of banks and a video decoder. The plurality of banks store the plurality of blocks, wherein every two vertically adjacent blocks are stored in different ones of the banks from one another. The video decoder writes the plurality of blocks to the plurality of banks.

In another embodiment, there is presented a system for storing a plurality of rows of blocks. The system comprises a plurality of banks and a video decoder. The plurality of banks store each of first sequence of blocks of a first row in particular ones of a plurality of banks, and for storing each of the blocks of a next row in particular ones of the plurality of banks. The video decoder writes the first sequence of blocks according to a particular order, starting at a first and then a second of the plurality of banks and writing each of the blocks of the next row according to the particular order, starting at a third and then a fourth of the plurality of banks.

In another embodiment, there is presented a circuit for decoding a macroblock. The circuit comprises a controller and an instruction memory operably connected to the controller. The instruction memory stores executable instructions. The execution of the executable instructions by the controller causes displacing a position associated with the macroblock with one or more motion vectors, resulting in a displaced region for a reference frame, retrieving a first macroblock of the reference frame that overlaps the displaced region, retrieving a second macroblock of the reference frame that overlaps the displaced region, while retrieving the first macroblock, retrieving a third macroblock of the reference frame that overlaps the displaced region, while retrieving the first macroblock, and retrieving a fourth macroblock of the reference frame that overlaps the displaced region, while retrieving the first macroblock.

DETAILED DESCRIPTION OF THE INVENTION

Referring now toFIG. 1, there is illustrated a block diagram describing MPEG formatting of video data305. The video data305comprises a series of frames310. Each frame comprises two dimensional grids of luminance Y, chroma red Cr, and chroma blue Cb pixels315. The two-dimensional grids are divided into 8×8 blocks335, where four blocks335of luminance pixels Y are associated with a block335of chroma red Cr, and a block335of chroma blue Cb pixels. The four blocks of luminance pixels Y, the block of chroma red Cr, and the chroma blue Cb form a data structure known as a macroblock337. The macroblock337also includes additional parameters, including motion vectors.

The data in the macroblocks337is compressed in accordance with algorithms that take advantage of temporal and spatial redundancies. For example, in a motion picture, neighboring frames310usually have many similarities. Motion between frames increases differences between frames. Motion compensation can be used to reduce these differences. When an object moves across a screen, the object may appear in different positions in different frames, but the object does not change substantially in appearance. The picture differences can be reduced by measuring and recording the motion as a vector. The vector can be used during decoding to shift a macroblock337of one frame to a more appropriate part of another frame.

Accordingly, most of the macroblocks337are compared to portions of other frames310(reference frames). When an appropriate portion of a reference frame310is found, the differences between the portion of the other frame310and the macroblock337are encoded. The location of the portion in the reference frame310is recorded as a motion vector. The encoded difference and the motion vector form part of the data structure encoding the macroblock337. In MPEG-2, the macroblocks337from one frame310(a predicted frame) are limited to prediction from portions of, no more than two reference frames310. It is noted that frames310used as a reference frame310for a predicted frame310can be a predicted frame310from another reference frame310.

The macroblocks337representing a frame are grouped into different slice groups340. The slice group340includes the macroblocks337in the slice group340, as well as additional parameters describing the slice group. Each of the slice groups340forming the frame form the data portion of a picture structure345. The picture345includes the slice groups340as well as additional parameters. The pictures are then grouped together as a group of pictures350. The group of pictures350also includes additional parameters. Groups of pictures350are then stored, forming what is known as a video elementary stream355. The video elementary stream355is then packetized to form a packetized elementary sequence360. Each packet is then associated with a transport header365a,forming what are known as transport packets365b.

The transport packets365bcan be multiplexed with other transport packets365bcarrying other content, such as another video elementary stream355or an audio elementary stream. The multiplexed transport packets form what is known as a transport stream. The transport stream is transmitted over a communication medium for decoding and presentation.

Referring now toFIG. 2, there is illustrated a block diagram of an exemplary decoder system for decoding compressed video data, configured in accordance with an embodiment of the present invention. A processor, that may include a CPU490, reads transport stream465into a transport stream buffer432within an SDRAM430.

The data is output from the transport stream buffer432and is then passed to a data transport processor435. The data transport processor435then demultiplexes the transport stream465into constituent transport streams. The constituent packetized elementary stream can include for example, video transport streams, and audio transport streams. The data transport processor435passes an audio transport stream to an audio decoder460and a video transport stream to a video transport processor440.

The video transport processor440converts the video transport stream into a video elementary stream and provides the video elementary stream to a video decoder445. The video decoder445decodes the video elementary stream, resulting in a sequence of decoded video frames. The decoding can include decompressing the video elementary stream. It is noted that there are various standards for compressing the amount of data required for transportation and storage of video data, such as MPEG-2. The video decoder445decompresses the video data.

A display engine450is responsible for and operable to select a frame (or field) for display at every vertical synchronization pulse, scale the frame, render the graphics, construct the complete display, and rasterize the frame, among other functions. The rasterized frame is passed to a video encoder455where it is converted to analog video using an internal digital to analog converter (DAC). The digital audio is converted to analog in the audio digital to analog converter (DAC)465.

The decoded video data includes a series of frames310. The frames310are stored in frame buffers452. The frame buffers452can be dynamic random access memory (DRAM) comprising 128 bit/16 byte gigantic words (gwords). As noted above, most macroblocks337in predicted frames310are encoded as an offset or difference from portions of reference frames310. Accordingly, the MPEG video decoder445decodes the reference frames310prior to decoding predicted frames310that are predicted thereon. The decoded reference frames310are stored in frame buffers452. The MPEG video decoder445fetches the portions of the reference frames310from the frame buffers452to decode macroblocks337from the predicted frame310.

Referring now toFIG. 3, there is illustrated a block diagram of a reference frame310. As noted above, the frame310is decoded on a macroblock by macroblock337basis. Macroblocks337of another frame310can be encoded as an offset or difference from portions310pof the frame310. The portions310pare not necessarily aligned with macroblocks337. A portion310pcan potentially straddle four adjacent macroblocks337a,337b,337c,337d.The MPEG video decoder445retrieves the macroblocks337a,337b,337c,337d,containing the portion310for decoding a macroblock337in a predicted frame310.

Referring now toFIG. 4A, there is illustrated a block diagram of an exemplary DRAM500. The DRAM500comprises four banks, namely bank0, bank1, bank2, and bank3. Each bank comprises any number of rows505(0) . . .505(n). Each row of a bank has 32 byte jumbo words (jword). The luma Y portion of the macroblocks337occupy 8 j-words. Therefore, each row of a bank can store the luma pixels from four macroblocks337.

To access data, a bank is charged. While the bank is charged, data from one row of the bank can be accessed. Access to other rows of the bank occurs after the first access is completed. Each memory access is associated with overhead time. As noted above, for decoding a macroblock337, the video decoder445may fetch up to four adjacent macroblocks. The time for decoding can be reduced by fetching the macroblocks337in parallel or in pipeline. However, if the macroblocks337occupy different rows of the same bank, the requests cannot occur in parallel or pipeline with many DRAMS. To avoid this, the frame310can be stored in a frame buffer452in a manner such that every set of four covering macroblocks337are stored in either different banks or the same row of a bank. Accordingly, the video decoder445can fetch any portion310pby fetching the macroblocks337overlapped by the portion310peither in parallel or in pipeline fashion.

Referring now toFIG. 4B, there is illustrated a graph describing the retrieval of a second, third, and fourth macroblock during retrieval of a first macroblock from a reference frame in accordance with an embodiment of the present invention. The graph will be described with references toFIGS. 3 and 4A. While decoding a frame, the video decoder445decodes a particular macroblock of the frame. The macroblock337is encoded as an offset to a portion310of a reference frame. The portion310of the reference frame overlaps macroblocks337a,337b,337c,and337d.Macroblock337acan be stored in bank0, macroblock337bcan be stored in bank1, macroblock337ccan be stored in bank2, and macroblock337dcan be stored in bank3.

Accordingly, the video decoder445can retrieve macroblock337a,and also retrieve macroblocks337b,337c,and337dwhile retrieving macroblock337a.The retrieval of macroblock337ais commenced by issuance of a command to fetch the macroblock337afrom bank0. Subsequent thereto, bank0charges. Charging bank0can take six clock cycles, depending on the frame buffer memory. The video decoder445issues a command to fetch the macroblock337bfrom bank1, immediately after issuance of the command to fetch macroblock337afrom bank0, and while bank0is charging. The video decoder445then issues a command to fetch the macroblock337cfrom bank2, immediately after issuance of the command to fetch macroblock337bfrom bank1, and while banks0and1are charging. Finally, the video decoder445can issue a command to fetch the macroblock337dfrom bank3, immediately after issuance of the command to fetch macroblock337cfrom bank2, and while banks0,1and2are charging.

At a certain time period, the banks0,1,2, and3finish charging and providing the requested macroblocks, macroblocks337a,337b,337c,and337d.In general, the charging period is substantially larger than the time for issuance of the fetch instruction and receiving the requested macroblocks. Accordingly, substantial time savings are realized because the charging times for the banks0,1,2, and3are substantially concurrent.

Referring now toFIG. 6, there is illustrated a block diagram of an exemplary frame buffer storing a frame in accordance with an embodiment of the present invention. The frame buffer comprises four banks, bank0, bank1, bank2, and bank3. Each bank has any number of rows505, indicated by the rows in the table. Each row of each bank can store 4 macroblocks.

The video decoder445stores a macroblock row, e.g., macroblocks A0. . . A44, by storing the first macroblock, A0, in a row505, e.g., row505(0), of bank0, storing the next macroblock, A1, in the same row of bank1, the next macroblock, A2, in the same row of bank2, and the next macroblock, A3, in the same row of bank3. After storing a macroblock in the last bank, e.g., bank3, the video decoder445checks if the row505(0) is filled and cannot store additional macroblocks. If the row is not filled and can store additional macroblocks, the video decoder445returns the first bank, e.g., bank0, and repeats the foregoing. However, if the row is filled and cannot store additional macroblocks, the video decoder445proceeds the next row, e.g., row505(1). For example, after storing macroblock A15in row505(0) of bank3, row505(0) of bank505(0) of bank0is filled and cannot store macroblock A16.

When the last macroblock of the macroblock row, e.g., macroblock A44, is stored (in row505(2) of bank0), the video decoder445proceeds to the next macroblock row, e.g., B0. . . B44. The first macroblock of the next row, e.g., macroblock B0is vertically adjacent to the first macroblock of the previous row, e.g., macroblock A0, and diagonally adjacent to the second macroblock of the previous row, e.g., macroblock A1. Accordingly, the contiguous portion310pcan cover macroblock A0, A1, B0, and B1. Accordingly, B0and B1should not be stored in either of the banks storing A0and A1, e.g., banks0and1. Macroblocks B0and B1should be stored in banks2and3, respectively. However, the last macroblock of the previous row, e.g., macroblock A44, is stored in bank0, making the next bank, bank1. Accordingly, the video decoder445stuffs a blank macroblock X in row505(2) for each bank in the order between the bank storing the last macroblock of the previous row, bank0, and bank2. The bank(s) between bank0and bank2, is bank1. Accordingly, the video decoder445stuffs a blank macroblock X in bank1.

The video decoder445proceeds to decode and store the next macroblock row B0. . . B44, starting from row505(2) in bank2and rotating to bank3, bank0, bank1, bank2, and again bank3, and proceeding to the next rows505when the current row is filled. At the end of the macroblock row B0. . . B44, the video decoder445proceeds to macroblock row C0. . . C44. The video decoder445stuffs blanks in each bank between the bank storing the last macroblock of the previous row, e.g. macroblock B44in bank2, and bank0, and begins storing macroblock row C0. . . C44in bank0. The video decoder445repeats the foregoing for each of the macroblock rows in the frame. Each macroblock row is stored starting in either bank0or bank2, in alternating fashion, such that each macroblock rows starts in a different one of bank0and bank2from its neighboring macroblock rows. For example, macroblock row B0. . . B44starts in bank2, while macroblock rows A0. . . A44, and C0. . . C44start in bank0.

Referring now toFIG. 7, there is illustrated a flow diagram describing the storage of a frame in accordance with an embodiment of the present invention. At705, the video decoder445selects the first macroblock of the frame, the first row, and the first bank, e.g., bank0. At710, the video decoder stores the first macroblock selected during705in the row and bank selected during705.

The video decoder445selects the next macroblock at715, and the next bank in the bank0, bank1, bank2, and bank3order at720. At725, the video decoder445determines whether the current row for the selected bank is full. If the current row for the selected bank is full, the video decoder445selects the next row at732. Otherwise, video decoder445bypasses732.

At735, the video decoder445stores the macroblock in the selected row of the selected bank. At740, the video decoder445determines if the macroblock is the last macroblock row in the block. If the macroblock is not the last macroblock row in the block, the video decoder445repeats715-740.

If the macroblock is the last macroblock in the macroblock row during740, the video decoder445proceeds stuffing the banks (745) with blank macroblocks in the bank order until the bank storing the third macroblock (A2, B2, C2, etc.). The video decoder445then repeats715-745for the next macroblock row.