Adnan Bouakaz
email: adnan.bouakaz@irisa.fr

Isabelle Puaut
email: isabelle.puaut@irisa.fr

Erven Rohou
email: erven.rohou@inria.fr

Predictable Binary Code Cache: A First Step Towards Reconciling Predictability and Just-In-Time Compilation

Keywords: Virtualization, Just-in-time (JIT) compilation, Worst Case Execution Time (WCET) estimation, static analysis, binary code cache

Virtualization and just-in-time (JIT) compilation have become important paradigms in computer science to address application portability issues without deteriorating average-case performance. Unfortunately, JIT compilation raises predictability issues, which currently hinder its dissemination in real-time applications. Our work aims at reconciling the two domains, i.e. taking advantage of the portability and performance provided by JIT compilation, while providing predictability guarantees. As a first step towards this ambitious goal, we study two structures of code caches and demonstrate their predictability. On the one hand, the studied binary code caches avoid too frequent function recompilations, providing good average-case performance. On the other hand, and more importantly for the system determinism, we show that the behavior of the code cache is predictable: a safe upper bound of the number of function recompilations can be computed, enabling the verification of timing constraints. Experimental results show that fixing function addresses in the binary cache ahead of time results in tighter Worst Case Execution Times (WCETs) than organizing the binary code cache in fixed-size blocks replaced using a Least Recently Used (LRU) policy.

I. INTRODUCTION

The productivity of embedded software development is limited by the growing diversity of hardware platforms. This trend is driven by many reasons. The main forces at play include economics and technology. Time-to-market and price pressure favor designs that integrate off-the-shelf components over complete redesigns. Process variability in the most recent technologies increases the probability that, for a given product, parts of a component are defective and must be turned off [START_REF] Duranton | The HiPEAC Vision[END_REF].

One way to address this heterogeneity is the introduction of virtualization [START_REF] Bertin | Compilation and virtualization in the HiPEAC vision[END_REF]. Programs are no longer compiled to native code, but rather target a platform-neutral bytecode representation. A virtual machine is in charge of efficiently running the bytecode on actual hardware. Virtualization is a well-established technology that has become important in computer science research and products; virtual machines are used in a number of subdisciplines ranging from operating systems to processor architectures.

Traditional compilation flows consist in compiling program source code into binary objects that execute natively on a given processor. Processor virtualization splits that flow in two steps: the first step consists in compiling the program source code into a processor-independent bytecode representation, whereas the second step provides an execution platform that can run this bytecode on a given processor. This latter step is achieved either by a virtual machine interpreting the bytecode, or by a just-in-time (JIT) compiler translating the bytecodes into binary code at run-time for improved performance.

Many applications have real-time requirements. The success of real-time systems relies upon their capability of producing functionally correct results within defined timing constraints. To validate these constraints, most schedulability analysis methods require that the worst-case execution time (WCET) estimate of each task be known. The WCET of a task is the longest time it takes when it is considered in isolation. Sophisticated techniques are used in static WCET estimation techniques [START_REF] Wilhelm | The worst-case executiontime problem -overview of methods and survey of tools[END_REF] to produce both safe and tight WCET estimates.

JIT compilers, because they perform many operations at run-time, raise predictability issues that hinder their dissemination in real-time applications. Our work aims at reconciling the two domains, i.e. benefit from the portability and performance provided by JIT compilation while providing predictability guarantees. This is an ambitious goal which requires introducing determinism in many currently non-deterministic features, e.g. bound the compilation time, provide deterministic data and code allocation schemes, provide a predictable binary code cache. This paper is a first step towards the use of JIT compilation in real-time systems: we study two structures of binary code caches and compare their predictability. On the one hand, the studied binary code caches avoid too frequent function recompilations, providing good average-case performance. On the other hand, and more importantly for the system determinism, we show that the behavior of the code cache is predictable, in the sense that one is able to safely predict, upon every function call or return, if the target function is resident in cache. This lets us compute an upper bound of the number of function recompilations, which can be incorporated to compute functions' WCET and thus verify if the overall system meets its timing constraints.

The contributions of our paper are threefold:

• Firstly, we study two structures of binary code caches that speed-up program average-case performance, for systems using JIT compilation; • Secondly, we propose a static analysis method for each cache structure, that provides safe upper bounds of the number of function re-compilations, thus demonstrating the code caches predictability; • Lastly, experimental results compare the worst-case performance of the two cache structures, and give insight on the parameters having an impact on their behavior. While there is a wealth of literature concentrating on the worst-case behavior of hardware caches, to the best of our knowledge, our work is the first analysis of a binary code cache in the context of just-in-time compilation.

The rest of the paper is organized as follows. Section II surveys related work. Section III gives a more detailed specification of the problem addressed in the paper, as well as the underlying assumptions. Section IV presents two code cache structures and the static analysis methods, based on abstract interpretation, used to bound the number of function recompilations. Section V provides experimental results that demonstrate that the worst-case number of recompilations can be predicted in reasonable time, and analyzes the factors impacting the superiority of a code cache structure over another one. Section VI concludes the paper with a summary of the paper contributions, as well as future directions.

II. RELATED WORK

Processor-independent bytecode representations (e.g. Java bytecode, CLI) ease the execution of applications on a wide range of hardware platforms. Two main directions can be followed to execute the bytecode efficiently. On the one hand, hardware support for bytecode execution can be used: entirely hardware-implemented virtual machines like JOP [START_REF] Pitter | A real-time Java chip-multiprocessor[END_REF], that provides full support for the predictable execution of Java (time-bounded execution of Java bytecodes, hardwaremanaged object and method caches); Jazelle [START_REF] Arm | ARM Jazelle technology[END_REF] moves interpretation into hardware for the most common simple Java bytecode instructions. On the other hand, JIT compilation may be used to generate binary code on-the-fly. Our work focuses on application portability at the bytecode level and relies on JIT compilation to achieve the same performance as classical compilers (referred to as ahead-of-time -AOTcompilers) 1 .

Validating timing constraints requires that an upper bound of the Worst Case Execution Time (WCET) of every piece of software be known. Many WCET estimation methods and tools have been devised in the last two decades [START_REF] Wilhelm | The worst-case executiontime problem -overview of methods and survey of tools[END_REF], mostly for code generated by AOT compilers.

Static WCET estimation methods need to work at a highlevel to determine the structure of a program's task (socalled high-level analysis). They also work at a low-level, using timing information about the target hardware (low-level analysis). By combining those two kinds of analyses through a calculation phase, the WCET estimation tools give an upper bound on the time required to execute a given task on a given hardware platform. WCET analysis for interpreted bytecode was first considered in [START_REF] Bernat | Portable worst-case execution time analysis using Java byte code[END_REF] for Java bytecode, concentrating on high-level analysis and WCET computation. In contrast to [START_REF] Bernat | Portable worst-case execution time analysis using Java byte code[END_REF], we focus on JIT compilation rather than interpretation. The work [START_REF] Bernat | Portable worst-case execution time analysis using Java byte code[END_REF] was extended to address the machine-dependent lowlevel timing analysis in [START_REF] Bate | Low-level analysis of a portable Java byte code WCET analysis framework[END_REF]. This latter paper concentrates on bytecode timing information and on the support for pipelining effects and does not consider caches.

