Shuvra S Bhattacharyya

Johan Eker
email: johan.eker@ericsson.com

Jörn W Janneck
email: jorn.janneck@xilinx.com

Christophe Lucarz

Marco Mattavelli

Mickaël Raulet
email: mickael.raulet@insa-rennes.fr

Overview of the MPEG Reconfigurable Video Coding Framework

Keywords: Reconfigurable Video Coding, Cal actor language, dataflow programming, code synthesis

HAL is

Introduction

A large number of successful MPEG (Motion Picture Expert Group) video coding standards have been developed since the first MPEG-1 standard in 1988. The standardization efforts in the field, beside having as first objective to guarantee the interoperability of compression systems, has also aimed at providing appropriate forms of specifications for wide and easy deployment. While at the beginning MPEG-1 and MPEG-2 were only specified by textual descriptions, with the increasing complexity of algorithms, starting with the MPEG-4 set of standards, C or C++ specifications, called also reference software, have became the formal specification of the standards. However, such descriptions composed of non-optimized non-modular software packages have started to show many limits. If we consider that they are in practice the starting point of any implementation, system designers have to rewrite these software packages not only to try optimize performances, but also to transform these descriptions into appropriate forms adapted to the current system design methodologies. Such monolithic specifications hide the inherent parallelism and the dataflow structure of the video coding algorithms, features that are necessary to be exploited for efficient implementations. In the meanwhile the evolution of video coding technologies, leads to solutions that are increasingly complex to be designed and present significant overlap between successive versions of the standards. Consequently, adding new coding tools to a standard involves a new specification for which all its components are modified whereas only a few tools and interfaces are changed. Another problem raised by the wide variety of video coding tools is the selection of the subsets of coding tools used by a specific application. These (sub-)sets are also known as "profiles" in MPEG. The "a priori" specification of a small number of such profiles has become very problematic. Such "average" subsets prevent the possibility of optimally satisfy a variety of specific applications, whereas the specification of too many profiles would result in an obstacle for guaranteeing interoperability. The observation of these drawbacks of current video standard specification formalism led to the development of the Reconfigurable Video Coding (RVC) standard. The key concept behind the project is to be able to design a decoder at a higher level of abstraction than the one provided by current generic monolithic C based specifications. Instead of low level C/C++ code, an "abstract" model based on modular components taken from the standard library, is the reference specification. Functionality of the coding tools and their potential concurrency are explicitly exposed to implementers by the specification formalism chosen. This solution is by far a better starting point for any design and implementation methodology and process. Conversely the old C/C++ source code specification had to include by its nature of being a sequential formalism a specific scheduling of operation without explicitly providing what scheduling are needed for the intrinsic algorithm data dependencies and which one are arbitrary defined in the reference specification. Indeed RVC provides a high-level description of the MPEG standard using as new expressive and compact form of reference SW, for each module of the standard library and for each instantiation of a new decoder configuration. A specific language called Cal [START_REF] Eker | CAL Language Report Specification of the CAL Actor Language[END_REF] is the core of the RVC dataflow model that expose the intrinsic concurrency of the algorithms by employing the notions of actor programming and dataflow. Concurrency and parallelism are fundamental aspects of embedded system design as we enter in the multicore era. Moreover, the standard ISO/IEC MPEG RVC framework is also supported by a non normative design framework composed by a simulation platform and by synthesis tools, Cal2C [START_REF] Roquier | Automatic software synthesis of dataflow program: An MPEG-4 simple profile decoder case study[END_REF][START_REF] Wipliez | Software code generation for the RVC-CAL language[END_REF] and Cal2HDL [START_REF] Janneck | Synthesizing hardware from dataflow programs: An MPEG-4 simple profile decoder case study[END_REF][START_REF] Janneck | Synthesizing hardware from dataflow programs: An MPEG-4 simple profile decoder case study[END_REF], providing direct conversions to C and HDL implementations.

The paper also provides an overview on such code generator tools and on the principles on which they are based. Results on a real design case of a MPEG-4 Simple Profile decoder show that systems obtained with the hardware code synthesis from a Cal model outperform the hand written VHDL version both in terms of performance, resource usage and design efforts.

Reconfigurable Video Coding: ISO-MPEG standardization

MPEG has produced several video coding standards such as MPEG-1, MPEG-2, MPEG-4 Video, AVC (Advanced Video Coding) and recently SVC (Scalable Video Coding). However, the past monolithic specification of such standards (usually in the form of C/C++ programs) lacks flexibility and does not allow to use the combination of coding algorithms from different standards enabling to achieve specific design or performance trade-offs and thus fill, case by case, the requirements of specific applications. Indeed, not all coding tools defined in a profile@level of a specific standard are required in all application scenarios. For a given application, codecs are either not exploited at their full potential or require unnecessarily complex implementations. However, a decoder conformant to a standard has to support all of them and may results in non-efficient implementations.

So as to overcome the limitations intrinsic of specifying codecs algorithms by using monolithic imperative code, a profiled version of Cal language has been selected by the ISO/IEC standardization organization in the new MPEG standard called RVC which stays for Reconfigurable Video Coding. RVC is composed of two ISO/IEC standard specifications: [START_REF]MPEG systems technologies -Part 4: Codec Configuration Representation[END_REF] and [START_REF]MPEG video technologies -Part 4: Video tool library[END_REF]. The data-driven programming paradigm of Cal dataflow language that lends itself naturally to describing the processing of media streams that pervade the world of media coding, has been restricted and simplified from its original formulation so as to provide description that can be synthesized to software and hardware implementation by already existing tools. However, the original expressivity of the language and the strong encapsulation features offered by the actor programming model have been preserved and provide a solid foundation for the compact and modular specification of media codecs.

MPEG RVC is a framework allowing users to define a multitude of different codecs, by combining together Functional Units (FUs) (i.e. actors in programming language) modeling video coding tools, from the MPEG standard library written in Cal, that contains video technology from all existing MPEG standards (i.e. MPEG-2, MPEG-4, MPEG-4 AVC , etc. . . ). The reader can also refer to [START_REF] Lucarz | Reconfigurable Media Coding: A New Specification Model for Multimedia Coders[END_REF] for more information and details about RVC. RVC-Cal is used to provide the reference software for all coding tools (FUs) of the entire library. The essential elements of the RVC framework (Fig. 1) include:

