Zouhir Mahani
email: z.mahani@uiz.ac.ma

Jalal Zahid
email: j.zahid@gmail.com

Sahar Saoud
email: s.saoud@uiz.ac.ma

Mohammed El Rhabi
email: elrhabi@gmail.com

Abdelilah Hakim
email: abdelilah.hakim@gmail.com

Text enhancement by PDE's based methods

In this work, we propose a new method to enhance text in document-image. Firstly, we introduce a classical model and a way to solve it by means of a non-convex optimization problem. So, a simoultaneaous estimation of the reflectance and the luminance is obtained when the non uniform illumination (also called luminance) is a smooth function and the reflectance is a function of bounded variation. We give an analyse of this problem and some conditions of existence and unicity. Then, we consider the "log" of the classical model. A new pde's model is proposed. This method is based on the resolution of an original partial differential equation (PDE) estimating the log of the luminance. We assume that the luminance is enough smooth and is the solution of a non classical second order's PDE.Then we deduce the reflectance from the estimated luminance and the acquired image. The effectiveness and the robustness of the proposed process are shown on numerical examples in real-world situation (images acquired from cameraphones). Then, we illustrate the ability of this method to improve an Optical Character Recognition (OCR) in text recognition.

Introduction

Computer vision based documents recognition could be an interesting way to dematerialize informations to manage clients and company's internal documents, offering enterprise wide fast access to business critical information while enhancing the achitecture in place. Typically the dematerialized document formats are PDF. Here, the problem could be separated as least in two steps: localization and recognition. Computer approach increases the performance of both steps, localization and recognition (see [START_REF] Wu | Model Based 3D object localization and recognization from a single intensity image[END_REF]). In the computer vision approaches, low cost cameras (webcam, cameraphone, ...) could introduce some distortions and noise artifacts, see [START_REF] Baird | The State of the Art of Document Image Degradation Modeling[END_REF] for an overview of document image degradation modeling.

The image restoration images by PDE's based models starts to produce signifiant results as images with the diffusion of documents to remove noise while preserving important information for readability ( [START_REF] Drira | Document images restoration by a new tensor based diffusion process : Application to the recognition of old printed documents[END_REF]) or to separate the back to front ink interferences ( [START_REF] Moghaddam | RSLDI: Restoration of single-sided low-quality document images[END_REF]) . These works have shown that could be improved up to 30% recognition rate of OCR by restoring the document images.

Generally speaking, an image u could be seen as the product of a reflectance v and the illumination effect I (see [START_REF] Horn | Robot Vision[END_REF]). This model has been used in [START_REF] Kim | Joint nonuniform illumination estimation and deblurring for bar code signals Optic Express[END_REF][START_REF] Dumas | An evolutionary approach for blind deconvolution of barcode images with nonuniform illumination[END_REF] to restore blurred barcode signals under nonuniform illumination.

This paper provide a new method based on an anisotropic diffusion to estimate the luminance (or the log of the luminance) of a document-image in order to enhance the text. This method could be use for example in a mobile phone scanning solution or as a first step OCR processing.

We develop previously an isotropic method with some relative success(see [START_REF] Martin | Realeyes3D SA[END_REF]). This process allows us to estimate the luminance and to enhance texts then to share or print document images. By document images, we mean all kinds of images which include some handwritten or machine printed text. The basic camera phones often produce images of lower qualities. In addition, the conditions make it difficult shooting the readability and printing of document images. Regarding the text, these conditions make it difficult to interpret the information contained in this image without proper pretreatment. We have develpped this method on a server side project, named "Qipit" : Qipit is a way to capture and share written documents with your camera phone or digital camera. Handwritten notes, signed contracts, whiteboards can be transformed into clean, crisp digital copies. After a specific treatment, this method has also directly embedded on photophones (Nokia, Samsung, Iphone . . . ). As an example, on a Nokia N73 (3.15 megapixels, Symbian OS 9.1, S60 3rd edition), the time processing is less than 6 secondes (it depends on the choosen resolution). So, we have built an OEM business with the likes of Samsung, Sanyo and others with over 100 million copies sold and shipped factory-installed by mobile phone manufacturers to date. In this paper, since we present a preliminary result, the time processing is not discussed.

Our methods can produce three kinds of documents: black and white, grayscale or color ones. In all cases, input images are color pictures. Producing color documents should be seen as a different workflow, involving mostly the same algorithms as in the grayscale processing.

Document images are supposed to be obtained from a mobile device -a cameraphone more exactly, but could also come from any digital camera. In the following, we will only suppose the device to be a cameraphone as this is the case where most of the problems occur. Basic cameraphones often produce document images with poor quality -meaning it should be really tedious or even impossible to be read by someone or by an OCR (Optical Character Recognition). Because of constraints design, cameraphones have some limitations which we have to take into account, if we want to produce legible documents.

The paper is organized as follows : section 2 gives a brief description of a camera lens. Section 3 presents the non uniform illumination problem and defines a global model. Then two methods are given as solutions, namely a natural criterion afterward a pde's based model. Section 4 describes the method and shows how to implement it. Finally, some numerical results illustrate this work in Section 5.

Description

Photographers control the camera and lens to expose the recording material (digital sensor or film) to the required amount of light. The controls include the focus of lens, the aperture of the lens (amount of light allowed to pass through the lens), the focal length and type of lens (macro, wide angle, or zoom), the duration of exposure (or shutter speed), the sensitivity of the medium to light intensity and color/wavelength, the nature of the light recording material, for example its resolution as measured in pixels or grains of silver halide.

Camera controls are inter-related, as the total amount of light reaching the image plane (the "exposure") changes proportionately with the duration of exposure, aperture of the lens, and focal length of the lens (which changes as the lens is focused, or zoomed). Changing any of these controls alter the exposure. Many cameras automatically adjust the aperture of the lens to account for changes in focus, and some will accommodate changes in zoom as well.

The duration of an exposure is referred to as shutter speed , often even in cameras that don't have a physical shutter, and is typically measured in fractions of a second. Aperture is expressed by an f-number or f-stop (derived from focal ratio), which is proportional to the ratio of the focal length to the diameter of the aperture.

Exposures can be achieved through widely differing combinations of shutter speed and aperture. The chosen combination has an impact on the final result. In addition to the subject or camera movement that might vary depending on the shutter speed, the aperture (and focal length of the lens) determine the depth of field, which refers to the range of distances from the lens that will be in focus.

The model

We suppose that the document-image u has been acquired by a cameraphone, we consider two sorts of problems due to this acquisition : image distortions and noise. Here, we adress a distortion, so-called "non uniform illumination" or variations of brihtness (see [START_REF] Gross | An image preprocessing algorithm for illumination invariant face recognition[END_REF]). These variations render image processing difficults. One of these effects is : the shadows. In image processing, a shadow is considered as a region with low lightness and high gradients contours. So, we could separate two kinds of shadows, the own shadow and the shadows due to the acquistion. Own shadow occurs when the light hits a surface with a slope change. The brightness of pixels corresponding to the area decreases as the angle of incidence deviates from the normal of the surface. The brightness reaches its minimum when the incident light and the surface normal are orthogonal. Drop shadow occurs when the light source is obscured by an object before the light reflection on the surface. Others distortions problems like blur or warping are beyond of the scope of this paper.

In this paper, we consider an image u ∈ R N1×N2 where N 1 et N 2 are two intergers. The non uniform illumination can be modeled as a multiplicative effect. This modelling combining the reflectance and the luminance of the image was proposed by Barrow and Tenenbaum in 1978 [10]. That said, due to various factors that may be involved in the construction of the image (the illumination of the object, the geometry of the scene acquired, the camera settings ...), such modelling is very difficult to tackle.

In 1999, Laszlo [START_REF] Laszlo | Monte-Carlo Global Illumination Methods -State of the Art and New Developments[END_REF] has proposed a generative model of the image, based on a combinaison of Fredholm integral and a modelling of the settings of the camera. This model is very difficult to implement. Thus, it is the global illumination method [START_REF] Laszlo | Monte-Carlo Global Illumination Methods -State of the Art and New Developments[END_REF] remains the most widely used :

