Christophe Lucarz
email: christophe.lucarz@epfl.ch

Jonathan Piat
email: jonathan.piat@insa-rennes.fr

Marco Mattavelli
email: marco.mattavelli@epfl.ch

Automatic Synthesis of Parsers

  L'archive ouverte pluridisciplinaire

Introduction

Video coding has changed a lot since its infancy in the early nineties. The first original MPEG video coding standard was released in 1993, and since then MPEG-2, MPEG-4 and AVC (Advanced Video Coding) have been produced and SVC (Scalable Video Coding) has been recently standardized. Each successive codec released by MPEG has been substantially more complex than the last, typically yielding twice the compression performance of its predecessor. Because of this growing complexity, the textual specification of recent standards (since MPEG-4) has lost its normative role, being replaced by the reference software implementation as the true normative specification. However, while this normative specification (typically in generic C or C++) is very precise, it presents a number of limitations. Large portions of compression technology (i.e. coding tools) are common across all MPEG standards, yet there is no direct way to recognize or exploit this commonality. Additionally, the sequential C/C++ descriptions do not expose the potential parallelism that is intrinsic to the algorithms constituting the codecs. They have also become excessively large (in terms of code size), making it extremely time consuming to transform the sequential reference software into a VHDL implementation or to map it onto a multicore platform. In other words, the complex sequential C/C++ specifications no longer constitute a good starting point for the implementation processes of standard video codecs on current and future platforms. The challenge taken by the Reconfigurable Video Coding (RVC) framework currently under its final standardization stage by MPEG is to provide a high level specification model for direct and efficient software and hardware synthesis.

Non Normative

Fig. 1 The Reconfigurable Video Coding framework

Essential concepts in RVC

The essential concepts of the RVC framework are the following:

• RVC-CAL [START_REF]MPEG systems technologies -Part 4: Codec Configuration Representation[END_REF] , a subset of the CAL data flow language [START_REF] Eker | CAL Language Report[END_REF] for describing the Functional Unit. This language defines the behavior of dataflow components called actors, which is a modular component that encapsulates its own state such that an actor can neither read nor modify the state of any other actor. The only interaction between actors is via messages (known in CAL as tokens) which flow from an output of one actor to an input of another. The behavior of an actor is defined in terms of a set of atomic actions. The execution inside an actor is purely sequential: at any point in time, only one action can be active inside an actor. An action can consume (read) tokens, modify the internal state of the actor, produce tokens, and interact with the underlying platform on which the actor is running. • FNL (Functional Unit Network Language) [START_REF]MPEG systems technologies -Part 4: Codec Configuration Representation[END_REF], a language describes the video codec configurations. FNL is a XML dialect that lists the FUs composing the codec, the parametrization of these FUs and the connections between the FUs. FNL allows hierarchical constructions: an FU can be defined as a composition of other FUs and described by another FND (FU Network Description). • BSDL (Bitstream Syntax Description Language) [START_REF]International Standard ISO/IEC FDIS 23001-5, MPEG systems technologies -Part 5: Bitstream Syntax Description Language (BSDL)[END_REF], a language for describing the structure of the input bitstream. BSDL is a XML dialect that lists the sequence of the syntax elements with possible conditioning on the presence of the elements, according to the value of previously decoded elements. BSDL is further explained in section 2. • A library of video coding tools [START_REF]MPEG video technologies -Part 4: Video tool library[END_REF], also called Functional Units (FU) covering all MPEG standards (the "MPEG Toolbox"). This library is specified and provided using RVC-CAL (a subset of the original CAL language) as specification language for each FU. • An "Abstract Decoder Model" (ADM) is constituted by the instantiation of a codec configuration (described using FNL) and the MPEG Toolbox. Figure 1 depicts the process of instantiating an "abstract decoder model" in RVC. • Tools capable to verify and validate the behavior of the Abstract Decoder Model (Open DataFlow environment [START_REF]Open DataFlow Sourceforge Project[END_REF]). • Tools capable to generate automatically software and hardware descriptions of the Abstract Decoder Model

Definition of the problem

The RVC framework aims at supporting the development of new MPEG standard and new decoding solutions. The flexibility offered by the standard video coding library to explore rapidly the design space is primordial. Defining coding tools and their interconnections becomes a relatively easy task if compared to the efforts in rewriting (very large) monolithic software specifications. However, testing new decoding solutions, new algorithms for new coding tools, or new tools configurations, the bitstream syntax may change from a solution to another. The consequence is that a new parser needs to be rewritten for each new bitstream syntax. The parser FU is the most complex actor in the MPEG-4 Simple Profile decoder [6] described in [START_REF] Lucarz | Reconfigurable Media Coding: A New Specification Model for Multimedia Coders[END_REF] and its behavior needs to be validated with all possible conforming bitstreams. Validating the parser behavior and the BSDL schema by hand become very burdensome tasks. Moreover, it is certainly not a good idea to have to write it by hand when a systematic solution for deriving such parsing procedure from the BSDL schema itself can be developed. Such procedure based on transforming the BSDL schema by a Extensible Stylesheet Language (XSL) Transformation is described in the second part of the paper. But being able to validate a bitstream description (written by hand or automatically generated) must be a preliminary step and is described in the first part of the paper. The paper is organized as follows: section 2 gives an overview of BSDL. Section 3 describes a procedure for the validation of BSDL schemas. Section 4 reports how it is possible to automatically generate a parser in a form compatible with the Abstract Decoder Model from a BSDL schema by using standard tools (i.e. XSL Transformation). Section 5 concludes the paper.

2 BSDL, a language to define bitstream syntaxes MPEG-B Part 5 is an ISO/IEC international standard that specifies BSDL [START_REF]International Standard ISO/IEC FDIS 23001-5, MPEG systems technologies -Part 5: Bitstream Syntax Description Language (BSDL)[END_REF] (Bitstream Syntax Description Language), a XML dialect describing generic bitstream syntaxes. In the field of video coding, the bitstream description in BSDL of MPEG-4 AVC [6] bitstreams represents all the possible structures of the bitstream which conforms to MPEG-4 AVC. A Binary Syntax Description (BSD) is one unique instance of the BSDL description. It represents a single MPEG-4 AVC encoded bitstream: it is no longer a BSDL schema but a XML file showing the data of the bitstream. Figure 2(a) shows a BSD associated to the corresponding BSDL schema shown in Figure 2(b).

