Maxime Pelcat
email: mpelcat@insa-rennes.fr

Jean-François Nezan
email: jnezan@insa-rennes.fr

Optimization of automatically generated multi-core code for the LTE RACH-PD algorithm

Embedded real-time applications in communication systems require high processing power. Manual scheduling developed for single-processor applications is not suited to multi-core architectures. The Algorithm Architecture Matching (AAM) methodology optimizes static application implementation on multi-core architectures. The Random Access Channel Preamble Detection (RACH-PD) is an algorithm for non-synchronized access of Long Term Evolution (LTE) wireless networks. LTE aims to improve the spectral efficiency of the next generation cellular system. This paper describes a complete methodology for implementing the RACH-PD. AAM prototyping is applied to the RACH-PD which is modelled as a Synchronous DataFlow graph (SDF). An efficient implementation of the algorithm onto a multi-core DSP, the TI C6487, is then explained. Benchmarks for the solution are given.

I. INTRODUCTION

The recent evolution of digital communication systems (voice, data and video) has been dramatic. Over the last two decades, low data-rate systems have been replaced or augmented by systems capable of data rates of several Mbit/s, supporting multimedia applications (such as DSL, cable modems, 802.11b/a/g/n wireless local area networks, 3G and WiMAX). The 3GPP Long Term Evolution (LTE) represents a recent part of this evolution, enabling data rates beyond hundreds of Mbit/s in potentially very wide cells.

As communication systems have evolved, the resulting increase in data rates has necessitated higher system algorithmic complexity. A more complex system requires greater flexibility in order to function with different protocols in diverse environments. Additionally, there is an increased need for the system to support multiple interfaces and multi-component devices. Consequently, this requires the optimization of device parameters over varying constraints, such as performance, area and power. Achieving this device optimization requires a good understanding of the application complexity and the choice of an appropriate architecture to support this application.

System on a Chip (SoC) with several cores such as multicore DSPs is becoming the standard basic element used to build complex telecommunication systems. The task of distributing pieces of an algorithm over a multi-component architecture is not straightforward. When performed manually, the result is inevitably a sub-optimal solution. There is a need for new methodologies that allow the exploration of several solutions thus producing a more optimal result. For the current work, the methodology of Algorithm-Architecture Matching (AAM, previously called AAA [START_REF] Grandpierre | From algorithm and architecture specifications to automatic generation of distributed real-time executives: a seamless flow of graphs transformations[END_REF]) is employed using the Parallel Real-time Embedded Executives Scheduling Method (PREESM) tool. The PREESM tool is an open framework which provides a flexible method for exploring architectures suited for deterministic applications. More than just a simulation tool, PREESM can generate code. Associated with welloptimized code, communication and synchronization, the automatic generation leads to an efficient algorithm implementation.

This article presents an overview of the LTE Random Access Channel (RACH) preamble detection algorithm and the PREESM tool. Subsequently, the preamble detection application is described using a Synchronous DataFlow graph (SDF). The virtual prototyping of this application over multiprocessor architectures using PREESM tool features is then detailed. The target architecture is a multi-core DSP from Texas Instruments, the C6487. An implementation onto this DSP is performed with optimized inter-core communication and synchronizations using Direct Memory Access (DMA). Finally future work is discussed and conclusions are given.

II. PREAMBLE DETECTION PROCESS

The RACH is a contention-based uplink channel used mainly for initial transmission requests from the User Equipment (UE) to the evolved base station (eNodeB) for connection to the network. The UE seeking connection with a base station sends its signature in a RACH preamble dedicated time and frequency window in accordance with a predefined preamble format. Signatures have special auto-correlation and inter-correlation properties that maximize the ability of the eNodeB to distinguish one UE from another. The RACH preamble procedure is implemented in the LTE eNodeB to detect and identify each user's signature and is dependent on the cell size and the system bandwidth. We assume that the eNodeB has the capacity to handle the processing of this RACH preamble detection every millisecond in a worst case scenario. The preamble is sent over a specified time-frequency resource, denoted as a slot, available with a certain cycle period and a fixed bandwidth. Within each slot, a guard period (GP) is reserved at each end to maintain time orthogonality between adjacent slots [START_REF] Jiang | Random Access Preamble Detection for Long Term Evolution Wireless Networks, submitted to SIPS[END_REF]. This preamble-based random access slot structure is shown in Figure 2.

The case study in this article assumes a RACH-PD for a cell size of 115 km. This is the largest cell size supported by LTE and also the case requiring the most processing power. According to [START_REF]3GPP technical specification group radio access network; Evolved universal terrestrial radio access (E-UTRA)[END_REF], preamble format#3 is used with 21,012 complex samples as a cyclic prefix for GP1, followed by a preamble of 24,576 samples followed by the same 24,576 samples repeated. In this case the slot duration is 3 ms which gives a GP2 of 21,996 samples.

As per Figure 1, the algorithm for the RACH preamble detection can be summarized in the following steps [START_REF] Jiang | Random Access Preamble Detection for Long Term Evolution Wireless Networks, submitted to SIPS[END_REF]:

• After the cyclic prefix removal, the preprocessing (Preproc) function isolates the RACH bandwidth, by filtering with downsampling and then transforms the data into the frequency domain. • Next, the circular correlation (CirCorr) function correlates data with several pre-stored preamble root sequences (or signatures) in order to discriminate between simultaneous messages from several users. It also applies an IFFT to return to the temporal domain and calculates the energy of each root sequence correlation. • Then, the noisefloor threshold (NoiseFloorThr) function collects these energies and estimates the noise level for each root sequence. • Finally, the peak search (PeakSearch) function detects all signatures sent by the users in the current time window. It additionally evaluates the transmission timing advance corresponding to the approximate user distance.

In general, depending on the cell size, three parameters of RACH may be varied: the number of receive antennas, the number of root sequences and the number of times the same preamble is repeated. The 115 km cell case displayed in Figure 1 implies 4 antennas, 64 root sequences, and 2 repetitions.

PreProcessing

BPF

Preamble