At the low-level, static WCET analysis is complicated by the presence of architectural features that improve the performance of the hardware. In particular, for general-purpose processors, many static analysis methods have been proposed in order to produce WCET estimates on architectures with hardware caches: instruction and data caches, cache hierarchies, support for multiple cache replacement policies [START_REF] Theiling | Fast and precise WCET prediction by separated cache and path analyses[END_REF], [START_REF] Mueller | Timing analysis for instruction caches[END_REF], [START_REF] Heckmann | The influence of processor architecture on the design and the results of WCET tools[END_REF], [START_REF] Hardy | WCET analysis of multi-level non-inclusive set-associative instruction caches[END_REF]. Related studies have focused on code positioning for minimizing respectively average-case execution times [START_REF] Garatti | FICO: A fast instruction cache optimizer[END_REF] and WCET estimates [START_REF] Garatti | FICO: A fast instruction cache optimizer[END_REF], [START_REF] Lokuciejewski | WCET-driven cache-based procedure positioning optimizations[END_REF]. The static analyses of the two binary caches presented in this paper are based on the same foundations as the analysis of hardware caches [START_REF] Theiling | Fast and precise WCET prediction by separated cache and path analyses[END_REF], the differences coming from the more complex cache structures that can be implemented in software, and the granularity of cache entries (entire functions vs. memory blocks).

WCET analysis for architectures with hardware support for bytecode execution is presented in [START_REF] Harmon | A modular worstcase execution time analysis tool for Java processors[END_REF], [START_REF] Kirner | Modeling the function cache for worstcase execution time analysis[END_REF], [START_REF] Schoeberl | Worst-case execution time analysis for a Java processor[END_REF] for the JOP Java processor. WCET estimation in JOP is simplified by the presence of time-predictable execution of instructions, the most complex architectural element to be analyzed being a hardware-implemented method cache. The method cache implements three management policies: a fixed-size 1-method cache, a fixed-size 2-method cache and a more complex variable-method cache organized in fixed-size blocks, using a FIFO replacement policy. [START_REF] Harmon | A modular worstcase execution time analysis tool for Java processors[END_REF] includes simple analysis methods for the two most simple cache structures, while [START_REF] Kirner | Modeling the function cache for worstcase execution time analysis[END_REF] and [START_REF] Schoeberl | Worst-case execution time analysis for a Java processor[END_REF] analyze the variable-method cache. Similar to our work, the static analysis of JOP method cache transposes the methods initially designed for general-purpose hardware caches. However, unlike [START_REF] Harmon | A modular worstcase execution time analysis tool for Java processors[END_REF], [START_REF] Kirner | Modeling the function cache for worstcase execution time analysis[END_REF], [START_REF] Schoeberl | Worst-case execution time analysis for a Java processor[END_REF], since our binary code cache is managed in software, more sophisticated cache structures and replacement policies can be designed and analyzed.

While many studies have been conducted for the timing analysis of real-time software, to the best of our knowledge, there is no attempt so far to provide predictability guarantees for systems using JIT compilation. Our work is a first step towards this ultimate objective.

III. PROBLEM STATEMENT

Reconciling predictability and JIT compilation is an ambitious goal. After a brief introduction to JIT compilation and its use of a code cache to avoid too frequent re-compilations ( § III-A and III-B), we present in § III-C the assumptions and restrictions made throughout the paper to focus on a specific predictability issue of JIT compilation: the management of the code cache.

A. JIT compilation

Just-in-time compilation is used to speedup the execution of bytecode compared to interpretation alone. The JIT compiler is in charge of translating the bytecode representation of the application into native code, ready to be executed. This translation occurs just-in-time, when a function is about to be executed, when no native code exists for it yet. Never executed functions are never compiled. Some systems compile all functions ahead of time [START_REF] Auerbach | Design and implementation of a comprehensive real-time java virtual machine[END_REF], at the cost of an increased startup time. Some other systems have a policy to first interpret the bytecode to avoid the penalty of compiling a function that executes only a few times. In this case, the JIT compiler will run as soon as the virtual machine has detected a hot function [START_REF] Kotzmann | Design of the Java HotSpot TM client compiler for Java 6[END_REF]. Even more advanced systems have a policy in which functions are first interpreted; they are compiled when the execution frequency reaches a first threshold, but without applying any optimization to keep compilation time low; when a second threshold is reached, the function is compiled again at a higher optimization level. The compilation time overhead increases each time, but there is a hope to recoup it when running a faster version of the function many more times.

B. Code cache

The JIT compiler places the generated native code in a dedicated memory area called the code cache. This size of this area is limited by the RAM size. Similar to a hardware cache, when no room is available for a new entry, some other entries must first be evicted. Note that arbitrarily complex cache structures and replacement policies can be used since the cache is implemented in software. Some systems may even implement several techniques and choose the most appropriate one based on the results of the static analysis.

In the case of the binary code cache, cache entries are entire functions. Because they are of different sizes, memory fragmentation might be introduced.

C. Problem statement and assumptions

JIT compilation has many advantages regarding averagecase performance as compared to bytecode interpretation. Its major drawback in a real-time environment is that it is a new source of non-determinism, since in the most complex systems, a given function may be compiled several times at unpredictable time instants. A function will necessarily be compiled the first time it is called (cold miss), but could also be recompiled in two other situations:

1) when the run-time system decides that a higher optimization level would be beneficial; 2) when the function has been evicted from the cache since the last time it was executed. This might occur because of a capacity miss (the function has been evicted because the code cache is full) or because of a conflict miss (a function with an overlapping address range has been loaded since the last function execution). One of our contributions is to analyze the predictability of two code cache structures, i.e. the computation of the maximum number of times each function will be compiled.

The determination of the worst-case number of compilations is based on static analysis of the application code, that detects at each call and return point if the access to the code cache will be a hit or a miss; the compilation time can then be added to the task WCET.

In order to concentrate on the binary code cache predictability, it is assumed that:

• all executed code is compiled, no code is interpreted; • all code to be executed is statically known (no dynamic code loading); • function sizes for the target architectures are known (measured or estimated); • functions are compiled at function call or return points only, when absent from the code cache; • there is only one level of optimization. Moreover, since our focus is on code cache management, other sources of unpredictability raised by JIT compilers (predictability of compilation time, garbage collection, object allocation) are considered outside the scope of the paper.

IV. CODE CACHE STRUCTURES AND ANALYSIS

In this section, we first briefly review the concepts and notations used by our static analyses. We then describe the proposed cache structures and their analyses. b) Abstract interpretation applied to a code cache: A binary code cache is a cache containing the compiled code of the functions likely to be reused in the future. What we wish to determine is whether or not the function's binary code is guaranteed to hit the code cache when a function call/return instruction occurs (Must analysis). In such a context, the concrete domain D is the actual contents of the binary code cache. The abstract domain D is the domain of function identifiers F (f i , f j denote function identifiers). Upon the fixed point analysis convergence, all function calls and returns are assigned a classification: HIT if the function is in the abstract 1. Update and Join functions for fixed-size blocks with LRU replacement cache state (ACS), meaning that the function is guaranteed to hit the code cache, or MISS otherwise. The classification will be used to determine function WCETs using classical WCET estimation methods [START_REF] Wilhelm | The worst-case executiontime problem -overview of methods and survey of tools[END_REF].

f f f f f f f f f f f f f f f f f f Fig.
B. First structure: fixed-size blocks with LRU replacement a) Cache structure: For this first structure, the code cache is decomposed in fixed-size blocks. The block size is equal to the size of the largest binary code of all program functions. The rationale behind the selection of a fixed size for cache blocks is to eliminate external fragmentation, possibly at the cost of increased internal fragmentation. The replacement policy for this cache structure is the LRU (Least Recently Used) replacement policy, selecting the least recently executed function in case of eviction. LRU is known to be the most amenable to accurate analysis [START_REF] Reineke | Timing predictability of cache replacement policies[END_REF].