<NALUnit> <startCode>00000001</startCode> <forbidden0bit>0</forbidden0bit> <nalReference>3</nalReference> <nalUnitType>20</nalUnitType> <payload>5 100</payload> </NALUnit> <NALUnit> <startCode>00000001</startCode> <!--and so on... --> </NALUnit>
(a) Bitstream Syntax Description (BSD) fragment of an MPEG-4 AVC bitstream <element name="NALUnit" bs2:ifNext="00000001"> <xsd:sequence> <xsd:element name="startCode" type="avc:hex4" fixed="00000001"/> <xsd:element name="nalUnit" type="avc:NALUnitType"/> <xsd:element ref="payload"/> </xsd:sequence> <!--Type of NALUnitType --> <xsd:complexType name="NALUnitType"> <xsd:sequence> <xsd:element name="forbidden_zero_bit" type="bs1:b1" fixed="0"/> <xsd:element name="nal_ref_idc" type="bs1:b2"/> <xsd:element name="nal_unit_type" type="bs1:b5"/> </xsd:sequence> </xsd:complexType> <xsd:element name="payload" type="bs1:byteRange"/> (b) BS schema fragment of MPEG-4 AVC codec Fig. 2 A BSD and its corresponding bitstream schema is BSDL An encoded video bitstream is described as a sequence of binary elements of syntax of different lengths: some elements contain a single bit, while others contain many bits.

The Bitstream Schema (in BSDL) indicates the length of these binary elements in a human and machine-readable format (hexadecimal, integers, strings . . . ). For example, hexadecimal values are used for start codes as shown in Figure 2(a). The XML formalism allows organizing the description of the bitstream in a hierarchical structure. The Bitstream Schema (in BSDL) can be specified at different levels of granularity. It can be fully customized to the application requirements [START_REF] Thomas-Kerr | Reconfigurable Media Coding: Self-Describing Multimedia Bistreams[END_REF]. BSDL was originally conceived and designed to enable adaptation of scalable multimedia contents in a format-independent manner [START_REF] Thomas-Kerr | Is That a Fish in Your Ear? A Universal Metalanguage for Multimedia[END_REF]. In the RVC framework, BSDL is used to fully describe video bitstreams. Thus, BSDL schemas must specify all the elements of syntax, i.e. at a low level of granularity. Before the use of BSDL in RVC, the existing BSDL descriptions described scalable contents at a high level of granularity. Figure 2(a) is an example BSDL description for video in MPEG-4 AVC format.

The choice of a language to describe the syntax of the bitstream has been firstly discussed in [START_REF] Thomas-Kerr | Reconfigurable Media Coding: Self-Describing Multimedia Bistreams[END_REF]. As a result, BSDL has been preferred over Flavor and XFlavor [START_REF] Eleftheriadis | Flavor: A Language for Media Representation[END_REF][START_REF] Hong | XFlavor: bridging bits and objects in media representation[END_REF] because:

it is stable and already defined by an international standard [START_REF]International Standard ISO/IEC FDIS 23001-5, MPEG systems technologies -Part 5: Bitstream Syntax Description Language (BSDL)[END_REF]; in XFlavor, the bitstream is described with a set of classes, in the object-oriented paradigm (C++ or java). The parsing is accomplished by the C++ or Java code generated from the Flavor description. The object-oriented paradigm has not been adopted by the RVC framework. Thus, the XML-based BSDL description of the bitstreams has been chosen because it does not operate a change of paradigm within a same framework. the XML-based description of BSDL interacts better with the XML-based representation of the configuration of RVC decoders (FU Network Descriptions) and the XMLbased infrastructure of the existing tools. It makes the platform more coherent, with a same technology.

Validation of a BSDL bitstream schema

Before generating parsers from bitstream schemas, one must guarantee that the schemas are correct, i.e. the schema reflects perfectly the structure of the compressed data which is sent with. If there is no validation procedure, which guarantees that the bitstream is structured exactly as the schema describes it, the generated parser may not be able to parse the bitstream. Thus, a validation procedure is necessary. Figure 3 summarizes the overall method for the validation of bitstreams schemas. Two tools are involved in the validation of such schemas: the BintoBSD parser creates a Binary Syntax Description (BSD) from a particular bitstream and its corresponding Bitstream Schema (BS). The reference decoder implementation outputs the reference BSD, representing the right structure of the data contained in the bitstream. The validation of the BSDL schema consists in comparing the reference BSD (generated by the reference decoder implementation) and the BSD generated by the Bin-toBSD parser from the Bitstream Schema. If the two BSD are identical, it means that the bitstream follows correctly the schema under evaluation. If this procedure is repeated on a set of input bitstreams which cover the whole BSDL schema, the schema is considered as correct.

The case of unsized elements of syntax

In many cases, the size in bits of a syntax element is not known neither at compile-time nor at run-time (e.g. Variable Length Codes). The size in bits of the syntax element is known only during the decoding process of this syntax element. The validation process implies the generation of a BSD from a given bitstream: it means at least the determination of the size of every syntax element. For the elements whose size is known a priori, generating the BSD is straightforward. But for the elements whose size is not known a priori, a parsing algorithm must be implemented in order to determine the size of the elements of syntax. For the validation process, these parsing algorithms are written in Javascript and are linked to the bitstream schema (in BSDL) by means of the bs1:codec and bs1:script BSDL constructs. Data types with the attribute bs1:codec in a bitstream schema are decoded using ECMAScript and the implementation is embedded in the bitstream schema via the bs1:script BSDL construct. It allows parsing algorithms to be specified in a bitstream schema and used by BintoBSD, enabling the processing of data structures that cannot be specified with BSDL constructs. Figure 4(a) shows an example of declaration of an user-defined element ("expGolomb") for which a Javascript parsing algorithm is necessary for decoding it. The code of the parsing algorithm in Javascript decoding the "ExpGolomb" syntax element is provided in figure 4(b).

The BintoBSD tool searches the bs1:script element, class or file (respectively) for a function (or method) with the signature BintoBSD(). The tool calls this script to generate the element value to which the bs1:codec attribute is attached. BintoBSD() function returns a string containing the lexical value of the element and modifies the Xpath variables contained in the BS schema -Xpath is standardized as an extended feature in [START_REF]International Standard ISO/IEC FDIS 23001-5, MPEG systems technologies -Part 5: Bitstream Syntax Description Language (BSDL)[END_REF]. The number of bits of the elements is consumed and the process of generation of the BS description can continue. Entropic decoders such as CAVLC and CABAC in MPEG4-AVC requires some contextual values from the already decoded macroblocks. Implementation of BintoBSD provide the ECMAScript with functions allowing to:

evaluate Xpath expression inside the BS schema, evaluate Xpath expression inside the outputted BS description, modify Xpath variable values. The bs1:script component defines the local name of the datatype, which inherits the target namespace of the schema document. The bs1:codec attribute can then reference this implementation via the URI of the datatype, which is obtained by adding the appending the local name as fragment identifier to the namespace.

For instance, ECMAScript datatypes may be used to allow a BSDL parser to process Variable Length Codes, such as Huffman codes or Arithmetic-coded values (Figure 4(b)). An ECMAScript implementation may be referenced by bs1:codec in the following ways:

the value of bs1:codec is a URL that resolves to a Bitstream Schema, with a fragment identifier corresponding to the value of an id attribute on a bs1:script element; the value of bs1:codec is a URL that resolves to an ECMAScript file, with a fragment identifier corresponding to the name of a class within that file; the value of bs1:codec is a URL that resolves to an ECMAScript file, with no fragment identifier.

Synthesis of parsers from a bitstream description

The bitstream structure is described in BSDL, a XML dialect (section 2). The bitstream needs first be validated (section 3). XSL Transformation is a language used for the transformation of XML documents into other XML documents. CAL can be also represented in a XML format: CALML. Thus, XSL Transformations are perfectly adapted to convert a bitstream schema written in BSDL into a parser in CALML. The difficulty of the transformation remains in the fact that a description (the schema) is converted into an executable: the bitstream schema (in BSDL) describes in the XML formalism the sequence of syntax elements constituting the bitstream. There is no indication on how to parse them. The parser is an executable that processes these elements of syntax. It is very difficult to make the transformations sufficiently flexible such as the resulting executable (the parser) allows all the combinations of the BSDL constructs constituting the schema.

Furthermore, the generated CALML code can be used as an input to the hardware and software code generators [START_REF] Janneck | Translating Dataflow Programs to Efficient Hardware: an MPEG-4 Simple Profile Decoder Case Study[END_REF][START_REF] Wipliez | Code generation for the MPEG reconfigurable video coding framework: from CAL actions to C functions[END_REF]. Thus, direct synthesis of the parser into hardware or software implementations can be performed.

Figure 5 illustrates the different steps of the XSL Transformation process. The BSDL to CALML transformation is composed of four main steps. At each step of the process, the BSDL schema is traversed and only some parts are transformed according to the step. For the step 1, 2, 3' and 4, CALML templates are used to create the final CALML parser. These templates are filled according to each syntax element.

The first step in the transformation is the creation of the header of the parser actor in CALML. It consists of adding constant values, initialized variables, input and output ports and the signature of the actor.

The second step is the creation of the actions for each syntax element of the BSDL schema. One or several actions can be created for each syntax element. Follows an nonexhaustive list of cases:

-If the syntax element is simple (fixed sized element, without any condition on its existence), only one action is created -If the syntax element has some condition on its existence, three actions will be created: the first action tests if this element exists, the second action consumes the tokens relative to this syntax element and the third action is created for jumping to the next syntax in case of this element does not exists. -If the syntax element must be repeated several times, three actions are created. An action is needed to check if this element needs to be repeated, an action which consumes the token of the syntax element and an action which is used to jump to the next syntax in case of the element must be not repeated anymore. -If the parser actor needs to communicate with an external actor to parse this syntax element, then several actions are created for establishing a communication protocol between these two actors (see section 4.1).

The third step consists of building the Finite State Machine (FSM) of the final CALML parser. A preliminary sub-step is performed in order to build an intermediate tree which is a more convenient representation of the initial tree so that it is then easier to perform the transformation for building the FSM. It consists of having a flatten representation of the relations between all the actions in order to have a better view on how the actions follows from each others.

Finally, the last step is to set the priorities between actions in case where they are more than one fireable actions at a given state of the actor.

Figure 6 shows a very simple example of BSDL description. The bitstream is composed of four elements: the first element is a 1-bit long element and is output on port A of the parser. The second element is 2-bits long and output on port B, third element is 3-bits long and output on part C and the fourth element is 4-bits long and output on port D. Figure 7 shows the example of CALML code generated for decoding the first syntax element. Figure 8 illustrates how the scheduling of the actions inside the parser.

<xsd:element name="bitstream_root"> <xsd:complexType> <xsd:sequence> <xsd:element name="firstelement" type="bs1:b1" rvc:port="A"/> <xsd:element name="secondelement" type="bs1:b2" rvc:port="B"/> <xsd:element name="thirdelement" type="bs1:b3" rvc:port="C"/> <xsd:element name="fourthelement" type="bs1:b4" rvc:port="D" /> </xsd:sequence> </xsd:complexType> </xsd:element> Fig. 6 Simple example of BSDL description.

<Action>

<QID name="firstelement.read"> <ID name="firstelement"/> <ID name="read"/> </QID> <Input kind="Elements" port="bitstream"> <Decl kind="Input" name="b"/> <Repeat> <Expr kind="Var" name="BS1_B1_LENGTH"/> </Repeat> </Input> <Output port="A"> <Expr kind="Var" name="b"/> <Repeat> <Expr kind="Var" name="BS1_B1_LENGTH"/> </Repeat> </Output> </Action> Fig. 7 Example of source code: action for decoding "firstelement" syntax element.

The case of unsized elements of syntax

As seen in the previous section, the parser is not only a simple actor that "demultiplexe" the raw data contained in the bitstream but runs also some parsing algorithms to decode some part of it. Unfortunately, automatizing the generation of these algorithms in CAL is <Schedule kind="fsm" initial-state="root.firstelement_exists"> <Transition from="root.firstelement_exists" to="root.secondelement_exists"> <ActionTags> <QID name="firstelement.read"> <ID name="firstelement"/> <ID name="read"/> </QID> </ActionTags> </Transition > <Transition from="root.secondelement_exists" to="root.thirdelement_exists"> <ActionTags> <QID name="secondelement.read"> <ID name="secondelement"/> <ID name="read"/> </QID> </ActionTags> </Transition > [...] </Schedule> Fig. 8 Example of source code: Finite State Machine of the parser challenging because the bitstream schema is only a list of elements of syntax contained in the bitstream and does not indicate how to decode them. With such purpose in mind a mechanism has been set up in order to establish a communication between the parser and external FUs which will decode these parts of the bitstream. It is the case when decoding Variable Length Codes (VLC). Figure 9 illustrates the idea.

Fig. 9 The data flow connections between the VLD table implemented as a Functional Unit and the parser.

During the validation phase, these algorithms were implemented in Javascript. In the code generation phase, these algorithms are implemented in FUs written in CAL. Currently, these FUs are not generated automatically and must be written manually.. However, in case of the Variable Length Decoding, a systematic procedure has been established in order to generate a part of these FUs in CAL from the VLD tables. The reader can refer to [START_REF] Li | Efficient Data Flow Variable Length Decoding Implementation For The Mpeg Reconfigurable Video Coding Framework[END_REF] for further details.

A communication protocol has been set up in the parser in order to communicate with the external FU capable of decoding the unsized elements of syntax. Each time a syntax element is met by the parser, the parser fires a xxxx.read action. When the parser meets a unsized syntax element (e.g. variable length codes), the parser fires a set of actions which are necessary to communicate with the external Functional Units: xxxx.read to read the bit from the input port and to send the bit the the FU implementing the parsing algorithm, and xxxx.finished / xxxx.notfinished to decide if the parsing algorithm is finished or not and if the parser must send an additional bit. An example of code is shown on figure 10. The example illustrates the case of Variable Length Decoding.

