M Lefevre

C Rigollier

S Cros

L Wald

Toward a solar climatological database: the HelioClim project

Keywords: Remote sensing, Meteosat, solar radiation, climatology

The HelioClim project aims at producing temporal series of solar radiation maps at ground level over Europe, Africa and Atlantic Ocean from 1985 up to now. Meteosat satellites images in visible channel and in the reduced resolution B2 format are used to produce this climatological database. The Heliosat II method was selected to convert these images into maps of the global irradiation at ground level. It is an improved version of the original Heliosat method which estimates the global irradiation by comparison of what is observed by the sensor to what should be over that pixel if the sky were clear. The improvements contained in the Heliosat II method consist mostly in a use of a more accurate clear sky model and explicit formulations of the radiance and the transmittance instead of empirical values. A comparison was performed between irradiation values retrieved by this method and measured by ground stations in Europe. A measuring station is not necessarily contained within a B2 pixel and an interpolation method is needed. The accuracy is less than that observed for the high-resolution images because of the smaller number of images and the interpolation process. Nevertheless, the observed relative root mean square error is around 20 %, a very satisfactory result. We conclude that B2 images processed by Heliosat II method gives good results especially for the estimation of daily irradiation or for the irradiation of larger period. They are also able to provide useful data to create a more than fifteen years solar climatological database.

INTRODUCTION

Time series of solar radiation available at ground level open the way to many applications for different users. It gives useful data for climatological and meteorological studies. This information help also domains concerned by solar data such as solar energy or photo-chemistry.

The HelioClim project at Ecole des Mines de Paris aims at mapping the solar radiation and its components over Europe, Africa and Atlantic Ocean from 1985 up to now, and subsequently at making these maps available for the different users. To develop such a climatological database of solar radiation, images of the visible channel of the series of Meteosat satellites are used. Once properly processed, such satellite images can produce maps of solar radiation which are more accurate than those obtained from interpolation of measurements of radiation made at ground level [START_REF] Perez | Comparing satellite remote sensing and ground network measurements for the production of site/time specific irradiance data[END_REF]. For the processing, the Heliosat II method was selected. It is an improved version of the original Heliosat method [START_REF] Cano | A method for the determination of the global solar radiation from meteorological satellite data[END_REF], Diabate et al. 1989). It converts observations made by geostationnary meteorological satellites into estimates of the global irradiation at the ground level. It is currently one of the most accurate methods presently available.

The high costs involved in acquiring Meteosat data prevented the HelioClim project to use highresolution images and lead to the purchase of reduced resolution images in B2 format instead. An hourly description of the irradiation would have necessitated 373,760 images at a cost of several hundreds of thousands of euros. B2 data are made available by Eumetsat at the reproduction cost. Since they are available every 3 hours, the number of purchased images amounts to 46,720.

This paper presents briefly the method Heliosat II. It then presents comparisons with ground measurements which quantify the accuracy of these satellite estimations. Finally, it presents the same study applied to B2 format images and concludes on the possibility of using B2 images to create the solar climatological database.

HELIOSAT 2: AN IMPROVED METHOD FOR THE MAPPING OF THE SOLAR RADIATION

The Heliosat method converts observations made by meteorological satellites into estimates of the global irradiation at ground level. The original version was implemented in many places and is routinely used to produce maps. The method Heliosat-II is an improved version.

The principle of the method, as well as most current methods, is that a difference in global radiation perceived by the sensor aboard the satellite is only due to a change in apparent albedo, which is itself due to an increase of the radiation emitted by the atmosphere towards the sensor.

A key parameter is the cloud index n, resulting from a comparison of what is observed by the sensor to what should be observed over that pixel if the sky were clear, which is related to the "clearness" of the atmosphere. In principle, it can be written as:

n t (i,j) = [ t (i,j) - t g (i,j) ] / [ t cloud - t g (i,j))
] where   t (i,j) is the reflectance, or apparent albedo, observed by the spaceborne sensor for the time t and the pixel (i, j): (i,j) is the apparent albedo over the brightest clouds,  and  t g (i,j) is the apparent albedo over the ground under clear skies.

 t (i,j) = Erreur !, where L t (i,j) is the observed radiance,   t cloud
If the sky is clear, the apparent albedo  t (i,j) is close to the apparent albedo over the ground and the cloud index n is close to 0 (possibly negative). If the sky is overcast, the cloud index n is close to 1 (possibly larger). In brief, the cloud index n may be considered as describing the attenuation of the atmosphere (1 minus the transmittance). Thus, the cloud index n is a very convenient tool to exploit satellite images.

The basic principle is not always verified. Other parameters may intervene, such as multiple cloud layers and dramatic changes in the ground albedo due to the snowfall or the shadow created by a neighbouring cloud. The change in sensor outputs is not necessarily linked to a change in the optical state of the atmosphere or a change in the optical state does not necessarily translate into a change in the cloud index. The albedos used in the above equation may be constructed from a time-series of satellite images. The optical state of the clear sky is given by a model, often in the form of the global irradiation and its direct and diffuse components and the beam and diffuse transmittances.

Finally, the cloud index n is related to the global irradiation on an hourly (or half-hourly) basis by the means of the clearness index (the ratio of the observed irradiation to the extraterrestrial irradiation for the same day) or the clear-sky index (the ratio of the observed irradiation to the irradiation that should be observed if the sky were clear for the same day). From these hourly irradiations, the daily irradiation can be constructed.

The accuracy gained in the assessment by the method Heliosat-II is mostly gained by the introduction of the ESRA clear-sky model [START_REF] Esra | European solar radiation atlas[END_REF][START_REF] Rigollier | On the clear sky model of the 4th European Solar Radiation Atlas with respect to the Heliosat method[END_REF] and the Linke turbidity factor. This factor provides a reasonable estimation for the water vapour and aerosols optical effects.

Contrary to the original Heliosat method, the approach adopted for the assessment of the cloud index and, further, of the quantities  g and  cloud , is based upon explicit formulations of the radiance and the transmittance. These formulations make use of the modeling of the clear sky radiation, thus offering a strong consistency. This explicit approach offers several advantages. It removes many empirical parameters, compared to the versions of the original method. It makes use of recognized expressions of the radiance and the transmittance. It permits to use known values of the albedo of specific objects, or to estimate such albedoes. Similarly to the method Heliosat-I, the approach does not behave satisfactorily for sun zenithal angles larger than 75 -78°. Though applicable, it produces larger errors.

From an operational point of view, the method Heliosat-II requests the knowledge of the Linke turbidity factor and the elevation for each pixel of the Meteosat image to be processed. This study demonstrates a posteriori that the Linke turbidity factor is sufficient to describe the optical state of the clear atmosphere in the broadband of the satellites Meteosat. An additional gain in operation is that only one map of the ground albedo is now necessary, instead of having one map per slot as presently in the most advanced versions of the method Heliosat-I.

COMPARISON BETWEEN RETRIEVED VALUES AND STATION MEASUREMENTS

A comparison between irradiation values retrieved by the processing of Meteosat images and measured by ground stations is performed. It permits to measure the accuracy of the method Heliosat II. Thirty-five stations from Europe were selected for the comparison. They were selected in flat areas, in order to avoid the specific errors encountered in mountainous areas. These countries are Belgium, France, Germany, Hungary, Norway, Spain and United Kingdom. The meteorological offices provided global hourly irradiation values. These offices perform a screening for quality check. The formats and units were unified before comparison.

Measurements are performed in mean solar time or true solar time. The time of the meteorological measurements is that of the end of the measure. For example, the hourly irradiation at 11 hours is the integral of the irradiance from 10 to 11 hours. The satellite observations are performed in universal time (UT). Consequently, the initial time series of measurements are converted into other time series expressed in universal time. The time for the satellite observation depends upon the position of the site within the field of view; it can be computed exactly knowing the characteristics of the observing system and is expressed in UT. For each meteorological station, knowing its longitude, the universal time of the satellite observation T sat is converted into local time t sat . By weighting the two consecutive irradiation values centred on this local time t sat and by assuming that the irradiance is constant within the hour, the estimated hourly value in universal time, G* h meas (T sat ), was computed:

G* h meas (T sat ) = G* h meas (t sat ) = (t 1 -t sat + 0.5) G h (t 1 ) + (t sat -t 1 + 0.5) G h (t 1 + 1)
where t 1 and t sat are local time expressed in hours, t 1 = Round(t sat ), and Round is the rounding operator such as (Round(10.4)=10; Round(10.5)=11 etc.).

The time series of estimated measurements G* h meas (T sat ) are hereafter considered as actual measurements.

Only were used the measurements of hourly irradiation greater than 10 Wh m -2 . This value corresponds to the level of diffuse hourly irradiation for the sunset and sunrise under clearsky at 60° N in Norway. For these hours of very low solar elevation, the measured irradiation is mainly of diffuse nature and is influenced by local conditions, including orography and the presence of nearby obstacles. By removing these values, we ensure better conditions for the validation process.

The satellite data are high resolution images covering Europe and brought to the infrared resolution, that is 5 km at nadir. They are available every half-hour, from July 1994 to June 1995. We used only the images acquired for even slots. The satellite data were processed using the method Heliosat-II. Estimates of the global hourly irradiation were thus obtained. Only the estimates, for which the solar zenithal angle is lower than 78°, were kept for the comparison, as it has been said that the description of the physical processes is not valid below that limit.

Three months were used for the comparison: January 1995, April 1995 and July 1994. From each data set of hourly irradiation, and for a given month, the daily irradiation was computed as follows.

For the station measurements, we sum up all the hourly irradiations greater than 10 Wh m -2 . The estimate is said valid if at least N hourly irradiations are used in the computation. N is equal to 6 in January and April and to 12 in July. For the high resolution images, we use the above-described algorithm. The estimate is said valid if at least N hourly irradiations are used in the computation. For each hourly irradiation, the mean solar elevation should be greater than 12°. N is equal to 5 in January and April and to 8 in July.