Processing: Antenna#1 second copy of the preamble III. THE ALGORITHM ARCHITECTURE MATCHING (AAM) Currently, development tools for processors are primarily based on the C-language and an associated compilation tool. The major issue with a monolithic syntax is the inability to express parallelism. One solution is to use a Real-Time Operating System (RTOS) and to describe threads and their communication links (Mailboxes and pipes). Unfortunately, the application model used in an RTOS is too complex to handle multi-processor architectures when the number of threads increases [START_REF] Lee | The Problem with Threads[END_REF]. For this reason, there is a need to explore methodologies better adapted at expressing the inherent parallelism within the application. Algorithm Architecture Matching (AAM [START_REF] Moreau | On Modeling the RapidIO communication link using the AAA Methodology[END_REF]) is an example of one of these methodologies. Algorithm Architecture Matching (AAM) maps an algorithm to a physical architecture given a set of constraints. The algorithm is described within PREESM using the algorithm graph (Figure 3). It relies on a description model which matches the application behavior. In the case of deterministic systems (including signal, image and communication applications), dataflow graphs have proven to be an efficient representation [START_REF] Shuvra | Ptolemy[END_REF][6] for transformation-oriented systems and heterogeneous multi-component architectures. The algorithm graph (Figure 3) in PREESM is a Synchronous DataFlow graph (SDF) suitable for multi-processor architecture implementations [START_REF] Pino | Hierarchical static scheduling of dataflow graphs onto multiple processors[END_REF]. Each vertex of the SDF represents an operation at coarse grain (equivalent of C function) and each edge represents a data dependency between the two operations at the end vertex. The vertices can be hierarchical, so allowing the description of the application at different resolutions. Thus, the SDF specifies the potential parallelism used in the matching step. The finest resolution vertex is called atomic operation; this type of operation may be described in a programming language such as C, VHDL, C++.

Within the PREESM tool, the architecture is described as the architecture graph (Figure 3) in which vertices represent operators and edges represent communication over a certain medium. An operator in this methodology is usually a processor connected to a local memory and has several communication resources. In this paper, operators are DSP cores and the media is an Enhanced Direct Memory Access (EDMA). The architecture graph specifies the available parallelism.

The matching consists of manually or automatically (AAM algorithms, Figure 3) exploring the implementation solutions with optimization heuristics. These heuristics aim to minimize the total execution time of the algorithm running on the multicomponent architecture, by taking into account the execution time of operations and of data transfers between operations. The result of the matching allows automatic code generation [START_REF] Raulet | SynDEx Executive Kernels For Fast Developments of Applications over Heterogeneous Architectures[END_REF] for multi-processor architectures handling synchronizations and data transfers between processors. Thus PREESM provides off-line static scheduling for multi-processor architectures. An implementation of AAM using the PREESM tool consists of:

• Performing a distribution (allocating parts of the algorithm to architecture components) • Scheduling (determining the order for the operations distributed over a component) the algorithm on the architecture.

• Providing an implementation graph including simulation results of the distributed application functions. • Generating C-code to verify the partitioning on target hardware and to provide a flexible implementation.

These functions enable PREESM to be used as an efficient virtual prototyping tool for our architecture exploration.

IV. ARCHITECTURE EXPLORATION

A. Algorithm Model

The goal of this exploration is to determine through simulation the architecture best suited to the 115km cell RACH-PD algorithm. The RACH-PD algorithm behavior is described as a SDF [3][9] in PREESM. An SDF description brings two major benefits to our implementation. The first is the proven possibility to schedule the algorithm statically. A static implementation enables static memory allocation, so removing the need for runtime memory administration. The second advantage is the high flexibility of communication parameter tuning, as achieved by modifying the SDF.

The RACH-PD algorithm model is shown in Figure 4. Initialization operations on the left-hand side are executed once as the system starts. Next, the three operations PreambleProcess, NoiseFloorThreshold and PeakSearch are executed sequentially in a loop while AntennaGen delivers samples to decode. The PreambleProcess operation is executed four times in each loop iteration; once per antenna. At the beginning of PreambleProcess, the atomic operation Preprocessing executes sequentially the bandpass filter, DFT and subcarrier demapping. It is repeated once for each of the two preamble repetitions. Then the circular correlation with 64 preamble root sequences is performed. Each circular correlation contains the correlation of the two preamble repetitions (SingleZCProc) with power accumulation similar to antenna power accumulation. Using the same approach as in [START_REF] Bhattacharyya | Memory Management for Dataflow Programming of Multirate Signal Processing Algorithms[END_REF], valid scheduling derived from the representation in Figure 4 can be described by the compact expression: Each of these steps is mapped on the available cores and will appear in the exploration results detailed in Section IV-D. The given description generates 1,357 operations; this does not include the communication operations necessary in the case of multi-core architectures. Placing these operations by hand on the different cores would be greatly time-consuming. The architecture exploration PREESM tool offers an automatic scheduling, avoiding the problem of manual placement.