the standard Video Tool Library (VTL) [START_REF]MPEG video technologies -Part 4: Video tool library[END_REF] which contains the video coding tools. RVC-Cal is used to describe the algorithmic behaviour of the FUs that end to be video coding algorithmic components self contained and communicating with the external world only by means of input and output ports. a language called Functional unit Network Language (FNL) [START_REF]MPEG systems technologies -Part 4: Codec Configuration Representation[END_REF], an XML dialect, used to specify a decoder configuration made up of FUs taken from the VTL and the connections between the FUs. Also this language is specified and standardized in [START_REF]MPEG systems technologies -Part 4: Codec Configuration Representation[END_REF]. a MPEG-21 Bitstream Syntax Description Language (BSDL) [START_REF]MPEG systems technologies -Part 5: Bitstream Syntax Description Language (BSDL)[END_REF] schema which describes the syntax of the bitstream that a RVC decoder has to decode. In [START_REF] Raulet | Validation of bitstream syntax and synthesis of parsers in the MPEG Reconfigurable Video Coding framework[END_REF][START_REF] Lucarz | Automatic synthesis of parsers and validation of bitstreams within the MPEG Reconfigurable Video Coding Framework[END_REF], tools and methodologies for the validation of BSDL syntaxes are described in full details as well as some examples of systematic procedures for the direct synthesis of parsers in the Cal dataflow specification formalism. Such BSDL to Cal translator is in its final stage of development as part of the Open Dataflow effort [START_REF]The OpenDF dataflow project sourceforge[END_REF][START_REF] Bhattacharyya | OpenDF -A Dataflow Toolset for Reconfigurable Hardware and Multicore Systems[END_REF] ADM by generating SW and/or HW implementations by means of appropriate synthesis tools.

Thus, based on Cal dataflow formalism, designers can build video coding algorithm with a set of selfcontained modular elements coming from the MPEG RVC standard library (VTL). However, the new Cal based specification formalism, not only provide the flexibility required by the process itself of specifying a standard video codec, but also yields a specification of such standard that is the appropriate starting point for the implementation of the codec on the new generations of multicore platforms. In fact the RVC ADM is nothing else that a Cal dataflow specification that implicitly exposes all concurrency and parallelism intrinsic to the model, features that classical generic specifications based on imperative languages have not provided so far.

MPEG RVC toolbox includes about 150 Functional units that can be configured to specify the MPEG-2 MP, MPEG-4 SP and ASP, AVCBP, AVCHP and SVC. Some FU can already be used to generate new extended profiles, for instance supporting 422 and 444 chrominance patterns if not available in the original profile. Conformance testing of the RVC toolbox for single FUs and entire decoders are currently on going.

As illustrated in picture 1 the MPEG RVC standard does not specify anything concerning the implementation methodology and technology of a RVC decoder. The upper part of the picture illustrates the process that, starting from a normative description of a decoder composed by a bitstream syntax description (expressed in RVC-BSDL in a XML schema), by a FU network description (expressed in FNL) and by the knowledge of the I/O behavior of the FU specified in the RVC toolbox, provide a normative (executable) description of the RVC decoder. Indeed what is called an abstract decoder description is a Cal dataflow program that constitutes the conformance point between the normative RVC specification and all possible proprietary implementations that be generated to decode the incoming bitstreams. Thus the MPEG RVC standard leaves open the platforms and the implementation methodologies that can be used to generate any RVC proprietary implementation. This provides all possibility of generating parallel and concurrent implementations for a wide variety of existing and emerging implementation platforms. An important consequence of the fact that no specific implementation technology is specified by the MPEG RVC standard is that it is not limited to applications that require direct download and on the fly instantiation of proprietary implementations. Several application scenarios and transport mechanism of the RVC decoder description are under development and will be included in appropriate amendment of the MPEG Systems standard. Thus, indirect generations of implementations, such as the one available via web download and other form of deployment, will be possible together with the direct synthesis of SW and HW from the ADM. All these possibilities enable, for each application scenario, the users to select the most appropriate implementation methodology.

More details on different implementation approaches, on the methodologies for generating parsers from bitstream syntax descriptions are available on papers published in this special issue. Detailed examples on new decoder configurations optimizing different implementation objectives such as concurrency and parallelism or overall complexity cannot be provided here for space reasons and only concept and principles behind all RVC formalism are discussed in the follow of the paper as well some the concept and examples of the tools synthesizing Cal to SW and HW implementations.

Why C etc. Fail

Having introduced the main motivations that lead MPEG to introduce Cal dataflow based specifications as well as the elements that compose the RVC framework, this section will briefly extend the discussion adding other reasons for which a paradigm shift in system specification and modeling has been necessary and could be advantageous not only for the field of video compression. The control over low-level detail, which is considered a merit of C, tends to over-specify programs: not only the algorithms themselves are specified, but also how inherently parallel computations are sequenced, how inputs and outputs are passed between the algorithms and, at a higher level, how computations are mapped to threads, processors and applicationspecific hardware. It is not always possible to recover the original knowledge about the program by means of analysis and the opportunities for restructuring transformations are limited.

Code generation is constrained by the requirement of preserving the semantic effect of the original program. What constitutes the semantic effect of a program depends on the source language, but loosely speaking some observable properties of the program's execution are required to be invariant. Program analysis is employed to identify the set of admissible transformations; a code generator is required to be conservative in the sense that it can only perform a particular transformation when the analysis results can be used to prove that the effect of the program is preserved. Dependence analysis is one of the most challenging tasks of high-quality code generation (for instance see [START_REF] Zima | Supercompilers for parallel and vector computers[END_REF]). It determines a set of constraints on the order, in which the computations of a program may be performed. Efficient utilization of modern processor architectures heavily depends on dependence analysis, for instance:

to determine efficient mappings of a program onto multiple processor cores (parallelization), to utilize so called SIMD or "multimedia" instructions that operate on multiple scalar values simultaneously (vectorization), and to utilize multiple functional units and avoid pipeline stalls (instruction scheduling).

Determining (a conservative approximation of) the dependence relation of a C program involves pointer analysis. Since the general problem is undecideable, a trade-off will always have to be made between the precision of the analysis and its resource requirements [START_REF] Hind | Pointer analysis: haven't we solved this problem yet?[END_REF].

Why dataflow might actually work

Scalable parallelism. In parallel programming, the number of things that are happening at the same time can scale in two ways: It can increase with the size of the problem or with the size of the program. Scaling a regular algorithm over larger amounts of data is a relatively well-understood problem, while building programs such that their parts execute concurrently without much interference is one of the key problems in scaling the von Neumann model. The explicit concurrency of the actor model provides a straightforward parallel composition mechanism that tends to lead to more parallelism as applications grow in size, and scheduling techniques permit scaling concurrent descriptions onto platforms with varying degrees of parallelism.

Modularity, reuse. The ability to create new abstractions by building reusable entities is a key element in every programming language. For instance, objectoriented programming has made huge contributions to the construction of von Neumann programs, and the strong encapsulation of actors along with their hierarchical composability offers an analog for parallel programs.

Scheduling. In contrast to procedural programming languages, where control flow is made explicit, the actor model emphasizes explicit specification of concurrency.

Portability. Rallying around the pivotal and unifying von Neumann abstraction has resulted in a long and very successful collaboration between processor architects, compiler writers, and programmers. Yet, for many highly concurrent programs, portability has remained an elusive goal, often due to their sensitivity to timing. The untimedness and asynchrony of streambased programming offers a solution to this problem. The portability of stream-based programs is underlined by the fact that programs of considerable complexity and size can be compiled to competitive hardware [START_REF] Janneck | Synthesizing hardware from dataflow programs: An MPEG-4 simple profile decoder case study[END_REF][START_REF] Janneck | Synthesizing hardware from dataflow programs: An MPEG-4 simple profile decoder case study[END_REF] as well as software [START_REF] Roquier | Automatic software synthesis of dataflow program: An MPEG-4 simple profile decoder case study[END_REF], which suggests that streambased programming might even be a solution to the old problem of flexibly co-synthesizing different mixes of hardware/software implementations from a single source.