Conclusion

Syntax parsing is a complex part in the video coding technology. Its complexity derive from the fact that the bitstream is composed of a large number of elements of syntax. The presence of some elements is conditioned by the value of other elements of syntax previously decoded. Writing a parser each time the syntax of the bitstream changes is a burdensome tasks for designers. It is often the case when developing new standards and new coding tools within MPEG. Thus, this paper presented a solution to the problem based on a systematic methodology for the validation of bitstream schemas (in BSDL) describing the syntax of bitstreams. The paper emphases a proof of concept of the methodology -starting from the validation of the BSDL schema and the automatic generation of CALML parsers -based on fully tested and proven standards (BSDL, XSL Transformation. . . ). After these two stages (validation and generation), the CALML parser needs to be transformed in CAL form in order to be integrated with the Abstract Decoder Model within the MPEG Reconfigurable Video Coding (RVC) framework. <Action> <QID name="dct_dc_size_L.read"> <ID name="dct_dc_size_L"/> <ID name="read"/> </QID> <Input kind="Elements" port="bitstream"> <Decl kind="Input" name="b"/> </Input> <Output port="size_L"> <Expr kind="Var" name="b"/> </Output> <Stmt kind="Assign" name="bit_number"> <Expr kind="BinOpSeq"> <Expr kind="Var" name="bit_number"/> <Op name="+"/> <Expr kind="Literal" literal-kind="Integer" value="1"/> </Expr> </Stmt> </Action> <Action> <QID name="dct_dc_size_L.notFinished"> <ID name="dct_dc_size_L"/> <ID name="notFinished"/> </QID> <Input kind="Elements" port="size_L_f"> <Decl kind="Input" name="f"/> </Input> <Guards> <Expr kind="BinOpSeq"> <Expr kind="Var" name="f"/> <Op name="="/> <Expr kind="Literal" literal-kind="Integer" value="0"/> </Expr> </Guards> </Action> <Action> <QID name="dct_dc_size_L.finish"> <ID name="dct_dc_size_L"/> <ID name="finish"/> </QID> <Input kind="Elements" port="size_L_f"> <Decl kind="Input" name="f"/> </Input> <Input kind="Elements" port="size_L_data"> <Decl kind="Input" name="data"/> </Input> <Guards> <Expr kind="BinOpSeq"> <Expr kind="Var" name="f"/> <Op name="="/> <Expr kind="Literal" literal-kind="Integer" value="1"/> </Expr> </Guards> <Stmt kind="Assign" name="dct_dc_size_L"> <Expr kind="Var" name="data"/> </Stmt> </Action> [...] <Transition from="dct_dc_size_L1_exists" to="dct_dc_size_L1_result"> <ActionTags> <QID name="dct_dc_size_L.read"> <ID name="dct_dc_size_L"/> <ID name="read"/> </QID> </ActionTags> </Transition> <Transition from="dct_dc_size_L1_result" to="dct_dc_size_L1_exists"> <ActionTags> <QID name="dct_dc_size_L.notFinished"> <ID name="dct_dc_size_L"/> <ID name="notFinished"/> </QID> </ActionTags> </Transition> <Transition from="dct_dc_size_L1_result" to="next syntax element"> <ActionTags> <QID name="dct_dc_size_L.finish"> <ID name="dct_dc_size_L"/> <ID name="finish"/> </QID> </ActionTags> </Transition> Fig. 10 Example of generated code in case of unsized syntax element

Fig. 3

 3 Fig. 3 Illustration of the Bitstream Schema validation procedure

Fig. 4

 4 Fig.4Call and example of a parsing algorithm in Javascript

Fig. 5

 5 Fig. 5 Block diagram of the XSL Transformation process.


Matthieu Wipliez
email: matthieu.wipliez@insa-rennes.fr

Ghislain Roquier
email: ghislain.roquier@epfl.ch

Jean François Nezan

Jean-Franc ¸ois Nezan
email: jean-francois.nezan@insa-rennes.fr

Keywords: Reconfigurable Video Coding, CAL actor language, dataflow programming, software code generation

Introduction

Processor frequencies no longer double every two years as predicted by Moore's law. Multicore architectures are now being proposed so that computational power keeps increasing. The main issue of this approach is that standard programming languages (C, C++, . . . ) are sequential and not suitable for parallel multicore architectures. The dataflow programming concept consists of describing an application with a directed graph where edges represent the flow of data between operations. Dataflow programming highlights the potential parallelism of the application, which can be used to distribute calculations over available cores.

MPEG is currently working on the development of the RVC standard. The key concept behind this project is to describe decoders using dataflow graphs: RVC provides a high-level description of the MPEG standard written in a specific language called RVC-CAL. Appropriate tools must implement the design flow and provide the optimization steps necessary for efficient implementations. Uniprocessor software code generation must be addressed before considering more complex implementations (multicore or hardware/software co-design). This paper presents a nonnormative (in terms of relation with the RVC standard) software code generator called Cal2C that from a dataflow program generates C code and an associated SystemC model. We show that the algorithm described with RVC-CAL can be automatically transformed, compiled and executed efficiently on a uniprocessor system.

The paper is organized as follows: Section 2 presents dataflow programming within the RVC-CAL environment. Section 3 describes the Cal2C software code generator. Results obtained with Cal2C are shown in section 4. Section 5 outlines perspectives of future work, while we conclude in section 6.

2 Dataflow programming for RVC RVC aims at providing a system-level specification for existing and future MPEG standards [START_REF] Lucarz | Reconfigurable Media Coding: a new specification model for multimedia coders[END_REF]. In RVC, an abstract video decoder is built as a block diagram in which blocks define processing entities, indifferently called actors or Functional Units (FUs), and connections represent the data flow between actors. RVC provides both a normative standard library of FUs described with the RVC-CAL language, and a set of decoder descriptions expressed as networks of FUs using the FU Network Language (FNL).

RVC-CAL is a subset of the CAL Actor Language (CAL) normalized as a part of the RVC standard. It restricts the datatypes, operators, and features that can be used when describing an FU. CAL [START_REF] Eker | CAL Language Report[END_REF] is an actor-oriented language created as part of the Ptolemy project [START_REF] Eker | Taming heterogeneity-the Ptolemy approach[END_REF], a Java framework that supports heterogeneous modeling, simulation, and design of concurrent dataflow systems made of actors.

FNL is an XML dialect with which networks can be described. FNL is based on a format used in the Open Dataflow environment 1 and standardized by MPEG. FNL supports local variable declarations, instantiation of blocks with parameters, and hierarchy: Blocks can be FUs or networks. Contrarily to other languages supported by OpenDF, FNL cannot create networks programmatically (e.g. with for loops).