b) Analysis: Analyzing such a cache structure is a straightforward extension of the analysis of fully associative hardware caches proposed in [START_REF] Theiling | Fast and precise WCET prediction by separated cache and path analyses[END_REF]. To determine whether a function is definitely in the cache, we use abstract cache states (ACS) where the position of a given function in the abstract cache state is an upper bound of the function ages in the LRU stack at run-time.

Fig. 1 depicts how the ACS are modified by the Update and Join functions in the abstract domain.

• The Update function updates the ACS when call and return instructions are found in the control flow graph (for all other instructions, Update is the identity function). The function simply updates the ages in the abstract cache state according to the LRU replacement policy. In the figure, when a call to f 4 is encountered, the ages of f 1 , f 3 and f 5 in the ACS are updated accordingly. relationships do not overlap in the code cache (see next paragraph for details). Upon a cache miss when calling, or returning to, a given function f , all functions that conflict with f are evicted from the cache, before f is compiled and its binary code inserted in the cache. An example of function layout is given in Fig. 2.

b) Analysis: The ACS for this second cache structure is the set of function identifiers for the functions guaranteed to be in the code cache at the considered program point. In contrast to the first cache structure, there is no concept of function age.

Functions Update and Join are defined as follow (see Fig. 3 for an example based on the code layout of Fig. 2):

• The Update function modifies ACSs in case of function calls and returns only. If the ACS already contains the function, it is left unmodified. Otherwise, the function identifiers of all conflicting functions are removed from the ACS, and the identifier of the called function is inserted. On the example, after f 1 starts execution, the ACS contains f 1 . When f 2 is called within f 1 , the ACS contains f 2 instead of f 1 since f 1 and f 2 conflict. When inside the loop f 1 calls f 3 , both function identifiers are in the ACS because they are not in conflict with each other. • The Join function is the intersection of the input ACSs.

On the example, two ACSs are joined at the end of the conditional construct; only f 1 is guaranteed to be in the code cache at this point.

Layout computation

The second studied cache structure requires the address range of every functions to be computed. We developed two methods for that purpose.

a) Sequential (baseline): Functions are statically assigned an address range through a sequential scan of the functions according to their declaration order. A function is placed after the previously placed function if there is enough available room in the code cache, or at the start address of the cache otherwise. As an example, Fig. 2 corresponds to the layout generated for an applications with five functions declared according to the order f 1 ; f 3 ; f 4 ; f 2 ; f 5 . This first layout generation method ignores caller-callee relationships between functions and therefore will only be used as a baseline layout generation method to evaluate the WCET-directed approaches detailed hereafter.

b) WCET-directed heuristics: We defined two greedy WCET-directed layout computation heuristics, named respectively WCEP and WCfreq. They operate as follows:

• First, functions are ordered according to their potential for WCET reduction weight(f) (as shown later, the two WCET-directed variants differ by their definition of weight(f)). • Functions are scanned in decreasing order of weight(f).

Each function f is placed by executing the algorithm shown below: end if 10: end for 11: f.start = first address in LI f; 12: f.end = f.start + f.size;

Algorithm
In the algorithm, variable LI f is the set of address intervals that minimize the conflicts between f and already placed functions (variable PlacedF). LI f , initially set to the whole cache area (line 1), is progressively refined to avoid conflicts with already placed functions (loop in lines 3-10). Placed functions f i are sorted by decreasing values of a cost function conflict cost(f i , f ), a large value meaning that a conflict between f i and f should be avoided as much as possible. conflict cost(f i , f j ) is defined as 1 dist(fi,fj ) * compilation time(f j ), with dist(f i , f j ) the distance between f i and f j in the program call graph considered as non-directed (in the example given in Fig. 2, ∀i = 1, dist(f 1 , f i ) = 1, and ∀i, j, i = j, dist(f i , f j ) = 2). compilation time(f j ) is an upper bound of the compilation time of function f j (see Section V).

The set of possible addresses for function f reduces (line 3) every time a conflict with a previously placed function is avoided. When all avoidable conflicts have been treated, the address range for function f can then be selected. The selected address range is the last non empty interval found which can contain f (lines 11 and 12). The two WCET-oriented heuristics WCEP and WCfreq estimate the potential for WCET reduction of a function f through a function weight(f) = freq(f)*compilation time(f). In the first heuristic, freq(f) is the frequency of execution of function f along the worst-case execution path. The idea here is to optimize function layout to reduce the length of the critical path, with the risk that the critical path changes after layout generation 2 . In the second heuristic, freq(f) is the worst-case number of times function f can be executed in the program according to the program structure only (i.e. N if a call to f is embedded in a loop that iterates at most N times, regardless of the control flow within the loop). The rationale behind this heuristic is to avoid the problem of unstable critical paths of the first heuristic while still considering function execution frequency during layout generation.

V. EXPERIMENTAL EVALUATION A. Experimental setup

We experimented our technique on the Debie software [START_REF] Holsti | Using a worst-case execution time tool for real-time verification of the DEBIE software[END_REF] developed by European Space Agency, that monitors space debris and micrometeoroids in situ by detecting impacts using mechanical and electrical sensors. The program contains periodic and sporadic tasks. Table I lists the characteristics of the analyzed tasks. The second column shows the number of functions of the task, the third and fourth column respectively show the total size of the benchmark, and the size of the largest function. Some functions are shared between tasks (hence the repeated maximum size across rows).

The performance metric used to compare the two proposed cache structures is the WCET of every task. We estimate it using the state-of-the-art static WCET technique IPET [START_REF] Puschner | Computing maximum task execution times -a graph based approach[END_REF] (Implicit Path Enumeration Technique). In IPET, program flow and basic-block execution time bounds are combined into sets of arithmetic constraints. Each basic block and edge in the task control flow graph is given a time value (t i ), expressing the upper bound of the contribution of that entity to the total execution time, and a count variable (f i ), corresponding to the number of times the entity is executed. An upper bound is determined by maximizing the sum of products of the execution counts and times (Σf i × t i ), where the execution count variables are subject to constraints reflecting the structure of the task and possible flows. The result of an 2 Critical path changes could be handled by re-evaluating the critical path in the course of the algorithm execution, at the cost of longer execution time for layout generation. We show in Section V that for the codes we have analyzed, management of critical path instability does not deserve the cost of an iterative solution. IPET also provides a worst-case count f i for each basic block, thus identifying the critical path. We used the SCIP ILP solver [START_REF] Achterberg | Constraint Integer Programming[END_REF] for WCET computation. Time values t i for basic blocks are computed as follows. First, for the sake of simplicity, we assume that each bytecode instruction takes one cycle to execute. In particular, hardware cache effects are not taken into account (hardware caches have an orthogonal impact and can be handled by extensions of classical techniques like [START_REF] Theiling | Fast and precise WCET prediction by separated cache and path analyses[END_REF]). Second, when a call or return instruction is found in a basic block, the analyses detailed in Section IV classify it as a hit or a miss. In the latter case, a compilation time is added to the time value of the basic block containing the call/return instruction.