Adaptivity. The success of a stream programming model will in part depend on its ability to configure dynamically and to virtualize, i.e. to map to collections of computing resources too small for the entire program at once. The transactional execution of actors generates points of quiescence, the moments between transactions, when the actor is in a defined and known state that can be safely transferred across computing resources.

The Cal Actor Language

Cal [START_REF] Eker | CAL Language Report Specification of the CAL Actor Language[END_REF] is a domain-specific language that provides useful abstractions for dataflow programming with actors. Cal has been used in a wide variety of applications and has been compiled to hardware and software implementations, and work on mixed HW/SW implementations is under way. The next section provides a brief introduction to some key elements of the language.

Basic Constructs

The basic structure of a Cal actor is shown in the Add actor (Fig. 2), which has two input ports A and B, and one output port Out, all of type T. The actor contains one action that consumes one token on each input ports, and produces one token on the output port. An action may fire if the availability of tokens on the input ports matches the port patterns, which in this example corresponds to one token on both ports A and B. An actor may have any number of actions. The untyped Select actor (Fig. 3) reads and forwards a token from either port A or B, depending on the evaluation of guard conditions. Note that each of the actions has empty bodies.

Priorities and State Machines

An action may be labeled and it is possible to constrain the legal firing sequence by expressions over labels. In the PingPongMerge actor, reported in the Figure 4, a finite state machine schedule is used to force the action sequence to alternate between the two actions A and B. The schedule statement introduces two states s1 and s2.

The Route actor, in the Figure 5, forwards the token on the input port A to one of the three output ports. Upon instantiation it takes two parameters, the functions P and Q, which are used as predicates in the guard conditions. The selection of which action to fire is in this example not only determined by the availability of tokens and the guards conditions, by also depends on the priority statement. actor Route (P , Q) A ⇒ X, Y, Z :

toX : action [ v ] ⇒ X: [ v ] guard P( v ) end toY : action [ v ] ⇒ Y: [ v ] guard Q( v ) end toZ : action [ v ] ⇒ Z : [ v ] end p r i o r i t y
toX > toY > toZ ; end end Fig. 5 Priority structure in a Cal actor.

Cal subset language for RVC

For an in-depth description of the language, the reader is referred to the language report [START_REF] Eker | CAL Language Report Specification of the CAL Actor Language[END_REF], for the specific subset specified and standardized by ISO in the Annex C of [START_REF]MPEG systems technologies -Part 4: Codec Configuration Representation[END_REF]. This subset only deals with fully typed actors and some restrictions on the Cal language constructs from [START_REF] Eker | CAL Language Report Specification of the CAL Actor Language[END_REF] to have efficient hardware and software code generations without changing the expressivity of the algorithm. For instance, Figures 3, 4 and 5 are not RVC-Cal compliant and must be changed as the Figures 6, 7 and 8 where T1, T2, T are the types and only typed paramters can be passed to the actors not functions as P, Q.

A large selection of example actors is available at the

OpenDF repository [START_REF]The OpenDF dataflow project sourceforge[END_REF], among them can also be found the MPEG-4 decoder discussed below. Many other actors written in RVC-Cal will be soon be available as standard MPEG RVC tool repository once the conformance testing process will be completed.

v i n ) end f u n t i o n Q(T v i n )--> T : \\ body o f t h e function P Q( v i n ) end toX : action [ v ] ⇒ X: [ v ] guard P( v ) end toY : action [ v ] ⇒ Y: [ v ] guard Q( v ) end toZ : action [ v ] ⇒ Z : [ v ] end p r i o r i t y toX > toY > toZ ; end end

Networks

A set of Cal actors are instantiated and connected to form a Cal application, i.e. a Cal network. Figure 9 shows a simple Cal network Sum, which consists of the previously defined RVC-Cal Add actor and the delay actor shown in Figure 10.

The source/language that defined the network Sum is found in Figure 11. Please, note that the network itself has input and output ports and that the instantiated entities may be either actors or other networks, which allows for a hierarchical design.

Formerly, networks have been traditionally described in a textual language, which can be automatically converted to FNL and vice versa -the XML dialect standardized by ISO in Annex B of [START_REF]MPEG systems technologies -Part 4: Codec Configuration Representation[END_REF]. The XML representation of the Sum network is found in Figure 12. A graphical editing framework called Graphiti editor [8] is available to create, edit, save and display a network. The XML and textual format for the network description are supported by such editor.

Tools

Cal Simulators and Code generators

Cal is supported by a portable interpreter infrastructure that can simulate a hierarchical network of actors. This interpreter was first used in the Moses [START_REF]Moses project[END_REF] project. Moses features a graphical network editor, and allows the user to monitor actors execution (actor state and token values). The project being no longer maintained, it has been superseded by an Eclipse environment composed of 2 tools/plugins-the Open Dataflow environ-<?xml version=" 1 . 0 " e n c o d i n g="UTF-8" ?> <XDF name="Sum"> <P o r t k i n d=" I n p u t " name=" I n " /> <P o r t k i n d=" Output " name="Out" /> <I n s t a n c e i d=" add " /> <I n s t a n c e i d=" z "> <C l a s s name="Z" /> <P a r a m e t e r name=" v "> <Expr k i n d=" L i t e r a l " l i t e r a l -k i n d=" I n t e g e r " v a l u e=" 0 " /> </ P a r a m e t e r> ment for Cal editing (OpenDF [START_REF]The OpenDF dataflow project sourceforge[END_REF] for short) and the Graphiti editor for graphically editing the network.

OpenDF is also a compilation framework. Today there exists a backend for generation of HDL (VHDL/Verilog) [START_REF] Janneck | Synthesizing hardware from dataflow programs: An MPEG-4 simple profile decoder case study[END_REF][START_REF] Janneck | Synthesizing hardware from dataflow programs: An MPEG-4 simple profile decoder case study[END_REF], and another backend that generates C for integration with the SystemC tool chain [START_REF] Roquier | Automatic software synthesis of dataflow program: An MPEG-4 simple profile decoder case study[END_REF][START_REF] Wipliez | Software code generation for the RVC-CAL language[END_REF]. A third backend targeting ARM11 and embedded C is under development [START_REF] Von Platen | Efficient realization of a cal video decoder on a mobile terminal[END_REF] as part of the EU project ACTORS [START_REF]Actors FP7 project[END_REF]. It is also possible to simulate Cal models in the Ptolemy II [START_REF]Ptolemy II[END_REF] environment.

Analysis Support

A major benefit of formulating RVC specifications in terms of a formal dataflow modeling language (CAL) is the potential for rigorous analysis and optimization of specifications. This is of increasing importance as more features are embedded and more demands are imposed in terms of real-time performance.