u (x, y) = I (x, y) v (x, y) cos θ (x, y) + b (x, y) , (1)
u(x, y) is the grayscale of the pixel (x, y), I is the luminance or the non uniform illumination, v(x, y) the reflectance and cos θ (x, y) the cosine of the angle between the incident light ray and the surface normal at the point of the object. In image processing, this modelling is even more simplied by integrating cos θ (x, y) on the component I(x, y). Thus, the final model becomes:

u (x, y) = I (x, y) v (x, y) + b (x, y) . (2)
This modelling of the image is far from perfect, because it does not take into account neither the problems of geometry of the object (the presence of surfaces which can create shadows on the object ...), or external factors in the formation of the image. The advantage of this simple model is to estimate the reflectance of an object from an approximation of its luminance.

The estimation of the reflectance v is crucial, because here we have an opportunity to characterize an object independently of illumination problems. Here, we suppose that the noise b is a gaussian random variable.

In the following, we suppose u, I and v ∈ L 2 (Ω) (where L 2 (Ω) is the square intergable space, Ω is the domain of the image) and the distortion is introduced by the measuring device and the conditions of acquisition.

Natural criterion

In this part, we consider the model defined by the equation 1. Thus and ideally, we would like to estimate both I and v up to the noise, a natural criterion could be:

J 1 (I, v) = 1 2 Iv -u 2 L 2 (Ω) + λ 1 R 1 (v) + λ 2 R 2 (I), (3)
where λ 1 , λ 2 are two positive hyperparameters, R 1 , R 2 are two regularization functions allowing to control the noise and to provide some a priori on the pair of solution.

If we suppose that I is a smooth function and that the singularities are reported on v. A classical choice for the regularization function is :

R 1 (v) = Ω |∇v|dΩ, R 2 (I) = Ω |∇I| 2 dΩ, (4)
in other terms, v ∈ BV (Ω) (see [START_REF] Cohen | Harmonic analysis of the space BV[END_REF] for more details on this space) and I ∈ H 1 (Ω). Then, we are looking for:

(I, v) = arg min l∈H 1 (Ω),w∈BV (Ω) J (l, w) . (5)
Proposition 1. If we suppose that the noise b = 0 and if solutions of (5) exist where

I ∈ ]0, 1] and v in E = u ∈ L 2 (R 2 ), u(x, y) = 0 or u(x, y) = 1 , let us consider two solutions (I 1 , v 1 ) and (I 2 , v 2 ) of (5) then v 1 = v 2 and when u 1 = u 2 = 0 then I 1 = I 2 .
Proposition 2. If we suppose that I is a positive unkown constant in ]0, 1] there exist a solution (I, v) satisfying problem [START_REF] Horn | Robot Vision[END_REF] in

E A = v ∈ E, v(x, y) = 0∀x, y ∈ R 2 \ A where A = [0, 1] 2 .
Proof -Under the assumption of the proposition, let I j and v j be a minimizing sequence of the problem (5), the sequence (v j ) j ) belongs to E A and has bounded variations. Then by a classical compactness result (see [START_REF] Giusti | Minimal Surfaces and Functions of Bounded Total Variation[END_REF]) for the functions whith bounded variation and the fact that the all element of the sequence (I j ) j ) belongs to a compact K ⊂ ]0, 1]. Then, we can extract a convergent subsequence, this subsequence converges toward

(I ∞ , v ∞ ) with I ∞ ∈ K. As E A is a closed subset of L 2 R 2 , we have v ∞ ∈ E A .
Following these propositions, it could be interessant to add a constraint to project the solution v as closed as possible to E. A natural candidate function could be :

g : [m, M ] → R + x → (M -x)(x-m) M -m
where m is the minimum value of the acquired image u and M is its maximum value. So, we could penalized the criterion defined in 5 as follow:

J 2 (I, v) = 1 2 Iv -u 2 L 2 (Ω) + λ 1 R 1 (v) + λ 2 R 2 (I) + λ 3 G(v), (6)
where

λ 3 > 0 and G(v) = Ω |g(v)| 2 dΩ.
Then, the researched solution is:

(I, v) = arg min l∈H 1 (Ω),w∈BV (Ω) J 2 (l, w) . (7)
The Euler-Lagrange equations associated to the problem 6 are:

∂J ∂v (I, v) = I (Iv -u) -λ 1 div ∇v |∇v| + λ 3 (M + m -2v)) (M -v)(v-m) (M -m) 2 = 0, ∂J ∂I (I, v) = v (Iv -u) -λ 2 (∆I) = 0. ( 8
)

A direct PDE based method

The objective of this approach is to extract the reflectance v from the non uniform illumination I. If we neglect for the moment the noise. The model 2 becomes:

u (x, y) = I (x, y) v (x, y) , log (u (x, y)) = log (I (x, y) v (x, y)) , log (u (x, y)) = log (I (x, y)) + log (v (x, y)) , (9)
Remark 1 The grayscale image could be shifted by an offset to avoid the null values.

We are thus reduced to find Ĩ and ṽ satisfying:

ũ = Ĩ + ṽ (10)
So, as Ĩ is assumed smooth, we will find a way to approach Ĩ regardless of ṽ, then deduce ṽ by substaction with ũ.

Here, we suppose that Ĩ is the solution of:

   w t = s max 0, s∆ A w , ∂w ∂n = 0 on ∂Ω, w (t = 0) = u, (11)
where s = 1 if the grayscales of the text are on average "smaller" than the background ones and s = -1 else. ∆ A is defined as:

∆ A := div ϕ (|∇u|) ∇u |∇u| . (12)
Now, we introduce the orthonormal set (τ, n), where n is defined by:

n(x) = ∇u |∇u| .
The vector fields τ et n are respectively tangent and normal to the level curves (isocontours) of u. Then (12) becomes:

∆ A = ϕ (|∇u|) |∇u| u tt + ϕ (t)u nn , (13)
where :

u tt = τ t ∇ 2 u τ = 1 |∇u| 2 u 2 x1 u x2x2 + u 2 x2 u x1x1 -2u x1 u x2 u x1x2 and u nn = n t ∇ 2 u n = 1 |∇u| 2 u 2 x1 u x1x1 + u 2 x2 u x2x2 + 2u x1 u x2 u x1x2 .
u t is the transpose of u, ∇ 2 u is the hessian, u xi and u xixj , i, j ∈ {1, 2} designe the first and second order partial derivative of u. This allows to separate both directions of diffusion: τ et n.

The term ϕ (|∇u|)

|∇u| u tt defines the diffusion in direction τ , while ϕ (|∇u|)u nn defines the diffusion in the direction n. Thus, we have some qualitative requirements on the function ϕ: an isotropic diffusion on homogeneous region (part) of the image, ϕ (0) = 0. We have also lim

t →0 ϕ (t) t = ϕ (0) > 0.
On the edge of the image, where we have a high gradient, we prefer a tangential diffusion and not in its transverse direction. So, we demand: lim

t →+∞ tϕ (t) ϕ (t) = 0.
An example of function satisfying these requirement is:

ϕ(t) = 1 + t 2 , ( 14
)
If Ĩ is estimated then we can deduce ṽ :

ṽ = (1 + s) 2 max (ũ) -s Ĩ -ũ , (15)
4 Discretization

In the discrete form, an image is composed of a set of pixels indexed by (i, j),

1 ≤ i ≤ N , 1 ≤ j ≤ M . u = (u i,j ) 1≤i≤N,1≤j≤M belongs in X, where X = R N ×M .
The space X is equipped with the euclidian inner scalar product:

∀u, v ∈ X, u, v X = N i=1 M j=1 u i,j v i,j .
By a minor abuse of the notation, we state for X m , where m ≥ 1, the space (R m ) N ×M . The gradient of u ∈ X, written ∇u belongs to X 2 and could be defined by several manners. One of them consists to set ∇u = (g (1) , g (2) ) with:

g (1) i,j = u i+1,j -u i,j if i < N, 0 si i = N. g (2) i,j = u i,j+1 -u i,j if j < M, 0 si j = M. ( 16
)
This div operator is defined in X 2 to X as the adjoint operator of -∇. So, for all p = (p (1) , p (2) ) ∈ X 2 , we have: ∀z ∈ X, divp, z = -p, ∇z .

In the case where the gradient is given by ( 16), one can prove that

(divp) i,j = (divp) (1)
i,j + (divp)

(2) i,j , (17) with (divp)
(1)

i,j =      p (1) i,j -p (1) i-1,j if 1 < i < N, p (1) i,j if i = 1, -p (1) i-1,j if i = N. (divp) (2) i,j =      p (2) i,j -p (1) i,j-1 if 1 < j < M, p (2) i,j if j = 1, -p (2) i,j-1 if j = N.
We state for all u ∈ X, ∆u = div(∇u).

(18) and

∆ A u = div ϕ (|∇u|) ∇u |∇u| (19)
Then, from the definition of the divergence, we keep in this discrtete form:

∀u, v ∈ X, ∆u, v = -∇u, ∇v = u, ∆v . (20)
Then, it follows the natural algorithm from 7, 17 and 18:

Data: u the acquired image Result: I the non uniform illumination and v the reflectance initialization : Given ε1 > 0,ε2 > 0, λ1, λ2 and λ3 > 0, I 0 = u max(u) , v 0 = u and µ > 0 adequately chosen do • update I and v:

v p+1 = v p -µ " I p (I p v p -u) -λ1div " ∇v p |∇v p | « + λ3(M + m -2v p ) (M -v p )(v p -m) (M -m) 2 « I p+1 = I p -µ `vp+1 `Ip v p+1 -u ´-λ2∆I p úntil v p+1 -v p < ε1 & I p+1 -I p < ε2 v = v p+1 , I = I p+1 Algorithm 1: Model 7
Now, if we use an explicit scheme in time and the discretization 19 for the anisotrope laplacian, we can derive the following algorithm from 11:

Data: u the acquired image, s = 1 or -1 Result: v the reflectance initialization : Given ε > 0, Ĩ0 = ũ := log (u) and dt > 0 adequately chosen do

• update I : Ĩp+1 = Ĩp + dt max " 0, ∆ A I p "
until Ĩp+1 -Ĩp < ε Ĩ = Ĩp+1 deduce ṽ from 15 and v = exp(ṽ).

Algorithm 2: Model 11

Numerical results

In this section, we present some simulation results comparing boths models. We show the ability of the proposed algorithms to successfully estimate the reflectance and the non uniform illumination and we compare also their performance by means of a text recognition software. As we don't control the recognition software errors, we present only how our process can improve this software. In other words, we show the recognition of the acquired image afterwards the recognition of the results obtained by the algorithms 1 and 2.

In the example 1, the original image is acquired from a Sony Ericksson K800i (3.2 megapixels) while images in Examples 2 and 3 are obtained from an Iphone 3GS (3 megapixels).

In these tests, the parameters of the algorithm 1-criterion 7 are taken equal to λ 1 = λ 2 = 0.1, λ 3 = 0.01 and ε = 0.00001. For algorithm 2-model 11, we take s = 1, dt = 0.5 and ε = 0.00001.

Figure 1 shows the estimated non uniform illumination and the estimated reflectance obtained from both algorithms. In this example, The image is affected by its own shadow. The resulting estimations are correct and quite similar.

In figures 2 and 3, the images are acquired in a severe rough environment. These tests are very interesting because the images contain receipts. If we could recognize the containts of the receipts. The consumer can then follow his budget in a detailed way. Then, we can propose an alternative solution to barcode scanning. This solution is more tracktable since we have only one shot and one scan when the barcode solution needs to decode the barcode for each product. Morever, barcodes acquired from photophones have also distortion problems that we must take into account during the decoding process (see [START_REF] Dumas | An evolutionary approach for blind deconvolution of barcode images with nonuniform illumination[END_REF][START_REF] Kim | Joint nonuniform illumination estimation and deblurring for bar code signals Optic Express[END_REF][START_REF] Rhabi | Realeyes3D SA[END_REF]).

In figure 2, the lightning conditions are very low and we deal with distortions which are beyond the scope of this work (blur and noise). Thus, here, we are on a "edge case" for both algoritms. As we can see, the text recognition software recognize some texts of the estimated reflectance for both algorithms whereas this software does not recognize any text from the original image. Both results are correct but the result of algorithm 2model 11 seems more suitable if we would like to read or to print the result. In figure 3, the image are affected by two kinds of shadows : its own shadow and a drop shadow. In this test, the algorithm 2-model 11 gives the best result.

Conclusion

Two methods for enhancing text in image-docmuents are proposed. The first is based on an highly non convex optimization problem while the second is based on a direct PDE's resolution. So far we have shown that the methods are robust to low lightning conditions. The second method based on an anisotropic pde's model provides the best result and is easier to implement. Moreover, the resulting algorithm depends only on few fixed parameters. However, this model needs some theorical investigations and a rigorous analysis (conditions of existence, unicity, numerical analysis of the associated algorithm . . . ) that deserves further investigations. Based In particular, this approach has been successfully applied to improve an OCR software to recognize texts from real images taken from photophones even in tough environment.

Fig. 1 .

 1 Fig. 1. Original image acquired from a Sony Ericsson K800i

Fig. 2 .

 2 Fig. 2. Original image acquired from an iphone 3GS: first test

  T U R E j r a n t M c D o n a l d ' s d e S E V R E

Fig. 3 .

 3 Fig. 3. Original image acquired from an iphone 3GS: second test


Ozcan Ozturk

Mahmut Kandemir

Mary Jane Irwin

BB-GC: Basic-Block Level Garbage Collection *

Memory space limitation is a serious problem for many embedded systems from diverse application domains. While circuit/packaging techniques are definitely important to squeeze large quantities of data/ instruction into small size memories typically employed by embedded systems, software can also play a crucial role in reducing memory space demands of embedded applications. This paper focuses on a software-managed two-level memory hierarchy and instruction accesses. Our goal is to reduce on-chip memory requirements of a given application as much as possible, so that the memory space saved can be used by other simultaneously-executing applications. The proposed approach achieves this by tracking the lifetime of instructions. Specifically, when an instruction is dead (i.e., it could not be visited again in the rest of execution), we deallocate the on-chip memory space allocated to it. Working on the control flow graph representation of an embedded application, our approach performs basic block-level garbage collection for on-chip memories.

Introduction and Motivation

Embedded or real-time systems include all those in which constrains imposed by the environment (e.g., available battery power and memory capacity) play a critical role in the design and implementation of the system. Common areas for embedded systems are machine and process control, medical instruments, smart telephony and data acquisition, and memory limitation is a serious concern in all these areas. In addition, as embedded systems become increasingly complex, there is a growing demand for executing multiple applications concurrently, thereby putting even higher pressure on memory system.

A common solution to the memory problem is to design a memory hierarchy where the higher levels are small, fast, and energy efficient, and the lower levels are large, slow, and energy hungry. A frequent instantiation of this model is a two-level hierarchy with an on-chip cache memory (possibly separate components for instructions and data) and an off-chip main memory. However, there are several critical problems associated with conventional hardware-managed caches. First, the success of a cache-based system depends strongly on the compatibility between the data access pattern and the hardware-guided cache line replacement policy. In many cases, the cache line-level data management can be very fine granular for a data-intensive embedded application. Second, since data transfers in and out of the cache are managed by hardware, there is no guarantee that a required data item will be in the cache at the time of access. This may be an important problem in real-time embedded systems where execution time predictability is a critical issue. Third, in many situations, the cache management policy is too general for a given embedded application. Fourth, the dynamic mapping of data to cache locations can be costly from an energy consumption viewpoint. These problems have motivated recent research on software-managed on-chip memories [START_REF] Panda | Efficient utilization of scratch-pad-memory in embedded processor applications[END_REF][START_REF] Steinke | Assigning program and data objects to scratch-pad for energy reduction[END_REF], where the data/instruction transfers between the on-chip and off-chip memories are controlled by the software (e.g., compiler).