We opted for a compilation time of the form a × x + b, where x is the size of the function in bytes, and a and b are two constants characterizing the JIT compiler. The rationale behind this formula is that compile time consists in a startup time and compilation speed (a and b respectively). JIT compilers run under severe constraints and cannot afford any non linear algorithm 3 . We also confirmed this behavior by measuring the compile time of the open source JIT compiler Mono [START_REF]The Mono Project[END_REF] for a wide range of functions. Fig. 4 depicts the variation of compilation time (in milliseconds) with the function size (in bytes) for over 600 functions taken from the Mediabench suite [START_REF] Lee | MediaBench: A Tool for Evaluating and Synthesizing Multimedia and Communications Systems[END_REF], on a 3.07 GHz Intel Xeon. Note that the objective of our present work is not determining the WCET of the JIT compiler itself, rather the behavior of the code cache. Hence, these numbers are only meant to inject realistic numbers in our model, and to determine realistic worst-case execution paths.

B. Results

Experimental results are presented in Fig. 5 and Fig. 6. For every analyzed task, the figures give the task's WCET for varying cache sizes (in bytes). We observed that the fixedlayout heuristics WCEP and WCfreq give identical results in all cases, they are reported only once under the name FL-heuristic. For the six tasks we analyzed, the problem of unstable critical path we anticipated in Section IV has no impact on the heuristics' results.

Fig. 5 illustrates all the proposed structures: fixed-size blocks with LRU (FSB-LRU), fixed-layout sequential (FLseq) and FL-heuristic. Fig. 6 does not show FSB-LRU and focuses on a reduced range of cache sizes to magnify lowerorder phenomena. It also shows a second version of each analysis in which each outermost loop has its first iteration peeled 4 . Finally, it depicts the WCET of every task assuming a perfect code cache (the compilation time of every function is accounted for exactly once).

a) General observations: As expected, the WCET globally decreases when the cache size increases. Nevertheless, there are some irregularities in the behavior of the layout determination heuristics. These glitches are explained by threshold effects: to lower the algorithmic complexity, the heuristics approximate conflict costs between functions. At the same time, functions cannot be split in the code cache. A single byte difference in the cache size may relocate a number of functions and have drastic effects. This is especially true at small cache sizes.

We observe that for all benchmarks and most cache sizes, the FSB-LRU structure performs worse (i.e. yields higher WCET) than the fixed-layout structure. This comes from two factors:

• Memory fragmentation: the block size of FSB-LRU is the size of the largest function, thus introducing potentially large internal fragmentation in blocks when function sizes are very heterogeneous; • Replacement strategy: in the FSB-LRU structure, the cache replacement policy (LRU) is fixed and independent of the application call patterns. In contrast, FL-heuristic structures compute the layout ahead of time based on some knowledge of the application. They have an opportunity to adapt the cache replacement to the application call pattern.

Having a closer look at the behavior of the FSB-LRU structure, we notice its very poor worst-case performance when the cache is small. Recall from Table I that, for example, the largest function (and hence the cache block size) of Acquisition is 5052 bytes. As long as the cache is smaller than 2 × 5052 = 10104 bytes, it cannot accommodate more than one block. All calls/returns are classified as MISS. In such cases, the fixed-layout structures perform much better because the memory fragmentation is then much lower.

b) Comparing heuristics: In Fig. 6, we observe that FLheuristic provides improvements over the baseline FL-seq for small cache sizes. For large sizes, the two layout generation methods behave identically, because the cache is large enough to store all functions after they are first compiled. However, for 3 out of 6 tasks, even a large cache does not result in a WCET comparable with a perfect cache. This is due to the presence of conditional constructs within loops, like in the example of Fig. 2 (calls to functions f 3 and f 4 ). Even if the loop is peeled (see below), none of the functions called in the conditional construct can be guaranteed to be in the cache after the first iteration, and thus both functions are classified as MISS. This phenomenon, well known when analyzing hardware caches, has a deeper impact on our analysis because of the granularity of cache entries. c) Loop peeling: Loop peeling improves the analysis tightness by detecting that a function, called during the first iteration of the loop, will be resident in the following iterations. All tasks benefit from peeling, but its effectiveness clearly depends on the tasks code structure (number of function calls within outer loops). For instance, the improvement for Acquisition is lower than for the other tasks, because there are fewer function calls in loops.

Improved tightness is obtained at the cost of higher computation time. Fig. 7 illustrates this trade-off: all WCET data points of Fig. 6 are represented with their computation time (in seconds). The left-most part of segments represent analyses without peeling (faster to compute, looser WCET), the rightmost part represents the same analysis with peeling (slower, but tighter WCET). The six clusters denote the six tasks. We observe that peeling always improves the WCET, sometimes by more than an order of magnitude. Computation time, however, can also increase significantly.

VI. CONCLUSION

JIT compilation has become an important tool to address application portability issues without deteriorating averagecase performance. Unfortunately, JIT compilation raises predictability issues, which currently hinders its dissemination in real-time applications. As a first step towards reconciling the performance and portability benefits provided by JIT compilation with predictability considerations, we have proposed and evaluated two structures of binary code caches. On the one hand, the binary code caches we propose avoid too frequent function recompilations, providing good average-case performance. On the other hand, and more importantly for the system determinism, we show that the behavior of the code cache is predictable, and that it is possible to compute safe upper bounds of the number of function recompilations. Experimental results show that fixing the function layout ahead of time yields lower WCETs than transposing to software some standard hardware cache structures (fixed block code cache with LRU replacement).

In the short term, our future work will consider more refined cache structures, i.e. function code splitting for the FSB-LRU cache structure, or multiple statically defined cache block sizes. Our longer term future work will further explore predictability issues raised by JIT compilers in real-time systems, among others: predictability of compilation times, memory management, and code optimization.

  A. Background and notations a) Abstract interpretation: Abstract interpretation (see[START_REF] Cousot | Abstract interpretation: a unified lattice model for static analysis of programs by construction or approximation of fixpoints[END_REF] for details) is a formal method used to determine program properties statically (without program execution). Instead of representing properties in a concrete domain D (in our case, the actual code cache contents), abstract interpretation represents program properties in an abstract domain D. The relation between the concrete and the abstract domains are given by an abstraction function α : P(D) → D and a concretization function γ : D → P(D), with P(D) the powerset of D. The results of an abstract interpretation are invariants for each program point, which are represented by values in the abstract domain D. The analysis consists of a fixed-point computation on a set of data-flow equations operating on values in the abstract domain. A function Update : D×I → D describes how an instruction i ∈ I transforms the abstract value that existed before the instruction. When an instruction has multiple predecessors, a commutative and associative function Join : D × D → D combines all incoming abstract values into a single one.

1 Fig. 2 .

 12 Fig. 2. Example of code fixed layout

Fig. 3 .

 3 Fig. 3. Update and Join functions for the fixed layout cache structure