To this end, CAL-based tools for RVC have been integrated with the dataflow interchange format (DIF), which is a textual language for specifying mixed-grain dataflow representations of signal processing applications, and TDP [29] (the DIF package), which is a software tool for analyzing DIF specifications. A major emphasis in DIF and TDP is support for working with and integrating different kinds of specialized dataflow models of computation and their associated analysis techniques. Such functionality is useful, for example, as a follow-on step to the automated detection of specialized dataflow regions in Cal networks. Once such regions are detected, they can be annotated with corresponding DIF keywords -e.g., CSDF (cyclo-static dataflow) and SDF (synchronous dataflow) -and then scheduled and integrated with appropriate TDP-based analysis methods. Such a linkage between Cal and TDP is under A particular area of emphasis in TDP is support for developing efficient coarse-grain dataflow scheduling techniques. For example, the generalized schedule tree representation in TDP provides an efficient format for storing, manipulating, and viewing schedules [START_REF] Ko | Parameterized Looped Schedules for Compact Representation of Execution Sequences in DSP Hardware and Software Implementation[END_REF], and the functional DIF dataflow model provides for flexible prototyping of static, dynamic, and quasi-static scheduling techniques [START_REF] Plishker | Functional DIF for Rapid Prototyping[END_REF]. Libraries of static scheduling techniques and buffer management models for SDF graphs, as well as an SDF-to-C translator are also available in TDP [START_REF] Hsu | Software synthesis from the dataflow interchange format[END_REF]. The set of dataflow models that are currently recognized and supported explicitly in the DIF language and TDP include Boolean dataflow [START_REF] Buck | Scheduling dynamic dataflow graphs with bounded memory using the token flow model[END_REF], enable-invoke dataflow [START_REF] Plishker | Functional DIF for Rapid Prototyping[END_REF], CSDF [START_REF] Bilsen | Cycle-static dataflow[END_REF], homogeneous synchronous dataflow [START_REF] Lee | Synchronous data flow[END_REF][START_REF] Sriram | Embedded Multiprocessors: Scheduling and Synchronization[END_REF], multidimensional synchronous dataflow [START_REF] Murthy | Shared memory implementations of synchronous dataflow specifications[END_REF], parameterized synchronous dataflow [START_REF] Bhattacharya | Parameterized dataflow modeling for DSP systems. Signal Processing[END_REF], and SDF [START_REF] Lee | Synchronous data flow[END_REF]. These alternative dataflow models have useful trade-offs in terms of expressive power, and support for efficient static or quasi-static scheduling, as well as efficient buffer management. The set of models that is supported in TDP, as well as the library of associated analysis techniques are expanding with successive versions of the TDP software.

The initial focus in integrating TDP with Cal is to automatically-detect regions [START_REF] Gu | Exploiting statically schedulable regions in dataflow programs[END_REF] of Cal networks that conform to SDF semantics, and can leverage the significant body of SDF-oriented analysis techniques in TDP. In the longer term, we plan to target a range of different dataflow models in our automated "region detection" phase of the design flow. This appears significantly more challenging as most other models are more complex in structure compared to SDF; however, it can greatly increase the flexibility with which different kinds of specialized, streaming-oriented dataflow analysis techniques can be leveraged when synthesizing hardware and software from Cal networks.

An example of implementation of a MPEG-4 SP decoder by direct synthesis of a MPEG RVC description

One interesting and very attracting implementation methodology of MPEG RVC decoder descriptions is the direct synthesis of the standard specification. It provides a source of relevant application of realistic sizes and complexity and also enables meaningful experiments and advances in dataflow programming. More details on the software and hardware code generators can be found in [START_REF] Janneck | Synthesizing hardware from dataflow programs: An MPEG-4 simple profile decoder case study[END_REF][START_REF] Wipliez | Software code generation for the RVC-CAL language[END_REF]. Some of the authors have performed an implementation study [START_REF] Janneck | Synthesizing hardware from dataflow programs: An MPEG-4 simple profile decoder case study[END_REF][START_REF] Janneck | Synthesizing hardware from dataflow programs: An MPEG-4 simple profile decoder case study[END_REF], in which the RVC MPEG-4 Simple Profile decoder specified in Cal according to the MPEG RVC formalism has been implemented on an FPGA using a Cal-to-RTL code generator called Cal2HDL. The MPEG-4 Simple Profile abstract decoder model that essentially results to be a dataflow program (Figure 14, Table 3), is composed of 27 atomic FUs (or actors in dataflow programming) and 9 sub-networks (actor/network composition); atomic actors can be instantiated several times, for instance there are 42 actor instantiations in this dataflow program. Figure 15 shows a top-level view of the decoder. The main functional blocks include the bitstream parser, the reconstruction block, the 2D inverse cosine transform, the frame buffer and the motion compensation module. These functional units are themselves hierarchical compositions of actor networks. The objective of the design was to support 30 frames of 1080p in the YUV420 format per second, which amounts to a production of 93.3 Mbyte of video output per second. The given target clock rate of 120 MHz implies 1.29 cycles of processing per output sample on average.

The results of the implementation study were encouraging in that the code generated from the MPEG RVC Cal specification did not only outperformed the handwritten reference in VHDL, both in terms of throughput and silicon area, but also allowed for a significantly reduced development effort. Table 1 shows the comparison between Cal specification and the VHDL reference.

It should be emphasized that this counter-intuitive result cannot be attributed to the sophistication of the synthesis tool. On the contrary the tool does not perform a number of potential optimizations, such as for instance optimizations involving more than one actor. Instead, the good results appear to be yield by the implementation and development process itself. The implementation approach was based generating a proprietary implementation of the standard MPEG RVC toolbox composed of FUs of lower level of granularity. Thus the implementation methodology was to substitute the FU of the standard abstract decoder model of the MPEG-4 SP with an equivalent implementation, in terms of behavior. Essentially standard toolbox FU were substituted with networks of FU described as actors of lower granularity. A notable difference of such implementation approach when compared with the classical hand writing of HDL code from a textual or sequential specification (i.e. a C/C++ program for instance) was that the Cal specification of the proprietary implementation toolbox (that can be directly derived from the standard RVC toolbox) could go through significantly more design iterations than the one applicable from a handwritten VHDL reference -in spite of being developed in approximately a quarter of the development time (including the time of developing the standard MPEG RVC toolbox from scratch). Whereas a dominant part of the development of a classical VHDL reference development need to be spent getting the system to work correctly, the effort of the Cal specification could be focused on optimizing system performance to meet the design constraints. The initial design cycle of the proprietary RVC library resulted in an implementation that was not only inferior to the VHDL reference, but one that also failed to meet the throughput and area constraints. Subsequent iterations explored several other points in the design space until arriving at a solution that satisfied the constraints. At least for the considered implementation study, the benefit of short design cycles seem to outweigh the inefficiencies that resulted from high-level synthesis and the reduced control over implementation details. In particular, the asynchrony of the programming model and its realization in hardware allowed for convenient experiments with design ideas. Local changes, involving only one or a few actors, do not break the rest of the system in spite of a significantly modified temporal behavior. In contrast, any design methodology that relies on precise specification of timing -such as RTL, where designers specify behavior cycle-by-cyclewould have resulted in changes that propagate through the design.

Size

Table 1 shows the quality of result produced by the RTL synthesis engine of the MPEG-4 Simple Profile video decoder. Note that the code generated from the high-level dataflow RVC description and proprietary implementation of the MPEG toolbox actually outperforms the hand-written VHDL design in terms of both throughput and silicon area for a FPGA implementation.