In such a software-controlled two-level memory hierarchy, one of the critical issues is ensuring effective use of available on-chip memory. Specifically, it is both performance and energy efficient to satisfy most of instruction/data requests from the on-chip memory. This is particularly important when available on-chip memory space is shared by multiple applications. There are at least two ways of increasing the effectiveness of on-chip storage:

• Increasing data reuse. This helps reduce the frequency and volume of the transfers between the on-chip and off-chip memory. The prior work considered code restructuring and data layout optimizations for improving data reuse in caches and software-managed memories.

• Reducing memory space requirements. The studies in this group exploit the lifetime information of different data to check whether two different data can share the same memory locations. As in the first group, the existing techniques target at both caches and software-managed memories.

In this paper, we focus on a software-managed two-level memory hierarchy and instruction accesses. Our goal is to reduce on-chip (instruction) memory requirements of a given application as much as possible, so that the memory space saved can be used by other applications. We achieve this by tracking the lifetime of instructions at the basic block granularity. Specifically, when an instruction is dead (i.e., it could not be visited again in the rest of the execution), we deallocate the on-chip memory space allocated to it. Working on the control flow graph (CFG) representation of the procedure, in a sense, our approach performs basic block-level garbage collection for on-chip memories.

Our scheme can be used in two different ways. In a multiprogrammed embedded environment, the memory space saved can be made available to other applications, thereby effectively increasing the degree of multi-programming. Alternately, in a multi-bank on-chip memory, the unused banks can be switched off to a low-power mode to save energy. In this paper, we also discuss how careful block placement in on-chip memory can reduce memory fragmentation.

The rest of this paper is structured as follows. Section 2 describes our two-level software-managed memory hierarchy and code execution model under this memory system. Section 3 gives the details of our approach to deallocating the on-chip memory space of dead basic blocks. Section 4 studies our aggressive on-chip memory deallocation where even the space occupied by live basic blocks are recycled for decreasing average memory occupancy further. Section 5 discusses the placement of basic block in on-chip memory to reduce memory fragmentation when dead blocks are deleted. Section 6 discusses related work, and finally, Section 7 summarizes our contributions.

Architecture

We assume a two-level software-managed instruction memory hierarchy, where the first level is on-chip and the second level is off-chip. Although our software-managed on-chip instruction memory is similar in performance/energy characteristics to a conventional hardware-managed on-chip cache memory, its management is very different from that of an instruction cache. Unlike instruction caches, the instruction flow to the on-chip instruction memory is controlled by software (compiler in our case). Since the on-chip memory is assumed to be very small in size compared to data volume that needs to be processed, its effective management is critical from both the power and performance perspectives. In particular, on-chip memory space can be shared by multiple applications at the same time, and its effective use determines the number of applications that could be run simultaneously. In this architecture, the on-chip memory space that could be saved/reclaimed from an application can be made available to other applications. We also assume existence of a separate on-chip data memory, but this pa-per is focused on instruction accesses (the off-chip memory can also be used to store data). Note that the architecture we are focusing on in this study contains a software-managed hierarchy and no hardware-managed cache. This allows the compiler to explicitly manage the data transfers in the memory system and discard the basic blocks whose lifetimes are over.

Our Approach

High-Level View

Our baseline approach operates as follows. When a procedure is invoked, all its basic blocks are transferred from off-chip memory to on-chip memory. As it executes from on-chip memory, we check whether any of its basic blocks is dead at the current point. If this is the case, that basic block is deleted from on-chip memory. In this work, a basic block (of code) is called dead if it is not possible that the execution thread can visit it in the rest of the program execution.

As a simple example to illustrate the concept, we consider the CFG depicted in Figure 1(a). When the execution thread reaches the basic block marked 2 we know for sure that the basic blocks marked as 1, 6, 7, and 8 are dead (i.e., they cannot be accessed); therefore, the on-chip memory space occupied by them can safely be deallocated. Similarly, if, on another input, the execution reaches basic block 8, the onchip space reserved for blocks 6 and 7 can be reclaimed (in addition to the space allocated for blocks 1, 2, 3, 4, and 5, which would be deallocated when basic block 6 is reached). However, when a procedure whose on-chip memory space has been deallocated is later re-invoked, all its basic blocks must be re-brought into the on-chip memory for execution. In the remainder of this paper, this approach of deallocating on-chip storage space of dead basic blocks is referred to as Basic Block-Level Garbage Collection, or BB-GC for short. The two subsections below describe BB-GC in detail.

Basic Block Marking for Space Reclaiming

BB-GC gives the task of managing the contents of the on-chip instruction memory to the compiler. Specifically, the compiler analyzes the application code, which is represented as a set of connected control flow graphs (CFGs) -one per procedure. A section of program code that does not cross any conditional branches, loop boundaries, or other transfers of control is referred to as basic block (BB). In a basic block, the branch instruction, if any, can occur only as the last instruction in the block. In a control flow graph, each node represents a basic block, and an edge from a node to another indicates a potential flow of control that could occur at runtime [START_REF] Muchnick | Advanced compiler design and implementation[END_REF]. Note that CFG is a conservative representation since it includes all possible flows of control in the program, some of which could not be exercised for a particular input. Our compiler analysis performs two important tasks:

• It inserts a special assembly instruction before each procedure call to copy the contents of the procedure from the off-chip memory to the on-chip memory, if it is not already there. Before doing so, however, it also deletes any basic blocks (of that procedure) that might have been left in the on-chip memory from the previous invocation. While at first glance this might seem overkill as one may potentially reuse some of these basic blocks, deleting such basic blocks and copying the entire procedure from the off-chip memory make the implementation much simpler than an alternate scheme that could try to track current locations and status of basic blocks at runtime.

• To each basic block BB i , it attaches a set of basic blocks ids (B i ) observing the following rule: whenever BB i is reached, all the basic blocks BB j ∈ B i can be safely declared dead, and the on-chip instruction memory space allocated to them can be returned to the pool of free spaces (this process is also called memory space reclamation). Note that the set B i for a given basic block BB i can be empty. For the example shown in Figure 1(a), we have the following B i sets (also called the dead block sets):

B1 = ∅ B2 = {BB1, BB6, BB7, BB8} B3 = ∅ B4 = ∅ B5 = ∅ B6 = {BB1, BB2, BB3, BB4, BB5} B7 = ∅ B8 = {BB6, BB7} B9 = {BB2, BB3, BB4, BB5} or {BB8}
We will describe shortly how these sets are automatically determined by BB-GC. The compiler also inserts an instruction at the beginning of block BB i to delete all the basic blocks in B i from the on-chip memory (if they have not been already deleted). Four important points should be noted here. First, the instruction to delete the blocks in B i should attempt such a deletion only in its first invocation. For example, considering the CFG in Figure 1(a) again, when the execution arrives at the basic block marked 6 the first time, we need to delete blocks BB 1 , BB 2 , BB 3 , BB 4 , and BB 5 . In the potential subsequent visits of this block (via the edge between BB 7 and BB 6 ), we should not attempt to delete any basic blocks (as the blocks in question would have already been deleted, and their space could have been re-assigned to other applications). This checking incurs an extra overhead which is accounted for in our experimental evaluation. The second point is that the determination of the B i sets should be done with care to minimize the overheads. For example, in Figure 1(a), B 3 is ∅ since when BB 2 is visited first time, all four blocks (BB 1 , BB 6 , BB 7 , and BB 8 ) would be deleted, and no additional basic blocks can be deleted when BB 3 is visited. The third point is that, due to lack of complete control flow information at compile time, the determination of some B i sets may need runtime information as well. For example, the basic blocks that will be removed from memory when execution arrives at BB 9 depends on the edge through which the execution enters BB 9 . We can keep track of this at runtime by using some extra variables as explained below (again with some extra overhead). Finally, when the last basic block completes its execution, all remaining basic blocks of the procedure are deleted from the on-chip memory. In the rest of this subsection, we discuss the algorithm that generates the B i sets.