4 :

 4 ListIntervals NewLI f = LI f -[fi.start,fi.end[;

Fig. 4 .

 4 Fig. 4. JIT compilation time vs. function size

Fig. 5 .Fig. 6 .Fig. 7 .

 567 Fig. 5. WCET (in cycles) for each cache structure

•

  The Join function is applied whenever a block in the control flow graph has multiple predecessors. A function identifier f i is present in the resulting ACS if it was present in both input ACSs. Its age is the maximum function age found in the input ACSs. In the example, f 5 is not guaranteed to be in the method cache, since only the left path compiles f 5 . f 4 is definitely in the cache at the considered program point.

C. Second structure: fixed layout cache a) Cache structure: In this second structure, every function is assigned a start address ahead of time. Start addresses are computed such that functions with heavy caller-callee

Note that JIT compilers can even surpass AOT compilers because they take advantage of run-time information, not available ahead of time, to apply focused optimizations[START_REF] Cohen | Processor virtualization and split compilation for heterogeneous multicore embedded systems[END_REF].

Special algorithms are developed when standard techniques are too expensive -for example the linear scan register allocator[START_REF] Traub | Quality and speed in linearscan register allocation[END_REF].

Loops are virtually peeled, for analysis purposes only, no physical loop peeling is undertaken.

ACKNOWLEDGMENTS

The authors would like to thank Benjamin Lesage, Damien Hardy and André Seznec, for fruitful brainstorming.


Erven Rohou

Andrea Carlo Ornstein

Ali Erdem Özcan

Marco Cornero

Ali Erdem Özcan

Combining Processor Virtualization and Component-Based Engineering in C for Many-Core Heterogeneous Embedded MPSoCs

The design of embedded systems is driven by strong constraints in terms of performance, silicon area and power consumption, as well as pressure on the cost and time-to-market. This has three consequences: 1) many-core systems are becoming mainstream, but there is still no satisfactory approach for distributing software applications on these platforms; 2) these systems integrate heterogeneous processors for efficiency reasons, thus programming them requires complex compilation environments; 3) hardware resources are precious and low-level languages are still a must to exploit them fully. These factors negatively impact the programmability of many-core platforms and limit our ability to address the challenges of the next decade.

This paper devises a new programming approach leveraging processor virtualization and component-based software engineering paradigms to address these issues all together. We present a programming model based on C for developing fine grain component-based applications and a toolset that compiles them into a processor-independent bytecode representation that can be deployed on heterogeneous MPSoCs. We also discuss the effectiveness of this approach and present future directions that will have a key role in addressing the above challenges.

I. Introduction

Compared to the general purpose computing world, embedded consumer systems are characterized by particularly stringent efficiency requirements in terms of performance, power and area. SoC (System-on-Chip) vendors used to design application specific hardware components (IPs) controlled by a host processor for implementing complex operations. This process is no longer valid because of today's technological and market constraints. Non-recurring engineering costs of silicon manufacturing are becoming so high that the same IP must be reused in many products. Short time-to-market also plays in favor of reuse. In other words, hardware needs to be more programmable. In this context, the design of software-based solution substituting the hardware IPs becomes one of the most critical topics of the overall production process of SoCs.

Problem Statement Unfortunately, designing software systems for those constrained platforms is a complex issue. The reasons can be categorized as follows.

1) Large scale multi-processing is a must. For almost 30 years, general purpose processors as well as embedded systems followed Moore's law. Performance used to "automatically" double every 18-24 months. However, since 2002, diminishing performance return, as well as increasing power consumption, and the approaching "temperature wall" made the microprocessor industry follow a new path for performance: the multicore approach. While it is true that embedded system have always been heterogeneous multicores, several studies take parallelism to unprecedented levels and forecast thousands of cores on a chip by the end of the next decade [START_REF] Asanović | The Landscape of Parallel Computing Research: A View from Berkeley[END_REF], [START_REF] De Bosschere | High-Performance Embedded Architecture and Compilation Roadmap[END_REF]. Programming distributed applications has always been difficult, even in general purpose computing, because of the lack of convenient programming abstractions and tools [START_REF] Mattson | Parallel programming: can we please get it right this time?[END_REF]. The situation is worse for SoC platforms, with minimum runtime support, and no alternative to low-level programming languages. This has always constituted a big barrier to the productivity. Given the new order of magnitude of cores, the exploitation of the available hardware is a major challenge of the coming decade.

2) Heterogeneity is unavoidable. Although the homogeneization of hardware platforms aims at reducing production costs, modern embedded platforms continue to integrate heterogeneous computing nodes (e.g. DSP, VLIW, etc.) for several reasons. First, suitable hardware support (i.e. instruction sets, data representation, etc.) is key to satisfying the performance requirements of different kinds of applications executed on a single chip. Second, these computing nodes are always evolving to enjoy the best technological solutions in the market. Beside evolving architectures, heterogeneity is a source of difficulties since it requires the software development kits (compilers, debuggers, profilers, etc.) to be ported and maintained, and the developers to be trained on them. Tools for different cores are likely to come from different vendors and to use different technologies, yielding to integration problems. The source code is likely to be written with conditional compilation directives (#ifdef) in order to adapt to each compiler and to best exploit each architecture. While they are of no theoretical nature, these issues are a significant burden (and cost) to software companies.

3) Physical resources are precious. Embedding software in consumer systems has always been a challenge for satisfying the performance requirements on top of limited constrained physical resources. Even though an unprecedented number of cores is expected soon, silicon area (be it CPU or memory) directly translates into cost. Each core must be as efficient as possible. Henceforth, software developers are still not free to enjoy high-level programming languages and run-time environments such as garbage collectors, exception handlers, and rich libraries. This results in many applications being coded from scratch and reduces the productivity while increasing the maintenance, support and evolution costs.

These issues motivate many language-oriented research projects [START_REF] Consel | Spidle: a DSL approach to specifying streaming applications[END_REF], [START_REF] Thies | StreamIt: A language for streaming applications[END_REF]. However, some pragmatic concerns (legacy, efficiency, toolset availability, etc.) make industrial solutions evolve with small steps. In particular, since many multimedia processors do not support higher level languages such as C++ or Java, the C language remains the de facto standard, although it does not sufficiently deal with heterogeneity and multi-processing issues. Indeed, the C language implies the use of different development kits (compiler, debugger, etc.), potentially coming from different vendors, for each processor. Beside the overhead related to their installation and maintenance, these tools may behave differently (command-line flags, error messages, etc.), and may imply the source code to be specialized for their own header files, intrinsics and library functions 1 . In addition, the lack of specific abstractions for application distribution makes plain C programs very difficult to deploy efficiently on multiple processors.

Contribution In the past, some research and industrial proposals partially addressed these issues. On the one hand, processor virtualization provided a way of dealing with heterogeneous target platforms. On the other hand, component-based software engineering approach improved the software modularity and contributed to the development of distributed systems.

The main contribution of this paper is the design and implementation of a toolset combining these two paradigms, for the C language, in order to start addressing the above issues all together. Using this toolset, legacy code written in C can be encapsulated into welldefined components programming model with limited reengineering effort. These components can then be composed using an Architecture Description Language (ADL) that describes the software architecture of the system, and compiled into a target independent bytecode representation. Using this toolset, programmers can develop reusable binary component libraries that can be used by system architects for composing applications to be deployed on heterogeneous multiprocessor SoC (MPSoC). Newly developed components, on the other hand, can be envisioned either in C or in any higher-level language that can be compiled to the bytecode representation.

In addition, the combination of component-based design with such a target independent bytecode representation opens various perspectives that leverage the performance of embedded systems. First, the design flexibility can be increased by mapping components on heterogeneous processors at deployment time. In particular, this lets programmers deal with memory hierarchy as an orthogonal issue. Second, important memory and performance optimizations can be obtained by on-board generation of interface-specific communication bridges between remote components.

Outline This paper is organized as follows. Section II overviews the paradigms we propose to combine, and it presents the state-of-the-art on these domains. Section III presents our proposal. Section IV discusses its effectiveness and presents some ideas that we will investigate in future work. Finally, we conclude in Section V.

II. Related Work

This paper proposes a new methodology and toolset for programming heterogeneous MPSoCs in the C language. We build upon previous works on processor virtualization and component based software engineering. This section reviews previous work related to both paradigms.