Another synthesis tool called Cal2C [START_REF] Roquier | Automatic software synthesis of dataflow program: An MPEG-4 simple profile decoder case study[END_REF][START_REF] Wipliez | Software code generation for the RVC-CAL language[END_REF] validates another implementation methodology of the MPEG-4 Simple Profile dataflow program provided by the RVC standard (Figure 14). Table 2 shows that synthesized C-software is faster than the simulated Cal dataflow program (20 frames/s instead of 0.15 frames/s), and close to real-time decoding for a QCIF format (25 frames/s). However it remains slower than the automatically synthesized hardware description by Cal2HDL [START_REF] Janneck | Synthesizing hardware from dataflow programs: An MPEG-4 simple profile decoder case study[END_REF][START_REF] Janneck | Synthesizing hardware from dataflow programs: An MPEG-4 simple profile decoder case study[END_REF]. As described above, the MPEG-4 Simple Profile dataflow program is composed of 42 actor instantiations in the flattened dataflow program. The flattened network becomes a C++ file that currently contains a systemC scheduler (sequential fashion scheduler) for both actor scheduling and token consumptions/productions. Each actor becomes a C file containing all its action/processing with its overall action scheduling/control. Its number of SLOC is shown in Table 3. All of the generated files are successfully compiled by gcc. For instance, the "ParserHeader" actor inside the "Parser" network is the most complex actor with multiple actions. The translated C-file (with actions and state variables) includes 1043 SLOC for actions and 1895 for action scheduling. The original Cal file contains 962 lines of codes as a comparison.

Conclusion

This paper describes the essential components of the ISO/IEC MPEG Reconfigurable Video Coding framework based on the dataflow concept and having as core the new specification formalism called RVC-Cal a subset of Cal dataflow language. The RVC MPEG tool library, that covers in modular form all video algorithms from the different MPEG video coding standards, shows that Cal is an appropriate language for supporting design flows aiming at building complex heterogeneous systems from high level system specifications. The MPEG RVC framework is also supported by a simulator, software and hardware code synthesis, and the DIF/TDP analysis tools. Cal dataflow models used by the MPEG RVC standard result also particularly efficient for specifying signal processing systems in a very synthetic form compared to classical imperative languages. Moreover, Cal model libraries can be developed in the form of libraries of proprietary implementations of standard RVC components to describe architectural features of the desired implementation platform, thus enabling the RVC implementer/designer to work at level of abstraction comparable to the one of the RVC video coding algorithms. Hardware and software code generators then provide the low level implementation of the actors and associated network of actors for the different target implementation platforms (multi-core processors or FPGA). Several works and extension of the tools and implementation methodologies supporting the MPEG RVC framework are currently in development. They include the evolution of the software and hardware code generators in terms the extensions specified by the standard RVC-Cal language, the development of scheduling tools such as the quasi-static scheduling [START_REF] Boutellier | Quasi-static scheduling of CAL actor networks for reconfigurable video coding[END_REF] or the DIF/TDP analysis tools [START_REF] Gu | Exploiting statically schedulable regions in dataflow programs[END_REF] for the scheduling/mapping on multicore platforms of SW synthesized from the RVC abstract decoder model and the evolution of the current Open DataFlow environment including tools for more accurate and extended profiling and debugging capabilities.

actorFig. 2

 2 Fig. 2 Basic structure of a Cal actor.

Fig. 3

 3 Fig. 3 Guard structure in a Cal actor.

actorFig. 4 FSM

 4 Fig.4FSM structure in a Cal actor.

Fig. 6

 6 Fig.6Guard structure in a RVC-Cal actor.

actorFig. 7 FSM

 7 Fig.7FSM structure in a RVC-Cal actor.

Fig. 8

 8 Fig. 8 Priority structure in a RVC-Cal actor.

Fig. 9 A

 9 Fig. 9 A simple Cal network.

  Fig. 12 XML representation of the Sum network.

Fig. 13

 13 Fig. 13 OpenDF: tools

Fig. 14 MPEG- 4

 144 Fig. 14 MPEG-4 Simple Profile RVC specification network.

Fig. 15

 15 Fig. 15 Top-level dataflow graph of the proprietary implementation of the RVC MPEG-4 decoder.

Table 1

 1 Hardware synthesis results for a proprietary implementation of a MPEG-4 Simple Profile decoder. The numbers are compared with a reference hand written design in VHDL.

			Speed	Code size	Dev. time
		slices, BRAM	kMB/s	kSLOC	MM
	Cal	3872, 22	290	4	3
	VHDL	4637, 26	180	15	12
	Improv.	1.2	1.6	3.75	4
	factor
	kMB/s=kilo macroblocks per second
	kSLOC=kilo source lines of code

Table 2

 2 MPEG4SP decoder speed and SLOC.

	MPEG4 SP	Speed	Clock speed	Code size
	decoder	kMB/s	GHz	kSLOC
	Cal simulator	0.015	2	3.4
	Cal2C	2	2	10.4
	Cal2HDL	290	0.12	4

Table 3

 3 Code size and number of files automatically generated for MPEG-4 Simple Profile decoder.


Jörn W Janneck
email: jorn.janneck@xilinx.com

Ian D Miller
email: imiller@sixisinc.com

David B Parlour
email: dparlour@tabula.com

Ghislain Roquier

Matthieu Wipliez

Mickaël Raulet
email: mickael.raulet@insa-rennes.fr

Synthesizing hardware from dataflow programs An MPEG-4 Simple Profile decoder case study

Keywords: Dataflow, Cal, Reconfigurable Video Coding, MPEG, high-level synthesis

The MPEG Reconfigurable Video Coding working group is developing a new library-based process for building the reference codecs of future MPEG standards, which is based on dataflow and uses an actor language called Cal. The paper presents a code generator producing RTL targeting FPGAs for Cal, outlines its structure, and demonstrates its performance on an MPEG-4 Simple Profile decoder. The resulting implementation is smaller and faster than a comparable RTL reference design, and the second half of the paper discusses some of the reasons for this counter-intuitive result.

Introduction

The growing complexity of video codecs has made it more difficult to accompany video standards with reliable reference implementations built from scratch. For this reason, MPEG has decided to explore a librarybased approach in which a modular library of video coding modules defines the basic capabilities of a standard. Rather than building an independent new library, future standards will incrementally extend the existing code base with new functionality simply by adding new modules to the library. MPEG's Reconfigurable Video Coding (RVC) effort [START_REF] Bhattacharyya | Overview of the MPEG Reconfigurable Video Coding Framework[END_REF] is in the process of constructing and standardizing this library [START_REF]MPEG video technologies -Part 4: Video tool library[END_REF]. The reader can refer to [START_REF] Bhattacharyya | Overview of the MPEG Reconfigurable Video Coding Framework[END_REF] for further information about the RVC motivations.