The proposed algorithm works on a CFG representation of a procedure, and is executed for each procedure in turn. It has two steps. The first step is an iterative loop, and in each iteration of this loop, we first determine the set of nodes (basic blocks) that are reachable from a particular node. Let us use C i denote the set of such nodes for basic block BB i . We refer to the set P i = N -C i as the potential dead block set for BB i , assuming that set N contains all the basic blocks in the procedure under consideration. We call this set as "potential" since the second step of our algorithm eliminates some of these sets and/or reduces the number of elements (basic blocks) in some others. To determine the set C i , one can use either depth-first search (where we search as deeply as possible by visiting a node, and then recursively performing depth-first search on each adjacent node) or breadth-first search (where we search as broadly as possible by visiting a node, and then immediately visiting all nodes adjacent to that node), the two techniques commonly employed in applications that perform graph processing.

In the second step, we use the dominator concept from the compiler theory [START_REF] Muchnick | Advanced compiler design and implementation[END_REF]. We say node BB i of the CFG dominates node BB j if every path from the initial node of the CFG to BB j goes through BB i . That is, it is not possible to reach BB j without first reaching BB i . Let D i represent the set of nodes that are dominated by BB i , and D -1 i the set of nodes that dominate BB i . In the second step of our algorithm, we reduce P i to B i . Initially, for all the basic blocks BB i without any predecessors in the dominator tree, we set B i = P i . Then, we use the following formula recursively to determine the B sets of the remaining nodes in the CFG if they are not merge nodes:

Bi = Pi - k B k ,
where BB k ∈ D -1 i and ∪ denotes set union operator. In other words, we exclude from P i all the nodes that are already captured by its dominators. On the other hand, for the merge nodes (i.e., the nodes into which multiple edges enter), we use:

Bi = Pi -{ k B k ∪ Vi},
where V i is the set of basic blocks that become dead when the execution reaches BB i but could not be captured by any dominator. It is important to note that a basic block can belong to ∪ k B k or V i but not both. Note also that, to compute V i , at runtime, we need to keep track of the CFG edge from which we come to BB i . We do this by associating a variable with each basic block. If there are f edges entering this basic block, this variable can take f different values (from 0 to f -1). The compiler adds special instructions to set the value of this variable for each merge node. Our experimental evaluation also accounts for the space and performance overhead of maintaining these extra variables.

Let us now briefly discuss the complexity of our approach. The asymptotic complexity of the search in the first step is O(E + N ), where E is the number of edges in the CFG and N is the number of nodes. Since N E in general, we can simplify this cost as O(E). Therefore, the total cost of the first step is O(N E) since the search is repeated for every node. Finding the dominators in flow graphs can be done in O(E) time in practice [START_REF] Lengauer | A fast algorithm for finding dominators in a flow graph[END_REF] (so can determining the V i sets), which is the main factor that determines the complexity of the second step of the algorithm. Consequently, the overall complexity of the static part of our approach is O(N E).

Considering the CFG in Figure 1 once more, after the first step, we determine the potential dead block sets as follows: 1(a). A dominator tree is a convenient way of presenting dominator information, in which the initial node is the root, and each node BB i dominates only its descendants in the tree. We see from this dominator tree that BB 2 dominates BB 3 , BB 4 , and BB 5 . Consequently, in determining B i where i = 3, 4, 5, we have B i = P i -{BB 1 , BB 6 , BB 7 , BB 8 }, which gives us the empty set for all three basic blocks. The dead block set of the other basic blocks in this example can be found using a similar strategy, except for BB 9 , which we discuss in more detail now. Note that, for BB 9 , ∪ k B k is empty set as BB 9 has only single dominator (see Figure 1(b)). If, during execution, we reach BB 9 through BB 5 , we need to delete only nodes BB 2 , BB 3 , BB 4 , and BB 5 . The reason that we delete only these blocks is that the others must have already been deleted by the time the execution arrives at BB 9 (through BB 5 ). In other words, V 9 is {BB 2 , BB 3 , BB 4 , BB 5 }. Note that we determine the potential V 9 sets at compile time. Similarly, if the execution comes at BB 9 via BB 8 , we have V 9 = {BB 8 }. Again, the reason for this is that, when we come to BB 9 via BB 8 , the latter is the only node (apart from BB 9 that still occupies memory). Our compiler records these alternate V 9 sets, and depending on the value of the runtime variables mentioned above, it uses (selects) the appropriate V 9 set at runtime. Therefore, at the end of this process, we find the B sets shown earlier in this subsection.

P1 = ∅ P2 = {BB1, BB6, BB7, BB8} P3 = {BB1, BB6, BB7, BB8} P4 = {BB1, BB6, BB7, BB8} P5 = {BB1, BB6, BB7, BB8} P6 = {BB1, BB2, BB3, BB4, BB5} P7 = {BB1, BB2, BB3, BB4, BB5} P8 = {BB1, BB2, BB3, BB4, BB5, BB6, BB7} P9 = {BB1, BB2, BB3, BB4, BB5, BB6, BB7, BB8}

Discussion

Our approach presented in the previous subsection has the important characteristic that it transfers an entire procedure body to the on-chip memory when the procedure is invoked. It then tries to reduce the on-chip memory space occupied by the procedure by removing its basic blocks considering their lifetimes. One might point out that an alternate implementation is also possible. Specifically, instead of bringing all the basic blocks at once at the time of invocation, we can bring them on a need basis. In other words, we can manage the on-chip memory as a cache for hot basic blocks, i.e., the ones that are executed frequently. In addition, when necessary, we can also employ a block eviction strategy based on LRU or a similar algorithm. In fact, the strategy described in [START_REF] Chen | Compiler-directed management of instruction accesses[END_REF] implements a similar scheme (though, instead of LRU, it relies on loop structures in the CFG). Unfortunately, one of the major consequences of such a scheme is that, at a given time, some of the basic blocks of the procedure can reside in the on-chip memory, whereas the others are in the off-chip memory, and the location of a basic block with respect to its neighbors can change during the course of execution. As a result, each time a basic block changes location (and the number of such location changes can be very high in a typical execution), the target addresses of all the branches to that basic block must be updated for correct execution. This situation is depicted in Figure 2. In Figure 2(a), three basic blocks (BB 2 , BB 3 , and BB 4 ) are in the on-chip memory, whereas in Figure 2(b) two basic blocks (BB 2 and BB 4 ). Notice that, depending on where basic block BB 3 is, the target of the branches to it from basic block BB 2 will be different (similar argument goes for block BB 4 as well, which also branches to block BB 3 ). This type of dy- namic address management at runtime is very difficult to track, is time consuming, and makes the underlying implementation very complex. This complexity can in turn have negative impacts on execution cycles and power consumption of the entire design. In contrast, in our proposal, all the intra-procedure branches are within the same memory component (on-chip), and consequently, the address management is much simpler. We rely on the fact that most of the branches among the basic blocks are within procedures not across the procedures. The basic block branches across procedures correspond to procedure calls and are relatively rare.

Aggressive Memory Deallocation

It is to be noted that the approach discussed in Section 3 is a conservative one. That is, the on-chip memory space allocated to a basic block is deallocated only when the block is dead, i.e., there is no CFG arch using which the block can be re-visited. While this conservative strategy eliminates any potential negative impact of space deallocation on execution cycles, one could do even better from a pure memory space saving perspective if one could deallocate blocks before they become dead. The main potential drawback of this strategy is the increase in execution cycles due to increased traffic between the on-chip and off-chip memories.