A. Processor Virtualization

Processor virtualization first appeared for deploying programs on computers connected through the Internet, and became a well established technique for dealing with the processor heterogeneity. While the traditional compilation flow consists in compiling program sources into binary objects that can be natively executed on a given processor, processor virtualization splits that flow in two parts. The first part -the front-end -compiles the program source code into a processor-independent bytecode representation.

The second part -the back-end -provides an execution platform to run this bytecode on a given processor. The back-end may either be a virtual machine interpreting the bytecode or a dynamic compiler translating the processorindependent bytecode to native binary at load time or run time in order to improve the execution performance. This split of the compilation flow has many benefits for dealing with the heterogeneity issue. First, developers can use the same development kit for compiling their programs on their workstation and debugging them on the platform. Second, the same bytecode can be loaded on a heterogeneous MPSoC, and the decision of the processor on which it will execute can be postponed until run time. Finally, split-compilation lets the back-end apply aggressive optimizations thanks to additional information computed offline by the front-end [START_REF] Cohen | Processor virtualization and split compilation for heterogeneous multicore embedded systems[END_REF].

The Java framework defines a bytecode-based virtual machine and a standard library for the Java language. The lightweight version of Java, namely Java Micro Edition, has been widely accepted in heterogeneous embedded systems in order to provide complementary capabilities, like games for cell phones or TV guides for set-top-boxes. Its use remains constrained to the host processor for the non-critical part of the application. Components models are supported (see Section II-B), but the C language cannot be compiled to the Java bytecode.

LLVM [START_REF] Lattner | LLVM: A Compilation Framework for Lifelong Program Analysis & Transformation[END_REF] is a compiler framework that defines a lowlevel code representation appropriate for program analysis and transformation. This representation is intended to be processor-and input language-independent, and well suited for optimized code generation. Many languages, including C, can be compiled to LLVM. However, the representation is at a lower level than CLI. In addition, it has not been standardized, and, as such, is subject to changes.

The Common Language Infrastructure (CLI) [START_REF]:2006 -Common Language Infrastructure (CLI), Partitions I to VI[END_REF] is an international standard that defines a rich virtualization environment for the execution of applications written in multiple languages. Beside the .NET Framework and the .NET Micro Framework provided by Microsoft, there exist several open-source programming environments based on CLI. Component models are supported. We have previously contributed GCC4CLI [START_REF] Costa | CLI Back-End in GCC[END_REF], a C compiler that generates efficient CLI code for embedded systems. We have shown that CLI is an appropriate format for the deployment of embedded software, in terms of both code size [START_REF] Costa | Comparing the size of .NET applications with native code[END_REF] and performance [START_REF] Cornero | An Experimental Environment Validating the Suitability of CLI as an Effective Deployment Format for Embedded Systems[END_REF]. We also demonstrated several flexible compilation flows from C to CLI [START_REF] Rohou | CLI-Based Compilation Flows for the C Language[END_REF].

B. Component-based Software Engineering

Although the foundations of composing the software systems by assembling components appeared very early [START_REF] Mcilroy | Mass produced software components[END_REF], component-based programming has been widely ac-cepted as a new programming paradigm in the last decade for succeeding the object-oriented programming [START_REF] Szyperski | Component software: beyond object-oriented programming[END_REF]. In a nutshell, component-based programming is about structuring the software modules as independent components that fulfill well-defined specifications in terms of client (required services) and server (provided services) interfaces. The strong encapsulation of data and behavior and the capture of the software architecture in terms of components, interfaces and their interconnections makes this approach suitable for distributing complex applications on multiple processors. Furthermore, these features allow the use of many appropriate design tools supporting the assembly, the verification and the distributed deployment of components using a description of the software architecture (ADL).

Many component models have been used in general purpose computing during the last decade for improving program modularity and managing software distribution. The most adopted ones include the COM family (COM, COM+, DCOM) from Microsoft, the CORBA Component Model (CCM) from OMG, the Enterprise Java Beans (EJB) from Sun Microsystems and the Open Services Gateway Initiative from OSGI Alliance. These component models are in general tailored for powerful workstation environments and most of the services that they implement (e.g consistency, security, failure recovery, etc.) fit neither the requirements nor the computational budget of MPSoCs.

Component-based programming has also appeared in embedded platforms in recent years. Real Time Software Components [START_REF]Real-Time Software Components[END_REF] (RTSC) from Texas Instruments provides an ADL toolset based on JavaScript and a packaging format for building modular system software from component libraries. OpenMAX [START_REF]OpenMAX Development Layer API Specification, Version 1.0.1[END_REF] from Khronos provides a component-based middleware for easing the integration of audio/video codecs for building complex multimedia applications. Both models are based on the C language, and aim at improving the software reuse. Nevertheless, they are designed for single processor systems.

There exist other component technologies especially designed for MPSoCs. DSOC [START_REF] Paulin | Distributed object models for multi-processor SoC's, with application to low-power multimedia wireless systems[END_REF] is a light-weight implementation of CORBA. It provides a toolset that generates middleware components in hardware for accelerating interprocessor communications over a given network on chip. Cecilia [START_REF]Cecilia web site[END_REF] is a C-based implementation of the Fractal Component Model [START_REF] Bruneton | The Fractal Composition Framework, The ObjectWeb Consortium -Interface Specification[END_REF] and provides a deployment environment for distributing multimedia components on heterogeneous MPSoC platforms. In addition, Cecilia provides an extensible ADL toolset [START_REF] Leclercq | Supporting heterogeneous architecture descriptions in an extensible toolset[END_REF] that allows the integration of new code generation features by third party developers. Khronos recently proposed a new standard, called Open Computing Language (OpenCL) [START_REF] Munshi | The OpenCL specification version 1.0[END_REF], for programming parallel graphics applications. OpenCL provides extensions to the C language for mapping the program data to a hierarchical memory architecture and for using a standard interface to vectorial instructions. Therefore, it requires either the Clang OpenCL compiler combined with the special runtime support for its bytecode on the target processors, or the target C compiler to be modified for supporting these extensions.

C. Combining Virtualization and Componentbased Engineering in C

While several approaches have been proposed both for processor virtualization and for component-based software engineering, to the best of our knowledge there is no prior art considering their combination with the C language.

We believe that this combination provides a promising groundwork for addressing the code generation challenges of the decade to come. That is, (i) component-based software engineering provides a suitable way of structuring software systems to be deployed on distributed systems, such as MPSoCs, (ii) virtualization helps dealing with the heterogeneity of target platforms without imposing the burden of binary compatibility on hardware designers, and (iii) the C language, which is the de facto standard for programming embedded systems, allows writing low-level code without any expensive run-time dependencies.

III. Our Proposal

Our proposal, namely Virtual Components for SoC (VC4SoC), consists in a programming toolset that enables target-independent component-based programming in C. The generated libraries are for deployment on heterogeneous MPSoCs. We first review the VC4SoC compilation flow. Then, we present its key features including the binary layout of components, the programming model used for implementing them in C, and the specific linker that maps the component implementations to the binary layout.

A. Compilation Flow

As depicted in Fig. 1, the development flow with VC4SoC consists of two parts: front-end and back-end. The front-end compiles source components into binary component libraries. It runs on a workstation. The backend is about the composition of applications from binary component libraries. It runs either on a workstation for static mapping of applications on a target platform, or on board to enjoy dynamic mapping at deployment time.