In addition to the library itself, RVC is also concerned with the language for describing individual modules, and the way in which they are composed into working decoders. Adopting dataflow as the fundamental design methodology, they have decided to use the Cal actor language [START_REF] Eker | CAL Language Report[END_REF] for building the modules, which are composed using an XML format called FNL [START_REF]MPEG systems technologies -Part 4: Codec Configuration Representation[END_REF] (FU Network Language formerly DDL [START_REF] Thomas-Kerr | Reconfigurable Media Coding: Self-describing multimedia bitstreams[END_REF][START_REF] Lucarz | Reconfigurable Media Coding: a new specification model for multimedia coders[END_REF]).

The use of dataflow as a specification language for video codecs opens interesting new opportunities. In the past, the reference code was at best a starting point for actual implementations. Especially hardware implementations could not directly be derived from the sequential software that served as an executable reference. Dataflow programs, on the other hand, are naturally concurrent, and a much better starting point for a range of efficient implementations, from sequential software, to multi-core architectures, to programmable hardware to ASICs.

This paper presents a tool that translates dataflow programs written in Cal into RTL descriptions suitable for implementation in programmable hardware, and its application to the construction of an MPEG-4 Simple Profile decoder. After reviewing the dataflow programming model and some basic properties of the Cal actor language in section 2 and the tools supporting MPEG's RVC effort in section 3, we present the MPEG-4 decoder design and its translation to hardware in section 4, explaining the various stages in the translation process. The quality of the resulting decoder implementation turns out to be better than that of a VHDL reference design, and section 5 discusses how some aspects of the dataflow design process contribute to this surprising result. Finally, section 6 closes with a discussion of the work and some conclusions.

Dataflow and CAL

The dataflow programming model presented in this paper composes systems from computational kernels called actors by connecting them using lossless directed FIFO channels. Through these channels they send each other packets of data, called tokens. Depending on the implementation platform, the FIFOs may be bounded or unbounded, and size constraints may or may not apply to individual tokens. Our model is a slight generalization of the one presented in [START_REF] Lee | Dataflow Process Networks[END_REF], permitting actors that are non-deterministic and not prefix-monotonic.

Actors themselves are written in the Cal actor language [START_REF] Eker | CAL Language Report[END_REF]. A detailed discussion of Cal is beyond the scope of this paper, but for our purposes it is sufficient to say that it provides the syntactical constructs to specify the essential pieces of an actor, viz. its input ports and output ports, a definition of the variables containing its internal state, and a number of transition rules called actions. Each actor executes by making discrete, atomic steps or transitions. In each step, it picks exactly one action from its set of actions (according to the conditions associated with that action), and then executes it, which consists of a combination of the following things:

1. consume input tokens, 2. produce output tokens, 3. modify the state of the actor.

The state of an actor is strictly local, i.e. it is not visible to any other actor. The absence of shared state is what allows the actors in a system to execute their actions without being concerned about race conditions on their state.

Actors are similar to objects in object-oriented programming in the sense that they encapsulate some state and associate it with the code manipulating it (the actions). They differ from objects in that actors cannot call each other-there is no transfer of control from one actor to another, each actor can be thought of as its own independent thread.

Dataflow tools for RVC

Simulator

Cal is supported by a portable interpreter infrastructure that can simulate a hierarchical network of actors. This interpreter was first used in the Moses1 project. Moses features a graphical network editor, and allows the user to monitor actor execution (actor state and token values). The project being no longer maintained, it has been superseded by the Open Dataflow environment (OpenDF2 for short). Contrarily to Moses, this project does not provide a network graphical editor. Networks have been traditionally described in a textual language called Network Language (NL), which can be automatically converted to FNL and vice versa. It is also possible to use the Graphiti editor3 to display networks in the FNL format.

Hardware synthesis

The work presented here is an available tool that converts Cal to HDL. After parsing, Cal actors are instantiated with the actual values for their formal parameters. The result is an XML representation of the actor which is then precompiled (transformation and analysis steps, including constant propagation, type inference and type checking, analysis of data flow through variables...), represented as a sequential program in static single assignment (SSA) form (making explicit the data dependencies between parts of the program).

Then follows the synthesis stage, which turns the SSA threads into a web of circuits built from a set of basic operators (arithmetic, logic, flow control, memory accesses and the like). The synthesis stage can also be given directives driving the unrolling of loops, or the insertion of registers to improve the maximal clock rate of the generated circuit.

The final result is a Verilog file containing the circuit implementing the actor, and exposing asynchronous handshake style interfaces for each of its ports. These can be connected either back-to-back or using FIFO buffers into complete systems. The FIFO buffers can be synchronous or asynchronous, making it easy to support multi-clock-domain dataflow designs.

Software synthesis

It is important to be able to automatically obtain a concrete software implementation from a dataflow description. The C language is particularly well-suited as a target language. The same code can be compiled on any processor, from embedded DSPs and ARMs to generalpurpose microprocessors, which considerably eases the task of writing a software synthesis tool. The interest of having an automatic C software synthesis is twofolded. The code obtained can be executed, in which case it enables a considerably faster simulation of the dataflow program and the ability to debug the program using existing IDEs (Visual Studio, Eclipse CDT). The C code description may be a basis for a tailormade decoder. For these reasons, we created the Cal2C tool [START_REF] Roquier | Automatic software synthesis of dataflow program: an MPEG-4 Simple Profile decoder case study[END_REF] that aims at producing functionally-equivalent, humanly-readable C code from Cal descriptions.

The Cal2C compilation process has been successfully applied to the MPEG-4 Simple Profile dataflow program written by the MPEG RVC experts (Fig. 1). The synthesized model is compared to Cal dataflow program simulated with the Open Dataflow environment so as to validate the Cal2C tool. The synthesized software is faster than the Cal dataflow simulated (20 frames/s instead of 0.15 frames/s), and close to real-time for a QCIF format (25 frames/s). It is interesting to note that the model is scalable: the number of macro-blocks decoded per second remains constant when dealing with larger image sizes. Using Cal2C has also permitted to correct some actors which had an implementation-dependent behavior, such as the assumption of a particular action schedule.

Synthesizing an MPEG-SP decoder

The MPEG-4 Simple Profile decoder discussed in this work is a computational engine consuming a stream of bits on its input (the MPEG bitstream), and producing video data on its output. At 30 frames of 1080p per second, this amounts to 30 * 1920 * 1080 = approx. 62.2 million pixels per second. In the common YUV420 format, each pixel requires 1.5 bytes on average, which means the decoder has to produce approx. 93.3 million bytes of video data (samples) per second.

Fig. 1 shows a top-level view of the dataflow program describing the decoder. 4 The main functional blocks include a parser, an reconstruction block, a 2-D inverse discrete cosine transform (IDCT) block, and a motion compensator. All of these large functional units are themselves hierarchical compositions of actors-the entire decoder comprises of about 60 basic actors.

The parser analyzes the incoming bitstream and extracts the data from it that it feeds into the rest of the decoder. It is by far the most complex block of the decoder, more than a third of the code is used to build the parser. The reconstruction block performs some decoding that exploits the correlation of pixels in neighboring blocks. The IDCT, even though it is the locus of most of the computation performed by the decoder, is structurally rather regular and straightforward compared to the other main functional components. Finally, the task of the motion compensator is to selectively add the blocks issuing from the IDCT to blocks taken from the previous frame. Consequently, the motion compensator needs to store the entire previous frame of video data, which it needs to address into with a certain degree of random access. This data storage and movement results in a few interesting design challenges, some of which are discussed in section 5.

