INTERNATIONAL ORGANISATION FOR STANDARDISATION
ORGANISATION INTERNATIONALE DE NORMALISATION
ISO/IEC JTC1/SC29/WG11
CODING OF MOVING PICTURES AND AUDIO

ISO/IEC JTC1/SC29/WG11 N2485
MPEG98/
Atlantic City - October 1998

Introduction

This page is a compilation of studies, reports and conclusions that have been produced by the MPEG-4 implementation group and its members. For more information, the reader is referred to Table 2 for an overview of the reports from which the information on this page has been derived. These reports are available through http://www.chips.ibm.com/.mpeg. If you do not have access to these pages, please contact your National Body.

Is MPEG-4 hardware or software oriented?

Unlike previous MPEG standards, MPEG-4 is not explicitly targeting hardware or software solutions. Given the wide variety of MPEG-4 functionality as reflected in the profiles and levels, and the different envisaged application scenarios, it is expected that hardware, software and hybrid (e.g. a programmable processor with application specific accelerators) solutions will coexist.

Why should algorithms be profiled?

The profiling of algorithms serves several purposes:

• It allows for the definition of MPEG-4 profiles, based on complexity measurements
• It gives feedback to other MPEG-4 subgroups on the complexity of some functionality. Functions with high complexity are encouraged to be simplified (e.g. simplification of the padding - see [M1097, M1490, M1578, M1814, M2039, M2129, M3572])
• It gives a framework for better defining graceful degradation parameters (see below).

What are the complexity measures?

It is not possible to give one unique way of measuring the intrinsic complexity of a system. Depending on the implementation platform, some cost parameters are considered to be more important than others. For instance, for portable systems, the power consumption is a very important characteristic. In interactive systems, the system delay is probably more important than the power consumption. Each designer therefore handles an other set of complexity parameters, which can be categorised as follows [N1169]:

• processing cost expressed in MIPS (Million Instructions Per Second), number of cycles per second and FLOPS (Floating Point Operations Per Second)
• memory size, organisation, I/O memory bandwidth
• ability to exploit or introduce parallelism and pipelining etc.
• control cost/overhead
• system inherent delay
• power consumption
• chip-area
• regularity of the processing (i.e. variation of the processing cost in time)

How should complexity measures be interpreted?

One has always to keep in mind that whatever the quality of the instrumentation tool, the outcoming results should be handled with care. Instrumenting non-optimized source code can provide disastrous profiling results, which are orders of magnitude worse than profiling results obtained from optimized code. As a simple example, the reader is referred to Table 1. The first column shows source code for an iterative calculation without optimization. The second column corresponds to the same functionality, but calculated in an optimized way for memory accesses, by introducing registers instead of external memory accesses. In the third column, the iterative calculation scheme has been transformed into a closed-form analytical calculation formula. Clearly, the number of arithmetic operations and memory accesses can vary drastically between the different versions.

Table 1: Difference in performances depending on the optimization level.

Which commercial profiling tools are available?

Different instrumentation tools can be used for measuring the complexity of a program. Some commercial tools are:

• Quantify (on Unix), which keeps track of the program flow during execution and counts the number of function accesses and their execution time.
• Vtune (on Intel platforms), that determines which function is active at sampling points over regular time intervals. The instrumentation results provided by Vtune are quite sensitive to the environmental settings, i.e. other programs active in the operating system.

Which freeware profiling tools are available?

The only freeware tool available to the MPEG-4 community is iprof [M0838, M0921, M1056, M2863, M3551]. It is based on the GNU C/C++ compiler and delivers very accurate statistics over time of the execution of the program, including arithmetic complexity, as well as memory access cost (only for SPARC processor). It has the advantage that no source code modifications are required to perform the profiling, since it instruments the executable. Unfortunately, it does not provide memory access statistics for x86 architectures. The tool iprof is available at:

http://www.lis.e-technik.tu-muenchen.de/people/second_page/kp/iprof.html

ftp://ftp.lis.e-technik.tu-muenchen.de directory: /pub/iprof

How does the instrumentation tool work?

Different approaches can be used for profiling. One approach consists of counting the number of activations of the different functions and the number of times that some loops in the function are traversed. This approach has the advantage that the profiling results can more easily be reinterpreted for different architectures. Indeed, if some function loops are pipelined over different hardware modules, the execution time is only limited by the slowest module. Therefore, mainly the profiling results corresponding to that particular module should be taken into account. An example of that approach can be found in [arithm coder].

At a finer granularity, one can count the number of arithmetic operations. Often, this is performed by overloading operations in C++ [M0724]. In general, statistics of the arithmetic operations are gathered without distinction of the function call, so that these fine granularity statistics can often not be remapped onto different architectures without repeated simulation processes.

To make this mechanism of operation overloading effective, the elements that are to be instrumented should be declared as class instances (e.g. Word8, Word16, Word32, Float32, Float64) instead of basic data types (char, short, long, float, double). Source code editing is therefore often required.

A last approach consists of subdividing a program into basic blocks. Basic blocks are straight-line sequences of machine instructions that execute sequentially, without jumps into or out of the sequence. This approach has the advantage that source code editing can be avoided, but the profiling results are completely architecture dependent.

How can I measure execution/CPU time?

The execution time can often be measured quite easily by reading the system clock. The disadvantage of measuring the system clock is that other processes can delay the execution of the program to be profiled, therefore influencing the execution time measurements. CPU time measurements do not have this disadvantage, but for practical reasons CPU time measurements have limited accuracy (in the order of magnitude of ms, which represents an eternity for processor time).

What is Computational Graceful Degradation?

The main idea of CGD is to render images or produce sound at poorer quality when the desirable quality cannot be obtained in real time, for instance because the complexity of the task exceeds the available processing power. This approach makes the guarantee of the correct scheduling of tasks possible, even when the computational system load fluctuates and necessary resources exceed the available ones.

The goal is to be able to provide the guarantee of real-time video and audio decoding with possible degradations of the image quality, i.e reductions of the peak signal to noise ratio (PSNR), without loosing parts of the image. Such alternative is certainly much more desirable than other straightforward options such as cutting image portions or simply skipping frames.

What is normative in Computational Graceful Degradation?

The implementation of specific CGD algorithms which provides the highest complexity reduction for the lowest image degradation is an implementation dependent issue which has no normative implications. Only the definition of the complexity parameters, that will be transmitted through the network, so that the decoder can estimate the required processing power for high quality rendering, is normative.

Overview of contributions

Table 2: Overview of contributions related to MPEG-4 implementation