While it is possible to adopt several strategies to decide which basic blocks to deallocate, any viable scheme must observe the rule that the space of a basic block that will be reaccessed (executed) shortly should not be deallocated (as this can significantly increase the volume of transfers between the off-chip and on-chip memory). In other words, one needs to select the victim block(s) among the ones with large interaccess time gap. An important question then is how one can decide whether the next access to a basic block is really far in execution. The scheme proposed in this section assumes that the next access to a given basic block can be predicted to be far if between the current access and next access there is at least a loop to be executed. The rationale behind this assumption is that most loops iterate large number of times before they terminate. Consequently, during long loop execution, one can achieve large savings in average memory occupancy. We expect this scheme to be most effective in applications whose CFGs have a big loop surrounding most of the basic blocks. Consider, for example, the CFG depicted in Figure 1(c). An important difference between this CFG and the one in Figure 1(a) is that former has a large outermost loop, whose back edge goes from BB 8 to BB 2 . The scheme described in the previous section cannot be very successful in this CFG as most of the basic blocks are dead only after basic block BB 8 exits (which is too late to save any memory space). In contrast, the aggressive scheme can be effective in such scenarios. Consider, for example, the loop that consists of blocks BB 2 and BB 3 in this CFG. The aggressive scheme deallocates the on-chip memory space allocated to them after the loop exits, i.e., the execution takes the edge between BB 3 and BB 4 . The reason is that, when BB 4 is reached, re-visiting BB 2 will require two loops (i.e., BB 4 -BB 5 and BB 6 -BB 7 ) to be completed. In our experimental evaluation, we compare our baseline implementation with this aggressive dead block elimination scheme.

Memory Placement of Basic Blocks

One of the characteristics of BB-GC is that it deallocates a memory region (that holds a dead basic block or a block whose next invocation is far in execution) whenever it is possible to do so. As a consequence, it is possible that the instruction memory space is fragmented as the execution progresses. Unfortunately, it is well known [START_REF] Jones | Garbage Collection: Algorithms for Automatic Dynamic Memory Management[END_REF] that a fragmented memory (where numerous small free regions/chunks are distributed all over the memory space) makes it difficult to utilize it for allocating space for new data/code structures. In other words, one would prefer a few large free regions in memory instead of many small free regions. In this section, we discuss a strategy, using which basic blocks of a procedure can be mapped to the on-chip instruction memory such that the deallocations generate large free spaces in memory as much as possible.

To achieve this, the proposed approach makes use of profile data. The specific profile information we use is the execution probabilities for CFG edges. Using these probabilities, our approach, which is an iterative process, decides how the basic blocks of the procedure should be laid out in memory.

Algorithm 1 P rof ileBasedSearch(v, L)

1: put v to the end of L. 2: while there are unvisited edges incident on v do 3: find e with smallest probability among unvisited edges incident on v. 4: find w such that e = (v, w) 5: if all incoming edges to w are visited then 6:

P rof ileBasedSearch(w, L) 7: end if 8: mark e as visited 9: end while

The approach can be best explained using an example. Consider the CFG illustrated in Figure 3. The numbers attached to the edges represent branch probabilities. As an example, the probability with which the execution moves to BB 2 after exiting block BB 1 is 90%, whereas that of proceeding with BB 3 (again, after exiting BB 1 ) is 10%. Based on these probabilities, we can decide that it is better to store BB 3 and BB 1 consecutively in memory since it is more likely that they will be dead at the same time, and (when this happens) their space can be deallocated together (which results in a larger free space). After making this decision, our approach continues with the next (unprocessed) smallest probability edge as deep as possible in the CFG. In our example, the next basic block to be stored (next to BB 3 and BB 1 ) is selected based on the probabilities of the edges outgoing from BB 3 . With a probability of 20%, BB 7 would be the next one in the list. After this, we consider BB 8 since it is the only candidate that could be reached from BB 7 . However, there exist other (unprocessed) edges entering BB 8 . As it can be seen from the CFG that it is not possible to deallocate the space for BB 8 until the entire procedure terminates. Consequently, our algorithm checks whether all of the incoming edges of a basic block are visited before it is decided to be stored next to the blocks that have already been processed. Therefore, after having reached BB 8 , our algorithm backtracks to BB 7 and then BB 3 . The next smallest probability edge would lead to basic block BB 6 and this shapes our current list of blocks to be stored next to each other as BB 1 , BB 3 , BB 7 , BB 6 . Since BB 8 still has unvisited incoming edges, our algorithm backtracks to BB 1 . In a similar fashion, we compute the next set of basic blocks to be stored one next to another as BB 2 , BB 4 and BB 5 . Finally, BB 8 would be the last basic block in the list since the edge between BB 5 and BB 8 is the last unvisited edge incoming to BB 8 . So, the final storage order would be BB 1 , BB 3 , BB 7 , BB 6 , BB 2 , BB 4 , BB 5 , BB 8 . In comparison, if we were to use a depth first search (DFS) algorithm to determine the storage order for basic blocks, it would be as follows: BB 1 , BB 2 , BB 4 , BB 8 , BB 5 , BB 3 , BB 6 , BB 7 . And, similarly, a breadth first search (BFS) algorithm would result in BB 1 , BB 2 , BB 3 , BB 4 , BB 5 , BB 6 , BB 7 , BB 8 . Algorithm 1 gives the sketch of our algorithm for determining the order in which basic blocks are laid out in memory. A call to P rof ileBasedSearch(s, L) forms the layout: L[0] . . . L [|v|], where |v| is the number of basic blocks and s is the first basic block in the CFG.

Related Work

Several prior studies focused on the use of scratch-pad memories (SPMs) for data accesses. For example, Panda et al. [START_REF] Panda | Efficient utilization of scratch-pad-memory in embedded processor applications[END_REF] present a powerful static data partitioning scheme for efficient utilization of scratch-pad memory. Cooper and Harvey [START_REF] Cooper | Compiler-controlled memory[END_REF] present two compiler-directed methods for softwaremanaging a small cache for holding spilled register values. Hallnor and Reinhardt [START_REF] Hallnor | A fully-associative softwaremanaged cache design[END_REF] propose a new software-managed cache architecture and a new data replacement algorithm. Bellas et al. [START_REF] Bellas | Energy and performance improvements in microprocessor design using a loop cache[END_REF] present an SPM management scheme for instruction accesses. Steinke et al. [START_REF] Steinke | Assigning program and data objects to scratch-pad for energy reduction[END_REF] focus on a strategy for placing program and data objects into SPM for saving energy. Lee et al. [START_REF] Lee | Instruction fetch energy reduction using loop caches for embedded applications with small tight loops[END_REF] also focus on reducing the energy consumption due to instruction accesses using a softwaremanaged SPM (called loop cache).

Concluding Remarks

One of the biggest roadblocks preventing software writers to achieve higher performance in embedded environments is memory limitation. Consequently, utilizing available on-chip memory space in the most effective way has been one of the most attractive research topics. Focusing on on-chip memory and instruction accesses, this paper presents a scheme that reduces the average memory occupancy of instructions by reclaiming the space allocated to dead basic blocks, i.e., basic blocks that completed their last execution. The paper also studies a more aggressive scheme and discusses the tradeoffs between memory savings and performance overhead. In addition, we study the impact of basic block placement in memory.

Figure 1 .

 1 Figure 1. (a-c) Two different CFGs. (b) Dominator tree for the CFG in (a).

Figure 1 (

 1 Figure 1(b) illustrates the dominator tree for the CFG in Figure1(a). A dominator tree is a convenient way of presenting dominator information, in which the initial node is the root, and each node BB i dominates only its descendants in the tree. We see from this dominator tree that BB 2 dominates BB 3 , BB 4 , and BB 5 . Consequently, in

Figure 2 .

 2 Figure 2. Two different cases for basic block level on-chip memory management.

Figure 3 .

 3 Figure 3. An example CFG with branch probabilities.

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05) 1530-1591/05 $ 20.00 IEEE

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05)

* This work was supported in part by NSF Career Award #0093082.


M Baleani

Anthony Ferrari

L Mangeruca

A L Sangiovanni-Vincentelli

U Freund

E Schlenker

H.-J Wolff

Correct-by-Construction Transformations across Design Environments for Model-Based Embedded Software Development

HAL is

Introduction

Embedded software design for real time reactive system has become the bottleneck in the market introduction of complex products such as automobiles, airplanes, and industrial control plants. Failures are unacceptable for safety-This work has been partially supported by EC IST-2001-34820 (ARTIST), EC IST-2-004527 (ARTIST-II) and NFS ITR CCR-0225610 (CHESS). Any opinions, findings and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the National Science Foundation. critical systems, such as transportation systems, and overengineering is unacceptable for systems with tight cost and resource constraints. Embedded software must interact with physical processes guaranteeing support for hard real-time operation and concurrency. Due to the increasing complexity and shrinking time-to-market, an effective methodology must at all stages involve automatic and semi-automatic support by software tools and favor code re-use.