Hardware synthesis

While there is no reason why the standard RVC reference code could not be translated into hardware, at present hardware synthesis does require some consideration on the part of the programmer to achieve very good results. Generally, for a system such as an MPEG decoder, a designer will strive to keep actions simple enough so that they can be executed in as few cycles as possible, often in a single cycle. This means, e.g., that performance-critical parts of the system will avoid the use of loops inside actions. Also, in such cases, programmers will want to avoid deeply nested expressions, which will result in either long combinatorial paths (leading to low clock rates) or they require pipelining, which introduces additional clock cycles.

When generating hardware implementations from networks of Cal actors (specified in some format, such as FNL mentioned above), we currently translate each actor separately, and connect the resulting RTL descriptions with FIFOs. Consequently, we currently do not employ any cross-actor optimizations.

Actors interact with FIFOs using a handshake protocol, which allows them to sense when a token is available or when a FIFO is full. We also do not synthesize any schedule between actors, which means that the resulting system is entirely self-scheduling based on the flow of tokens through it.

The translation of each Cal actor into a hardware description follows a three-step process:

1. instantiation 2. precompilation 3. RTL code generation This is followed by the synthesis of the network that connects the actor instances.

Instantiation. The elaboration of the network structure yields a number of actor instances, which are references to Cal actor descriptions along with actual values for its formal parameters. From this, instantiation computes a closed actor description, i.e. one without parameters, by moving the parameters along with the corresponding actual values into the actor as local (constant) declarations. It then performs constant propagation on the result.

Precompilation. After some simple actor canonicalization, in which several features of the language are translated into simpler forms, precompilation performs some basic source code transformations to make the actor more amenable to hardware implementation, such as e.g. inlining procedure and function calls. Then the canonical, closed actors are translated into a collection of communicating threads.

In the current implementation, an actor with N actions is translated into N +1 threads, one for each action and another one for the action scheduler. The action scheduler is the mechanism that determines which action to fire next, based on the availability of tokens, the guard expression of each action (if present), the finite state machine schedule, and action priorities.

To facilitate backend processing for both hardware and software code generation, the threads are represented in static single-assignment (SSA) form. They interact with the environment of the actor through asynchronous token-based FIFO channels. Their internal communication happens through synchronous unbuffered signals (this is, for instance, how the scheduler triggers actions to fire, and how actions report completion), and they also have shared access to the state variables of the actor.

RTL code generation. The next phase of the translation process generates an RTL implementation (in Verilog) from a set of threads in SSA form. The first step simply substitutes operators in expressions for hardware operators, creates the hardware structures required to implement the control flow elements (loops, if-thenelse statements), and also generates the appropriate muxing/demuxing logic for variable accesses, including the Φ elements in the SSA form.

The resulting basic circuit is then optimized in a sequence of steps.

1. Bit-accurate constant propagation. This step eliminates constant or redundant bits throughout the circuit, along with all wires transmitting them. Any part of the circuit that does not contribute to the result will also be removed, which roughly corresponds to dead code elimination in traditional software compilation. 2. Static scheduling of operators. By default, operators and control elements interact using a protocol of explicit activation-e.g., a multiplier will get triggered by explicit signals signifying that both its operands are available, and will in turn emit such a signal to downstream operators once it has completed multiplication. In many cases, operators with known execution times can be scheduled statically, thus removing the need for explicit activation and the associated control logic. In case operands arrive with constant time difference, a fixed small number of registers can be inserted into the path of the operand that arrives earlier.

Memory access optimizations. Arrays are mapped

to RAM primitives for FPGA implementation. Typical FPGA RAM resources range in size from 16 bits (lookup table memory) to 18 kBit or more (block RAM). RAM primitives can be ganged up to form larger memories, or a number of small arrays may be placed into one RAM. Furthermore, these RAM primitives usually provide two or more ports, which allows for concurrent accesses to the same memory region. Based on an analysis of the sizes of arrays and the access patterns, the backend maps array variables to RAM primitives, and accesses to specific ports. 4. Pipelining, retiming. In order to achieve a desired clock rate, it may be necessary to add registers to the generated circuit in order to break combinatorial paths, and to give synthesis backends more opportunity for retiming.

Network synthesis. The RTL implementations of all the actors in the system are connected by a network that is obtained from a straightforward translation of the original graph structure into HDL, replacing every dataflow connection with the appropriate handshaking signals that mediate the token traffic between actors. Also, during this step the FIFO buffers are instantiated, sized according to the annotations the user provided in the network description.

The network description also allows the user to add annotations that declare actors to be running in different clock domains. Network synthesis will recognize those and generate the appropriate clock network. It will also use either synchronous or asynchronous FIFO implementations depending on whether the two actors connected by the FIFO are in the same or in different clock domains.

Size Speed Code Time The above table shows the quality of the result produced by the RTL synthesis engine for the MPEG decoder. Note that the code generated from the high-level dataflow description actually outperforms a commercially produced VHDL design in terms of both throughput and silicon area-and this in spite of the relative simplicity of our synthesis engine. The next section illustrates some of the reasons for this result.

Dataflow development process

In order to illustrate some of the practical aspects of dataflow development, consider the motion compensator subsystem in Fig. 2. Motion vectors come in on its MV input port, and from those the address actor generates addresses into the frame buffer (in the framebuf actor), which retrieves the data, and interpolate and add proceed to build the final video data.

The engineering challenge is the result of a number of technical constraints. First, we need to produce no fewer than 93.3 million bytes of video data per second in order to do 1080p at 30 frame per second. Furthermore, say we aim for a target clock rate of about 120 MHz. Together with the requirement of 93.3 million samples per second for 1080p at 30 frames per second, this leaves on average no more than 1.29 cycles for each sample.

Finally, let us assume we have DRAM with a setup time of 10 cycles, followed by bursts of 4 bytes per cycle. 5Motion compensation happens on 8x8 blocks, separately for the Y, U, and V components. For each of those blocks, we need to read a 9x9 block from the frame buffer (because of potential half-pixel interpolation). In a straightforward line-by-line frame buffer organization, we thus need to read, for each block of 8x8=64 samples, 9 bursts of length 3 words (each of those being 4 bytes). This takes at least 9 * (10 + 3) = 117 cycles-with 64 samples produced, this comes to 1.83 cycles per sample, which is too much. In order to meet the requirement of 1.29 cycles per sample, we need to exploit the locality of the motion compensation, i.e. the fact that adjacent blocks tend to refer to similar regions in the previous frame.

Caching

One approach might be to use a cache in front of the frame buffer, which reads data from the previous frame in larger bursts and stores them in local memory. The cached image data can be retrieved at a higher rate and single-cycle latency, thereby reducing the impact of the setup latency of the frame buffer memory. Fig. 3a shows the modified motion compensator design, with the cache inserted in front of the frame buffer.