RVC-CAL language

An RVC-CAL actor is a modular component that encapsulates its own state. It can neither access nor modify the state of any other actor. An actor performs computation as a sequence of atomic steps called firings. During a firing, computation is done by one action, chosen among the several actions an actor may have. An action defines the amount of tokens consumed on the input, may change the actor state, and may output tokens using a function of inputs tokens and actor state.

Figure 1 shows an actor A that makes use of both functional and imperative features of RVC-CAL to extract red, green, blue components and luminance out of a pixel where colors are packed together. The actor has a parameter COMPUTE Y that states whether luminance should be computed, and several constants that contains the masks and shift offsets for the different components. Actor A's single anonymous action requires COUNT tokens on the PIX input port to fire.

The body of an action is the same as a procedure's body in most imperative programming languages. Variables may be declared and initialized before any statement. Statements may be conditionals (if/then/else), loops (for/while), calls to functions and procedures, and assignments to local and state variables, either scalar or array. The language is strictly structured, in the sense that gotos are not allowed. Similarly it is not possible to break, to continue or to return a value. Needless to say, an actor cannot exit either.

RVC-CAL also borrows from functional programming. For instance pure (side-effect free) functions are distinct from imperative procedures. The expressions that can be written in conditions and in the right-hand side of assignments resemble what is found in functional languages. They include if/then/else conditional expressions as well as generators. A generator is a kind of inline for loop that creates a list whose members are described by an expression.

The differences that are most significant between CAL and RVC-CAL are: (1) RVC-CAL supports only six types, which are divided into four primitive types (bool, float, int, uint) and two extended types (List, String) (2) all variables must be typed, this means that integers, signed or not, must have a size, and lists must be declared with the type of their elements and their maximum size (3) type parameters (called generics in Java or templates in C++) such as T in actor A [T] must not be used in type expressions such as List[T] (4) advanced features of CAL are prohibited, such as channel selectors and multi-ports, or lambda-functions.

For instance CAL allows developers to use λexpressions. An example of a λ -expression is f (x, y) = x+y, where f can be evaluated partially: We can write g = f (5), which is equivalent to declare g(y) = 5 + y. Compilers for languages that support λ -expressions must use closures made of the code of the expression and a set of variables and their values at the time the closure is created. Hardware synthesis of programs written in a functional language is easier if the language is restricted, especially if closures are forbidden [START_REF] Frankau | Stream processing hardware from functional language specifications[END_REF]. Indeed, closures require dynamic memory allocation in the general case, something which is trivial in a software environment but requires a heavy machinery with hardware [START_REF] Séméria | Resolution of dynamic memory allocation and pointers for the behavioral synthesis from c[END_REF].

Semantics

In this document, we use the following conventions: a designates an action and the set of all actions inside an actor is written A. In the actor A of Figure 2, A equals to the set {a.x, a.y, b, c}. Actions may be tagged. A tag is a non-empty list of identifiers separated by colons. The tag of an action a is written t a . |t a | denotes the length of t a . The empty tag ε verifies |ε| = 0. The set of non-empty tags of an actor is denoted T . There is a prefix relation, noted , between tags: t t means that t is a prefix of t . For instance with tags a and a.x from actor A shown in Figure 2, we have a a.x and a a. A set of actions that start with the same tag as an action a is described as follows:

ta = {a x ∈ A| t a t a x } (1)
An action may have firing conditions, called guards, where the action firing depends on the values of input tokens or the current state. When an actor fires, an action has to be selected based on the number and values of tokens available and whether the guard is true. Action selection may be further constrained using a Finite State Machine (FSM), to select actions according to the current state, and priority inequalities, to impose a partial order among action tags. An FSM is defined by the triple (S, s 0 , δ ) where S is the set of states, s 0 ∈ S is the initial state, and δ is the state-transition function: δ : S × T → S. Note that a state transition allows a set of actions obtained with t from equation 1 to be fireable. Priorities have the form t 1 > t 2 . These inequalities induce a binary relation on the actions as follows:

a 1 > a 2 ⇔ ∃ t 1 ,t 2 : t 1 > t 2 ∧ a 1 ∈ t1 ∧ a 2 ∈ t2 ∨ ∃ a 3 : a 1 > a 3 ∧ a 3 > a 2 (2)
FNL and RVC-CAL are expressive enough to create dataflow programs that follow a variety of computation models which differ by the trade-off they offer between expressive power and analyzability [START_REF] Eker | Taming heterogeneity-the Ptolemy approach[END_REF]. A network can be executed with the Synchronous Dataflow (SDF) model [START_REF] Lee | Static scheduling of synchronous data flow programs for digital signal processing[END_REF] if all actions inside an actor have the same token rates and at least one action may fire when actor is executed.

An important property of the SDF model is that liveness and boundedness can be decided at compile-time. Actors can be scheduled statically at compile-time and the memory requirement may be fixed a priori.

If actors contain state-and/or data-dependent firing conditions (called dynamic actors for short), then Dataflow Process Networks (DPN) [START_REF] Lee | Dataflow Process Networks[END_REF] must be used. A DPN contains actors that communicate with each other using unidirectional FIFOs, where reads are blocking and writes are nonblocking. Contrarily to Kahn processes [START_REF] Kahn | The semantics of a simple language for parallel programming[END_REF], actors may test an input for the absence of data. DPNs must be scheduled dynamically, hence actors are scheduled at runtime by an actor scheduler.

Each time an actor is scheduled, if the input tokens available and the actor state allow it, an action is fired. Testing an action's fireability is done by an action scheduler according to Algorithm 1, which is a reformulation of the conditions to fire an action as described in the CAL Language Report [START_REF] Eker | CAL Language Report[END_REF].

Algorithm 1 selects an action as follows. If the actor has a Finite State Machine (FSM), the set of eligible actions at runtime is found by Algorithm 2, otherwise the set equals A. The subset of eligible actions for which the is activable(a) function is true form the activated set. This function returns true if there are enough tokens to execute action a and the guard of action a evaluates to true. The set of fireable actions is computed by Algorithm 3 as the set of activated actions with a priority greater or equal to the priority of all other actions. Finally, the action selected to fire is any fireable action.

Input: A, δ , current state Data: eligible, activated, fireable Output: action selected if actor has an FSM schedule then 1 eligible ← select eligible(A, δ , current state); Algorithm 2 founds the set of eligible actions. This set contains the actions that can be fired according to the FSM and the current state, in addition to all anonymous actions. This allows high priority anonymous actions to run outside an FSM whenever needed and can be used when one wishes to execute a given action from different states without changing state and without writing transitions.

With proper data structures, the set of transitions is computed by select eligible in O(1), and if the subsets a ∈ t have been pre-computed at compile-time the eligible actions are found in O(n) on the order of transitions.