The front-end development starts with the specification of components (0). Two specific languages are involved to improve the robustness of these specifications compared to hand-written C header files. First, a strongly-typed Interface Definition Language (IDL) specifies the methods that can be used for the interaction between components.

Fig. 1. Overview of the compilation flow

The IDL allows many static verifications to be done and part of the interaction code to be generated. Second, an Architecture Description Language (ADL) specifies the set of interfaces that are provided and required by components, as well as their interconnections. The expressiveness of the ADL eases the description of complex composition schemes. Static verifications can be performed and the glue code to assemble the components can be generated.

These specification files are used for generating two separate files. The skeleton of the component is generated in CLI (1) in respect to its architecture specification. This skeleton defines the binary layout of a CLI object representing the component without the implementation of its interfaces. The implementation is provided by the programmer in C using a lightweight programming model based on standard pre-processing macros. These macros are used to access component's members such as client interfaces or private data fields. This implementation is completed with a generated header file containing the values of these macros, according to the architecture specifications (2). The implementation source files are then compiled to CLI (3) using a C-to-CLI compiler [START_REF] Costa | CLI Back-End in GCC[END_REF], [START_REF] Rohou | CLI-Based Compilation Flows for the C Language[END_REF]. Finally, a specific linker, described in Section III-B3 merges the skeleton of the component with its implementation (4).

The role of the back-end is to compose applications from a binary component library output by the frontend. The input driving this process is an ADL description specifying the top-level architecture of the application to be composed. Based on this description and the architecture specifications reflected by the binary components in CLI, the back-end generates the glue code that is required for assembling the application components and mapping them to the target execution platform (5). A typical example for glue code generated within the context of MPSoCs may be the inter-processor communication channels implementing the interactions between remote components. The glue code is directly generated in CLI on the target platform Fig. 2. Binary structure of a component in CLI using lightweight bytecode manipulation tools such as Cecil [START_REF]Cecil Library[END_REF]. Finally, a merger tool can be used for gathering the components that go on to the same processor in order to optimize their deployment on the target platform [START_REF] Cohen | Processor virtualization and split compilation for heterogeneous multicore embedded systems[END_REF].

B. Component model

VC4SoC is based on the Cecilia Component Framework 2 [START_REF]Cecilia web site[END_REF], a lightweight implementation of the Fractal Component Model [START_REF] Bruneton | The Fractal Component Model and its Support in Java," Software Practice and Experience, special issue on Experiences with Autoadaptive and Reconfigurable Systems[END_REF], [START_REF] Bruneton | The Fractal Component Model[END_REF] dedicated to the development of embedded applications and systems. This section first presents the binary layout of VC4SoC components. Then it describes the programming model and the linker tool that is designed for encapsulating standard C programs into these components.

1) Binary layout: VC4SoC provides a cost-effective implementation of components based on unmanaged CLI structures. As depicted in Fig. 2, a component at run time consists of a data structure in addition to the implementation of its methods. This is similar to the native of a C++ object. The main part of this data structure, namely component context, contains fields for implementing the set of client interfaces of the component as well as its private data members. In addition, the component context inherits interface structures for each of its server interfaces. These interface structures contain pointers giving access to the implementation of the methods implemented by the component.

In addition to the above functional fields, the component context structure is annotated with CLI metadata attributes giving supplementary information about the component's architecture (e.g. interface names, component name, etc.) This information is required by the back-end of the VC4SoC infrastructure for composing applications from 2 Cecilia was formerly called Think [START_REF] Fassino | THINK: A Software Framework for Component-based Operating System Kernels[END_REF]. binary component libraries. This metadata can be removed at run time to save memory or be kept to enjoy reflective programming.

Note that only the component context needs to be duplicated when a new instance of a component is created. Hence, the performance overhead of VC4SoC components is comparable to C++ objects, and is expected to be even less since they require only unmanaged CLI structures.

2) Programming model: VC4SoC defines a programming model for encapsulating standard C programs into the above component model. This programming model consists of few pre-processing macros that define handles for linking the implementation code written by the programmer with the skeleton code generated by the ADL compiler.

Fig. 3-b illustrates the implementation of a simple component printing a message on a printer interface. PRIVATE_DATA and DATA macros used for declaring and accessing the instance data structure of the component, respectively. The METHOD macro is used for declaring the implementation of a method provided by the component. Finally, the CLIENT macro is used for referencing a client to be invoked.

The implementation code depicted in Fig. 3-b needs to be completed with the definition of the above macros to become a correct C program. For that purpose, the frontend of the VC4SoC compiler generates a header file from the ADL of the component. As depicted in Fig. 3-a, this header file starts with the definition of PRIVATE_DATA macro which defines the component context structure and declares an instance of the latter (_this variable). DATA and CLIENT macros define accesses to this context variable. The METHOD macro mangles the name of the implemented method with the name interface and the component to which it belongs to avoid name clashes.

Careful readers may have noticed that the type definitions in the above header file do not match the binary layout presented in Fig. 2. In particular, the component context does not inherit from the server interface structures and the global definition of _this variable makes the component a singleton instance. Indeed, these are placeholders (fake definitions) intended to be substituted at linktime time by the component skeleton, generated in CLI. These placeholders are used for two reasons: first, they complete the implementation code and make it legal C code, that can be compiled with a standard C compiler; and second, they mark some fields with specific compiler attributes (e.g. ClientInterface) so that these fields can be easily located by the skeleton/implementation linker.

The benefits of generating the component skeletons in CLI rather than in C are twofold. First, CLI provides native support for modeling component interfaces and annotating data structures with additional information. This way,

p u b l i c i n t e r f a c e M a i n I n t e r f a c e { i n t main ( ) ; } p u b l i c i n t e r f a c e P r i n t e r { v o i d p r i n t ( s t r i n g msg ) ; } ;

[ P r i v a t e D a t a S t r u c t u r e ] s t r u c t MyComp data t {} ; p u b l i c u n s a f e s t r u c t MyComp context : M a i n I n t e r f a c e { [ C l i e n t I n t e r f a c e ( " p " ) ] P r i n t e r p ;

[ P r i v a t e D a t a ] MyComp data t d a t a ;

p u b l i c i n t main ( ) { r e t u r n 0 ; } } ;

(c) the architecture information is natively embedded in the binary, without the need for any adhoc extension. Second, CLI enables the inheritance of interface structures within data structures for modeling the interfaces implemented by an object. As depicted in Fig. 3-c 3 , the component skeleton uses these features for defining the component context structure matching exactly the binary layout presented in Section III-B1. On the other hand, empty bodies are generated for component's private data members and method implementations. The latters are intended to be filled with the information coming from component's implementation by the linker described in the following section.

3) Skeleton/implementation linker: As described previously, during the first part of the compilation flow, the hand-written implementation in C is compiled to CLI, and the skeleton is directly generated in CLI. They still need to be linked together in order to form a binary component. This is done by a specific linker which completes the binary skeleton file with the information coming from the implementation file.

The steps of this link process are as follows.

1) The definition of the private data members of the component is copied from the implementation file into the skeleton. This operation is straightforward since all data members are gathered in a data structure definition whose name conforms to a convention translated by the PRIVATE_DATA macro.