In order to test this design, we insert the test cache in Fig. 3. This small actor is parametric in the cache size (number and length of cache lines), logs cache accesses and records the percentage of misses for a given configuration. As a typical result, for 16 lines of 32 samples, we thus obtain a miss rate of 8.3%. Because of the relatively regular access patterns, that rate does not go down significantly by increasing the cache size.

Unfortunately, each of these 8.3% cache misses incurs an 18 cycle penalty (10 cycles setup, 8 cycles per 32-sample burst). Even if the remaining 91.7% of cache hits were infinitely fast, this amounts to 18 * .083 = 1.49 cycles per sample-better than without the cache, but still not good enough.

Prefetch

Besides statistical locality, motion compensation has two other properties that we can exploit: (1) It is always limited to a relatively small search window, and (2) it happens in a predictable and fixed order as we scan down the video frame block by block. In addition, the search windows for neighboring frames mostly overlap, which means that as the decoder advances from one block to the next, the search window shifts some blocks from the previous frame out, and some new ones in, while most data remains.

In our case, the search window is 3x3 macroblocks, where each macroblock consists of 6 blocks of 8x8 samples, or 384 samples. Reading a macroblock from the frame buffer takes 10 + (384/4) = 106 cycles, thus reading three macroblocks takes 318 cycles. 6 This has to be done once per macroblock of data, or once every 384 samples-consequently, we spend 318/384 = 0.83 cycles per sample reading data from the frame buffer, which conveniently meets our requirements. Note that reading the next set of macroblocks can be concurrent with the processing related to the current search window.

Summary

The design narrative above is intended to illustrate two important aspects of building systems such as the MPEG decoder as dataflow programs. First, the analysis of the cache approach, and its subsequent rejection, happened without ever synthesizing the system to hardware, purely by interactive and quick untimed simulation. In this way we obtained quantitative data (the cache miss rate), which together with some of the engineering constraints (target clock, target sample rate) led us to reject the cache approach. Using high-level tools enabled us to quickly experiment with, and falsify, a design idea without long development cycles, or tedious analyses. The result of this as far as the development process is concerned, is that the dataflow design undergoes many more design cycles than the RTL design-in spite of being done in a quarter of the time. Most of the time in RTL design is spent on getting the system to work correctly. By contrast, a much higher proportion of the dataflow design time is spent on optimizing system performance. At least in the current case study, the positive effects of the shorter design cycles seem to outweigh the inefficiencies introduced through high-level synthesis, and the reduced control of the designer over specific implementation details.

Second, comparing the original design of the motion compensator in Fig. 2 with the design incorporating the prefetched search window in Fig. 4, the difference is exactly one actor, and a few slightly altered connections. None of the other actors in the motion compensator, and of course none of those in the rest of the decoder, were ever touched or modified by this design change. The asynchrony of the programming model, and its realization in hardware, assured that the rest of the system would continue to work in spite of the significantly modified temporal behavior. Any design methodology relying on a precise specification of the timing aspects of the computation-such as RTL, where designers specify behavior cycle-by-cycle-would have resulted in changes rippling throughout the design.

Discussion and conclusion

The central points of this paper can be summarized as follows:

1. We presented a tool that translates dataflow programs like those in the MPEG RVC framework into efficient implementations in programmable hardware. 2. The high-level design methodology based on dataflow and the Cal actor language has been shown to rival RTL design in terms of the implementation quality, at least in the case we have studied here. 3. We have attributed the surprising quality of the resulting implementation to properties of the dataflow design process, rather than to, e.g., the quality of the translation tool or any particularly sophisticated set of optimizations.

The first point may change the role of the MPEG reference code in future implementation flows-especially when building designs on parallel machines or hardware, dataflow-based reference code is a much better starting point, and the existence of an efficient translation to the target platform means that future video codec implementations may be closer to gradual refinement and optimization of the reference code, rather than from-scratch redesigns of the same functionality.

The other two points may be surprising to RTL designers, so they merit closer inspection. Fundamentally, the use of low-level tools seems to create an illusion of optimality simply because of the range and detail of control these tools provide to the designer: if we can control every aspect of the design, how could the result be anything but optimal? The answer seems to be that for sufficiently complex designs, there are in fact too many things that can be controlled. As a result, a realworld designer with limited time and limited resources will introduce abstractions to make the task intellectually manageable (and, if a group of designers is involved, modularizable), effectively waiving some control in favor of design efficiency.

High-level tools do the same-however, their abstractions are pervasive, consistent, enforced and checked by the tools, and often presented in the form of languages that make it difficult or impossible to break the abstractions. The ad hoc abstractions created by designers may be geared to the specific requirements of an application, but they lack all of the other benefits provided by high-level tools, and often exist only as more or less informal conventions.

The key benefits of the dataflow methodology presented in this paper are the fast design cycles (mostly through eliminating hardware synthesis from the cycle by providing a high-level simulation capability), and a model of strongly encapsulated asynchronously communicating components. Fast design cycles provide a lot of feedback for the designer and frequent opportunity for debugging and performance tuning. The design gets functional sooner, and more time can be spent on optimization.

The dataflow model of strongly encapsulated components that communicate asynchronously has a number of benefits for building complex concurrent systems. In this paper we demonstrated one: asynchronous communication makes components naturally less sensitive to the timing properties of their environment, and consequently changes in those properties are less likely to ripple through the rest of the system. A related aspect of the dataflow actor component model is that actors are very flexible with respect to their implementation. For instance, the parser might not need to run at the same speed as the rest of the decoder, as it has much less data to process. Therefore we might consider im-plementing it in software on a processor. As long as the overall throughput remains sufficient, we can be confident that this choice will not affect the functional correctness of the decoder; the thin FIFO-style interfaces through which actors communicate provide complete abstraction from the specific implementation of an actor.

The work presented in this paper is only the starting point for many potential directions of research. As we have pointed out, the implementation tools themselves provide many opportunities for improvement, involving sophisticated analyses, static scheduling of those parts of a system that can be statically scheduled, crossactor optimizations, folding, and other program transformations and refactorings such as automatic multichannelization (i.e. multiplexing the same design for multiple streams of data). Constructing efficient software code generation for Cal (such as the one in [START_REF] Roquier | Automatic software synthesis of dataflow program: an MPEG-4 Simple Profile decoder case study[END_REF]), and combining it with the RTL generation to build families of hardware/software systems from one common source is another direction of work, as is the construction of backends that translate dataflow programs to other parallel platforms, such as multi-core architectures.

Fig. 1

 1 Fig. 1 Top-level view of the MPEG decoder, depicting parser, AC/DC reconstruction, IDCT, and motion compensation.

Fig. 2

 2 Fig. 2 Basic motion compensator in an MPEG decoder.

Fig. 3

 3 Fig. 3 Motion compensator with caching.

Fig. 4

 4 Fig. 4 Motion compensator with prefetch block.

http://www.tik.ee.ethz.ch/∼moses/

http://opendf.net/

http://sourceforge.net/projects/graphiti-editor

http://opendf.net.

To simplify the discussion, we assume the DRAM is dualported, so that reading and writing to it can be treated independently.

This assumes that the frame buffer is structured by macroblocks, so that each macroblock can be read in one burst. This organization would not have made much sense previously, but with the complete prefetched search window in local storage, it can be arranged in this manner.