fireable ← {a 1 ∈ activated | ∀ a 2 ∈ activated, a 1 ≥ a 2 }; 1 Algorithm 3: select fireable 2.

Motivations and issues for software code generation

The main motivation for a software code generator for RVC-CAL was that there did not exist one even though it is necessary for successful development with the language. Cal2HDL [START_REF] Janneck | Synthesizing hardware from dataflow programs: An mpeg-4 simple profile decoder case study[END_REF] is able to generate high-speed VHDL from CAL, but this is far from an ideal solution for two reasons.

On the one hand synthesis time is too long when developing an application. Simulation is an answer, but it runs very slowly, which increases development time. A software code generator is somewhere in-between by generating reasonably fast code in a reasonable amount of time. On the other hand the VHDL language is used as a description language for programmable logic such as FPGAs, and FPGAs are typically used as coprocessors to speed up repetitive computations. A software code generator is thus also necessary to obtain the software part of mixed hardware/software programs from RVC-CAL.

Translating actors and networks to software raises a number of issues. Contrarily to hardware code generation, having one thread per action in a software code is not efficient. FPGAs can execute several pieces of code in a truly parallel manner. Multi-core processors also provide true parallelism to a lesser extent, but it comes at a far higher cost because of the necessary synchronizations between cores. To lower the impact of this cost the pieces of code executed at the same time must be large enough, yet data dependencies limit the amount of available parallelism.

Cal2C software code generator

Cal2C is open-source software under a BSD-like license programmed in Objective Caml, a functional ML-like language. Cal2C takes as input CAL actors and FNL networks and generates one C file per actor and a single C/C++ file from all the networks. We chose to use C as the target language for our software code generator because this language has become universal for software development and as a consequence there are libraries and compilers available for almost every platform. Figure 3 presents an overview of the process detailed in the following sections. A hierarchical network composed of several networks and actors is flattened, and transformed to a C/C++ actor scheduler (section 3.1). Each CAL actor is parsed to an abstract representation called Abstract Syntax Tree (AST), which is transformed by instantiation using parameters from the flat network, and translated to C (section 3.2). The structure of the code generated is discussed in section 3.3.

FNL code generation

Flattening an FNL network facilitates the actor code generation. Actors instances are renamed to ensure they have unique names, and actors are closed, which means their parameters are replaced by constant values. This has three consequences: (1) there can be a direct mapping between an actor instance and a C file generated, (2) the state variables of an actor can simply become global variables, (3) the generated code is more efficient because all uses of a parameter can be replaced by its value.

On the contrary, dealing with a hierarchical network is more complicated. Parameters have to be carried all the way through the hierarchy. The state of actors must be dynamically allocated each time an actor is instantiated, and given as a parameter to every action of the actor. The code that would be generated for a given network would be cleaner however, because there would be less code and it would be more structured. We deliberately chose to have a more efficient and cleaner code in actors at the expense of the network generated code's quality.

The flat network is used to automatically create an actor scheduler written in SystemC [START_REF]IEEE: Ieee std 1666 -2005 ieee[END_REF], a uniprocessor simulation framework. We chose SystemC because it provides us with a user-level scheduler, threads, FIFOs, and a model that closely matches ours: An actor becomes a SC MODULE, input and output ports sc ports, connections sc fifos. A restriction of SystemC compared to FNL networks is that broadcast (multiple connections from a single output port to several input ports) is not supported, so special "broadcast" actors are inserted.

The actor scheduler implements Dataflow Process Networks (DPN) semantics on top of the SystemC model. sc fifos cannot peek data, so it is necessary to add a buffer per FIFO to store the tokens peeked. Also, sc fifos have blocking reads and writes while the DPN model has nonblocking writes. Therefore, after an action is found to be fireable, the action scheduler must test whether there is enough room to store the tokens the action will produce. Note that contrarily to RVC-CAL, unrestricted CAL does not make it possible to know in advance the number of tokens that may be produced by an action. Lack of room in output ports means that writing would block, which is not allowed by DPN semantics. The action scheduler thus simply indicates that the actor cannot fire and that it must wait. At this point, SystemC's scheduler suspends the actor, and attempts to fire another one picked from the list of currently sleeping actors.

SystemC sc fifos admit a maximum size that must be specified at compile-time. FIFOs should be big enough for the network to be executed without artificially deadlocking, which occurs when an actor cannot write to a FIFO and no other actor can be fired to consume tokens from the same FIFO. With this in mind, choosing too big a size for every FIFO in the network will induce high latency and low average throughput with the current actor scheduler implementation. The user can use a default size for all FIFOs and fine-tune some particular FIFOs if necessary.

The action scheduler of each actor needs to check the presence and values of tokens on its input ports, get tokens from its input ports, and put tokens on its output ports. All these operations are dependent of the API that is used by the actor scheduler. To keep the actor code generic and actor scheduler-agnostic, actor scheduler and action scheduler exchange data through a set of well-defined functions. These functions are declared in the action scheduler and defined (implemented) by the actor scheduler. The functions have the following signatures:

-int hasTokens A i p j (int n) returns 1 if the input port p j of actor A i has at least n tokens present and 0 otherwise. -void peek A i p j (int n, T[] tokens) peeks n tokens from the port p j of actor A i and puts them into tokens. -void read A i p j (int n, T[] tokens) reads n tokens from the port p j of actor A i and puts them into tokens. -int hasRoom A i p j (int n) returns 1 if the output port p j of actor A i has room for at least n tokens and 0 otherwise. -void write A i p j (int n, T[] tokens) writes n tokens to the port p j of actor A i .

Note that the functions hasTokens, peek A i p j , and read A i p j must use a "snapshot" of the tokens available on all input ports of actor A i at a time t because the firability of all actions shall be evaluated in the exact same conditions. This is the case with our implementation of DPN using Sys-temC because we allow the scheduler to switch to another actor only when the so-called actor cannot fire. This guarantees that the state of FIFOs will not change while an action scheduler examines them.

Actor code generation

The first stage of the compilation process is to parse each CAL actor to an Abstract Syntax Tree (AST). To this end we used a LL(k) parser bundled with OCaml called Camlp4. The grammar parsed is embedded in the code where a Syntax Directed Translation generates a node for each grammar rule or group of rules. For instance a simplified version of the AST generated for the CAL statement x := if a > b then a else b end is shown in Figure 4.

After parsing the AST is modified when the actor is instantiated. Instantiation closes the actor i.e. it removes its parameters and replaces them by local variable declarations whose values are specified in the parent network. The next step is a series of transformations to the AST. The first one is type checking. It begins by annotating every expression in the AST with the type found according to the inference rules of the type system. An inference rule has the general form:

Γ P Γ expr : t (3)
It is read as follows: under the assumptions about the types of the variables in Γ , if the premises P are true, then the expression expr is well-typed and has type t. If an expression cannot be typed it is invalid according to the type system and it is not possible to generate code for the actor. If all expressions are well-typed, Cal2C checks that expressions assigned to variables have types that are compatible with the types of the so-called variables. If this is not the case, then compilation stops.

Once the AST is proven to be correctly typed, we apply a constant propagation algorithm. Such an algorithm is able to find values that are constant for all executions and propagate them through the program. Constant propagation is necessary to ensure a successful compilation of the C code. Variables of an actor can be initialized from the initial value of other variables of the actor, especially the variables initialized from parameters that are also variable declarations at this stage. Actor variables are translated to C global declarations, but in C global declarations cannot reference other global variables, even if they are constant. Propagating those constants solves the problem.

The last transformation converts the typed CAL AST to an Intermediate Representation closer to C. To our knowledge, CIL [START_REF] Necula | CIL: An Infrastructure for C Program Analysis and Transformation[END_REF] (C Intermediate Language) is the framework that is best-suited for our purpose because it has a robust Intermediate Representation and the code it generates is a lot more readable than what SUIF [START_REF] Wilson | Suif: An infrastructure for research on parallelizing and optimizing compilers[END_REF] or LLVM [START_REF] Lattner | LLVM: A Compilation Framework for Lifelong Program Analysis & Transformation[END_REF] can generate. Before converting CAL to CIL names of variables, actions, etc. must be altered to be valid C identifiers. Some characters that are allowed in CAL identifiers but not in C (for instance '.' or '$') must be replaced. After that, Cal2C transforms CAL functional expressions into CIL imperative constructs: ifs for if-then-else expressions, for loops for list generators. In the process temporary variables are created to hold temporary results in compound expressions. Figure 5 presents the CIL representation obtained from the CAL AST shown in Figure 4. C code is obtained by calling the pretty-printer of the CIL API on the CIL tree. Fig. 5 CIL AST obtained from the CAL AST of Figure 4 3.3 Structure of the code generated for an actor As shown in Figure 3 the code generated for actions is separated from the code generated for the action scheduler. Each action becomes a functionally equivalent C function, and the action scheduler is implemented in yet another function. The rationale for separating actions from the action scheduler is two-folded: (1) the generated code is smaller than if the code for actions were generated inside the action scheduler, because actions may be referenced several times in a Finite State Machine (2) the generated code is easier to read because it has a structure similar to the original CAL code. Additionally, this does not impact performance because an optimizing compiler will automatically inline small-enough functions. Figure 6 shows how the a.x action of actor A detailed in Figure 2 is translated to C. The function wears a name deduced from the CAL name with respect to the rules defined in section 3.2, i.e. the dot in a.x is replaced with an underscore. The function starts by reading tokens from the ports it uses, and puts them into local arrays. The function then executes the C equivalent of the CAL action body and finally writes tokens to output ports.

The action scheduler for an actor A is a function A scheduler() called every time an actor fires. This function is an implementation of Algorithm 1 described in section 2.2 that selects a fireable action if input tokens and actor state allow it. Because action scheduler functions are virtually called all the time during the execution of a network, it is crucial they be as fast as possible.

The following describes how to generate optimal code to compute the different steps of Algorithm 1. The implementation of select eligible(A) is detailed in section 3.5. This function selects the actions eligible according to the current FSM, or every action if the actor has no FSM. is activable(a) is translated to C conditions that are evaluated at runtime each time the action scheduler is run, and are true if [START_REF] Conchon | Designing a generic graph library using ML functors[END_REF] there are enough tokens to execute action a and (2) the guard of action a evaluates to true. Testing the number and values of tokens on port j of actor i is done by calling the functions from the actor scheduler presented in section 3.1, hasTokens A i p j and peek A i p j . The last step is finding the fireable actions, i.e. the actions in activated with the highest priority. This is done by the select fireable function described in section 3.4.

Computing select fireable at compile-time

Computing the set of fireable actions can be done in the generated code with if-then-else statements by sorting actions by priority at compile time. To this end a total order of priorities is obtained from the partial order priority relations by topologically sorting a Directed Acyclic Graph (DAG) created by Algorithm 4.

Algorithm 4 works on a directed graph G = (V, E) where V ⊆ T is the set of vertices and E ⊆ V 2 is the set of edges. A vertex is a tag involved in a priority relation. An edge from source to target is equivalent to the priority relation source > target. The graph G is initially filled from the priority relations. The second for loop iterates over each tag t a present in the graph. If there exists in the graph a tag t a that is the longest strict prefix of t a , the algorithm adds edges between the predecessors of t a and the tag t a and between the tag t a and the successors of t a .

Figure 7 presents the initial graph created from the priorities of the sample actor given in Figure 2 after the first step of Algorithm 4 and the final graph after the second step of the algorithm. The final graph is sorted by topological order that gives a total order from the priorities that were stated: In the translation of an FSM (S, s 0 , δ ), the set of states S becomes a C enum filled with the states. State names are modified to provide valid C identifiers. Cal2C creates a switch statements with as many cases as there are states; they are labeled with created identifiers. The current state is available through an integer variable named state whose range is the enum.state is initialized to the initial state s 0 .

Input: priorities Output: G = (V, E) as a DAG V ← / 0; 1 E ← / 0; 2 //
Each triple (s f ,t a i , s t ) of the state transition function δ is transformed as follows. Inside the case s f , the set of eligible actions is defined as

eligible = n i=1 ta i (4)
As explained in section 3.4, actions of eligible are sorted by priority and translated to if-then-else statements. The statetransition is done by an assignment state = s t ; added at the end of each then branch. As an example, the translation of the FSM of the actor of Figure 2 is presented on Figure 8. Cal2C is able to successfully translate two different MPEG-4 Simple Profile decoder descriptions. These decoders differ both from the topology of the network and from the granularity of actors. The first decoder D 1 contains 54 actors that come from the Video Tool Library, the normative FU database [START_REF] Roquier | Automatic software synthesis of dataflow program: an MPEG-4 Simple Profile decoder case study[END_REF]. Y, Cb and Cr components are decoded separately, exposing coarse grain parallelism in the network. Similarly actors expose only coarse-grain parallelism. For instance, the Inverse Discrete Cosine Transform (IDCT) is implemented with a single actor that performs the IDCT using an 8-point based sequential algorithm in a single action.