PeakSearch Threshold) NoiseFloor 64 ( )) )))) )( Pr ( ( 2 ( ( 64 ( 4 )

B. Architecture Exploration

The four architectures explored are shown in Figure 5. The cores are all Texas Instrument TMS320C64x+ DSPs running at 1 GHz [START_REF]TMS320C64x/C64x+ DSP CPU and Instruction Set Reference Guide, Texas Instrument technical document[END_REF]. The connections are made via Direct Memory Access (DMA) links. The first architecture is a single-core DSP such as the TMS320TCI6482. The second architecture is dual-core, with each core similar to that of the TMS320TCI6482. The third is a tri-core and is equivalent to the new TMS320TCI6487 [START_REF][END_REF]. Finally, the fourth architecture is a theoretical architecture for exploration only, as it is a quad-core. The exploration goal is to determine the number of cores required to run the random RACH-PD algorithm in a 115 km cell and how to best distribute the operations on the given cores.

C. Architecture Model

To solve the implementation problem, each operation is assigned an experimental timing (in terms of CPU cycles). These timings are measured with implementations of the atomic functions on a single C64x+. The EDMA is modelled as a nonblocking medium transferring data at a constant rate. Assuming the EDMA has the same performance from the L2 internal memory to the L2 internal memory as the EDMA3 of the TMS320TCI6482, then the transfer of N bytes via EDMA should take approximately (see [START_REF] Feng | TMS320TCI6482 EDMA3 Performance[END_REF]):

cycles N N transfer 375 . 3 135 ) ( + =
The average size of the transmitted buffers in the 115 km preamble detection procedure is 4,800 bytes. Consequently, the average transfer speed used for simulation is 3.08 GBytes/s.

D. Architecture Choice

The PREESM automatic scheduling process (i.e. the application of the AAM methodology to the RACH-PD algorithm) is applied for each architecture. The simulation results obtained are shown in Figure 6. Due to the 115 km cell constraints, preamble detection must be processed in less than 4 ms. Two kinds of experimental timings feed the simulation. The first set of timings is measured in loops, each calling a single function with L1 cache activated and appears as striped bars in Figure 6. It represents the application behaviour when data access is ideal. The second set of benchmarks is measured with L1 cache deactivated and leads to the higher cycles displayed in light grey. It represents the worst case of internal data accesses. For more details about C64x+ cache, see [START_REF]TMS320C64x/C64x+ DSP CPU and Instruction Set Reference Guide, Texas Instrument technical document[END_REF]. The RACH application is well suited for a parallel architecture, as the addition of one core reduces the latency dramatically. With L1 cache activated, two cores can process the algorithm within a time frame close to the real-time deadline. Simulation on the dual core with deactivated cache produces significantly higher cycles and misses the real-time deadline, so disqualifying the 2-core solution. The 3-core solution is clearly the best one: its CPU loads (68% with realistic cache misses and 88% without cache) are satisfactory and do not justify the use of a fourth core, as can be seen in Figure 6.

V. IMPLEMENTATION ON THE CHOSEN ARCHITECTURE

With the architecture chosen, we can now start the static implementation process. Our goal is to automatically generate a highly optimized and flexible code with the necessary transfers and synchronization. The TMS320TCI6487 [START_REF][END_REF] is a three-core DSP specifically created for communication signal processing. Two modes are has 1MByte of L2 memory while in asymmetric mode, core 0 has 1.5Mbyte, core 1 has 1MByte and core 0.5MByte. Each CPU can access the L2 memory of the two other cores via the EDMA. Each CPU has also access to an external DDR2 memory. The EDMA can transfer a value from one core on-chip L2 memory to another core L2 memory in parallel with CPU calculation. This capability brings a higher flexibility than an architecture with cores interconnected via communication media.

A. Description of the chosen Architecture

available for memory sharing: in symmetric mode, each CPU hared accesses between cores can be synchronized with ha to develop a c

Real Time Deadline

S rdware semaphores and inter-core interruptions. 32 semaphores may interrupt any core when a resource is accessed or released. Inter-core interruptions may launched from any core by writing in specific registers. Interruptions can carry a 7-bit value to distinguish one from another. Local to each CPU, the RTOS, DSP/BIOS, provides threads and local synchronization between threads with software semaphores. These features will be exploited to implement the RACH-PD algorithm and automatically generate function calls and synchronization. The use of software semaphores is consistent with a high performance implementation as passive wait is generated. Waiting for a DSP/BIOS semaphore puts the CPU in idle state.

B. Using the EDMA as a message passing system

In order to prepare for code generation, we need ommunication library which provides synchronization. The communicator interface should be simple and may be called by generated code. The target architecture offers two communication possibilities: queues which are a message passing system built in DSP/BIOS operating system or the EDMA. As the queues are expected to be slower, the choice was made to use the EDMA. T to N small frames and a remainder. The frames and the remainder are sent on two different chained channels. In order to avoid conflicts, 12 channels are used as shown in Figure 8. Since the channel number contains the sender and receiver identifiers, the receiver always knows, even in interruption The m th intermediate memory solution imposes the static allocation of previously, two different modules may be used to generate inter-core synchronization: hardware semaphores or in ng the same method as in [START_REF] Grandpierre | From algorithm and architecture specifications to automatic generation of distributed real-time executives: a seamless flow of graphs transformations[END_REF], the PR ates two threads per core: one for processing e for sending communication orders and waiting for transfer completion. As shown in Figure 9, when two successive functions are distributed on different CPUs, two semaphores Sem1 and Sem2 are generated on each core to synchronize the processing and communication threads. While communication threads are waiting for the completion of a transfer, processing threads can process data that does not impact this transfer. These local semaphores are implemented with DSP/BIOS operating system. t design problem to solve is the communicat e e sender alone knows the source buffer address and the receiver alone knows the destination buffer address. There are two solutions (Figure 10 The second solution is called mem ver poses a bidirectional communication but is lighter than the preceding solution, as the address transfer of 4 bytes may be achieved through scratch buffers and synchronization through hardware semaphores or inter-core interruptions. During these transfers, we use only 12 of the 256 parameter set registers of the EDMA. The unused registers can be utilized as scratch buffers to transmit the transfer destination addresses. emory pull solution is chosen for two reasons. Firstly, e an additional buffer of size at least as large as the largest one in the algorithm. In the RACH-PD case, this buffer should be of a minimum size of 100 kBytes with strong memory optimization. Secondly, the double transfer results in a division by 2 of the communication speed. Even with rates of several GBytes/s, this data rate reduction is not negligible. Simulation shows a communication cost of almost 5% for the RACH-PD algorithm.

As stated ter-core interruptions. In order to simplify the synchronization, a small library is created, with an interface close to the one of the local semaphores:

• HardSEMPend(int id): Waits for a semaphore with the given semaphore identifier • HardSEMPost(int id): Launches a semaphore with the given semaphore identifier.

Int ij0

The transfer c tion code identifies omplethe sender and receiver Timeslot when original buffer must be protected

The semaphore identifier is chosen to be the Sender CPU nu hen the sender receives an interruption indicating the av When the cores are started, each core waits for the two other co complete, our attention tu hen the multi-core program is run with data in external tion programming is complete, we ge mber. Hardware semaphores are designed to protect critical sections from multiple accesses. They are typically used in resource access requests; access is granted when a semaphore is acquired. Programming the synchronization library with such a system leads to a clumsy implementation where the acquired resource is purely virtual. It is for this reason that the choice was made to base the library on inter-core interruptions. The principle of a inter-core synchronization library based on interruptions is quite simple. Any core can send an inter-core interruption to another core by providing the right identifier. An interruption is launched by the sender HardSEMPost function and is caught in an interrupt service routine of the receiver. The receiver then releases a local semaphore that was pending in the HardSEMPend function.

W ailability of the address, it launches the EDMA copy and waits. At the end of the transfer, the EDMA launches an interruption giving a transfer completion code equal to the EDMA channel number. The sender and receiver identifiers are deduced and communication threads of both CPUs are released. res to run before sending any interruption. This system ensures that no inter-core interruption is ignored.

D. RACH-PD memory consideration

Once the communication model is rns to memory. The data buffers are statically allocated, some in the fast L2 memory of their CPU and others in the huge DDR2 external memory. We thus need to decide which buffers should be allocated in L2 and which configuration (symmetric or asymmetric) should be chosen. For the buffers in DDR2, sections of L2 memory must be used as cache for DDR2 so that performance does not decrease dramatically (see [START_REF]8Communications Infrastructure Digital Signal Processor, Texas Instrument technical document[END_REF] for more details). Thus, we activate L2 cache with its maximal size of 256kBytes to improve DDR2 access time. W memory, the EDMA reads and writes DDR2 data cached in L2. Cache coherency must then be taken into account. Indeed, the EDMA module runs the risk to read "dirty" data or to write in a cached value. Before sending data, a cache "write-back" is called to retrieve the data from cache. Before receiving data, a cache "invalidate" is called to mark the cache value as obsolete. With these precautions, cache coherency is maintained.

E. Implementation tests

When the communica nerate a 3-core code for C64x+ with the PREESM tool. We initially test a simple PREESM project by copying a buffer from one core L2 to another. The benchmarks of these copies are shown in Figure 11. The fixed overhead of an inter-core copy is approximately 2,700 cycles. This overhead is due to the synchronization process, the interruption routines and the EDMA configuration. When transferring big buffers, the EDMA data rate reaches 1.6 GBytes/s, half the speed of the TMS320TCI6482 EDMA employed in the simulations and benchmarked in [START_REF] Feng | TMS320TCI6482 EDMA3 Performance[END_REF]. ) Single-core test: A first version is tested on one core wi n: L2 cache is then activated with the ma 3) Three-core implementation: The application is distribute T e TMS320TCI6487 platform in several steps: 1 th code in L2 and data in DDR2. This implementation allows us to debug, dimension the stack and ensure that the code is working. The time of one preamble detection with this configuration is 240 ms.

2) Cache activatio ximal size of 256 kBytes. The preamble detection time is then reduced to 69 ms. d over three cores. When we let the PREESM tool choose a strongly parallel implementation without constraints, it generates a very complex solution with 10,000 semaphores. We thus tune this solution, reducing inter-core communication and still allowing good pipelining (see Figure 12). The number of semaphores is then reduced to approximately 100. The complex solution which results from the non-constrained operation shows a limitation in the present PREESM mapping: a fixed cost for transfers needs be added to the tool to avoid the explosion of communication. The non-constrained PREESM automatic code generation allocates buffers of approximately 1.65 Mbytes for one core, 1.25 Mbytes for a second core and 200 kBytes for a third core, to which the heap and the code size must be added. This asymmetry justifies the use of asymmetric memory. With this configuration, one preamble detection takes 50 ms. Internal allocation of some power buffers leads to a detection within 6.5 ms. Finally, after circular correlation buffer optimization, the detection time becomes 3.6 ms, under the constraint limit for response time.

The final implementation has one core loaded at 90%, one core at 75% and one at 70%. The simulation and code generation have led to a real implementation very close to that predicted with L1 cache worst case where the simulation loads were respectively: 88%, 83% and 83%. The added constraint of deactivating the cache in simulation inputs compensates for the external memory accesses that were not simulated and the EDMA rate slower than intended. These results show that prototyping the application enables a precise simulation of the multi-core solution before solving complex implantation problems.

VI. FUTURE WORK

In the near future, a new communication model for the TMS320TCI6487 will be built based on message queues from DSP/BIOS operating system. This model will then be compared with that based on the EDMA. Its advantage will be the portability on devices using RapidIO (see [START_REF] Moreau | On Modeling the RapidIO communication link using the AAA Methodology[END_REF]), as the operating system DSP/BIOS can use this communication system to pass messages.

Furthermore, other algorithms of LTE will be studied and implemented. It is expected that this will help to improve the architecture models of the PREESM tool. Specifically, internal/external allocation and advanced timings taking into account data caching may be automated, thus eliminating the manual step of memory allocation. Additionally, a more accurate communication model in the PREESM tool will remove the need for the manual reduction of semaphores.

VII.

CONCLUSIONS The intent of this paper was to demonstrate a methodology using rapid prototyping and automatic code generation to develop an optimized multi-core implementation of a communication algorithm. After exploring 4 solutions, the best target architecture for the 115km cell RACH-PD algorithm was chosen, and an implementation is described and benchmarked. Memory allocation, function calls and EDMA calls are generated in C-code by the PREESM tool. Inter-core communication and memory partitioning are considered in the prototyping methodology. The result is an efficient and highly reconfigurable implementation, proving that the generation of static implementations from SDF descriptions is a viable solution for deterministic signal processing applications.

In the near future, an increasing number of CPUs will be available in complex System on Chips. Developing methodologies to efficiently partition code on these architectures is thus an increasingly important objective.

Fig. 1 Fig. 2 A

 12 Fig. 1 Random Access Channel Preamble Detection (RACH-PD) Algorithm

Fig. 3

 3 Fig. 3 PREESM Description

Fig. 4

 4 Fig. 4 Preamble Detection SDF Description

C64x+Fig. 5

 5 Fig. 5 Four architectures explored

Fig. 6

 6 Fig. 6 Timings of the RACH-PD algorithm schedule on target architectures

Fig. 7

 7 Fig. 7 Architecture of theTMS320TCI6487

Fig. 8

 8 Fig. 8 EDMA channels used for communication between cores

Fig. 9

 9 Fig. 9 Threads and synchronization within the cores

  ) to complete a transfer in this situation: use an intermediate address or transfer the destination address. When a ust occur twice: from local memory to intermediate and from intermediate to destination. The dimension of the intermediate buffer is also a problem. In Figure 10, only the communication threads of the CPUs are represented.

Fig. 11

 11 Fig. 11 Benchmarks of TCI6487 synchronized EDMA3 buffer copy

Fig. 12

 12 Fig.[START_REF][END_REF] Simple pipelining of the RACH-PD decoding 4) Smart allocation and code: If buffers are allocated in L2,pre-processing memory and code optimization brings the preamble detection processing time to approximately 10 ms. Internal allocation of some power buffers leads to a detection within 6.5 ms. Finally, after circular correlation buffer optimization, the detection time becomes 3.6 ms, under the constraint limit for response time.


Ghislain Roquier
email: groquier@insa-rennes.fr

Matthieu Wipliez
email: mwipliez@insa-rennes.fr

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

Jean-Franc ¸ois Nezan
email: jnezan@insa-rennes.fr

Olivier Déforges
email: odeforge@insa-rennes.fr

SOFTWARE SYNTHESIS OF CAL ACTORS FOR THE MPEG RECONFIGURABLE VIDEO CODING FRAMEWORK

Keywords: MPEG RVC, CAL Actor Language, dataflow modeling, software synthesis

The MPEG Reconfigurable Video Coding (RVC) framework aims to provide a unified specification of all video technology. In this framework, a decoder is modularly built as a configuration of video coding tools taken from the MPEG toolbox library. The elements of the library are specified using the CAL Actor Language. CAL is a dataflow based language providing computation models that are concurrent and modular. This paper presents a synthesis tool that from a CAL specification generates multithread C code. Indeed, code generators are fundamental supports for the deployment and success of the MPEG RVC framework. This paper focuses on the automatic translation of a CAL actor. This approach has been used to obtain a C implementation of the inverse DCT module which is a part the MPEG-4 Simple Profile decoder, chosen by MPEG experts to validate the RVC approach. The generated code and the associated translated model are validated against the original CAL description and simulated using the Open Dataflow environment.

INTRODUCTION

A large number of successful MPEG video coding standards have been developed since the first MPEG-1 standard in 1988. The standardization process has always aimed to provide appropriate forms of specifications for a wide and easy deployment. While at the beginning MPEG-1 and MPEG-2 were only specified by textual descriptions, starting with MPEG-4 C/C++ descriptions, reference software became the formal specification of the standard. Such descriptions are composed of non-optimized software packages and face now many limitations. For real implementations all reference SW have to be rewritten to optimize performances and to adapt it to current design methodologies. Such monolithic specifications hide the inherent parallelism and data flow structure of the video coding algorithms, features that are necessary to be exploited for efficient implementations. In the meanwhile the growth of video coding technologies leads to solutions that are increasingly complex to be designed and present significant overlap between standards. Consequently, adding tools in a standard involves a new process in which all the technology is modified. The observation of these drawbacks of current video standard specification formalism led to the development of the Reconfiguration Video Coding (RVC) standard. The key concept was to design a decoder at a higher level of abstraction. An "abstract" model focusing on functionality and concurrency is the specification formalism chosen, which is the best starting point for any design and implementation process. RVC provides a high-level description of the MPEG standard using a specific language called CAL. Once the high-level model is available the challenge is then to develop appropriate tools providing optimized implementations. The work presented here aims to provide a non-normative software synthesis tool called Cal2C. This paper proposes an automated process to handle CAL actors, analyze them and generate multithread C code. The paper is organized as follows: section 2 introduces the RVC framework. This is followed by the description of the CAL actor synthesis process. As part of the MPEG-4 SP decoder, the inverse DCT case study is reported in section 4. Finally conclusions and future work are given in section 5.

RVC FRAMEWORK

The MPEG RVC framework is currently under development by MPEG as the part of MPEG-B and MPEG-C standards. It aims to provide a model of defining MPEG standards at system-level [START_REF] Lucarz | Reconfigurable media coding: a new specification model for multimedia coders[END_REF]. An abstract decoder is built as a block diagram in which blocks define processing entities called Functional Units (FUs) and connections represent the data path. RVC provides both a normative standard library of FUs and a set of decoder descriptions expressed as networks of FUs. Such a representation is modular and helps the reconfiguration of a decoder by modifying the topology of the network. RVC mainly focuses on reusability by allowing decoder descriptions to contain common FUs across standards. The CAL Actor Language (CAL) has been chosen as the normative language to specify the standard library of FUs. CAL is a dataflow oriented language created as part of the Ptolemy project [START_REF] Eker | Cal language report[END_REF]. A CAL actor is a computational entity with interfaces (input and output ports), internal state and parameters. An actor is strongly encapsulated; it can neither access nor modify the state of any other actor. An actor may only interact with others by sending data (called tokens) along channels. During an execution (called firing), it maps input tokens onto output tokens and changes its internal state. An actor may contain any number of actions that are computations performed during a firing. An action is specified by the number of tokens it consumes and produces. When an actor is fired, it has to select one of them based on the availability of input tokens and optionally based on conditions (called action guards) relating to their values or current state. In addition, action selection may be constrained using action schedules specified with Finite State Machines (FSM). Action firing is then state-dependent. Finally, action priorities impose a partial order among actions to select. In short, an action is fireable if it respects the following conditions: (1) there are sufficient tokens on input ports and adequate room on output ports;

(2) guard clauses evaluate to true; (3) the current state enables the action to fire according to the FSM; (4) no higher-priority action respects (1), ( 2) and (3).

RVC Decoder Description

The Decoder Description Language (DDL) enables the description of the decoder structure. A decoder is a network formed by a set of interconnected actors. DDL is an XMLbased language that can be used to specify the topology of the network. DDL is hierarchical -a network may be a part of a more general network -and is used to pass parameters to actors. For instance, the graphical representation of the macroblock-based MPEG-4 Simple Profile decoder description is shown Figure 1. The parser and the inverse DCT block are hierarchical, otherwise all blocks are atomic actors. Note that only one egde is represented to simplify the decoder when two actors are connected by more than one edge. Decoder descriptions may be generated automatically by a graphical composition tool called Moses1 that is a CAL editing and simulation framework. The Open Dataflow project2 is also an environment for building and simulating CAL actor models with a textual description of the network (using the Network Language) that may be automatically translated into an RVC decoder description.

Network interpretation

The whole system behavior is conditioned by interactions between actors. Those interactions are governed by a Model of Computation (MoC) that defines which scheduling policy is used to execute actors and how communication is done between them. CAL does not have any bias towards any particular MoC. In other words, a CAL network exhibits neither the scheduling policy nor the communication. As a consequence, an RVC decoder description may behave differently depending on the MoC used. This paper does not intend to draw up an exhaustive list of models (cf. [START_REF] Lee | Embedded software[END_REF] for more details). Nonetheless, two dataflow-related MoCs are chosen to demonstrate network interpretation. On one hand, the Process Network (PN) model [START_REF] Kahn | The semantics of a simple language for parallel programming[END_REF] is efficient when describing asynchronous systems. The PN model is deterministic: the output result is not affected by the scheduling algorithm. However, it requires run-time scheduling, which makes the system verification harder. On the other hand, the Synchronous Dataflow (SDF) model is suitable for fixed-rate systems [START_REF] Lee | Static scheduling of synchronous data flow programs for digital signal processing[END_REF]. In SDF, all computation and communication may be statically scheduled. As a consequence, real-time execution and bounded memory usage can be known at compile-time. However, the fixed-rate requirement makes it difficult to model more flexible systems like those in video coding. Indeed, CAL actors in the standard library often contain multiple actions and an abundance of priorities, FSM or guard clauses. It leads to state-dependent or conditional execution hardly modelizable with the SDF formalism. Conversely, the PN model is a model of choice if implementing such networks.

CAL ACTOR SYNTHESIS

Action translation

Actions of an actor are translated to equivalent C functions in several steps. A CAL source file is parsed to an Abstract Syntax Tree (AST) using the rules described in Caltrop Language Report [START_REF] Eker | Cal language report[END_REF]. It holds the same information as CAL source code: both functional and imperative coding styles are used, some variables are missing a type, and actions have different semantics than functions. To generate decent C code, this AST needs to be transformed and fully typed. First, to ease both typing and code generation, actions are considered just as other functions, whose parameters are actions ports. The next step, type inference, consists in annotating declarations nodes with type information. To this end, we use the type system along with the W algorithm defined by Damas and Milner in [START_REF] Damas | Principal type-schemes for functional programs[END_REF]. This algorithm is able to infer a type-scheme for any expression expressed in the λ-calculus formalism, extended with the let clause. A property of this formalism is that any computable function can be expressed using it: each CAL expression is converted to λ-calculus and typed by W. The type information allows other AST transformations that are typedependent. For the sakes of simplicity and efficiency, CAL lists are modeled as C arrays, requiring list declarations to be updated with computed size information. Another requirement imposed by the target language is that locally-allocated arrays can not be returned on the stack. CAL functions that return a list are thus transformed to take an additional output list parameter instead, and calls to these functions are modified accordingly. A final transformation is replacing purely functional constructs by imperative ones. At this point, the AST is converted to CIL (C Intermediate Language [START_REF] Necula | CIL: An Infrastructure for C Program Analysis and Transformation[END_REF]). CIL is a framework and an intermediate language that is both lowerlevel and more precise than ASTs: it disambiguates C syntactic constructs and embeds type information. This allows seamless translation of expressions and types. C code is generated by calling the pretty-printer included in the framework.

Guard and priority resolutions

Determining a total order of actions is required to have a consistent evalutation of actions during execution. The firing condition for a1 is the availability of tokens on i1 and sel ports but also that the control token value s is true (due to the guard clause) whereas only the availability of input tokens is required for a2. Without priority statement, this actor is nondeterministic. Indeed, if the two actions fulfill their firing conditions, it is not possible to determine which action will be fired and then, there is more than one possible output result for the same inputs tokens. To avoid this nondeterminism, action priorities introduce a partial order among the actions that contrain action selection. An action may fire if no higher-priority action is fireable. In the example, a1 will be selected even if a2 also fulfill the firing conditions. Formally, the total order is determined as follows;

(1) first consider untagged actions, (2) actions without priority statements and finally (3) actions with priority statements. then sort action according to priority if actions have priority statements or according to the document order otherwise.

Action scheduling

CAL actors may include finite state machine (FSM) to schedule their actions. It consists of a set of states and a set of actions (view as transitions). An action may be fired only if its current state is in accordance with the FSM statement. Figure 3 depicts the graphical representation of the textual FSM inside the "add" actor from the decoder description. Nodes and edges respectively represent states and actions. This actor adds the prediction error (from the texture decoder) to the prediction (from the motion compensation decoder). Actions schedules constrain action selection according to the current state of actors. For instance, when the current state of "add" is "motion", only motion and done actions can be evaluated for firing. Formally, FSM translation is done according to the

RESULTS

The PN model is chosen to interpret CAL networks (cf. section 2.3). Any environments which support multithreading may be chosen to implement PN model. For instance it can be done with POSIX threads by translating CAL actors into threads and by replacing connections with FIFOs. However, low-level considerations such as communication or scheduler implementation, render this solution time-consuming and error prone. Another approach for PN implementation is SystemC 3 [START_REF] Grotker | System Design with SystemC[END_REF] whose simulation environment permits highlevel programming, well-adapted to functional verifications. A PN-oriented SystemC application is expressed as a network of modules communicating with each other via blocking FIFOs. SystemC comes with an efficient data-sensitive scheduler suitable for dataflow programming. CAL actors are translated into SystemC modules and networks become an instanciation of modules and FIFOs. In order to test the functionality, the case study application is the two-dimensional inverse DCT, which is part of the MPEG-4 SP decoder. More precisely, it is the new normative inverse DCT as specified in [START_REF]Fixed-point 8x8 IDCT and DCT[END_REF] and given in Figure 4. It consists of separately applying one-dimensional IDCT along the row and column axis of an 8×8 pixel block. The network is composed of 2 input ports, 1 output port and 7 actors. The testbench consists of applying stimulus (a random number generator) to the top network and verifying the response against an expected result (from the CAL description simulated using the Open Dataflow environment). It has been successfully applied with consistent results between the original and the synthesized networks.

CONCLUSION AND FUTURE WORK

This paper has presented a brief overview of the process that translates CAL actors into C code. The process has been successfully applied to translate the normative IDCT, as well as most actors inside the MPEG-4 SP decoder description. Moreover, a network implementation has been automatically generated from the top network and simulated using the Sys-temC environment. The results obtained so far show the efficiency and soundness of the synthezised code. But as far as software is concerned, the PN model faces limitations when it comes to hard real-time implementation. Future work will have to provide network analysis and CAL coding guidelines in order to achieve compile-time scheduling of most MPEG RVC decoder descriptions. More precisely, we plan to automatically transform CAL networks into an SDF-related representation that will allow us to statically schedule and map the resulting model onto multiprocessor architectures.

Fig. 1 .

 1 Fig. 1. MPEG-4 Simple Profile decoder description

  Fig. 3. Graphical representation of the FSM inside the "add" actor

Fig. 4 .

 4 Fig. 4. CAL network of the DCT -1 block

  To this end, § ¤ Fig.2. if-then-else statement in a basic multiplexer actor considering both action priority and guard may be of help. For instance, an actor with priority and guard is depicted Figure2. It is a basic multiplexer with 2 actions tagged a1 and a2, 3 input ports i1, i2 and sel and 1 output port o. During a firing, the actor puts the token from either i1 or i2 on o according to the boolean value of the token from sel. Action tagged a1 contains a guard clause that constrains the firing.

	actor MUX () int i1, int i2, bool sel ==> int o :
	a1: action i1:[data], sel:[s] ==> o:[data]
	guard s = true
	endaction
	a2: action i2:[data], sel:[s] ==> o:[data]
	endaction
	priority
	a1 > a2;
	endpriority
	endactor ¦	¥

  3. Graphical representation of the FSM inside the "add" actor following state-transition mechanisms: (1) each state of the FSM is a label in the C code; (2) the first label in the code is the initial state; (3) each label is followed by function calls to the translated actions (sorted like in 3.2) which are transitions from this state to others; (4) unconditional branch (goto statement) is used after each function call to the next state.

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

http://opendf.sourceforge.net/


Matthieu Wipliez
email: mwipliez@insa-rennes.fr

Ghislain Roquier
email: groquier@insa-rennes.fr

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

Jean-Franc ¸ois Nezan
email: jnezan@insa-rennes.fr

Olivier Déforges
email: odeforge@insa-rennes.fr

CODE GENERATION FOR THE MPEG RECONFIGURABLE VIDEO CODING FRAMEWORK: FROM CAL ACTIONS TO C FUNCTIONS

Keywords:

The MPEG Reconfigurable Video Coding (RVC) framework aims to provide a unified specification of all video technology. In the RVC framework, a decoder is build in a modular manner as a configuration of video tools taken from the MPEG toolbox library. The elements of the library are specified using the CAL Actor Language (CAL). CAL is a data flow based language providing computation models that are concurrent and modular. This paper describes a synthesis tool that from a CAL specification generates an executable SW module. Code generators are fundamental supports for the deployment and success of the MPEG RVC framework. This paper focuses on the automatic translation of a CAL action, which is the first step to a complete actor translation. The techniques described here is capable of automatically generating C executable code according to a finite set of rules. This approach has been used to obtain a C implementation of the IDCT module which is one element of the RVC library. The generated code is validated versus the original CAL description and simulated using the Open Dataflow environment.

INTRODUCTION

A large number of successful MPEG video coding standards have been developed since the first MPEG-1 standard finalized in 1988. The standardization process has always aimed to provide appropriate forms of specifications for a wide and easy deployment. While at the beginning MPEG-1 and MPEG-2 were only specified by textual descriptions, starting with MPEG-4 C/C++ descriptions, called reference software, became the formal specification of the standard and the textual part became an additional component with the aim of clarifing the reference SW descriptions. Such descriptions are composed of non-optimized software packages and face now many serious limitations. For real implementations all reference SW have to be re-written from the beginning to optimize performances and to adapt it to current design flow methodologies. Such monolithic specifications hide the inherent parallelism and data flow structure of the video coding algorithms, features that are necessary to be exploited for efficient implementations. In the meanwhile the growth of video coding technologies leads to solutions that are increasingly complex to be designed and present significant overlap between standards. Moreover, several codecs and associated profile levels have to coexist in a single product. This is the result of the standardization process: adding tools in a standard involves a new process in which all the technology is modified. In short, the process has to be improved to face its limitations and to avoid bottlenecks in the future.

The observation of these drawbacks of current video standard specification formalism led to the development of the Reconfiguration Video Coding (RVC) standard. The key concept was to design a decoder at high system level to avoid lowlevel implementation considerations during the system specification stage. An "abstract" model focusing on functionality and concurrency is the specification formalism chosen, which is the best starting point for any design and implementation process. RVC provides a high-level description of the MPEG standard using a specific language called CAL. Once the high level model/specification is available the challenge is then to develop appropriate tools providing optimized implementations. Indeed, efficient SW/HW implementations need hardware and software code generators. Some work have be done to directly generate HDL from a CAL model [START_REF] Janneck | From actors to gates[END_REF]. The work presented here aims to automatically generate optimized software for multiprocessor and multicore targets. To achieve these ambitious objectives the first step is to provide a nonnormative software synthesis tool called Cal2C. It is designed to become a tool available in the RVC framework. The main issue is to deal with various syntaxes allowed in the CAL language. This paper proposes a safe process to handle CAL operators, analyze them and generate functional C code. The paper is organized as follows: sections 2 and 3 introduce the RVC framework. This is followed by a description of Cal2C functionalities. As part of the MPEG-4 SP decoder, the IDCT case study is reported in section 5. Finally conclusions and several perspectives are given in section 6.

RVC FRAMEWORK

Scope

The MPEG RVC framework is currently under development by MPEG as the part of MPEG-B and MPEG-C standards. It aims to provide a new interoperable model of defining MPEG standards at system-level [?]. An abstract decoder is built in a block diagram manner in which blocks define processing entities called Functional Units (FUs) and connections represent the data path. RVC provides both a normative standard library of FUs and a set of decoder descriptions as a network of FUs. Such a representation is modular and helps the reconfiguration of a decoder by modifying the topology of the network or adding new FUs to describe new standards. RVC mainly focuses on reusability by allowing decoder descriptions to contain common FUs across standards.

FU specification

The Cal Actor Language (CAL) has been chosen as the normative language to specify the standard library of FUs. CAL is a suitable language for the modular approach of RVC. CAL is a dataflow oriented language created as part of the Ptolemy project [START_REF] Eker | Taming heterogeneity-the ptolemy approach[END_REF]. A CAL actor is a computational entity with interfaces (input and output ports), internal state and parameters. An actor is strongly encapsulated; an actor can neither access nor modify the state of any other actor. An actor may only interact with others by sending data (called tokens) along communication channels. When an actor is executed (fired), it consumes tokens from input ports, changes its internal state and produces tokens on the output ports. An actor is executed in a sequence of steps called actions. An action is a piece of computation that an actor performs during firing. An action is specified by the number of tokens it consumes and produces. An actor may contain any number of actions. When an actor is fired, it has to select one of them based on the availability of input tokens and optionally based on conditions relating to their values or the current state. In addition, it may also contain constructs that constrain action selection. An action guard enables conditional action firing according to input tokens or state variables. A finite state machine (FSM) allows actions to be scheduled according to the current state of the actor and action priorities enabled to order action selection. In short, an action is fireable if it respects the following conditions:

√ there are sufficient tokens on input ports and adequate room on output ports; √ guard clauses evaluate to true; √ the current state enables the action to fire according to the FSM; √ no higher-priority action may fire.

RVC Decoder Description

On the other hand, the Decoder Description Language (DDL) enables the description of the decoder structure. A decoder is a network formed by a set of interconnected actors. DDL is an XML-based language that can be used to specify the topology of the network. DDL is hierarchical -a network may be a part of a more general network -and is used to pass parameters to actors. Decoder descriptions may be generated automatically by a graphical composition tool called Moses1 that is a CAL editing and simulation framework. The Open Dataflow project2 is an environment for building and simulating CAL actor models with a textual description of the network (using the Network Language) that may be automatically translated into an RVC decoder description. This non-normative tool also provides an automatic HDL synthesis from a CAL network [START_REF] Janneck | From actors to gates[END_REF].

CODE GENERATION PRELIMINARIES

Concurrent programming

A dataflow network is inherently concurrent. Understanding concurrency brings with it understanding of how the whole system behaves and how interactions between actors are done. Scheduling policy and data transfer mechanism are the key concepts when interpreting a dataflow network. CAL does not have any bias towards any particular network interpretation. In other words, a CAL network exhibits neither the scheduling policy nor the data transfer mechanism. Formal models are used to interpret a network. This paper does not intend to draw up an exhaustive list of models: cf. [START_REF] Kahn | The semantics of a simple language for parallel programming[END_REF] for more details. However, two particular models are chosen to demonstrate dataflow network interpretation. On one hand, the Process Network (PN) model [START_REF] Lee | Static scheduling of synchronous data flow programs for digital signal processing[END_REF] is efficient when describing asynchronous systems. The PN model is determinate: the output result is not affected by the scheduling algorithm. The downside of this model is the asynchronous execution. It requires run-time scheduling, which makes the system verification harder. On the other hand, the synchronous dataflow (SDF) model has more constraints but is suitable for fixed-rate systems [START_REF] Necula | CIL: An Infrastructure for C Program Analysis and Transformation[END_REF]. It is especially well-adapted for software synthesis; a network analysis may lead to compile-time scheduling. This being so, indications about real-time behavior or execution in bounded memory can be determined at compile-time.

However, the fixed-rate requirement makes it impossible to model more flexible systems like those in video coding. Indeed, CAL actors in the standard library often contain multiple actions and an abundance of priorities, FSM or guard clauses. It leads to state-dependent and/or conditional execution that makes it difficult to analyze the network. Then, the PN model is a more appropriate model if implementing such networks.

Software synthesis

The goal of the C code generator is to produce a code that behaves exactly like the CAL reference code. Non-automatic verification is a manual comparison between the generated and the original files. This requires the source code produced to be recognizable. Another approach to the checking of program behavior, required for a decoder to be qualified as RVCcompliant, is to assert that the tokens consumed and produced by each actor equal the tokens described by the norm. In both cases, it is preferable to generate a C code that has a similar structure to the CAL code: an actor is translated into a file, an action into a function. There are different means of translating CAL to C while meeting the above requirements. The first is to use source transformation programming systems, such as Stratego/XT or TXL. Such systems are very general, and based on context-free grammars and rules. Their purpose is to perform transformation from a language to another. Another possibility, since we are specifically aiming at producing C code, is to use C-specific transformation tools. SUIF (Stanford University Intermediate Format) and CIL (C Intermediate Language [START_REF] Damas | Principal type-schemes for functional programs[END_REF]) can parse C code to an Intermediate Representation (IR), perform transformations on it, and print it back to C. These systems have the advantages of producing a clean representation and a pretty-printer, without having to learn another language or have a complete toolset. We chose CIL over SUIF because its IR has clean semantics, as detailed in section 4.3, and produces a higher quality C code.

FROM CAL ACTIONS TO C FUNCTIONS

Translating the actions of a CAL actor to C functions consists of the following steps: a CAL file is parsed to an abstract tree representation of the source program (section 4.1); this tree is then annotated with type information (section 4.2), and converted to CIL Intermediate Representation (section 4.3). Finally, CIL pretty-prints the IR to C code.

CAL parser

The CAL parser parses a CAL file using an LALR parser created from the rules described in the Caltrop Language Report [START_REF] Eker | Taming heterogeneity-the ptolemy approach[END_REF], and produces an Abstract Syntax Tree (AST). In this tree, a variable become a Var node, an access to the ith element of a list, an I node, unary and binary operations, U and B nodes respectively. Assignments, function applications, and conditionals are transformed in Assign, App, and If nodes. The AST holds the same semantic information as the source code, but its form makes it easier to process automatically.

Type inference

The AST obtained at this stage may not have complete type information, as CAL allows the programmer to omit type annotations of declared variables whereas C does not. This makes it necessary to guess types when they are not explicit: this step is called type inference. To this end, we use the type system and the W algorithm defined by Damas and Milner in [?]. This algorithm is able to infer a type-scheme for any expression in the λ-calculus formalism, extended with the let clause. A λ-expression is either a term, a function application, a function definition, or a local definition:

e := x | e 1 e 2 | λx.e | let x = e 1 in e 2
One property of this formalism is that it can be used to express any computable function. To compute the type of CAL expressions, we transform them to their equivalent λ-calculus representation using the rules shown in Table 1. Arithmetic operations become λ-terms with known types: unary and binary operators become functions with one and two arguments respectively. An access to a list element and a conditional become function applications. The nth function takes two parameters of types α list and integer, and returns an element of type α. The "if" function accepts a boolean parameter, two parameters of type α, and returns a result of type α. After conversion, we apply the W algorithm to the λexpressions associated with each declared variable. If there is a type error, the algorithm fails, and the process stops. Otherwise, the variables are updated with the type information obtained.

CAL abstract syntax λ-calculus

Var(v) v I(list, e) (nth

Converting to CIL

C expressions can be purely functional or make use of sideeffects: functions are allowed to modify global state or local arguments. CIL goes further by distinguishing control flow statements and instructions among side-effect expressions, from functional side-effect free expressions. Control flow statements include branch statements (goto, while. etc.) and conditionals. Instructions are assignments and function calls. Expressions include constants, unary and binary operations, and the operator address. Lvalues, that can appear at the left of an assignment, are expressed in terms of host and offset, and have precise typing rules. The conversion of CAL AST to CIL is done by a translation function hereinafter called T . This function takes a CAL expression, and returns a CIL expression and a list of statements, with no particular difference between control flow statements and instructions. The environment Γ maps variables names to their corresponding CIL lvalues. The newV ar function creates a new temporary variable named β, and returns Lval(β). The expression resulting from T (e) is shown below:

RESULTS

The CAL-based MPEG4-SP standard is used to validate the C code generation. Yet, about 90% of actions in the decoder are successfully translated with CAL2C (the remaining 10% actions are located in the bitstream parser subnetwork [?] which require few other investigations). In order to test the functionality, the case study application is the two-dimensional IDCT, which is part of the MPEG4-SP decoder. CAL networks are implemented using the PN model; the POSIX threads are used to implement actors and circular buffers are used for communication. Actions are automatically generated by CAL2C and are subroutines handled by the actor thread. Two IDCT are used [?, 10]. The first one is depicted in Figure 1, composed of 2 input ports, 1 output port and 5 actors. They have almost the same scheme, separately applying one-dimensional IDCT along the row and column axis of an 8×8 pixel block. The testbench consists of applying stimulus (a random number generator) to the top network and verifying the response against an expected result (from the original CAL description simulated using the Open Dataflow environment). Many scenarios have been tested during which no errors occur that confirm the validity of CAL2C. Note that the compiling is done faster in this approach and the use of C enhances IDCT run times.

CONCLUSION AND FUTURE WORK

This paper has presented a brief overview of the software used to translate CAL actions to C functions. The process has been successfully applied to translate the normative IDCT, as well as most of the actions of RVC MPEG-4 SP decoder actors. However, FSM, action priorities and guard clauses are not yet considered. The automatic actor code generation must be completed by considering the relevant control structures of the CAL language. Moreover, network implementation (which has been a manual task until now) has to be automatically generated from the top network. Finally, the ultimate goal of the software synthesis in RVC is to provide a tool that enables to generate code from CAL actors as well as schedule and map the network onto SW architectures. To this end, network analysis and CAL coding practice rules may lead to compile-time scheduling of MPEG standards.

V

  ar var → Lval(Γ(var)) B(e 1 , op, e 2 ) → BinOp(op, T (e 1 ), T (e 2 )) U (op, e) → U nOp(op, T (e)) I(host, e) → Lval(host, Index(T (e), 0)) Assign(e dst , e src ) → T (e dst ) App(e f un , e args ) If (e cond , e then , e else ) → newV ar() The statement list returned for side-effect free expressions is empty. An assignment returns a Set instruction, a function application and a Call instruction with result placed in β while a conditional returns a statement of the form: If(e c , e t , e e ) (e c , s c ) = T (e c ), (e t , s t ) = T (e t ) (e e , s e ) = T (e e ) [s c ; If (T (e c ), [s t ; β = e t ], [s e ; β = e e ])]

Fig. 1 .

 1 Fig. 1. 2D-IDCT CAL network

Table 1 .

 1 list) e U(op, e) op e B(e 1 , op, e 2 ) (op e 1 ) e 2 App(e, e 1 , e 2 , . . . , e n-1 , e n ) (. . . ((e e 1 ) e 2 ). . . e n-1 ) e n If(e cond , e then , e else ) ((if e cond ) e then ) e else Lambda([p 1 , p 2 , . . . , p n ], [v 1 = e 1 , . . . , v n = e n ], e ) λp 1 .λp 2 . . . . λp n . let v 1 = e 1 in . . . let v n = e n in e Conversion rules

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

http://opendf.sourceforge.net/