Model based design is emerging as a solution to embedded software design issues as witnessed by both accademic [START_REF] Henzinger | From control models to real-time code using giotto[END_REF] and industrial efforts [START_REF] Ferrari | From conception to implementation: a model based design approach[END_REF]. The basic tenet of this methodology is to move away from manual coding from informal specifications by capturing embedded software functional and non-functional requirements from abstract mathematical models. Clearly, a mathematical model offers a common ground for a systematic and coherent integration of diverse efforts in system specification, design, synthesis (code generation), analysis (validation), execution (runtime support), and maintenance (design evolution). Today, no single model exists that is agreed upon for embedded software design, and flows are based on different tools and models (e.g., in the automotive domain, UML-based, Simulink, and ASCET models are commonly used to represent designs at different abstraction levels).

Integration is certainly possible at the code level, i.e. using C as a common language. However, code-level integration does have severe limitations. In the model-based methodology, a design is usually represented as a set of components interacting with each other and with the environment where a precise model of computation (MoC) defines the behavior and interaction mechanisms of these modules. The MoC describes how each component performs internal computation, how components transfer information between them and how they relate in terms of concurrency. When integrating executable models, there is much more to tool inter-operability than just the definition of a common syntax or data exchange format: we cannot leave aside how the different MoC relates. While C code can be used effectively to represent the functionality of each component, it can hardly be used to express formally their composition (i.e. communication and concurrency). As a consequence, code-level integration require manual integration to some extent and the need of extensively verifying the correctness of models composition. Last but not least, codelevel integration actually prevents the use of analysis and/or optimization techniques that may be applicable to the original source model.

This calls for the integration of tools and design representation using rigorous semantics. An example ofthis approach is [START_REF] Caspi | Translating discrete-time simulink to lustre[END_REF], an excellent paper about the model-based transformation of a Simulink representation into a Lustre representation. In this paper we present a similar correctby-construction approach to transformations across design environments. To demonstrate this approach we chose two tools (ASCET and Simulink) that are widely used in the automotive domain. Our choice is motivated by the complexity of the embedded software design problem in today cars where premium cars feature up to 5 Giga-Byte of software. The approach is based on the use of a common formal model, namely the synchronous reactive model of computation, which is used as the common ground to interpret system specifications given with different underlying models. In particular, we build an SR abstraction of any given system specifications. This abstraction removes some specific aspects of the original models and this is the price to pay to build a rigorous transformation. We made sure that the behavior of each component is preserved and retain that degree of coordination (i.e. communication and concurrency) needed to ensure the functionality of the system.

The paper is organized as follows. In Section 2 we briefly review the basic features of the MATLAB/Simulink and ASCET design environments. In Section 3 the synchronous reactive model of computation is introduced as the basis for model transformation between the two environments and in Section 4 the SR interpretation of ASCET and MATLAB/Simulink specification is presented. In Section 5 we demonstrate how ASCET models can be ported to Simulink models and vice versa in a consistent way using the common SR semantics. Section 6 presents some final considerations.

ASCET and Simulink Design Environments

ASCET [START_REF]ASCET[END_REF] supports the Task Programming Model (TPM) paradigm for single processor implementations of embedded software controllers. According to TPM, system specifications are given as a collection of software components called tasks and an appropriate scheduling policy. The system specification in ASCET is called a project and consists of a set of modules. Modules instantiate classes and define processes. Classes are reusable components consisting of variables and methods. Component state is held by variables. Component outputs can be computed by calling methods. Processes are methods defined in modules and can call the methods defined by the classes instantiated within the module. Processes communicate via messages, which are shared variables protected via local copy: each process works on a local copy of its input/output messages. The protection mechanism is guaranteed by the underlying operating system (RTOS), which is assumed to be OSEK compliant. Processes are scheduled within tasks that are scheduled by the RTOS on a time or event basis. The scheduling mechanism is based on static priority with preemption.

MATLAB/Simulink [START_REF]MATLAB/Simulink[END_REF] is a system specification, verification, simulation and synthesis environment for real-time systems. Its model of computation is discrete-time [START_REF] Edwards | Design of embedded systems: formal models, validation, and synthesis[END_REF]. As often is the case, the results from the "execution" of the model depend on the scheduling algorithm of the simulator that executes the model thus making the semantics of the model not self-contained. This has three disadvantages: the definition of the Simulink's MoC is 1) complex and difficult to comprehend as a whole, 2) can be significantly dependent of the tool version and 3) unexpected behavior can come up from hidden implementation details of the simulator.

Formal Model

The formal model on which we base the correct-byconstruction transformations presented in this paper is the synchronous reactive model of computation (SR MoC) [START_REF] Edwards | The semantics and execution of a synchronous block-diagram language[END_REF]. It is a block-diagram formalism devised for specifying synchronous real-time systems, where system specifications are provided as an interconnection of blocks. The model of time is discrete and represented as a totally ordered sequence of "ticks" (logical time).

Blocks can have state and their outputs can also be combinatorial functions of the inputs. Interconnections represent signals, that are defined as functions over the sequence of ticks. Interconnections are regarded as zerodelay communication channels between blocks, unless one or more memory elements are introduced on the interconnection channel, each one specifying a one-tick-delay.

The execution semantics of the SR model is based on fixed-point computation, which is used to compute the stable point of the interconnected combinatorial functions at every tick. When no combinatorial loop exists the fixedpoint computation reduces to causal computation: if some output of a block is interconnected to some input of another block, the former is required to execute before the latter.

The set of values that a signal can take up at each tick is extended with a special symbol ⊥ called bottom. This way, at each tick, all signals are assigned a value even though the signal is actually undefined for that tick (in this case, we assign the signal the ⊥ value). SR blocks are allowed to execute only when at least one input is different from ⊥.

The choice of the SR MoC is dictated by its expressiveness, i.e. on the basis of what the model allows us to represent and how "economic" is this representation. The SR MoC is a good match for control intensive systems, exactly the ones that are specified in ASCET and Simulink (at least for automotive applications). Particularly, the Simulink model of computation is based on discrete time simulation and it is fully compatible with the SR MoC, also discrete time.

To better understand how SR and ASCET MoC relate, we must dive in some more details into the TPM paradigm. In general, the TPM can be regarded as an "asynchronous" paradigm, in the sense that each task (or process) has internally no notion of synchronization with other tasks (or processes). This makes the behavior of the system specification dependent on implementation details such as execution time and preemption. In fact, depending on tasks' execution time, the presence of preemption may invert the order of process executions, which may differ from the causal order. Moreover, preemption effects may even impair the consistency of shared variables. This contrasts with the SR MoC where the "atomic" execution of each block prevents inputs to change during execution, and the behavior of the system at each tick is determined by the fixed-point semantics.

Nonetheless, well-known techniques can be implemented to enforce data consistency and a deterministic execution order of tasks as dictated by causality. Notice that, since tasks are executed once at each activation reference no combinatorial loop exists and the causal order ensure the convergence of the fixed point computation.

Our analysis focuses on single processor implementations as supported by ASCET. Since every single processor implementation is endowed with a global scheduler, we resort to scheduling techniques such as priority assignment and the priority ceiling protocol [START_REF] Sha | Priority inheritance protocols: An approach to real-time synchronization[END_REF] for shared resources and we define the procedure in Figure 1 to check (and possibly enforce) whether the behavior of the system implementation is consistent with the SR semantics. In [START_REF] Scaife | Integrating model-based design and preemptive scheduling in mixed time-and event-triggered systems[END_REF] a more conservative check is presented for fixed-priority scheduling with lock-free data sharing.

The procedure of Figure 1 is based on the analysis of data dependencies and priority assignment. When T EX and T SEP cannot be measured, we can assume the worst case given by T EX = ∞ and T SEP = 0. In such a case the algorithm only checks (and possibly enforce) that the priority assignment complies with the causal order, i.e. if T 1 sends a message to T 2 , then T 2 must not be assigned a higher priority than T 1 .