The second decoder D 2 is a proprietary decoder from Xilinx, available in the OpenDF project [START_REF] Janneck | Synthesizing hardware from dataflow programs: An mpeg-4 simple profile decoder case study[END_REF]. Being targeted at hardware it emphasizes fine-grain parallelism and pipelining. It decodes Y, Cb and Cr components serially, and its IDCT is a network that performs computations at pixel level. This decoder totals up 32 actors. The video sequence used in the experiment is "Foreman" with 300 frames, 176x144 (QCIF), IPPP mode, encoded at 30 fps. These experiments were run on an Intel E8500 Core2Duo processor at 3.2 GHz. Only one of the cores was used by generated software because of SystemC. The throughputs of the two descriptions are expressed in macroblocks per second and compared in table 1. The first column gives the throughput of the CAL model simulated using the Open Dataflow runtime environment. The second column gives the throughput of the binary programs compiled from the code generated by Cal2C using Microsoft Visual Studio 2008 with maximal optimizations. The third column gives the throughput of the circuit synthesized from Cal2HDL on a Xilinx Virtex-2 (this result comes from [START_REF] Janneck | Synthesizing hardware from dataflow programs: An mpeg-4 simple profile decoder case study[END_REF]).

The fidelity of the generated code can be tested in two ways. The first one is a general method that allows a single actor to be tested. In the simulator, tokens read and written by an actor A to test are recorded in separate files, say f in and f out . The designer then generates code for a simple network that contains three actors, a source actor that produces tokens read from f in , the A actor, and a sink actor that compares tokens produced by A against tokens in f out . The second way of testing the fidelity of the generated code for a whole decoder is to match decoded macroblocks against a reference YUV file.

Results show that not only is Cal2C robust enough to successfully generate code for both decoders, but it also generates code that decodes the sample QCIF sequence at 30 fps in both cases. Results also indicate that the code generated from coarse grain actors performs better than code generated from fine grain actors. This is due to the fact that in our current implementation an actor performs computation in its own thread, which means the coarser the actor the more work it will do without triggering a context switch.

Perspectives

As said in section 3.1, SystemC is a good choice for easily implementing DPNs, but it is far from an ideal solution. Each actor, or SC MODULE, is executed in its own thread. Each time an actor must wait, several context switches occur because the SystemC scheduler does not take the dataflow nature of the model into account, and schedules any sleeping actor even if it could clearly not fire (e.g. no data on its input ports). When networks contain tens of threads (like the decoders we tested), those context switches adds a visible overhead. Another limitation of SystemC is that FI-FOs can be read from/written to only one token at a time by calling read/write functions, which is a double source of overhead. The cost of calling a function only to load/store an integer is not negligible, and neither are the memory copies between SystemC FIFOs and peekable buffers.

We believe that it is necessary to implement our own user-level scheduler. A decent DPN scheduler should have the three following characteristics: (1) no use of threads, (2) specific to the network it is generated for, (3) direct access to peekable FIFOs via pointers.

The DPN model was chosen to be as general as possible. Indeed, our initial goal was to create a compiler that translated any actor that could be written with the RVC-CAL language. The selected computation model considers all actors as dynamic and schedules them at runtime. This overhead may be reduced by using restricted dataflow computation models when possible, such as the SDF model. Even though a network may not be statically schedulable as a whole, regions of the network may be. The SDF model allows for compile-time analysis, making it possible to statically schedule such regions at compile-time with bounded memory. The scheduler is turned into a simple sequencer that executes periodically actors in a predefined order inside a single thread. We plan to implement analysis techniques in Cal2C that would detect such statically schedulable regions, which may improve significantly the efficiency of the compiled program.

As a matter of fact, the SDF model also has advantages for scheduling and code generation in the context of multicore targets. For instance, PREESM [START_REF] Pelcat | Scalable compiletime scheduler for multi-core architectures[END_REF] is a tool that schedules and maps actors at compile-time over multicore targets and generate optimized distributed code (including communication and synchronization between cores). Our final goal is to provide a complete framework using Cal2C, PREESM and Cal2HDL to generate efficient code for heterogeneous platforms with multicores and programmable logic devices.

Conclusion

This paper presents a software code generator that automatically translates dataflow programs written in RVC-CAL to C and a SystemC model. We show how to generate readable C code from the actions and action scheduler of actors, and define a clear interface between the actor scheduler and the action schedulers. Cal2C successfully translates two descriptions of an MPEG-4 SP decoder. The results obtained so far show the efficiency of the generated code considering it uses a uniprocessor simulation framework. Perspectives are given to improve the efficiency of the generated code.

Another contribution is that the results presented here show that a network of RVC-CAL FUs provided by the MPEG group can be translated automatically into an efficient software implementation. This specification can also be translated into RTL code targeting FPGAs leading to smaller and faster design than a handmade VHDL reference design [START_REF] Janneck | Synthesizing hardware from dataflow programs: An mpeg-4 simple profile decoder case study[END_REF]. In our opinion, RVC-CAL is a high-level language well suited for functional description and for fast prototyping methods that aim to provide hardware/software optimized implementations.

Fig. 1 A

 1 Fig. 1 A sample actor showing both RVC-CAL programming styles

Fig. 2 A

 2 Fig. 2 A sample actor showing action-level control structures

8 Algorithm 1 :

 81 {a ∈ eligible | is activable(a)}; 6 fireable ← select fireable(activated); 7 action selected ← any action in fireable; Action Scheduler

Fig. 3

 3 Fig. 3 Code generation for m and n networks

Fig. 4

 4 Fig. 4 AST of x := if a > b then a else b end

v o i d a x ( ) { u n s i g n e d s h o r t I 1 [ 2 ] ; u n s i g n e d char I 2 Fig. 6

 1226 Fig. 6 Action a.x translated to a functionally-equivalent C function

Fig. 7

 7 Fig.7From a sparsely-connected priority graph to a DAG

Fig. 8

 8 Fig. 8 FSM of Figure 2 translated to C

  creation of the initial graph ∪ {(t p ,t a ) | (t p ,t a ) ∈ E};11 E ← E ∪ {(t a ,t s ) | (t a ,t s ) ∈ E};Since the actor does not define any relations between a and a.x or a and a.y, the topological order of the graph will yield either [b; a; a.x; a.y; c] or [b; a.x; a; a.y; c]. In the present example this is not relevant because there is no action a. If there was one however, this would lead to nondeterministic behavior, in which case the code generator or simulator is free to choose whether to test a before a.x. In our case the choice is made by the underlying graph library ocamlgraph[START_REF] Conchon | Designing a generic graph library using ML functors[END_REF], using a lexical order over vertices with the same topological rank.

	3 4 5 6 7 8 9 10 E ← E 12 for each t 1 > t 2 relation do V ← V ∪ {t 1 } ∪ {t 2 }; E ← E ∪ {(t 1 ,t 2 )}; end // transformation into the final graph for t a ∈ V do if ∃ t a t a ∧ t a ∈ V ∧ max(|t a |) then
	13 14	end	end
		Algorithm 4: Creating a DAG from priorities
	[b; a.x; a.y; c].

Table 1

 1 Runtime of MPEG-4 SP decoder's descriptions

	decoder	throughput OpenDF Cal2C Cal2HDL
	D 1 D 2	20 16	4318 3614	-290000