Video Clip	Orig.l MPEG4 Motion Comp. Cycle Count	Opt. MPEG4 Motion Comp. Cycle Count	Speedup
Miss America	1.620 Gcycles	21.43 Mcycles	75.6X
Susie	1.660 Gcycles	27.18 Mcycles	61.6X
Foreman	4.571 Gcycles	90.14 Mcycles	50.8X
Carphone	4.296 Gcycles	79.35 Mcycles	54.1X
Monsters Inc.	15.578 Gcycles	194.96 Mcycles	79.9X

Implementing the Inverse DCT algorithm

There are two groups of algorithmic implementations available for computing a two-dimensional (2-D) 8x8 iDCT: full 2-D iDCTs and algorithms based on the sequential application of a 1-D iDCT to the columns and then the rows of the 8x8 block. The MoMuSys MPEG-4 uses the latter approach, which is well suited to the SIMD engine. Executing eight 1-D iDCTs in parallel using the SIMD engine accelerates the 8x8 iDCT. The parallelized routine performs 1-D iDCTs on the columns directly. However, the image data isn't organized in memory properly to allow the SIMD engine to directly transform the rows so the data must be transposed after performing the column-oriented 1-D iDCT. Once the data has been transposed, the SIMD engine performs 1-D iDCTs on the row data, which is then transposed back to the original data layout to complete the full 2-D iDCT.

A full transposition of an 8x8 block using the SIMD select instruction requires 24 cycles so the overhead of the two transposition operations consumes 48 cycles. However, this overhead can be greatly reduced by transposing the data in a special transposition memory added to the processor using hardware based instruction extensions (see Table below).

Video Clip	Orig. Av. iDCT Cycle Count	Opt. Av. iDCT Cycle Count	Speedup
Miss America	3220.86	345.24	9.4X
Susie	3283	343.77	9.5X
Foreman	3414.7	342.22	10X
Carphone	3356.83	342.62	9.8X
Monsters, Inc.	3349.21	343.26	9.8X

Bit-Stream Processing

Video decoders use a set of bit-stream functions to process video. All data is extracted from the video stream using one of these functions. Processor extensions can accelerate bit-stream processing functions by moving the video bit stream through a special shift register, added to the processor using instruction extensions, that aids in bit-field manipulation and extraction. Note that this is not a SIMD operation.

Performing bit-stream processing functions with processor extensions also helps optimize variable-length decoding. The variable-length coding algorithm reduces the average number of bits needed to encode a code word by assigning a short bit string to the most frequently occurring code word and longer bit strings to code words that hardly ever occur. Variable-length coding allows the MPEG-4 encoder to reduce the number of bits needed to encode an 8x8 iDCT block. The code word represents the run, level, and sign of the iDCT coefficient (also called run-length coding). The run values indicate the number of zero's that occur between two values. The decoder fills the iDCT block by extracting variable-length code words from the incoming bit stream and decoding them. The bit-stream processing hardware discussed above also extracts the variable-length codes from the video stream.

Additional MPEG-4 Decoder Optimizations

One portion of the MPEG-4 compression algorithm transforms the values of an 8x8 block into the frequency domain and then divides the resulting numbers by a quantization value. The video bit stream carries the quantization value and the decoder must perform the reverse transformation, called dequantization. The dequantization algorithm multiplies the decoded iDCT value by the quantization value to approximate the original DCT value. It's possible to quantize multiple iDCT values simultaneously and the MPEG-4 SIMD engine easily performs this task. Using the SIMD approach reduces the dequantization cycle count from 1647 cycles to 259 cycles per iDCT block for the Suzie test stream, a 6.4x improvement.

AC/DC prediction is only used for MPEG-4 Intra frames, which occur much less frequently than Inter frames. However, Intra frames require significantly more decoding cycles than Inter frames so it's very important to optimize this function because the clock rate required to decode an Intra frame sets a lower bound on the decoder's clock frequency. The decoder must be fast enough to decode any Intra frame in real time. AC/DC prediction reduces the number of bits required for encoding an Intra frame by estimating DC and/or AC values from the iDCT blocks. AC prediction, in particular, requires a large number of cycles to perform divisions and logarithmic functions inside a loop. These calculations can be moved outside the loop by rewriting the MoMuSys code. This optimization reduces the cycle count for AC/DC prediction from 2080 to 520 cycles.

The MoMuSys MPEG-4 decoder uses YCbCr color-space coding. The YCbCr representation usually must be transformed into a different color space such as RGB during the decoding operation. Transforming data from the YCbCr color space to RGB requires matrix multiplication. The transformed values for R, G, and B must also be shifted right by 16 bits to obtain the real RGB value. Color conversion is yet another critical decoding operation because every pixel undergoes matrix multiplication.

To accommodate the YCbCr-to-RGB color-space conversion requirements, the MPEG-4 SIMD engine multipliers are designed to handle 16x18-bit multiplications. The higher precision multipliers eliminate extra instructions that would otherwise be needed to deal with constants that are too big for traditional 16-bit, two's-complement multipliers. The SIMD engine performs a matrix multiplication for 8 pixels in parallel, producing an 8x performance improvement in the color-space conversion algorithm.

MoMuSys Can Be Faster, Smaller

Overall, MoMuSys MPEG-4 decoder optimization factors ranged from 28x to 40x for different video test streams (see Table below). Consequently, this MPEG-4 decoder based on an extended processor core runs at a very low clock rate-much lower than for an unaugmented processor. The reason for the range of optimization factors is due to differences in the video streams. For example, this MPEG-4 decoder optimizes motion compensation more than dequantization or computing the iDCT so encoded streams with more iDCT blocks require more decoding cycles. Different test streams simply have different requirements. This characteristic of all video makes defining the worst-case bit stream problematic and it also demonstrates how important it is to use exactly the same test streams when comparing performance numbers for various video decoders.

Video Clip	Orig. MPEG4 Decoder Cycle Count	Opt. MPEG4 Decoder Cycle Count	Opt. Clock Frequency (15 fps)	Speedup
Miss America	3.126 Gcycles	76.81 Mcycles	7.7 MHz	40.1X
Susie	3.389 Gcycles	102.19 Mcycles	10.3 MHz	33.2X
Foreman	10.045 Gcycles	359.5 Mcycles	13.5 MHz	27.9X
Carphone	9.222 Gcyclces	308.7. Mcycles	12.2 MHz	29.9X
Monsters, Inc.	29.327 Gcycles	833.8 Mcycles	8.6 MHz	35.6X

Even at these performance levels, this software-based MPEG-4 decoder is not fully optimized. However, because this is a software-based decoder, it would be easy to refine the optimizations further should even better performance be required (for higher-resolution MPEG-4 implementations as an example).

The processor configuration used for this MPEG-4 decoder requires around 53K gates and the gate count for the programmable SIMD-engine and bit-stream-processing extensions is 67K gates. The resulting decoder is capable of decoding MPEG-4 video streams and other compressed-video streams with performance on par with hardware video decoders and a relatively low gate count. Even more important, the entire project (developing and tailoring a SIMD-enhanced processor using the MoMuSys reference code) consumed only seven man months.