Figure 5 shows the task communication pattern, where

Def.1: let P (A) be the priority assigned to task A. Def.2: the duration of task A is a known upper bound of the execution time of A when it completes execution without being preempted.

Def.3: let T EX (A) be an upper bound of the execution time of task A.

This is a function of the durations of the tasks that can preempt task A. Def.4: let T SEP (A, B) be a lower bound of the time separation between any activation time of A and any activation time of B, when the former precedes the latter.

Step 1: build a dependence graph, where vertices represent tasks. Define a directed arc from vertex A to vertex B if task A modifies a protected resource accessed by task B.

Step 2: label every directed arc from A to B with L T = T SEP (A, B) -T EX (A) and with L P = P (A) -P (B). Proposition 1: If tasks, whose activations can be simultaneous, either have different priorities (the execution order is fixed) or do not modify any common shared resources (the execution order does not matter), a sufficient condition for a single processor implementation to be deterministic is that for every arc at least one of L T and L P is non-negative.

Step 3: check that for every arc at least one of L T and L P is non-negative.

Figure 1. Data dependency analysis algorithm

M i represents a protected shared variable, and the corresponding dependence graph. Since the arc from T 4 to T 3 has both a negative L P = 5-10 and a negative L T = 5-7, the implementation is not guaranteed to be deterministic, because preemption may invert the order of task executions with respect to the task activation order. After changing the priority of T 4 to 10, L P becomes 0 on the loop and determinism is ensured by the algorithm.

SR Interpretation of System Specifications

Every ASCET specification that is compliant with the rules given in Section 3 can be interpreted within the SR MoC. In fact, ASCET provides all the basic mechanisms, i.e. variable protection, priority assignment, priority ceiling, to ensure this compliance.

Let us start by looking at a simple example. An ASCET specification of a seat-belt alarm controller is divided into 5 modules, as shown in Figure 6, each consisting of a single process. The task specification comprises 5 different tasks to accommodate the 5 processes.

In ASCET the state of processes is represented by their local variables. Communication between processes occurs in ASCET via messages and shared variables. The AS-CET interpretation of the seat-belt alarm controller example within the SR MoC is shown in Figure 7. The interpretation procedure is summarized by the rules in Figure 2.

Referring to Rule R1 and Figure 8, since processes are assigned to tasks and the latter are executed on a given activation reference, a "trigger" input signal is added to each block in the SR model. By trigger, we mean a signal that is defined only on ticks corresponding to the activation instants and takes up the value ⊥ otherwise. While the SR block is executed at each tick, the role of the triggering signal, is to make the function defined by the ASCET process be executed only when the trigger value is not ⊥ (the function is not executed when all its inputs are ⊥). In all other cases, the SR blocks preserve the last computed values on its outputs.

As far as Rule R3 is concerned, the higher-priority task will be scheduled first using the old value of the message written by the lower-priority task. This is modeled in the SR MoC by the memory element that holds the old value on the channel.

A Simulink 1 specification can be interpreted according to the SR model in a simple way if at the top hierarchical level every loop between blocks is broken by at least one memory element. In this case no combinatorial loop can exist and the blocks can be considered as SR blocks, while the Simulink continuous time memory element can be transposed into an SR memory element. To interpret triggered blocks as SR blocks, the triggering signals must be considered as triggering inputs of the corresponding SR block.

An example of an SR interpretation of a Simulink specification is shown in Figures 10 and11.

Model Transformation

Porting ASCET Projects to Simulink

The SR interpretation of Simulink specifications given in Section 4 shows that SR specifications that do not have combinatorial loops can be easily ported in Simulink by applying the rules in Figure 3.

Hence, any specification that can be interpreted with an SR model that do not exhibits combinatorial loops can be easily transformed into a Simulink model by deriving the SR model of the specification and applying the transformation rules of Figure 3. In particular, given the ASCET SR interpretation provided in Section 4, a correct by construction transformation from ASCET to Simulink is easily obtained by applying the Rules in Figure 2 and Figure 3 in sequence. 1 We refer to Simulink V6.5 R14 version R3: ASCET processes corresponding to SR blocks with the same triggering input are organized within the same task in a sequence that is compatible with the causal order in the SR model. R4: Triggering inputs become task activation references. R5: Scheduling priorities are assigned so that if B causally depends on A, then either 1) A is assigned to a higher priority task than B, or 2) A and B have the same triggering input and are assigned to the same task with A preceding B.

Figure 4. SR to ASCET transformation rules

Figure 9 shows the Simulink specification obtained by the SR model of Figure 7, which in turn is the SR interpretation of the ASCET project shown in Figure 6.

Porting Simulink Specifications to ASCET

The SR interpretation of ASCET specifications given in Section 4 shows that SR specifications in which every block has one triggering input and no combinatorial loop exists can be easily ported in ASCET by applying the rules in Fig- ure 4.

The priority assignment rule (R5) guarantees a sufficient condition for the ASCET specification to comply with the SR semantics. Observe that the algorithm of Figure 1 provides a less conservative condition for the priority assignment, that can be exploited when T EX and T SEP are known.

The above rules show that it is straightforward to define a rigorous transformation of a Simulink specification to AS-CET when the SR interpretation of the Simulink specification is as introduced at the beginning of this section, i.e. at the top hierarchical level every block is triggered and every loop between blocks is broken by at least one memory element.

The condition above is not restrictive. Indeed, SR blocks without a triggering signal, as defined in Section 4, are executed at every tick, which can be considered as their implicit triggering input. From the TPM perspective this results in an inefficient implementation. Nonetheless, in many cases used in practice functional analysis of the SR block allows to relax the triggering condition. Due to space limitations it is not possible to discuss exhaustively how functional analysis can be carried out. As an example, consider a block without triggering signals whose inputs all come from triggered blocks. If the block modifies its state and outputs only when its inputs change, then it is not necessary to execute the block at every tick, because the block can be equivalently executed on the triggering signals of its input blocks.

In Simulink a given triggered block can be activated by several signals that are multiplexed into a single trigger. If at a given simulation instant more than one triggering signal exhibits a triggering event and the block is not a Stateflow block, the triggered block is executed once. Since we transform Simulink triggering signals into triggering inputs and in the end into ASCET task activation references, we need to assume that triggering signals of non-Stateflow triggered blocks are never simultaneous. This is because in the TPM model, tasks are not aware of simultaneous tasks activations.

The transformation of Simulink specifications to the TPM model has been independently discussed in [START_REF] Scaife | Integrating model-based design and preemptive scheduling in mixed time-and event-triggered systems[END_REF], where the event-based SCADE simulation system is the target environment. In such work, different techniques are used for preserving the synchronous semantics, that require a dedicated RTOS support.

Conclusions

Using our method, model validation is not required each time models are transformed across different design environments. In fact, analysis and synthesis capabilities of the tool to which the model is exported can be applied. For example, a model imported from Simulink can be consistently integrated with other models specified in ASCET to produce an OSEK compliant application taking advantage of ASCET automatic integration features.

We believe that future design flows will be based on a similar approach. We envision that an intermediate format with formal semantics for embedded software models could be defined where the semantics of the different tools could be embedded and manipulated easily. The existence of this intermediate format with formal semantics does not guarantee that mapping a model from an environment to another is transparent. It will provide though an important bridge to map one semantic model into another avoiding the N 2 translation problem.

Figure 2 .

 2 Figure 2. ASCET to SR transformation rules

Figure 3 .

 3 Figure 3. SR to Simulink transformation rules

Figure 5 .Figure 6 .Figure 7 .Figure 8 .Figure 9 .

 56789 Figure 5. Data dependency analysis example

R1 :

 R1 SR blocks can be introduced as Simulink blocks with the same next-state and output functions, R2: SR block interconnections correspond to Simulink interconnections. R3: triggering inputs, if present, are mapped to triggers, R4: Memory elements are mapped to Simulink continuous time memories.

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05) 1530-1591/05 $ 20.00 IEEE

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05)