Given the two time-series, and for all stations together, we compute the difference (measuredestimated) in several ways:  for hourly irradiation for a given month, for all the hours,  for the monthly mean of hourly irradiation for a given hour, for all hours,  for daily irradiation for a given month, for all the days,  for the monthly mean of daily irradiation,  for the cumulative of the daily irradiation during 5 days (5-days irradiation). Only are kept 5-days estimates, which are made from at least 3 daily estimates (60 %),

 for the cumulative of the daily irradiation during 10 days (10-days irradiation). Only are kept 10-days estimates, which are made from at least 6 daily estimates (60 %).

For each parameter, the differences have been computed and are summarized in the Table 3.1 below. The bias is usually useful for assessing the accuracy. For example, it ranges from 23 Wh m -2 in July 1994 to -10 in January 1995. However, it strongly depends upon the selected stations and the selected period and has no great statistical significance in this context because the field is not stationary. Consequently, only the RMSE is dealt with in the following. This parameter is more stable.

The results are good compared to the expected accuracy for the Heliosat-II method. The correlation coefficient is high in all cases. The accuracy shows a relative increase of approximately 30 % compared to that observed with the Heliosat-I method.

Table 3.1 shows a problem with the low sun elevations. This appears in the comparison of the hourly and daily irradiations. The method Heliosat-II does not behave well in these cases. It implies that the relative error is greater in January, when the frequency of low sun elevations is greater and the mean hourly irradiation is low, than in July. To assess better the influence of these cases, we introduce the estimates made for any sun elevation, without any constraint, in the comparison with ground measurements. This study confirms that the quality of the assessment decreases as the sun elevation decreases.

However, it is possible to remove the constraint on the sun zenithal angle if necessary, still keeping an acceptable accuracy. Removing this constraint, or decreasing the threshold, leads to a larger number of estimates, which may be useful. As said previously, high resolution images will not be used for the construction of the solar climatology because of their high cost. Reduced resolution data are used instead in the ISCCP-B2 format. This format was set up in the framework of the International Satellite Cloud Climatology Project (ISCCP) [START_REF] Schiffer | The International Satellite Cloud Climatology Project (ISCCP): The first project of the World Climate Research Programme[END_REF][START_REF] Schiffer | ISCCP global radiance data set: A new resource for climate research[END_REF] part of the World Climate Research. This set is derived from the operational Meteosat images, in both visible and thermal infrared bands. The B2 reduced resolution set is produced according to the following steps:

Informatio n type

 first, a time sampling of geostationnary images reduces the frequency of observation to synoptic three hours intervals, starting at 0000 Universal Time (UT),

 second, the higher resolution visible channel data (images of 5000*5000 pixels) are averaged to match the lower resolution of infrared channel data. This gives an image of 2500*2500 pixels instead with a resolution of 5 km,  third, overlapping image pixels are removed,  fourth, spatial sampling of images is performed to reduce the apparent resolution to approximately 30 km at nadir by taking 1 pixel over 6 in each direction. The value of the corresponding B2 pixel is given by the radiance of the south-eastern most pixel in a 6*6 pixels square.

The images B2 are formed by pixels that are effectively pixels of original size (i. e. 5 km) but with a sub-sampling of 6 in each direction. This means that a B2 pixel is not an average of say, 30 * 30 km 2 , but is a pixel of 5 km in size, which represents an area of 30 km x 30 km (figure 4.1). The same comparisons with ground measurements as above were performed but now with the estimates derived from these images in B2 format. The same parameters than above are computed. The construction of daily irradiation is as for the high resolution images, but the number N of hourly irradiations should be greater than or equal to 2 in January and April and 3 in July. The comparisons present in this case an additional problem: a measuring station is not necessarily contained within a B2 pixel. An interpolation method is requested to estimate locally the irradiation from irradiations computed at the surrounding B2 pixels. A comparison between several method was performed by Iehle et al. (1997) and they recommended the nearestneighbour technique. The results strongly depend upon the relevance of the selected technique to the local spatial properties of the irradiation. The smoother the field, the better the assessment by the nearest-neighbour technique. In case of high spatial variations, the technique will be inappropriate as most of the standard ones. Given the properties of the areas under concern this work, the results should be regarded as the typical accuracy that can be achieved. Lower accuracy will be find in cases of large variations in orography or juxtaposition of local climate.

The accuracy observed by comparisons with ground measurements is really satisfactory. The correlation coefficient is high in all cases (Table 4.1).

Nevertheless the accuracy is less than that observed for the high resolution images. The degradation of the accuracy comes from both the smaller numbers of images available for the B2 format to construct a daily integral, and the interpolation process.

We performed an analysis of the influence of the difference in the number of images used to compute the daily irradiation. For this purpose, we used only the high resolution images. The daily irradiation was computed by using the nine possible slots on the one hand, and the B2 slots taken every 3 hours (0000 UT, 0300 UT, 0600 UT ...) on the other hand. Of course, there are discrepancies, which are approximately half of the differences observed between Tables 3.1 and 4.1. The larger the number of images, the more accurate the retrieval. Then, still using the high resolution images, we compare the satellite estimates of the daily irradiation for the true pixel and for the simulated B2 pixel. We observed that the gap in space between the measuring station and the B2 pixel has as much influence as the weak number of images for computing daily irradiation. These results demonstrate clearly that the method Heliosat II may apply to the images in B2 format with a satisfactory accuracy. The B2 images may even be used to assess the hourly irradiation. However, given the poor sampling in time of these images, it may be recommended to limit their use to the assessment of daily irradiation or to the irradiation for larger periods.

Informatio

CONCLUSION

In this paper, we evaluated the accuracy of the Heliosat-II method to estimate solar irradiation at the ground level using comparisons with ground measurements. The quality of estimations are proven for the high resolution images from the visible channel Meteosat satellite. The use of B2 images gives also good results especially for the estimation of daily irradiation or for the irradiation for larger periods. Even with their low resolution in time and in space, B2 images are able to provide useful informations to create a solar climatological database. HelioClim project will be able to make a more than fifteen years time series of solar irradiation maps of Europe, Africa and Atlantic ocean. This will constitute a unique database in that type of solar information.

Figure 4

 4 Figure 4.1. Scheme showing the sub-sampling in the B2 format.

  Differences between measured and estimated values in Wh m -2 for B2 images.

	n type	Mont h	Mean value	RMS E	Correlatio n coefficien t	Nb. of obs.
		Jan 95	136	65	0.78	1767
	Hourly irradiation	Apr 95	337 112	0.86	3097
		Jul 94	539 128	0.82	3059
		Jan 95	984 291	0.89	345
	Daily irradiation	Apr 95 3401 730	0.91	1044
		Jul 94 5797 852	0.86	954
	5-days irradiation (at least 60 % of valid days)	Jan 95 4559 907 Apr 95 1700 2242 1 Jul 94 2891 2 2914	0.93 0.94 0.86	76 209 203
	10-days irradiation (at least 60 % of valid days)	Jan 95 8792 1717 Apr 95 3398 3 3990 Jul 94 5786 5 4862	0.93 0.94 0.84	42 105 101
	Monthly	Jan 95	140	41	0.87	56
	mean of hourly	Apr 95	338	52	0.94	105
	irradiation	Jul 94	538	59	0.94	102
	Monthly	Jan 95	892 225	0.85	19
	mean of daily	Apr 95 3402 350	0.92	35
	irradiation	Jul 94 5792 399	0.86	34
	Table 4.1


Li-Zhang Method

Skander Samy

Bahoura

NOTE ON THE CHEN-LIN RESULT WITH

INTRODUCTION AND RESULTS.

We set ∆ = -∂ 11 -∂ 22 the geometric Laplacian on R 2 .

On an open set Ω of R 2 , with a smooth boundary, we consider the following problem:

(P ) ∆u = V e u in Ω. 0 < a ≤ V ≤ b < +∞
The previous equation is called, the Prescribed Scalar Curvature, in relation with conformal change of metrics. The function V is the prescribed curvature.

Here, we try to find some a priori estimates for sequences of the previous problem. Equations of the previous type were studied by many authors. We can see in [B-M], different results for the solutions of those type of equations with or without boundaries conditions and, with minimal conditions on V , for example we suppose V ≥ 0 and

V ∈ L p (Ω) or V e u ∈ L p (Ω) with p ∈ [1, +∞].
We can see in [B-M] the following important Theorem, Theorem A(Brezis-Merle).If (u i ) i and (V i ) i are two sequences of functions relatively to the problem (P ) with, 0 < a ≤ V i ≤ b < +∞, then, for all compact set K of Ω, sup

K u i ≤ c = c(a, b, m, K, Ω) if inf Ω u i ≥ m.
A simple consequence of this theorem is that, if we assume u i = 0 on ∂Ω then, the sequence (u i ) i is locally uniformly bounded.

If, we assume V with more regularity, we can have another type of estimates, sup + inf. It was proved, by Shafrir, see [S], that, if (u i ) i , (V i ) i are two sequences of functions solutions of the previous equation without assumption on the boundary and, 0 < a ≤ V i ≤ b < +∞, then we have the following interior estimate:

C(a/b) sup K u i + inf Ω u i ≤ c = c(a, b, K, Ω). We can see in [C-L], an explicit value of C(a/b) = a b . Now, if we suppose (V i ) i uniformly Lipschitzian with A the Lipschitz constant, then, C(a/b) = 1 and c = c(a, b, A, K, Ω), see Brézis-Li-Shafrir [B-L-S]
. This result was extended for Hölderian sequences (V i ) i by Chen-Lin, see [C-L]. Also, we can see in [L], an extension of the Brezis-Li-Shafrir to compact Riemann surface without boundary. We can see in [L-S] explicit form, (8πm, m ∈ N * exactly), for the numbers in front of the Dirac masses, when the solutions blowup.

On open set Ω of R 2 we consider the following equation:

∆u i = V i e ui on Ω. 0 < a ≤ V i ≤ b < +∞, |V i (x) -V i (y)| ≤ A|x -y| s , 0 < s < 1, x, y ∈ Ω.
Theorem B((Chen-Lin). For all compact K ⊂ Ω and all s ∈]0, 1[ there is a constant c = c(a, b, A, s, K, Ω) such that,

sup K u i + inf Ω u i ≤ c, ∀ i.
Here we try to prove the previous theorem by the moving-plane method and Li-Zhang method.

We argue by contradiction, and we want to proof that:

∃ R > 0, such that 4 log R + sup BR(0) u + inf B2R(0) u ≤ c = c(a, b, A),
Thus, by contardition we can assume:

∃ (R i ) i , (u i ) i R i → 0, 4 log R i + sup BR i (0) u i + inf B2R i (0) u i → +∞,
The blow-up analysis Let x 0 ∈ Ω, we want to prove the theorem locally around x 0 , we use the previous assertion with x 0 = 0. The classical blow-up analysis gives the existence of the sequence (x i ) and a sequence of functions (v i ) i such that:

We set,

sup B R i (0) u i = u i (x i ), s i (x) = 2 log(R i -|x -xi |) + u i (x), and s i (x i ) = sup B R i (x i ) s i , l i = 1 2 (R i -|x i -xi |).
Also, we set:

v i (x) = u i [x i + xe -ui(xi)/2 ] -u i (x i ), Vi (x) = V i [x i + xe -ui(xi)/2 ], Then, ∆v i = Vi e vi , v i ≤ 2 log 2, v i (0) = 0, v i → v = log 1 (1 + [V (0)/8]|x| 2 ) 2 converge uniformly on each compact set of R 2 with V (0) = lim i→+∞ V i (x i ).
The classical elliptic estimates and the classical Harnack inequality, we can prove the previous uniform convergence on each compact of R 2 .

The Kelvin transform and the moving-plane method: Li-Zhang method.

For 0 < λ < λ 1 , we define:

Σ λ = B(0, l i M i ) -B(0, λ).
First, we set :

vλ i = v λ i -4 log |x| + 4 log λ = v i λ 2 x |x| 2 + 4 log λ |x| , V λ i = Vi λ 2 x |x| 2 , M i = e ui(xi)/2 ,
and,

w λ = vi -vλ i . Then, ∆v λ i = V λ i e vλ i , min |y|=RiMi vλ i = u i (x i + rθ) -u i (x i ) + 2u i (x i ) ≥ inf Ω u i + u i (x i ) → +∞,
and,

∆(v i -v λ i ) = Vi (e vi -e v λ i ) + ( Vi -V λ i )e v λ i ,
We have the following estimate:

| Vi -V λ i | ≤ AM -s i |x| s |1 - λ 2 |x| 2 | s , We take an auxiliary function h λ : Because, v i (x λ ) ≤ C(λ 1 ) < +∞, we have, h λ = C 1 M -s i λ 2 (log(λ/|x|)) + C 2 M -s i λ 2+s [1 -( λ |x| ) 2-s ], |x| > λ, with C 1 , C 2 = C 1 , C 2 (s, λ 1 ) > 0, h λ = M -s i λ 2 (1 -λ/|x|)(C 1 log(λ/|x|) 1 -λ/|x| + C ′ 2 ), with, C ′ 2 = C ′ 2 (s, λ 1 ) > 0. We can choose C 1 big enough to have h λ < 0.
Lemma 1: There is an λ k,0 > 0 small enough, such that, for 0 < λ < λ k,0 , we have:

w λ + h λ > 0.
We have,

f (r, θ) = v i (rθ) + 2 log r, then, ∂f ∂r (r, θ) =< ∇v i (rθ)|θ > + 2 r ,
According to the blow-up analysis,

∃ r 0 > 0, C > 0, |∇v i (rθ)|θ > | ≤ C, for 0 ≤ r < r 0 , Then, ∃ r 0 > 0, C ′ > 0, ∂f ∂r (r, θ) > C ′ r , 0 < r < r 0 , if 0 < λ < |y| < r 0 , w λ (y) + h λ (y) = v i (y) -v λ i (y) + h λ (y) > C(log |y| -log |y λ |) + h λ (y)
, by the definition of h λ , we have, for C, C 0 > 0 and 0 < λ ≤ |y| < r 0 ,

w λ (y) + h λ (y) > (|y| -λ)[C log |y| -log |y λ | |y| -λ -λ 1+s C 0 M s i ], but, |y| -|y λ | > |y| -λ > 0, and |y λ | = λ 2 |y| , thus,
In the first step of the lemma 2, we have,

v i ≥ min v i = C 1 i , v λ i (y) ≤ C 1 (λ 1 , r 0 ), if r 0 ≤ |y| ≤ R i M i , Thus, in r 0 ≤ |y| ≤ R i M i and λ ≤ λ 1 , we have, w λ + h λ ≥ C i -4 log λ + 4 log r 0 -C ′ λ 1 2+s then, if λ → 0, -log λ → +∞, and, w λ + h λ > 0, if λ < λ i 0 , λ i 0 (small), and r 0 < |y| ≤ R i M i ,
By the maximum princple and the Hopf boundary lemma, we have:

Lemma 2: Let λk be a positive number such that:

λk = sup{λ < λ 1 , w λ + h λ > 0 in Σ λ .}.
Then, λk = λ 1 .

The blow-up analysis gives the follwing inequality for the boundary condition, For y = |y|θ = R i M i θ, we have,

w λ i (|y| = R i M i ) + h λ i (|y| = R i M i ) = = u i (x i +R i θ)-u i (x i )-v i (y λ i , |y| = R i M i )-4 log λ+4 log(R i M i )+C(s, λ 1 )M -s i λ 2+s [1-( λ R i M i ) 2-s ], 4 log Ri + u i (x i ) + inf Ω u i → +∞,
which we can write,

w λ i (|y| = R i M i ) + h λ i (|y| = R i M i ) ≥ min Ω u i + u i (x i ) + 4 log R i -C(s, λ 1 ) → +∞, because, 0 < λ ≤ λ 1 ,

E-mail address: samybahoura@yahoo.fr


Antonia Bertolino

Felicita Di Giandomenico

Paolo Masci

Antonino Sabetta

Fabio Martinelli

Ilaria Matteucci

Antinisca Di

Valérie Issarny

Rachid Saadi

Dependability in dynamic, evolving and heterogeneous systems: the CONNECT approach [Project Paper]

Keywords:

The EU Future and Emerging Technologies (FET) Project Connect aims at dropping the heterogeneity barriers that prevent the eternality of networking systems through a revolutionary approach: to synthesise on-the-fly the Connectors via which networked systems communicate. The Connect approach, however, comes at risk from the standpoint of dependability, stressing the need for methods and tools that ensure resilience to faults, errors and malicious attacks of the dynamically Connected system. We are investigating a comprehensive approach, which combines dependability analysis, security enforcement and trust assessment, and is centred around a lightweight adaptive monitoring framework. In this project paper, we overview the research that we are undertaking towards this objective and propose a unifying workflow process that encompasses all the Connect dependability/security/trust concepts and models.

INTRODUCTION

Our everyday activities are increasingly dependent upon the assistance of pervasive inter-connected digital systems. However, the efficacy of integrating and composing such systems is proportional to the level of interoperability achieved between the systems' respective underlying technologies. This leads to a landscape of technological islands of networked systems, among which ad hoc connection bridges are possibly deployed, which are strongly technology-dependent. Yet, the fast pace at which technology evolves, at all abstraction layers of networked systems, challenges the lifetime of interoperability in the digital environment. The European Project Connect 1 aims at dropping the heterogeneity barriers that prevent networked systems from being eternally Connected and at enabling their seamless composition in spite of technology heterogeneity and evolution. Connect targets the dynamic synthesis of Connectors via which networked systems communicate. The resulting emergent Connectors then compose and further adapt the interaction protocols run by the Connected systems.

The above prospected Connect approach comes at risk from the standpoint of dependability. Indeed, as described in [START_REF] Di Marzo | Robustness and dependability of self-organizing systems -a safety engineering perspective[END_REF], there exist many potential threats to the dependability of modern dynamic, evolving and heterogeneous systems such as those tackled in Connect. Recently, other European projects and Networks of Excellence specifically focused on achieving dependability against accidental and intentional failures, both in traditional settings [START_REF]Dependable Systems of Systems (DSoS) EU FP5 Project[END_REF], and in evolving systems [START_REF]European Network of Excellence ReSIST[END_REF], where an additional concern is how to face changes. In the latter perspective, which is very close to the Connect vision, dependability is more precisely referred to as resilience [START_REF] Hollnagel | Resilience engineering: concepts and precepts[END_REF][START_REF] Laprie | From dependability to resilience[END_REF]. In Connect, we are investigating a comprehensive approach, which combines dependability analysis, security enforcement and trust assessment, and is centred around a lightweight adaptive monitoring framework. In this project paper, we overview the research we are undertaking towards this goal and propose a unifying workflow process view that encompasses all the Connect dependability/security/trust concepts and models.

The paper is structured as follows: Section 2 presents the challenges of the Connect project; Section 3 surveys Connect dependability concerns and illustrates our monitoringcentric view; Section 4 gives a unifying workflow process view of the dependability related activities in Connect, and Section 5 concludes the paper.

CONNECT CHALLENGES

The core objective of Connect is to establish eternal interoperability among networked systems through on-the-fly synthesis, implementation and deployment of emergent Connectors.

We depict schematically in Figure 1 To achieve its goals, the Connect project undertakes interdisciplinary research in the areas of behaviour learning, formal methods, semantic services, software engineering, dependability, and middle-ware. Among the above areas, this paper specifically focuses on dependability concerns.

In Connect, dependability addresses two complementary issues: (i) verification and validation techniques to ensure that Networked Systems and synthesised Connectors behave as specified with respect to their functional and nonfunctional properties, and (ii) security, trust, and privacy assurance for interacting parties.

DEPENDABILITY IN CONNECT

In Connect, we direct the investigation on dependability towards the peculiar aspects of the project, i.e., the threats deriving from the on-the-fly synthesis of Connectors. We explore appropriate means for assessing/guaranteeing that the Connected system yields acceptable levels for different non-functional properties, such as dependability (e.g., the Connector will provide continued communication without interruption), security and privacy (e.g., the transactions do not disclose confidential data), and trust (e.g., components are put in communication only with parties they trust). In order to have a label that includes all the above concerns, hereafter we will use the term "dependability" with two different senses: a stricter one, consistent with the classical definition given in [START_REF] Avizienis | Basic concepts and taxonomy of dependable and secure computing[END_REF], and a broader one, in which the term dependability is meant as a label inclusive of all the different concerns listed above. The context will make clear if we mean dependability in strict or in broad sense.

With reference to the four types of entities illustrated in Figure 1, dependability issues are of concern to all of them. Hence, the characterisation of the fault model and of the metrics of interest is specific to the individual entity considered. In general terms, and inspired by consolidated literature on fault types [START_REF] Avizienis | Basic concepts and taxonomy of dependable and secure computing[END_REF], we consider both development and operational faults, affecting both hardware and software components, caused by an accidental event or maliciously introduced by humans, and whose persistence may be either transient or permanent.

Classical dependability metrics defined in the literature are very useful to give a conceptual classification of different concerns in assigning reliance on a system. Starting from such concepts, we are working on a Connect metrics conceptual framework [START_REF]Deliverable 5.1 -Conceptual models for assessment and assurance of dependability, security and privacy in the eternal CONNECTed world[END_REF] that can be used to refine classical metrics with respect to some peculiar aspects of the Connect vision. Indeed, in Connect, Enablers may need to synthesise Connectors on-the-fly, even when the knowledge on the behaviour and capabilities of some Networked Systems is still incomplete. In these cases, Connect Enablers may initially synthesise a basic Connector that permits only some elementary form of interaction, and an enhanced Connector may be synthesised only in a second phase, when Connect Enablers have learnt the behaviour of the new Networked Systems. Two basic refinement dimensions are envisaged for dependability metrics: (i) a CONNECT-dependent dimension, which considers the four actors of the Connect architecture (Networked Systems, Enablers, Connectors and the Connected System); (ii) a context-dependent dimension, which takes into account the application scenario and the heterogeneous and evolvable aspects of the different actors.

In the following, we introduce the four activities related to dependability in Connect: (i) Model-based analysis, (ii) Security enforcement and Privacy, (iii) Trust management, and (iv) Monitoring.

Model-based Analysis

Model-based analysis techniques are sought in Connect to ensure that Networked Systems and Connectors satisfy specified levels of accomplishment for dependability requirements, according to pertinent dependability metrics. Both off-line and on-line approaches to verification and validation and to fault forecasting are pursued, to cover a wider range of needs from the point of view of dependability assurance. As commonly intended in the literature, off-line analysis refers to activities devoted to analyse the system at hand before its deployment, or after deployment but in isolation with respect to the system in operation. On the contrary, on-line analysis refers to activities performed while the system is in operation, so accounting for the detailed system and environment aspects during that specific system execution. We adopt the off-line and on-line terminology with this meaning.

Methods considered in Connect belong to those for probabilistic, model-based quantitative evaluation, which aim at evaluating, in terms of probabilities, the extent to which the attributes of interest are satisfied. Research in dependability analysis has developed a variety of models, each of which focuses on particular levels of abstraction and/or system characteristics. Model-based approaches [START_REF] Nicol | Model-based evaluation: from dependability to security[END_REF][START_REF] Bondavalli | Model-based evaluation as a support to the design of dependable systems[END_REF], being based on the construction of a model of the system from the elementary stochastic processes that model the behaviour of the system components and their interactions, are very suited to early detect design errors and deficiencies, which could otherwise be very costly or even catastrophic when discovered at later stages. Therefore, with reference to the different Connect entities, such assessment methods could: (i) help in guiding the process towards the on-line synthesis of Connectors with the desired dependability accomplishment level (ii) allow to assess whether the emergent Connector satisfies a desired dependability requirement; the provided assessment could be used as a further criterion for the optimal selection of the Connector to deploy to satisfy specific interaction needs (iii) quantify metrics for end-toend dependability, in order to verify whether desired levels are satisfied.

Model-based methods for dependability evaluation are currently applied as traditional off-line methods. However, investigations are undertaken for extending the approach to deal with the dynamic aspects involved in the generation of Connectors in Connect, so as to allow to some extent an on-line assessment of quantitative dependability properties. How to deal with model generation and, especially, model solution so as to provide feedback from the analysis in proper time to be profitably used are the big challenges in this context. Methods based on progressive model definition and refinement, so as to allow for partially pre-determined analysis to be refined/completed at run-time, seem to be promising directions to explore. Monitoring activities (see Section 3.4), by providing accurate information on those model parameters that cannot be estimated in advance, constitute a paramount support to on-line assessment. Also, monitoring can guide model refinement by revealing mismatches between the actual dependability level and the expected level estimated through the off-line analysis.

In addition, forms of partially-dynamic/partially-static methods will be analysed as well, such as Case Based Reasoning methodologies, where, e.g., a Knowledge Base (KB) repository (or simply a Look-up table) could be set up off-line, storing information on the most appropriate fault-tolerance solution for the Connector to be synthesised for specific dependability requirements, on the basis of the results of a (off-line) model-based evaluation activity. At run-time, the KB is used to search for the best pre-determined solution mapping the requested non-functional properties (or the closest one, in case a proper match is not found). This way, fast decision-making is achieved. The KB is dynamically extended with new "cases" to be added, to account for interoperability requests of evolving Networked Systems.

It is worth noting that, in Connect, the activity on dependability assessment is complemented by a verification framework that includes on-line verification and quantitative compositional reasoning, which is part of the foundations and verification methods for composable Connectors [START_REF]Deliverable 2.1 -Capturing functional and non-functional connector behaviours[END_REF].

Security and Privacy

Connect aims at guaranteeing that the communication between components is always secure. For that reason, we propose and elaborate the Security-by-Contract (S×C) paradigm [START_REF] Dragoni | Security-by-contract (SxC) for software and services of mobile systems[END_REF][START_REF] Dragoni | Security-by-contract: Toward a semantics for digital signatures on mobile code[END_REF] for providing security in Connected systems. The basic idea of the S×C framework is the concept of the contract of an application. The contract is a description of the behaviour of the application and it is provided with the application itself.

Consider two Networked Systems that want to communicate. Consider also that each Networked System has a security policy set on it, P1 and P2 respectively. In order to communicate, both Networked Systems send their communication request and their security policies to an Enabler that has to provide a Connector to allow Networked Systems to communicate. Such a Connector will be a mobile code, that the Enabler may chose among a set of already existing Connectors or it synthesises a new one on-thefly. In both cases, the Enabler provides, to each Networked System, a Connector and a contract C that describes the Connector behaviour. Moreover C satisfies both P1 and P2.

We are considering the case in which both Networked Systems have also a private policy, P 1 priv and P 2 priv respectively. Before executing the Connector, each Networked System locally checks if the contract C is compliant with the local private policy. If this is the case then the Connector is executed, otherwise the local private policies are enforced. In both cases the communication is established.

The basic idea of the proposed enforcement architecture is the following: when the Enabler provides the Connector to each Networked System, both of them verify if the code and the contract actually match by an evidence checking procedure (Check Evidence). This step is intended to provide a formal proof that the contract effectively denotes every possible behaviour of the running program. This step can be implemented, for instance, using the model-carrying code [START_REF] Sekar | Model-Carrying Code (MCC): a New Paradigm for Mobile-Code Security[END_REF][START_REF] Sekar | Model-carrying code: a practical approach for safe execution of untrusted applications[END_REF] method. Briefly, the Enabler attaches a formal proof that the Connector satisfies its contract. Then, the Networked Systems simply check whether the code satisfies the proof.

If the check fails, the user can decide to refuse the Connector or to enforce the private security policy on it (Enforce Policies) by exploiting the run-time enforcement infrastructure (e.g., [START_REF] Castrucci | Enhancing java me security support with resource usage monitoring[END_REF]). Otherwise, the Networked System can proceed to verify whether the contract (correctly representing the application) satisfies the private security policy (Contract-Policy matching [START_REF] Greci | A framework for contract-policy matching based on symbolic simulations for securing mobile device application[END_REF] at deployment-time). Once again, if this step fails, the solution consists in enforcing the private security policy on the execution. Finally, if the previous checks were positively passed, the communication is established without any run-time monitoring (Execute Application).

Trust

Thanks to Connect Enablers, Networked systems get Connected via Connector(s) that can be composed and reused.

Thus, the Connect trust model is defined to allow: (i) Enablers to safely cooperate in order to build and deploy Connectors, (ii) Enablers to assess Connector trustworthiness and hence provides Connected systems with the most trusted Connector and (iii) handle monitoring feedbacks to fairly update the trustworthiness of both Enablers and Connectors.

Enablers Assessment. In order to assess the trustworthiness of each Enabler, the Connect trust model applies a reputation mechanism. The trust reputation of each Enabler is computed from trust relations among Enablers and also from the Enabler's behaviour. The Connect trust model assesses for each Enabler a trust reputation value through a decentralised reputation mechanism. Thus, the reputation of each Enabler is managed by other Enablers, which have been selected with a distributed hash table, such as in CAN [START_REF] Ratnasamy | A scalable content-addressable network[END_REF] or Chord [START_REF] Stoica | Chord: A scalable peer-to-peer lookup service for internet applications[END_REF]. We use several hash functions to replicate the reputation of each Enabler. This prevents against malicious Enablers and also keep the system more resistant to inherent dynamic network behaviour, namely, Enablers that unexpectedly disconnect.

Connector Assessment. In the Connect trust model, Synthesis Enablers assess the Connectors they produce by computing a trust recommendation value, which results from (i) the trust on the Connector based on previous deployment and also from (ii) the trustworthiness of all the Enablers that are involved in the specific synthesis. The deployment history of each Connector is maintained by its Synthesis Enabler. We take inspiration from trust assessment in Web Service composition [START_REF] Nepal | Reputation propagation in composite services[END_REF][START_REF] Paradesi | Integrating behavioral trust in web service compositions[END_REF][START_REF] Kim | Trust Type based Semantic Web Services Assessment and Selection[END_REF], in which all trust relations that are involved in this composition are aggregated and composed in order to return the trust recommendation of the whole composition.

Feedbacks management. The Connect trust model has to update fairly (increase or decrease) the trustworthiness of each Connect stakeholder (i.e., the reputation of the involved Enablers and the trustworthiness of the Enabler on its synthesised Connector) after each Connector deployment. Thus, the Connect trust model deals with two parameters: (i) the degree of involvement (i.e., responsibility) of each Enabler in the process of synthesising and running Connectors and (ii) the recommendation value that is given by each Enabler for its contribution to the Connector. Indeed, we consider that each Enabler must be rewarded or penalised proportionately to both its involvement and the value of its given recommendation. Therefore, in course of time, the Connect trust model will be able to identify trustworthy Enablers and hence will provide more efficient and relevant Connectors. However, after a while, the Connect system will mostly solicit Enablers with a high reputation (i.e., good history). This will preclude newcomers (without history) by making their participation to the running system very difficult or even impossible. Thus, in order to allow Connect networks to evolve with new capable Enablers, we endow the Connect trust model with an incentive Risk-based property, in which, Enablers that have a high reputation are pushed to reduce their recommendation values in order to maintain their reputation (i.e., minimise the penalisation). To implement this incentive property we use The Behaviour function that is defined in [START_REF] Saadi | T2D: A Peer to Peer trust management system based on Disposition to Trust[END_REF]. Thus, by adopting this behaviour, everyone wins. On the one hand, the entities with high reputation will save their position, and on the other hand, this incentive behaviour will boost the bootstrapping phase by giving the opportunity to new legitimate Enablers to be considered by Connect.

Monitoring

The very vision of Connect, i.e., achieving automated and eternal interoperability puts monitoring in a central position for the overall project. In Connect, monitoring is conceived as a common core service used by the other Enablers to implement feedback loops whereby approaches that are normally used off-line (e.g. techniques for dependability analysis, Connector synthesis, behaviour learning) can be adapted to an on-line setting and can be enhanced to cope with change and dynamism. Monitoring is performed alongside the functionalities of the Connected system and is used to detect conditions that are deemed relevant by its clients (i.e., the other Connect Enablers). Upon detecting the occurrence of such conditions, the monitoring system alerts the interested client which, in turn, triggers an update of the analysis, synthesis, and learning. In this way, powerful but expensive techniques are executed only when necessary.

As we intend to realise a monitoring system that can address different purposes, covering both functional and nonfunctional aspects, it must be designed with special emphasis on flexibility. Furthermore, although monitoring can provide valuable support to dependability assurance, it can easily incur in feasibility problems caused by excessive overhead. To cope with this issue, the performance penalty due to monitoring should be minimised, while achieving the intended observation goals. Approaches for reducing the impact of monitoring include using statistical sampling or self-tuning algorithms for directing the focus of monitoring to certain parts of the overall monitored system that are deemed especially critical or interesting [START_REF] Bertolino | Scaling up sla monitoring in pervasive environments[END_REF]. As a matter of fact, most existing monitoring systems follow a best-effort policy, whereby overhead is kept as low as possible but is in fact unbounded. In Connect, we pursue efficiency by adopting predictable strategies to estimate the computational, storage and transmission resources that are demanded by a given set of monitoring goals. This means that the load caused by monitoring will not only be limited, but also predictable and controllable, along the lines of the approach advocated in [START_REF] Callanan | Software monitoring with bounded overhead[END_REF]. Providing a reasoning framework to handle the trade-offs between monitoring precision and efficiency is one of the goals of our research in the remainder of the project.

WORKFLOW PROCESS VIEW

In Connect, the four activities related to dependability span over all stages of the Connect process, i.e., discovery time, synthesis time, and execution time. Combining and integrating the activities within the overall Connect process is a complex iterative endeavour. During this first year of the project, we envisaged a dependability-centric scheme of the Connect process. The high-level description of the scheme is depicted in Figure 2. In the figure, the Connect process is modelled as an activity diagram with separate swim-lanes. There is one swim-lane for each activity related to dependability, plus an additional swim-lane "other Connect activities", which represents the rest of the Connect To serve S1 request, we have here a first decision point: does there already exist a suitable Connector that can be reused? So, when a Discovery Enabler E accepts the request, it will first search for a suitable Connector already synthesised. Suitable here means that, among all the functional and non-functional characteristics of the Connector, this yields adequate dependability properties and a trust level at least equal to the trust level associated to E. If the answer is positive, then the Enabler retrieves an implementation of the Connector from a repository and deploys it, Connecting S1 with a receiver Networked System S2. Moreover, the deployed Connector is provided with a monitor that at execution time will warn the Enabler when and if the established communication is no longer satisfying S1 needs (this may happen for many reasons: because either the environment or S2 changed, or because the trust reputation decays, or due to negative reports from on-line analysis).

If no suitable Connector is available, then the synthesis process is started by the Synthesis Enabler. The latter may interact with the Learning Enabler to infer the desired functional behaviour of the Connector, and may also obtain some dependability requirements from S1 interface description. Hence, during synthesis, the Enabler will interact with the Dependability Analysis Enablers to predict whether the built Connector is satisfacing2 . At execution time, the monitoring mechanism is activated to keep track of the Connector behaviour (monitoring at the Networked Systems interfaces) and of the Connected System (end-to-end). Additionally, when security specifications are provided (security-by-contract), security enforcement mechanisms are activated at execution time. This discover and synthesis flow cycles whenever the communication is no longer satisficing. Throughout, the trust management model is pervasive; among the available Enablers, those yielding the highest trust reputation can be chosen, and trust reputation is updated at execution time according to monitoring feedback.

CONCLUSIONS

We have briefly introduced the European Project Connect and have focused on the unifying dependability framework that is currently under development [START_REF]Deliverable 5.1 -Conceptual models for assessment and assurance of dependability, security and privacy in the eternal CONNECTed world[END_REF]. The concept of dependability in Connect is quite broad, and includes four main activities: model-based V&V, security enforcement and privacy, trust management, and monitoring. A first proposal of a unified dependability-centric life-cycle has been outlined. The life-cycle spans over three phases of the Connect process (discovery time, synthesis time and execution time) and points out the role of the different activities related to dependability. At the time of writing, the Connect project has just concluded its first year, during which we focused on devising appropriate models and background material for the various dependability concerns. In the remaining years of the project, we will focus on developing the workflow process explained in this paper, which integrates different approaches to address the dependability challenges of dynamic, evolving, heterogeneous systems.

  the architectural vision of Connect. Four types of entities populate the Connect world: (i) Networked Systems, which use Connect services; (ii) Connect Enablers, which encapsulate the Connect logic that allows to synthesise a communication bridge between heterogeneous Networked Systems; (iii) Connectors, i.e., the emergent communication bridges synthesised by Enablers; (iv) the Connected System, which is obtained by Connecting different Networked Systems.

Figure 1 :

 1 Figure 1: The CONNECT vision Connect Enablers represent the core of the Connect approach: they can accept requests from Networked Systems, discover new Networked Systems, gather / learn information on their functional and non-functional behaviour, and synthesise a suitable Connector that allows inter-operation among Networked Systems willing to interact. There are different types of Enablers, according to their provided functionality: Discovery Enablers, Learning Enablers, Synthesis Enablers, Monitoring Enablers, and so on.

Figure 2 :

 2 Figure 2: Life-cycle workflow of activities within the CONNECT process

The word satisfice, coined by Herbert Simon, blends "satisfy" and "suffice", to highlight the aim to meet criteria for adequacy, rather than to identify an optimal solution.

ACKNOWLEDGEMENTS

This work is partially supported by the European Commission Framework Program 7 Project Connect (FP7-231167)


Refactorisation de modèles répétitifs pour l'exploration d'architecture d'applications de traitement de signal intensif 1 Introduction

Computation intensive multidimensional signal processing applications are predominant in several application domains such as image and video processing or detection systems (radar, sonar). By multidimensional, we mean that they manipulate primarily multidimensional data structures such as arrays. The difficulty and the variety of these intensive signal processing applications come from the way the elementary functions access their input and output data as parts of multidimensional arrays. The complex access patterns lead to difficulties to schedule these applications efficiently on parallel and distributed execution platforms such as multiprocessor systems-on-chip. Three kinds of scheduling constraints sum up: data dependency constraints, environmental constraints (real-time, power consumption, etc) and hardware platform constraints (available computation, storage and communication resources). A design exploration tool that would guaranty the respect of some of these constraints (data dependencies) while allowing to improve on the others (usage of resources) would be very helpful.

The MARTE (Modeling and Analysis of Real-time and Embedded systems) UML profile [START_REF]A UML profile for MARTE[END_REF][START_REF] Rioux | MARTE: A new profile RFP for the modeling and analysis of real-time embedded systems[END_REF] is the standard for modeling real-time and embedded systems. It is well suited to model intensive signal processing applications thanks to its Repetitive Structure Modeling extension of UML. This extension is designed to provide ways of compact expression of systems having a repetitive structure or topology by the decomposition into repetitions of regularly interconnected components.

We propose here a refactoring tool (included in Gaspard2 [START_REF]Graphical Array Specification for Parallel and Distributed Computing (GASPARD2)[END_REF][START_REF] Piel | Gaspard2: from MARTE to SystemC simulation[END_REF], an Integrated Development Environment dedicated to the visual co-design for embedded systems based on MARTE) for the design space exploration of repetitive MARTE models of intensive multidimensional signal processing applications and we experiment it on a typical radar processing application.

After briefly summarizing the principles of the modeling language in Section 2, the radar application used in the paper is described in Section 3 and modeled in Section 3.2. Accordingly to the rules of transition from the specification model to the execution model presented in Section 4, the refactoring transformations are used to adapt the application to the execution model by the reduction of array sizes and granularity changes in Section 4.2.

Multi-dimensional modeling

To model multi-dimensional signal processing applications, the language must support their core characteristics: multi-dimensional data structures, access to these data structures in a regular way, sliding windows, several sampling rates, cyclic data access (for cyclic space or frequency dimensions) and stateful computations. These requirements have been taken into account in the design of the MARTE Repetitive Structure Modeling package.

Models using the MARTE profile represent visual abstractions that, by the extensive use of the Repetitive Structure Modeling package, aim at expressing a maximum of the parallelism of computations, of targeted architectures and the repetitive distribution of computations on parallel execution units. Throughout the paper we will refer to such models as MARTE RSM models/specifications.

The repetitive specification provides ways to access multidimensional arrays via sub-arrays, the support of sliding windows, the possibility to deal with cyclic data accesses, several sampling rates in the same specification and can express stateful computations such as recursive filters through uniform inter-repetition dependences [START_REF] Glitia | Array-OL with delays, a domain specific specification language for multidimensional intensive signal processing[END_REF]. To make such models statically scheduleable, rules are imposed on the specification, namely regarding the single assignment and the complete production of array elements. These rules and a complete formalism of the Array-OL (Array Oriented Language) model of computation (MoC), the theoretical basis of the MARTE RSM models, are available in [START_REF] Boulet | Formal semantics of Array-OL, a domain specific language for intensive multidimensional signal processing[END_REF]. A comparison to similar models of computation dedicated to signal processing, mainly in terms of allowed data structures and expressiveness, like synchronous dataflow languages (SDF [START_REF] Lee | Static scheduling of synchronous data flow programs for digital signal processing[END_REF] and its multidimensional extensions (G)MDSDF [START_REF] Murthy | Multidimensional synchronous dataflow[END_REF], WSDF [START_REF] Keinert | Modeling and analysis of windowed synchronous algorithms[END_REF]), functional languages (Alpha [START_REF] Karp | The organization of computations for uniform recurrence equations[END_REF]) or imperative languages (Sisal [START_REF] Attali | A formal semantics for sisal arrays[END_REF], SaC [START_REF] Scholz | Single assignment c: efficient support for high-level array operations in a functional setting[END_REF]), is available in [START_REF] Glitia | Array-OL with delays, a domain specific specification language for multidimensional intensive signal processing[END_REF].

Formally, with MARTE RSM, an application is a set of tasks connected through ports, representing multi-dimensional arrays characterized by their shape and their direction. The tasks are equivalent to mathematical functions reading data on their input ports and writing data on their output ports. The tasks are of three kinds: elementary, compound and repetition. An elementary task is atomic (a black box), it can come from a library for example. A compound is a dependence graph whose nodes are tasks connected via their ports, it allows to express task parallelism. A repetition is a task expressing how a single sub-task is repeated, each instance of the repeated task operates with sub-arrays of the inputs and outputs of the repetition, making the repetitions independent and therefore parallel by construction, it allows to express data parallelism. For a given input or output, all the sub-array instances have the same shape, are composed of regularly spaced elements and are regularly placed in the array. The tiler (one tiler per input or output) concept represents the mathematical expression of the elements of the patterns as tiles of the array, and is composed of: a fitting matrix F , whose column vectors represent the regular spacing between the elements of a pattern in the array; o, the origin of the reference pattern (for the reference repetition) and a paving matrix P , whose column vectors represent the regular spacing between the patterns. We can summarize the pattern construction with one formula. For a given repetition index r, 0 ≤ r < s rep (the repetition space is unique for a repetition task and all its inouts and outputs) and a given index i, 0 ≤ i < s pattern in the pattern, the corresponding element in the array has the coordinates

o + (P F ) • r i mod s array , (1)
where s array is the shape of the array, s pattern is the shape of the pattern, s rep is the shape of the repetition space. The pattern construction allows the construction ranging from simple block tiled patterns to complex uniform accesses where accesses non-parallel with the axes are combined with strides and modulo. Nonetheless, in real intensive signal processing applications, most of the access remain parallel with the axes, by block or with sliding windows:

Parallel with the axes. With such accesses, all the vectors of the paving and the fitting matrixes contain at most one non-zero value, making the corre-

INRIA

spondence between the repetition's or pattern's corresponding dimension and an array dimension.

Access by blocks. Uniform and perfectly tiled block-like patterns are accessed.

The fitting and the paving matrix express parallel with the axes construction where the patterns are continuous tiled blocks in the array (each fitting vector contains just one value equal to 11 ) and the blocks are perfectly tiled one after another (paving vectors have non-zero values equal to the dimension of the pattern on the corresponding array dimension).

Example 1

An array with a shape of (80, 50) can be tiled into (10, 5) blocks of (10, 8) elements using the following tiler: fitting = ( 0 1 1 0 ) , paving = ( 8 0 0 10 ) as illustrated on the figure on the right.

Entire tiled dimensions. It is a special case of block access where pattern dimensions take entire array dimensions.

Sliding windows. It represents a block access where the blocks do not perfectly tile on some dimensions, with overlapping blocks which cause array elements to be tiled in multiple patterns. On the dimensions of the sliding, paving vectors do not have non-zero values equal to the dimension of the pattern and the value represents the step of the window on this dimension.

Example 2

Leaving unchanged the paving and the fitting matrix of the block access example and by enlarging the pattern to a block of [START_REF] Labbani | Introducing control in the gaspard2 data-parallel metamodel: Synchronous approach[END_REF][START_REF] Lee | Static scheduling of synchronous data flow programs for digital signal processing[END_REF], we have a sliding window access on the first dimension of the array, with a step of 8.

STAP radar application

This paragraph describes a MTI (Moving Target Indication) application, whose goal is to detect from an aircraft the objects that move on the ground, and especially move slowly among all the other generally still reflecting surfaces under the radar beam (ground clutter). This is done by receiving the echo from the ground of a periodic sequence of radar pulses (bursts). Radar processing permits to estimate both the position of a target through the delay between transmission of a signal (pulse) and reception of its echo, and its speed through the Doppler effect that affects echoes of several identical pulses sent periodically: the speed of the target results in a (small) variation of its distance from the radar, which is only visible as a phase shift on the radar signal (e.g. around 10 GHz). In this basic approach, Doppler processing consists in a bench of filters (e.g. a Fast Fourier Transform) each tuned towards a particular phase shift between successive echoes. This kind of Doppler processing is in some situations sufficient to separate reflecting objects on the basis of their speeds. When the beam is directed toward the ground, the largest part of the echoed energy is supposed to come from the still objects that compose the ground (called clutter), while the moving objects of interest send weak but phase-shifted echoes. However, the radar beam is not perfectly sharp and has a width of a few degrees, which results in giving to some still objects on the ground at the borders of the beam a relative speed with respect to the aircraft (due to the aircraft's own speed) and creating undesired interferences over the moving targets echoes: this creates an ambiguity between intrinsic speeds and azimuths of targets. Adaptive filtering techniques, where fixed filters are replaced by filters that are computed at run-time from the received signal itself, help to minimize at best the effects of this unwanted clutter signal: in this MTI case, the Space Time Adaptive Processing is used. In this method, a set of filters is computed at every burst, by solving linear systems whose right hand side terms are reference vectors of theoretical phase patterns expected on antenna sub-arrays at several consecutive pulses, each of which corresponding to a particular (velocity, angle) hypothesis of the target relatively to the aircraft. This is shown in Figure 1 where 2D patterns on dimensions antenna and pulse (rec) are considered to compute filters that remove the natural ambiguity between velocity and azimuth.

Implementation constraints

Those characteristics are mainly:

A large part of the application is data-flow, manipulating multi-dimensional arrays of data.

The processing chain uses different operators, with in particular different needs in terms of precision and dynamic range.

INRIA

The main STAP application, GlobalSTAP takes as input an multidimensional infinite array of data from the sensors (InputSignalET ) and, using the steer vectors provided by SteerVectCompIET and the Doppler coefficients provided by Gen Coef DopplerET, processes the data and provides the radar detection results as an infinite array, which are consumed by OutputSignalET for display, storage or post-treatment. the processing chain is dynamic, and varies during run-time by frequent variation of algorithm parameters (sizes of arrays, loop bounds, . . . ) while keeping roughly the same processing graph. This is generally called multimoding in the radar community.

the computational load is high enough to clearly involve parallel computing hardware.

real-time performance is one of the key requirements, both in terms of computation throughput and latency. This may result from some operational requirements and/or embedded architecture constraints such as memory limitations.

STAP model

The STAP application was modeled in Papyrus UML using the MARTE Profile2 .

Starting from the top level, the application is successively depicted using a compound or repetitive decomposition, until the wanted detail level is reached, represented by elementary tasks that can be deployed on library functions. The top level of the specification, illustrated on Figure 2, describes the global functionality and the interaction with the environment.

The infinite dimension of the arrays processed by GlobalSTAP represents the abstraction of time and Figure 3 describes the data-flow level of the application, the infinity repetition (time) of a single STAP data treatment.

Just one sample tiler is shown, expressing how the infinite radar signals, represented by an array of shape {8, 128, 111, * } is decomposed into an infinity, { * }, patterns of shape {8, 128, 111}. The paving matrix of {{0, 0, 0, 1}} expresses the correspondence between the infinite repetition and the last dimension of the array, while the fitting matrix of {{1, 0, 0, 0}, {0, 1, 0, 0}, {0, 0, 1, 0}} expresses the correspondence between the pattern dimensions and the first three dimensions of the array. Figure 4 illustrates the compound decomposition of the repeated task of Figure 3 into successive repetitive filters, with array sizes and repetition spaces shown on the figure. The tilers that express the pattern/tiles construction for each repetition were not made visible. 3Each repetitive filter has a different functionality and different data access patterns:

PulseCompression takes sliding windows with a step of {1} of {16} values on the third dimension of the input array and computes an average value for each of the pattern.

CovMatrixEstim takes {119, 96} blocks of {10, 8}, with a sliding window with a step of {1} on the second dimension of the input array and expands them into blocs of {80, 80} which will be arranged into an array of size {80, 80, 119, 96}.

AverageCovar eliminates the third dimension of the arrays by computing an average of {119} values.

MatInv takes {96} square matrices of {80, 80} and inverses them.

Stap Filter applies the {128} steering vectors of dimension {80} to each line of the inverted matrices, producing an array of size {128, 96, 80}.

Stap Application compares the filtered values with the initial compressed pulses, by blocks of {8, 10} to identify the movements.

RR n°0123456789

For the PulseCompression repetition, starting from each element of the input array (identity paving matrix), a pattern of {16} elements on the third dimension is used to compute a single value, {}, values rearranged into a tree dimensional array with a shape of {8, 128, 96}. The difference of size between the input and the output array on the third dimensions (111 -96 = 15) is caused by the sliding window accesses, for the last 15 elements the access window will exit the array dimensions. CovMatrixEstim repetition has a similar sliding window functionality, this time 2D blocks with a shape of {10, 8} sliding on the second dimension with a step of 1. These blocks are expanded into {119, 96} square blocks of {80, 80}. Int Doppler applies the {128} Doppler vectors of size {119} to identify the speeds of the moving targets.

Each repetition is characterized by different repetitive and uniform pattern accesses, data consumption or production, expressed by the tiler informations of each connection inside the repetition, accordingly to relation 1. Figure 5 illustrates the tiler construction for two of the STAP filters, PulseCompression and CovMatrixEstim.

At filter level, each repeated task has an elementary functionality which can be deployed on library functions: matrix inversion, average computations, etc.

MARTE RSM models are static and therefore we have chosen to implement a single mode of the multi-moding functionality mentioned in Section 3.1. Multiple modes can be modeled with the use of control structures based on mode automata have been proposed by Labbani et al. [START_REF] Labbani | Introducing control in the gaspard2 data-parallel metamodel: Synchronous approach[END_REF][START_REF] Labbani | UML2 profile for modeling controlled data parallel applications[END_REF] or in the upcoming beta3 or 1.0 version of MARTE (no public reference yet available at the time of writing) but they are outside the scope of this study.

Towards an execution model

A MARTE RSM specification expresses the maximum of parallelism through the use of the repetitive decomposition. It describes the data dependencies between the elements of the arrays and, as a direct consequence, a strict partial order between the calls of the tasks. A valid specification must be statically INRIA defined and therefore defines a strict partial order. Indeed, any schedule that respects this order will computes the same output values from the same inputs. The construction rules that assure that a specification is valid are described and proved in [START_REF] Boulet | Formal semantics of Array-OL, a domain specific language for intensive multidimensional signal processing[END_REF].

The execution model represents the abstraction of the execution and it must abide with the strict partial order defined by the specification. It is a design intention that, by expressing the minimal order of execution, lots of decisions can and have to be taken when mapping a MARTE RSM specification onto an execution platform: how to map the various repetition dimensions to time and space, how to place the arrays in memory, how to schedule parallel tasks on the same processing element, how to schedule the communications between the processing elements? It is a strength of this specification that the space-time mapping decision is separated from the functional specification. This allows to build functional component libraries for reuse and to carry out some architecture exploration with the least restrictions possible.

We have chosen to make the transition from a MARTE RSM specification to an execution model the most straight-forward possible. Indeed the execution model should reflect the specification. This choice has as advantage that the execution model remains similar to the structure of the specification (parallelism, granularity), at least until the code generation. A representative example is the generation of VHDL code that will be used for FPGA synthesis 4 and where the component structure of the specification can be found in the VHDL modules and even on the FPGA layout. It comes down to the constraint that a component may starts its execution when all its input arrays are available. This constraint introduces a major problem, represented by the so called "synchronization barriers" between the components. Such a barrier is created by the data dependencies; a representative illustration of the problem is the presence of any intermediate array that contains an infinite dimension, which would cause the execution to be stalled in that point. As a solution, some repetitions can be transformed to flows, the execution of the repetitions is pipelined and the patterns are read and written as a flow of tokens (each token carrying a pattern).

High-level data-parallel transformations

The data-parallel code transformations can be used to adapt the application to the execution, allowing to choose the granularity of the flows and a simple expression of the mapping by tagging each repetition by its execution mode: data-parallel or pipeline. A great care has been taken with these transformations to ensure that they do not modify the precise element to element dependences [START_REF] Dumont | Spécification Multidimensionnelle pour le traitement du signal systématique[END_REF][START_REF] Soula | Principe de Compilation d'un Langage de Traitement de Signal[END_REF]. A comparative study between these transformations and the loop transformations in the context of program optimizations can be found in [START_REF] Glitia | High level loop transformations for multidimensional signal processing embedded applications[END_REF]. Loop transformations [START_REF] Bacon | Compiler transformations for highperformance computing[END_REF] are used intensively for optimizations at compilation time but the complexity of optimization algorithms is one reason why many compilers still use heuristics.

Our high-level transformations are designed as tools at the specification level that can be used for adapting the application to the execution on parallel embedded platforms and for design space exploration, leading to some interesting characteristics:

The transformations work as a refactoring tool, their result is translated into model changes at the same level of abstraction.

The application keeps its exact functionality, the same output values are computed for the same inputs.

As optimization targets, the reduction of array sizes and the parallelism management are the priority. A specification expresses the maximum of parallelism and the transformations can be used to change its granularity for a better mapping on a parallel execution platform.

The specification, the refactoring and the transition to an execution model are separate stages. The same specification can be adapted differently to the execution, accordingly to platform and execution constraints.

Regardless of their role, all these transformations have a similar impact on an application, by redistributing repetitions through the hierarchy levels, with the creation or suppression of hierarchy levels.

Taking each transformation one by one, we have:

Fusion takes two successive repetitive tasks, creates a superior hierarchy level for the computed common repetition, while what is left of the initial repetitions is placed on the inferior hierarchy level, minimizing the size of the intermediate array.

Tiling splits a repetition into blocks, by creating a hierarchy level.

Change paving (either by dimension creation or by linear growth) acts on redistributing repetitions through successive levels of hierarchy and modifying the granularity of the application.

Collapse, by being the opposite of fusion and tiling, suppresses the superior hierarchy level, its repetitions being added to each of the inferior level repetitions.

Refactoring using high-level transformations

Next, we will see how the STAP specification can be adapted to the execution using the refactoring and how a heuristic of transformation chaining can be deduced.

Isolation of the infinite dimensions. The presence of infinite dimensions (of arrays or repetitions) throughout the application is the first thing to take care of when passing to the execution. An infinity value of a repetition will block the execution in that point and an array with an infinite dimension cannot be placed in a limited size memory. As the infinity is used to express the time (or the data flow), a solution is to isolate the infinity values at a high level of the hierarchy and consider this level as the data-flow level at the execution: the arrays will not be allocated entirely in memory (just the patterns) and an sequential execution will be chosen for the repetition. By the use of the fusion transformation on successive infinite repetitions, a common repetition can be computed and will represent the data-flow level at execution5 . The STAP application was modeled already having all the infinity values at one hierarchy level, Figure 3, and therefore this step can be skipped. A specification where the infinity values would have been at the filter decomposition level, Figure 4, would express the same exact functionality but would necessitate the isolation of the infinity at a data-flow level before passing to the execution.

Granularity change. Execution constrains may impose changes in the granularity of an application. Taken for instance, if we have 4 processors and want to execute the repetition of Figure 3 in parallel, a tiling transformation can be used to split the repetition into blocks of 4 repetitions that will be placed on the 4 processors and executed in parallel, while the sequence of blocks will represent the data-flow level. It is what we call changing the granularity of a repetition and the result of such transformation is shown on Figure 6.

Reduction of the size of the intermediate arrays. The reduction of the size of the intermediate arrays can be achieved by the use of the fusion transformation. An elementary fusion computes the minimum intermediate array between two successive repetitions.

Definition 1 (Minimum intermediate array) Between two successive repetition tasks6 , a minimal intermediate array is represented by a minimum group of patterns produces by the first task that allows the second task to execute at least once, therefore producing elements and in consequence allowing a non-blocking execution. Definition 2 (Multiple fusion) A fusion between several connected repetitive tasks can be achieved by the chaining of elementary fusion and collapse transformations. Following the dependence order between tasks, each task is fusioned with the result of the previous fusion8 , while a collapse transformation limits the explosion of hierarchy levels. Another factor that comes into play is the amount of re-computations introduced into the application by the fusion. Definition 3 (Re-computation) Re-computations are represented by an increase of the repetitions for the first task involved in a fusion, caused by the pattern production/consumption between the two tasks.

Remark 3

The complete repetition of a task is given by concatenating all the shapes of the hierarchical repetitions starting at the level of the task and climbing the hierarchy levels to the top level 10 . Re-computations are represented by an increase in the complete (takin into account all the levels of hierarchy) repetition of a task after the fusion.

Sliding windows accesses with some initial elements found in several pattern groups determines the first task to compute them several times, after the fusion. In the case of re-computation, the decrease of intermediate array size has as side effect an increase of computations.

Example 5 On Figure 7, the complete repetition of the first repeated task is, by concatenating the repetition spaces of the two hierarchy level, of {119, 96, 10, 8}, while the initial repetition was of {8, 128, 96} and therefore the number of repetitions increase with a factor of 119 × 96 × 10 × 8/(8 × 128 × 96) = 9.29. Thus, in the case of intermediate values that are used several times, the designer has to make a trade-off between the storage in memory or multiple computations of these intermediate values. The hierarchy of repetitions is represented by brackets in the table. After a complete fusion of the repetitions, a common repetition of {128, 96} is computed and the total repetition for each sub-repetitions is given by multiplication with this common repetition. The re-computation is computed as the division of the repetition after and before the refactoring.

Reduction of intermediate arrays on STAP

Table 1: Repetitions for the complete fusion.

The first four repetitions are grouped into a common repetition of {96} and the last two into a repetition of {128, 96} of a compound containing two subrepetitions of the initial tasks, shown on Figure 10. Complete fusion. A complete fusion (the fusion of all the repetitions at a hierarchy level) is not appropriate in this case, as shown in Table 1 (containing informations on the repetitions before, after and the introduced re-computations), where we find ourselves with a great amount of re-computations. Accordingly to Definition 2, the fusion of multiple repetitions minimizes only the last intermediate array. Table 2 shows how just two intermediate arrays have a reduced size, as for the others we have even an increase in array size, caused by the multidimensional re-arrangement of patterns as result of the succession of fusion/collapse transformations 11 Array size in memory is given in memory units of the data type of array elements, by the multiplication of the multidimensional dimensions of its shape.

In the table, arrays are identified by the tasks that produce/consume the array (Producer→Consumer) and the reduction in size is given by the division of array sizes before and after the refactoring.

Table 2: Array sizes for the complete fusion.

Nonetheless, such a transformation provides useful informations that can be used for finding the best sequence of fusions for our objective. First of all, it provides the fusion order representing the strict partial order between the repetition tasks, in this case: PulseCompression ⊕ CovMatrixEstim ⊕ Aver-ageCovar ⊕ MatInv ⊕ StapFilter ⊕ StapApplication ⊕ IntDoppler. Secondly, on Table 1 we can identify where changes in the re-computations appear and therefore the fusions that introduce re-computations, in our case: MatInv ⊕ StapFilter and StapFilter ⊕ StapApplication. In our goal to reduce at minimum the re-computation, it would suggest that the grouping of the first four repetitions and of the last two for fusion, while isolation StapFilter, would not introduce any re-computations. Two-by-two fusions. Other fusions that provide useful informations are the fusions of each two successive repetitions. The results contain informations on the minimal intermediate array achievable between any two repetitions and on the re-computations introduced by the fusions, as shown on Table 3. The maximum reduction of the intermediate array together with the recomputations introduces on the first sub-repetition, achieved by the fusion of each two successive repetitions.

Table 3: Fusion two-by-two.

Best choice fusion. The informations provided by the complete and the twoby-two fusions can guide the choice of a sequence of fusions that achieves the best results for our chosen objective of reducing at maximum the intermediate arrays while limiting the re-computations. The complete fusion suggests the grouping of the first four repetitions and of the last two but the two-by-two fusions indicate that the fusion of the first two repetitions introduces re-computations with a factor of nearly 10 for a reduction of array size with a factor of 1228.8. We have two alternatives for the first group of repetitions:

If the re-computation factor of 10 is acceptable, we can group the first four repetitions for the fusion.

Otherwise, just repetitions two to four will be fusioned, with no re-computations.

For illustration, we have chosen the first alternative, grouping the first four tasks and the last two. The result shows a reduction to maximum (accordingly to Table 3 A part of the transformed application accordingly to the previous algorithm are illustrated on Figure 9, the transformed filters level, and on Figure 10 the sub-repetitions for the last two tasks.

Result analysis

In the previous section we have seen how the high-level transformations can be used to adapt a specification to the execution. Optimizations can be of two kinds, platform dependent or general-purpose. The reduction of intermediate arrays can be considered as a general-purpose optimization but, as shown, execution constrains can guide the choice of fusions that lead to the reduction of intermediate arrays. The granularity changes, through the use of transformations like change paving, tiling or collapse, are more platform-dependent optimizations, aiming at the adaptation of the specification to the execution platform and the optimization of the placement of repetitions on parallel architectures.

Signal processing applications are often represented as successive repetitive filters, as the case of the STAP application of Figure 9. The complex pattern accesses makes it impossible to reduce at maximum every intermediate array and sometimes only with the introduction of additional computations. We have shown how, by exploring some fusion configurations, we can extract informations that lead us to the best choice of chain of transformations. The complete fusion provides informations on the strict partial order and on where changes in re-computations appear, while the two-by-two fusions provide the values of the maximum achievable reductions and on the re-computations introduced by such a reduction. These informations were used to separate the repetitions into groups by forbidding fusions that introduce considerable re-computations. Different objectives and different applications might determine the alternative use of fusions, taken for instance the presence of an infinite dimension intermediate array, where the elimination of the infinite dimension has priority on the introduced re-computations.

Acknowledgement

This work has been partially supported by the Ter@ops [START_REF]avenue de l'Europe -38334 Montbonnot Saint-Ismier Centre de recherche INRIA Nancy -Grand Est : LORIA, Technopôle de Nancy-Brabois -Campus scientifique 615, rue du Jardin Botanique -BP 101 -54602 Villers-lès[END_REF] project of the System@tic competitiveness pole.

Conclusions

The present article shows how high-level data-parallel transformations can be used to explore the design space of multi-dimensional intensive signal processing applications with the objective of adapting a specification to the execution. In the context of Gaspard2 environment [START_REF]Graphical Array Specification for Parallel and Distributed Computing (GASPARD2)[END_REF], using a visual UML interface and the MARTE profile, multi-dimensional intensive processing applications can be modeled, together with repetitive architectures and repetitive placement of the applications on such architectures. Before the code generation, a MARTE RSM specification must be adapted to the execution platform by reducing array sizes and adapting the application's granularity to the architectural and execution constraints. Starting from an application model, different strategies can be chosen to adapt the specification to the execution. These strategies together with different mappings can be easily explored with possible feedback from the code generation, simulation or execution. As future work, these different strategies could be implemented and integrated in the environment together with a semi-automatic refactoring: proposition to the user of different strategies with computed gains in array size reduction and re-computations.

Figure 1 :

 1 Figure 1: STAP.

Figure 2 :

 2 Figure 2: STAP: top level.

Figure 3 :

 3 Figure 3: STAP: data-flow level.

Figure 4 :

 4 Figure 4: STAP decomposition.

Figure 5 :

 5 Figure 5: First two filters: tiler construction.

Figure 6 :

 6 Figure 6: Tiling into blocks of shape {4}.

Figure 7 :Remark 1 Example 3

 713 Figure 7: Repetitions of first two tasks after the fusion.

Remark 2 Example 4

 24 By a multiple fusion, just the last9 intermediate array is minimized. The other intermediate arrays represent the minimum group of patterns needed for the execution at least once of the last repeated task, and not of the repetitive task that consumes this array. Figure8shows the fusion of the repetitions PulseCompression ⊕ CovMatrixEstim ⊕ AverageCovar ⊕ MatInv. The first three sub-repetitions

Figure 8 :

 8 Figure 8: Repetitions of first four tasks after the fusion.

Figure 9 :

 9 Figure 9: Top level transformed application. The reduction of intermediate arrays is the principal use of fusion transformations. Having several successive repetitive tasks, we need a way of reducing at maximum the set of intermediate arrays, while avoiding blocking points in the execution and limiting as much as possible the re-computations introduced by the fusions. Different mappings might impose slightly different heuristics, like forbidding re-computations or the priority of minimizing the array sizes in the detriment of re-computations. On STAP application of Figure 4, we have chosen as objective to minimize the intermediate arrays while limiting the re-computations.

Figure 10 :

 10 Figure 10: Sub-repetitions of StapApplication and IntDoppler.

  .

	Array	Size before	Size after	Reduction
	PC→CME	8 × 128 × 96	8 × 128 × 119	0.807
	CME→AC	80 × 80 × 119 × 96	80 × 80 × 119 × 119	0.807
	AC→MI	80 × 80 × 96	80 × 80 × 119	0.807
	MI→SF	80 × 80 × 96	80 × 80 × 119	0.807
	SF→SA	80 × 128 × 96	80 × 119	103.26
	PC→SA	8 × 128 × 96	8 × 128 × 119	0.807
	SA→ID	119 × 128 × 96	119	12288

  of three levels of repetitions for these two repetitions. The arraysize reductions are shown in Table4, while the repetitions and re-computations in Table5.

	Array	Size before	Size after	Reduction
	PC→CME	8 × 128 × 96	8 × 10	1228.8
	CME→AC	80 × 80 × 119 × 96	80 × 80 × 119	96
	AC→MI	80 × 80 × 96	80 × 80	96
	MI→SF	80 × 80 × 96	80 × 80 × 96	1
	SF→SA	80 × 128 × 96	80 × 128 × 96	1
	PC→SA	8 × 128 × 96	8 × 128 × 96	1
	SA→ID	119 × 128 × 96	119	12288

) of arrays: CovMatEst→AvCov, AvCov→MatInv and StapApp→IntDopp but a reduction non-maximal for PulCompr→CovMatEst. On the second level of the hierarchy, by the fusion of the two sub-repetitions, PulseCompresion and CovMatrixEstim, we can further reduce (to maximum) this array, with as result INRIA the presence

Table 4 :

 4 Array sizes for the best choice fusion.

	Task	Rep. before			Rep. after		Re-comp.
	PC CME AC MI	8 × 128 × 96 119 × 96 80 × 80 × 96 96	96 ×	    	119 ×	10 × 8 1 80 × 80 1	    	9.29 1 1 1
	SF	128 × 96 × 80			128 × 96 × 80		1
	SA ID	119 × 128 × 96 128 × 96		128 × 96 ×	119 1		1 1

Table 5 :

 5 Repetitions for the best choice fusion.

Résumé : La conception efficace d'applications pour le traitement intensif de signal demande de prendre en compte trois types de contraintes : celles dérivées des dépendances de données, les exigences non fonctionnelles (temps réel, consommation d'énergie) et la disponibilité des ressources de la plateforme d'exécution. Nous proposons ici une stratégie visant à utiliser un outil de refactoring dédié à ce type d'applications pour aider dans l'exploration de l'espace de conception. Cette stratégie est illustré sur une application industrielle de traitement radar, modélisée en utilisant le profile UML Marte conçu pour la modélisation et l'analyse de systèmes embarqués temps réel. Cela nous permet de trouver de bons compromis entre l'utilisation des ressources de stockage et de calcul et dans l'exploitation du parallélisme (parallélisme à la fois de tâches et de données).Mots-clés : langage de spécification, parallélisme, transformations de code de haut-niveau, optimisations, exploration de l'espace de conception, stratégie de refactoring

RR n°0123456789

Pseudo-identity matrix, on each line or column we can find at most one non-zero value of 1, but the matrix may not be square.RR n°0123456789

Throughout the paper, figures represent real manipulable UML models.RR n°0123456789

A complete model is available at http://gforge.inria.fr/frs/download.php/5755/ examples_papyrus.zip.INRIA

available within Gaspard2 framework.RR n°0123456789

The fusion of two infinite repetitions that fails to isolate the infinity at top level indicates an invalid specification.

The first task produces an array consumed by the second one.RR n°0123456789

In this case exactly once, {}.

We start by fusioning two repetition.

The order of tasks in a multiple fusion is given by the strict partial order between these tasks.INRIA

The infinite repetition at data-flow level is neglected in out paper.RR n°0123456789

Initial overlapping accesses are expanded through multiple dimensions with elements duplication.RR n°0123456789

http://www.inria.fr ISSN 0249-6399