2) The method bodies are copied from the implementation file into the skeleton. This operation is straightforward as well since the methods to be copied are annotated using specific attributes (e.g. cli attribute in Fig. 3-a). 3) In each method body, references to the fake _this variable are replaced by accesses to private data members defined in the first step. This way, the singleton content definition that uses a global context variable _this (Fig. 3-b) is turned into standard CLI containing method implementations from which multiple instances can be created at run time. 4) Finally, a new argument is added to each method call found in method bodies in order to specify the target of the invocation. The convention used for translating the CLIENT macro helps the recognition of whether the call is directed to the component itself or to a one of its client interfaces. Note that, the skeleton/implementation linker is processor-independent since it only manipulates the CLI representation. Moreover, its implementation required limited effort thanks to the use of an existing CLI manipulation tool, namely Cecil. Such a CLI manipulation tool can also be used in the back-end of the compilation flow in order to implement optimizations such the removal of CLI attributes and the merge of multiple components into one.

IV. Discussion

A. Analysis

We have implemented the VC4SoC compiler as an extension of the Fractal ADL Compiler [START_REF] Leclercq | Supporting heterogeneous architecture descriptions in an extensible toolset[END_REF]. It accepts as input a top-level architecture description of the assembly of components for building an application. The output is an executable object in CLI. This object can then be executed on any CLI-compliant platform.

Exhaustive performance analysis would have to be performed on different heterogeneous MPSoC platforms for verifying that applications of interest developed using VC4SoC do not raise significant overheads in terms of execution time and memory footprint. Yet, previous results on component-based programming and processor virtualization paradigms -both well established -have separately demonstrated that they have acceptable overheads within the context of embedded systems. In particular, Özcan et al. [START_REF] Özcan | A Componentbased Approach for MPSoC SW Design: Experience with OS Customization for H.264 Decoding[END_REF] has shown that the fine-grained component-based re-engineering of an H.264 video decoder using the Fractal Component Model in C resulted in 1.5% overhead in execution time and about 7% overhead in memory footprint while easing notably the distribution of the decoder on multiple processors. The potential direct cost is similar to the penalty object-oriented languages incur. Moreover, Fassino et al. [START_REF] Fassino | THINK: A Software Framework for Component-based Operating System Kernels[END_REF] has shown that modular design with component-based programming may also result in better performance by designing on-demand software systems. Efficient CLI code can be generated from the C language [START_REF] Costa | Comparing the size of .NET applications with native code[END_REF], [START_REF] Cornero | An Experimental Environment Validating the Suitability of CLI as an Effective Deployment Format for Embedded Systems[END_REF], and robust and flexible compilers and toolchains are available. The performance achieved with these schemes is similar to native code [START_REF] Costa | CLI Back-End in GCC[END_REF], [START_REF] Rohou | CLI-Based Compilation Flows for the C Language[END_REF].

It is also important to note that the performance of applications developed with VC4SoC is extremely related to the performance of the target execution platform. Previous studies [START_REF] Dupont De Dinechin | Inter-Block Scoreboard Scheduling in a JIT Compiler for VLIW Processors[END_REF] show that, in the case of DSP or VLIW processors, advanced just-in-time compilation techniques may result in even more optimized code compared to static native compilation.

A limited performance penalty must also be contrasted with the significant gain in productivity and the additional flexibility brought by our approach.

Our proposal does not directly address memory hierarchy issues. However, we provide the means for the programmer to postpone the processor mapping decisions until deployment time, when the actual memory hierarchy is known. In this respect, we do not provide the policy, but the tools to implement it.

B. Limitations

The approach we presented in this paper has two main limitations that may impact the reuse of existing legacy. The first one is related to the use of a specific C compiler (GCC4CLI [START_REF] Costa | CLI Back-End in GCC[END_REF]) that we extended to recognize some annotations. In particular, we took advantage of the GCC attribute mechanism. Legacy code that uses language extensions or compiler features from another vendor might be a problem, even though we feel that our contribution to the simplification of the development environment makes the porting worth the effort in many cases. In any way, annotations are essentially used as markers that must be propagated unmodified in the CLI representation. Any other mechanism that achieves this goal can be considered. For example, we preferred attributes over pragmas simply because the GCC internals discourage the use of pragmas.

The second limitation is related to the use of processorindependent bytecode. Although the latter is unavoidable for portability on heterogeneous platforms, the use of inline assembly (asm blocks) introducing processor-specific optimizations in the C code are not supported anymore. Note that it is still possible to invoke native binary code (libraries, or hand-optimized routines) from CLI components thanks to the pinvoke mechanism [START_REF]:2006 -Common Language Infrastructure (CLI), Partitions I to VI[END_REF]. In any case, this latter approach is superior in terms or software engineering: code readability, portability, and maintenance.

C. Perspectives

The combination of processor virtualization with component-based programming opens many perspectives for embedded applications. Two of them, which we plan to investigate as future work, are discussed hereafter.

1) On-board component assembly: Current practice of quality-of-service implementation on MPSoCs consists of switching between different combinations of statically linked application mappings according to the application scenarios executed by the end-user. On heterogeneous platforms, the number of combinations becomes very significant. Henceforth, the mapping flexibility is often limited by the memory budget.

Splitting the compilation life cycle into two phases as presented in Section III-A is key to break the above limitation. This way, applications can be assembled on board just before their deployment. Furthermore, as VC4SoC components can be deployed on any processor, any application mapping can be produced at run time from a given component library.

2) On-board communication adapter generation: Automatic generation of communication adapters from IDL descriptions is a well established technique for implementing remote interactions on multi-processor systems. Nevertheless, current tools designed for the C language require a workstation to generate and compile such components. As a result, programmers must forecast the possible application mappings on different processors and specify the interfaces for which adapters must be generated. Yet, this constitutes an obstacle to the mapping flexibility.

VC4SoC components provide two features that are key to solve this issue. First, binary components can be introspected to access their interface specifications. Second, CLI bytecode can be directly generated on board using bytecode manipulation tools such as Cecil. Using these features, communication adapters can be generated dynamically when they are needed. The combination of such a tool with an on board component assembler, as discussed above, may result in a very flexible execution environment for building performance effective solutions based on heterogeneous multi-processor platforms.

V. Conclusion

This paper proposes a new programming methodology and toolset to improve the software development practice on many-core heterogeneous MPSoCs. Our approach has its roots in two well established paradigms, namely component-based software engineering and processor virtualization. Using this toolset, programmers can encapsulate legacy C code into software components with limited effort. The use of component-based programming enables the assembly of complex applications from reusable component libraries and the generation of glue code for mapping these components on a multi-processor platform. Thanks to the CLI processor virtualization technology, binary components that are output by this toolset can be deployed on any target processor of a heterogeneous system. Moreover, the latter provides programmers with an homogeneous development platform by offering them a single virtual target for all cores present on an MPSoC. This greatly simplifies the software engineering process and reduces the burden (thus, the cost) associated with software development for multiple targets or heterogeneous targets. We believe that this combination of paradigms provides a promising groundwork to address the code generation challenges of the future MPSoC platforms by defining a framework for the development of C-based applications for heterogeneous many-core platforms.

Our proposal also opens up several opportunities, which we will explore as future work. First, it makes it possible to postpone the deployment choices to run time, giving more flexibility to system designers. Second, communication adapters between components can be generated on board, and precisely tuned for the current mapping, instead of being statically generated for a given set of envisioned mappings.

Fig. 3 .

 3 Fig. 3. Excerpt of hand-written and generated files. (a) Generated header file, (b) hand-written component implementation, (c) generated component skeleton.

Target-specific source-code specialization makes the code difficult to maintain and hinders debugging on the workstation.

Note that, for readability purposes, we used C# syntax to illustrate the generated skeleton. The actual skeleton is directly generated in CLI.