Françoise Guichard

What can we learn from AMMA about physical processes and models?

Broad context

AMMA stands for African Monsoon Multidisciplinary Analysis; it is "an international project to improve our knowledge and understanding of the West African monsoon (WAM) and its variability with an emphasis on daily-to-interannual timescales" [START_REF] Redelsperger | African Monsoon Multidisciplinary Analysis (AMMA): An international research project and field campaign[END_REF]; further information can be found at http://science.amma-international.org/about/index.

An important motivation for AMMA is the major regional scale and multi-decadal West African drought. It started at the end of the 1960's, and was particularly severe in the seventies and eighties (Figure 1). It is indeed considered as the strongest observed event of rainfall variability at these time and space scales, and the actual mechanisms accounting for this drought are yet to be precisely determined (e.g.; Hulme 2001). In fact, modelling the West African weather and climate with current GCMs appear to be particularly difficult (Panareda et al. 2008, Hourdin et al. 2008). It is therefore not unexpected that climatic projections diverge widely over this region; Cook and Vizi (2006) for instance show how different ocean-coupled general circulation models (GCMs) predict either much drier or much wetter conditions over the Sahel for the twenty-first century.

(a) (b)

Figure 1, source [START_REF] Ali | The Sahelian standardized rainfall index revisited[END_REF] :(a) Sahelian precipitation index (SPI) for the period 1905-2006; the SPI corresponds here to an arithmetic mean of normalized precipitation per year i from individual stations j , , i.e. SPI(i) = Σ j (P i,j -<P j >) / σ j , where P i,j is the annual rainfall for year i at station j, σ j the standard deviation of annual rainfall at station j, and <P j > the average annual rainfall at station j, and (b) map of present rain gauges and SYNOP network.

As a result, the significance of conclusions that have been drawn from modelling approaches is sometimes limited. This probably contributes to the contrasting views found in the literature (e.g.; Charney 1975, Eltahir and[START_REF] Eltahir | Dynamics of wet and dry years in West Africa[END_REF]. Indeed, datasets have been particularly limiting for testing the relevance of hypotheses or mechanisms put forward to account for various features of the West African monsoon. For instance, the role of human-induced changes on the variability of the land surface -and its consequences on the monsoon system-had been proposed as a major cause for the drought emphasized above. However, this view has been much debated subsequently. It appears now that the reality involves more subtle modes of soil-surfacevegetation-atmosphere interactions [START_REF] Taylor | The influence of land use change on climate in the Sahel[END_REF] as well as oceanic influences and climatic variability [START_REF] Lamb | Large-scale tropical surface circulation patterns associated with Subsaharan weather anomalies[END_REF][START_REF] Folland | Sahel rainfall and worldwide sea temperature 1901-1985[END_REF].

Physical and dynamical processes are strongly coupled within the West African monsoon. Therefore, (i) a better quantification of processes at play together with (ii) an identification of mechanisms and feedback loops actually operating, including their space and time scales, are probably central to advancing our understanding of this monsoon system.

In this respect, AMMA provides the first dataset documenting physical and dynamical processes on a range of time scales, from turbulent to inter-annual ones, along a pronounced meridional gradient, from the Gulf of Guinea to the Sahara, in a region where routine observations are notably sparse. In very short and incomplete, this includes: (a) a reinforcement of the existing network, notably for the soundings [START_REF] Parker | The AMMA radiosonde program and its implications for the future of atmospheric monitoring over Africa[END_REF], (b) the installation for a few years of several ground-based stations (measuring in particular surface flux, precipitable water from GPS, aerosols properties), (c) an intensive observation period in 2006, when several aircraft, ships and ground-based radar were used, the frequency of soundings was enhanced, the ARM mobile facility was deployed in Niamey [START_REF] Miller | The Arm Mobile Facility and its first international deployment: Measuring radiative flux divergence in West Africa[END_REF], among other instruments and platforms not listed here. This will allow us to conduct analyses of datasets, thus providing valuable guidance for model developments.

The importance of physical processes in the West African monsoon system implies that, in models, the parametrizations of these processes need to be explored in details. This includes interactions among them (e.g. surface, cloud and radiative processes) and couplings with the dynamics. In the past, such studies have been few, so that our knowledge is limited. On this modelling side, coordinated studies started within AMMA towards the assessment of models. Namely, this concerns land-surface modelling (ALMIP, Boone et al. 2008), the simulation of the water budget associated with convective systems in mesoscale models (Guichard et al. 2008a), and the seasonal cycle in climate models, including intraseasonal and synoptic modes of variability (AMMA-MIP, [START_REF] Hourdin | The AMMA-Model Intercomparison Project[END_REF], WAMME, Xue et al. 2008a).

Hereafter, I first present some important aspects of the West African monsoon system (section 2). In section 3, I summarize results from model intercomparisons; this helps providing an updated view on the capacities and limits of currently used modelling systems. Then, in section 4, I focus more precisely on processes involved in the water and energy cycles, as directly inferred from surface data in the Sahel. Such observational studies allow in particular to discriminate between mechanisms actually operating against existing hypotheses. Finally, in section 5, I conclude and present some perspectives regarding how AMMA can contribute to process studies and improvement of models in the future.

Note that results and discussions presented in sections 3 and 4 do not aim at covering the whole range of processes involved in the WAM system; they focus mainly on convection, cloud and radiative processes in relation to the surface water and energy budgets, and make use of material presented in [START_REF] Hourdin | The AMMA-Model Intercomparison Project[END_REF] (section 3.1), Guichard et al. (2008a) (section 3.2) and Guichard et al. (2008b) (section 4).

Basics features of the West African monsoon

It emerges from past research on the West African monsoon a significant but partial and composite knowledge, some elements of which are summarized below (and illustrated in the talk). Results from past experiments GATE (1974), COPT (1981), SEBEX (1990SEBEX ( -1991)), HAPEX-Sahel (1992) and JET2000 (2000) and related research stand out as important but separated steps in the building process of this knowledge.

At large scale, the area displays well defined and strong meridional gradients South of the Sahara. They are manifest on surface fields (rainfall, vegetation, albedo), as well as in the atmosphere above (e.g.; the African Easterly jet developing in the Summer on the northern side of the rainbelt around 650 hPa, Thorncroft andBlackburn 1999, Cook 1999). These meridional features vary widely throughout the year (wet and dry seasons), and they display coupled seasonal and interannual fluctuations [START_REF] Grist | A study of the dynamic factors influencing the rainfall variability in the West African Sahel[END_REF] -see also [START_REF] Janicot | Large-scale overview of the summer monsoon over West Africa during the AMMA field experiment in 2006[END_REF] for an overview of the 2006 monsoon. This configuration inspired several modelling studies based on a zonally-symmetric modelling framework (e. g.; [START_REF] Zheng | A soil moisture-rainfall feedback mechanism, 2, Numerical experiments[END_REF]Eltahir 1998, Peyrillé et al. 2007) and motivated the AMMA-CROSS project (Hourdin et al. 2008, briefly discussed below).

Then, the seasonal cycle is not smooth, i.e. intraseasonal variability is significant. For instance, the onset of the rainfall in the Sahel often takes the form of a fast "monsoon jump" during which the rainbelt is shifted some 5° northwards from its Spring location, at around 5°N along the coast of the Guinean Gulf. The depiction of this phenomenon is actually recent (Le Barbé et al. 2002, Sultan and[START_REF] Sultan | The West African monsoon dynamics. Part II: the "preonset" and "onset" of the summer monsoon[END_REF]).

Nevertheless, it can be noticed that such jump-like structures also characterizes other monsoon regions (e.g.; [START_REF] Lau | Seasonal variation, abrupt transition, and intraseasonal variability associated with the Asian Summer monsoon in the GLA GCM[END_REF]. More broadly, the mechanisms driving intraseasonal variability are not yet well understood. Recent studies have pointed to some role for the spatial configuration of the surface albedo (see [START_REF] Ramel | On the northward shift of the West African monsoon[END_REF], and for equatorial Kelvin and Rossby waves (e.g.; Matthews 2004).

At synoptic scale, atmospheric variability in Summer is dominated by African easterly waves (disturbances) travelling across West Africa (e.g.; [START_REF] Reed | The structure and properties of African wave disturbances as observed during Phase III of GATE[END_REF], and accounting at least partly for the large-scale organization of moist convection (this alone does not mean however that moist convection is simply forced by the dynamics of African easterly waves (AEWs)). These waves display a well defined signature in the meridional wind of the lower atmosphere; they are typically the strongest and the most coherent in September, a period during which Atlantic tropical cyclones have been shown to be associated with AEWs [START_REF] Thorncroft | African easterly wave variability and its relationship to Atlantic tropical cyclone activity[END_REF]. Their development had been initially related to the instability of the AEJ. However, recent studies, which consider more realistic background flows and examine the actual morphology of the waves, advocate other sources of AEW initiation (e.g.; [START_REF] Berry | Case study of an intense African easterly wave[END_REF]; they also emphasize interactions between waves and physical processes (Taylor andClark 2001, Hsieh and[START_REF] Hsieh | Generation of African easterly wave disturbances: Relationship to the African easterly jet[END_REF]. Thus, it appears that much is still to be understood regarding the nature of AEWs, their initiation, and more widely their entire life cycle (maintenance, splitting, merging, decay).

At mesoscale, attention has been paid to deep precipitating convection, but not so much to shallower clouds, nor to diurnal cycle issues. Over the region, moist convection can be very deep, with intense lightning activity. In the Sahel, this strength is not necessarily coupled to very high rainfall rates though, which points to the significance of rainfall evaporation. This is an area where long-lived spectacular mesoscale squall lines develop, accompanied by strong convective outflows sometimes materialized by lifted dust as haboobs (see talk, last page, middle photo). Mesoscale convective systems, taking or not the form of well defined squall lines, account for more than 70% of rainfall over this area (Mathon et al. 2022). This mesoscale organization of convection is nevertheless accompanied by a significant patchiness of surface rainfall down to scales on the order of ten kilometres. The nature of this patchiness is not well known, although observations provide evidence of positive soil moisture-rainfall feedbacks [START_REF] Taylor | Observational evidence of persistent convective-scale rainfall patterns[END_REF].

Finally, on a wide range of space and time scales, the surface and low atmospheric levels are thought to be key elements of the West African monsoon (e.g.; Charney 1975, Eltahir and[START_REF] Eltahir | Dynamics of wet and dry years in West Africa[END_REF]. However, the mechanisms of interactions actually operating between the surface and the overlying atmosphere are not well -and not all-known nor quantified. For instance, low-level mesoscale features were identified during JET2000 [START_REF] Parker | Analysis of the African easterly jet, using aircraft observations from the JET2000 experiment[END_REF], but their significance in the WAM remains to be more fully explored. From the modelling side, the considerations above implies that particular care is required to simulate surface and boundary layer processes, and therefore, rainfall, vegetation, as well as clouds and aerosols, and likely convective outflows and falling rainfall evaporation.

3.

Assessing current performances and limitations of models over West-Africa

At large scale

As pointed out in section 1, at regional scale, current coupled GCMs diverge particularly widely over West Africa. In such a modelling configuration however, errors in the ocean and in the ocean-atmosphere coupling can dominate over other sources of differences. This points to the need for alternative modelling frameworks. At large scale, three modelling projects have been set up, ALMIP, AMMA-MIP and WAMME (Xue et al., 2008b); their first goal is to provide such adequate frameworks and to evaluate GCMs and land-surface models over West Africa.

Within AMMA-MIP for example, a "light but relevant framework to assess the model skill in terms of seasonal and intra-seasonal variations of West African monsoon" [START_REF] Hourdin | The AMMA-Model Intercomparison Project[END_REF]) had been set up as follows. SST have been prescribed, as it aims to evaluate more basic aspects of the simulation of the WAM at large scale. In practice, the focus is on the predominant dynamical structures such as the monsoon flow and AEJ, the rainfall belt, surface fluxes, and the mechanisms accounting for their simulation. As in [START_REF] Siebesma | Cloud representation in general-circulation models over the northern Pacific Ocean: A EUROCS intercomparison study[END_REF], a cross-section (a meridional one here), AMMA-CROSS is used for this purpose. It appears that current NWP (re-)analyses are valuable to assess some of these features, although not all of them. Namely, they provide relatively close pictures of zonal circulations and intraseasonal fluctuations (Figure 2), but not of meridional wind and vertical velocity (Figure 3), nor of rainfall, or surface and TOA energy fluxes.

For instance, the AEJ location (latitude and height) and strength are very close among (re-)analyses, while the basic characteristics of the low-level monsoon flow such as its meridional extend, height and strength are more contrasted. Note that some of the differences in the AEJ are likely explained by differences in available vertical grids (coarser versus finer, see legend of Figure 2).

However, the summer rainbelt is not well positioned in NWP products: it is shifted to the South by a few degrees in the ECMWF-IFS compared to surface-based and satellite rainfall estimates (Panareda et al. 2008), this is also the case in the NCEP reanalysis.

Satellite products also show a well defined tropical tongue of maximum TOA net radiative flux (R net,TOA ) reaching the Sahel in Summer (Figure 3, top right). The surface energy balance over land implies that R net,TOA provides an estimate of the net energy input to the atmospheric column below (assuming a negligeable ground heat flux). High R net,TOA values are indicative of regions where convection, either dry or moist, is thermodynamically favoured [START_REF] Chou | Mechanisms Limiting the Northward Extent of the Northern Summer Monsoons over North America, Asia, and Africa[END_REF]. Over West Africa, the high R net,TOA tongue arises from a particular combination of season-varying surface and cloud radiative properties in both the longwave and shortwave. Furthermore, meridional contrasts in cloud radiative properties are responsible for Several climate models participate to this ongoing AMMA-MIP project. They are generally able to simulate a monsoon flow and an AEJ over West Africa, but they display large spread already in their zonal circulations, and wide differences in their rainbelts and magnitudes of intraseasonal variability. These largescale features do not seem to involve a significant role for model internal sources of variability. On the other hand, they show a strong sensitivity to physical parametrizations. For instance, the AEJ disappeared when changing the parametrization of moist convection in the LMD climate model (see [START_REF] Hourdin | The AMMA-Model Intercomparison Project[END_REF] for more details). A full understanding of the different mechanisms operating in these models and an assessment of their relevance is still to be gained, but observations collected within AMMA will contribute to reach this goal.

At mesoscale

Large-scale models do not capture properly some basic characteristics of moist convection such as its diurnal cycle and mesoscale organization; this is the case over West Africa (WA) as well (e.g.; [START_REF] Lebel | From GCM scales to hydrological scales: rainfall variability in West Africa[END_REF].

On the other hand, the simulation of MCSs over WA with mesoscale modelling showed more success [START_REF] Diongue | Numerical study of a Sahelian synoptic weather system: Initiation and mature stages of convection and its interactions with the large-scale dynamics[END_REF]. Within AMMA, modelling studies focused on the water cycle are currently carried out. One of the objectives of the study summarized below was to compare the simulation of an observed MCS, its associated rainfall and surface evapotranspiration as obtained from different mesoscale models (see Guichard et al. 2008a for more details).

It appears that initial and boundary conditions, which in the present case are provided by an analyse, significantly control the location of the simulated rainfall field at synoptic scales for 1-2 day forecasts (in case of strong AEW activity at least). Indeed, the use of initial and boundary conditions derived from different analyses leads to fairly distinct simulations of large-scale patterns in convection and rainfall for otherwise identical configurations of a mesoscale simulation.

On the other hand, when different mesoscale models are initialized and forced at their boundaries by the same analysis (from ECMWF in the present case), they are able to simulate a propagating rainfall feature that crosses a broad area [0°W-10°E,7°N-16°N] (Figure 5), as estimated from high frequency satellite rainfall products (Figure 6, upper panel), and as also simulated by the ECMWF-IFS (Figure 5, bottom left). This occurs even though several of these mesoscale simulations made use of a horizontal resolution coarser than 10 kilometres and therefore made use of a parametrization for the representation of deep precipitating convective processes.

The differences in rainfall rates between the two satellite estimates (illustrated in Figure 6 underlines the difficulty encountered with currently available data and algorithms. Nevertheless, both satellite products indicate the same timing and propagation speed of the rainfall feature (compare Figure 6 left and right panels). Such an agreement is not found in mesoscale simulations. The simulated propagating rainfall feature does not depart so much in terms of its speed, but it is usually not precisely located within the area delineated by the two blue curves. This reflects a problem of timing. In addition, significant rainfall rates are often forecast at other locations. Another issue is the difficulty to simulate the path followed by the rainfall feature along latitude (Figure 7). For this case, both satellite estimates indicate a northward propagation (Figure 6, lower panel), while mesoscale simulations diverge widely, especially at nighttime, when rainfall is shifted Southwards in many cases.

Simulated surface evapotranspiration (E) fields are also found to vary significantly among mesoscale models, in terms of magnitude and meridional gradients, and much more so than estimates provided by different land surface models (LSMs) used in an offline mode (ALMIP, [START_REF] Boone | The AMMA Land Surface Model Intercomparison Project (ALMIP)[END_REF]. A major difference between these two estimates is the rainfall field and surface incoming radiative flux "seen" by the LSM: in offline simulations, observational products are used (satellite based estimates). In the present case, a common weakness of the simulated evapotranspitation fields is their lack of zonal asymmetry, compared to ALMIP estimates. In some models, it is associated with a large overestimation of E, of about 20% for 24hmean values over an area more than 1000 km wide. A comparison of surface energy budgets implies that these differences are not explained by differences in the evaporative fraction. They are in fact related to different surface net radiative fluxes. The latter is in turn linked to much higher surface incoming solar radiative fluxes in the mesoscale simulations. This points to a lack of cloudiness in these simulations, and implies a large impact on daytime boundary layer at synoptic spatial scales, in terms of growth (height) and water vapour amount in particular.

This too approximate depiction of surface fluxes, involving feedbacks on -and from-other physical processes, probably play a role in the fast (one to a few days) drifts affecting mesoscale simulations of monsoonal circulations (e.g.; [START_REF] Söhne | Verification of cloud cover forecast with satellite observation over West Africa[END_REF], as previously highlighted in NWPs by [START_REF] Thorncroft | The JET2000 project: aircraft observations of the African easterly jet and African easterly waves[END_REF], see also [START_REF] Tompkins | Influence of aerosol climatology on forecasts of the African Easterly Jet[END_REF]. The choice of a higher, 'deep-cloud-resolving', resolution (less than 5 km) is found to affect the simulation in the following ways: spatio-temporal distributions of rainfall and surface heat fluxes display more variability at scales of a few tens of kilometres, the simulated MCS propagates somewhat faster, and its trajectory is shifted northwards (compare Figure 8(a) and (b)). The seemingly close distributions of daily cumulative rainfall (Figure 8(c), dotted lines) involves compensations between the rainfall patterns at smaller time scale and the propagation as can be inferred from 3-h cumulative rainfall distributions (Figure 8(c), solid lines). These differences involve quantitative changes in simulated processes, which result in part from differences in their couplings. As an example, for this case-study, rainfall in the coarser-grid simulation, using a parametrization of convection, develops earlier in the day, in response to an increase in CAPE [START_REF] Guichard | Modelling the diurnal cycle of deep precipitating convection over land with CRMs and SCMs[END_REF]); the CAPE increase itself is related to the daytime increase of boundary layer equivalent potential temperature in the present case. This affects an area several hundreds of km wide, but does not generate much cloud cover, so that this early day surface wetting is followed by an enhanced daytime evapotranspiration. The scenario will probably vary from one model to the other, as it relies heavily on the functioning of a convection scheme, in particular its triggering criteria, but also on a cloud scheme and the parametrization of their interactions.

In summary, this section emphasizes how the representation of physical processes is key to the simulation of numerous features of the West African monsoon on a range of space and time scales. Conversely, from another perspective, it shows how the West African monsoon corresponds to a very rich test bed for process studies and for the development of physical parametrizations.

Sahelian surface thermodynamics and radiative budget

Previous sections emphasize the importance of surface energy fluxes in the WAM. Data collected within AMMA allow exploring this issue further. They provide guidance for modelling. This is illustrated below with results from Guichard et al. (2008). It addresses the issue of the factors controlling surface net radiation, and their coupling with surface meteorological data. Multi-year high-frequency surface data collected in the Sahel are well suited for such studies. They point to radical differences but also similarities of this semi-arid continental surface with other mid-latitude and tropical land regions (e.g.; [START_REF] Betts | Understanding hydrometeorology using global models[END_REF]Ball 1998, Betts et al. 2002). Hereafter, data presented are from an automatic weather station located in Agoufou, at [1°W, 15°N], within the Malian Gourma, in a grassland over sandy soil, which is the dominant surface type in this area. Departure of the ECMWF-IFS from these data is also briefly discussed.

Major features

In the Sahel, the contrast is sharp between dry conditions prevailing from October-November to April-May and the moist summer months. This is illustrated in Figure 9 with time series from 2003. The area is the coldest around December, then a sustained heating takes place from January to May. From May until October, the monsoon flow is well established, but the majority of rainfall events take place only between June and September (vertical bars in Figure 9). Specific humidity at 2m AGL (q) increases progressively from May until August, while the low-level monsoon flow actually weakens during the same period, in both speed and depth (Figure 10). Thus, the rainy core of the monsoon season (August, day of year 213 to 244) does not coincide with the period during which the low-level south-westerly flow is maximum. This probably involves (i) the weaker dynamic influence of the Saharan heat low which moves northwards and westwards in Summer, and (ii) changes in the vertical extend of turbulent mixing between the low-levels and the atmosphere above between June (over a dry bare soil) and August (over a wet vegetated surface). Finally, a fast drying and heating takes place in October when the monsoon flow retreats. Figure 10: Time-height series of wind speed in the "monsoon flow" -ECMWF analysis for the column above the measurement site, using a 10 day-running mean; only positive zonal and meridional components of the wind have been retained; the vertical axis is the surface pressure minus pressure height.

A striking feature of the Sahelian surface climate is the strong dynamics associated with the transition from a drier hot Spring to a brief cooler moist tropical Summer climate (Figure 9). It also involves large transformations of the diurnal cycles of thermodynamic, dynamic and radiative fields. In particular, for all moist Summer months except August, specific humidity decreases in such a way during daytime (Figure 11a) that it prevents an afternoon increase of the equivalent potential temperature θe (Figure 11b). For instance in June, q decreases by more than 2g.kg -1 between 8Z (equivalent to local solar time here) and 14Z, and θe actually decreases slightly after 10Z despite the daytime temperature increase. In fact, the diurnal cycle of θe is almost flat in June. This also leads to large daytime drops of relative humidity, which enhances the daytime rise of the lifting condensation level lcl (Figure 11c)lcl is expressed here as the departure, in mb, from surface pressure, noted Ps-Plcl ; this cloud-base estimate can also be considered as a proxy for the mixed layer height in case of a cloudy convective boundary layer (see the seminar lecture by A. K. Betts for a comprehensive explanation on the strong correlation between relative humidity and the lcl). defined pattern results nevertheless from a subtle combination of changes in surface incoming and upwelling shortwave and longwave fluxes (R net = SW in -SW up + LW in -LW up ). These changes results surface and atmospheric processes which are differently coupled throughout the year. They emphasize the continental nature of this tropical semi-arid area, as presented below.

Surface radiative budget

Firstly, the seasonal cycle of R net is not simply related to SW in , and the seasonal fluctuations of SW in in turn depart significantly from the seasonal cycle of the incoming solar radiation at the top of the atmosphere (TOA) (Figure 13, upper curve). Note that, given the latitude of the Sahel, two minima of the solar zenith angle (SZA) are recorded within the year -above the site, the TOA incoming solar flux displays its maximum in May, but it does not changes much until the second SZA minimum, around mid-August. At the surface, SWin also increases from January to early May, but then weakens sharply until mid-June. The departure of SWin from the solar incoming radiation at the TOA involves changes in humidity, but also a significant radiative forcing by clouds and aerosols. At the surface, they are found to account for a reduction of the incoming shortwave flux of about 25% in July-August, which corresponds roughly to 80 W.m -2 . This result points to the need of an accurate modelling of the cloud field, even for such a semi-arid area.

The solar radiation reflected by the surface, SW up , does not follow the seasonal evolution of SW in (Figure 13, middle curve), as it is shaped by the seasonal cycle of both SWin and surface albedo (Figure 13 lower curve), discussed in more details by [START_REF] Samain | Analysis of the in-situ and MODIS albedo variability at multiple time scales in the Sahel[END_REF]. The consistent negative trend developing throughout the monsoon season (higher than 0.1 in 2003) is linked to the growth of the vegetation, which is darker than the bright sandy surface. Rainfall events also induce albedo drops reaching up to 0.1 (the sand is darker when wet), but they are short-lived (1-2 days). Therefore, this effect is enhanced when rainfall events are more numerous, and when the vegetation cover is low.

The longwave upward flux, LW up (Figure 14, upper curve) and surface air temperature (Figure 9, upper curve) display similar seasonal evolutions, with two maxima, in Spring and Autumn, two minima, in Winter and Summer, and a weakening of their diurnal ranges in Summer (grey shading). As the surface warms up, from January until mid-May, LW up increases steadily. Then, from mid-May until the end of August, LW up decreases, in two steps. In a first step, once the monsoon flux becomes established, LW up decreases very slightly until the first significant rainfall event, a few weeks later, in June (days of year 135 to 165). This arises from a much weaker daytime surface longwave emission, linked to reduced insolation (Figure 13), which more than compensates for the positive jump of nighttime LW up , associated with a weaker nocturnal cooling (Figure 9). In a second step, after the first significant rainfall event until the end of July, LW up decreases sharply in response to rainfall events, by several tens of W.m -2 each time. As the albedo, LW up also increases back rapidly after rainfall. Finally, in August, LW up remains low, mostly because of its daytime reduction. The response to rainfall events is less dramatic than in July, with LW up overall lower than before.

Finally, the surface downward longwave flux LW in displays large seasonal fluctuations, but again along another path (Figure 14, lower curve). LW in is much lower during the colder months and much higher from May to September during the moist months. From January to May and October to December, its synoptic fluctuations closely match those of precipitable water (see Guichard et al. 2008). However, from January to April (dry warming months), they are superimposed to a larger-scale positive trend mirroring the steeper trend of LW up ,(Figure 14, upper curve) until the sharp jump of LW in at the arrival of the monsoon flow. Thus, LW in is maximum from mid-May to mid-June, i.e., once the monsoon flux is established, but prior to the onset of rainfall, when the atmosphere is quite warm, moist and aerosol loaded. In fact, from April to Mid-June, LW in fluctuations closely match those of -SW in (Figure 13, upper curve). Regarding this Spring moistening period prior to rainfall, it implies:

(1) a daytime warming of the optically thicker atmosphere at the expense of the surface,

(2) a partial balance of this daytime process by the nighttime downward radiative emission of the now warmer atmosphere (LWin increases), consistent with the higher nighttime surface LW emission and temperature at 2m.

As a result, from late May until the first rainfall event, LW up and surface air temperature decrease, but only slightly.

Then, day to day variations of LW in are weak until September. Nevertheless, the negative trend of LW in taking place throughout the monsoon season is astonishing. It occurs despite the increase of precipitable water from June to August and likely involves an overall cooling of the atmosphere as a whole operated by the monsoon phenomenon.

The partition of R net into surface longwave and shortwave radiative fluxes (LW net and SW net ) highlights how, from January until the first rainfall event, LW net and SW ne t almost cancel each other (Figure 15(a)). This reflects a low capacity of the coupled surface-atmosphere system to efficiently trap the top of the atmosphere increasingly high solar influx, until the atmosphere becomes moist. Indeed, as emphasized by [START_REF] Betts | Understanding hydrometeorology using global models[END_REF] for other regions, in this semi-arid Sahelian location as well, fluctuations of daily-mean LW net and moisture are strongly linked all year long (Figure 16(a)). In this figure, the lifting condensation level is used as the moisture variable: a lower height of the lcl -or alternatively a higher relative humidity -is associated with higher surface LW net , across the whole range of humidity fluctuations.

The shortwave-longwave partition used above does not provide a simple explanation for the seasonal evolution of R net though. Another partition consists in splitting the radiative budget into incoming and upwelling fluxes. Then, the negative LW in and positive SW in trends happen to partly cancel each other during the moist Spring and Summer months, so that their sum, R in does not changes much during this period. Therefore, the enhancement of R net mostly reflects changes of surface properties that arise in relation with the monsoon, and results from changes of both LW and SW surface upwelling radiative fluxes (Figure 15(b)). Thus, R net can efficiently increase only within a narrow time window, shifted by about two months with respect the TOA incoming radiative flux, a window further restricted in time by the retreat of the monsoon flow and fast increase of LW up after the last rain.

Surface thermodynamic-radiative coupling during the monsoon

A synthetic view of specific couplings encountered during the monsoon season is shown in Figure 17.

LW net was previously found to be strongly linked to the lcl (Figure 16(a)). R net is found to increase even more than LW net as lcl decreases (Figure 17(a)). This feature is explained by the semi-arid nature of the area, where the reduction of the incoming solar radiation by the cloud cover and aerosols is lower than other sources of variations of R net (namely surface longwave emission and albedo). The few heavily cloudy days account for the scatter obtained at lower R net values (cf dots in Figure 12 and upper grey curve in Figure 13). Thus, both θe and R net increase at lower lcl heights (Figure 17(a,b)) and are found to be positively related (Figure 17(c)). This result is broadly consistent with previous studies which have related low-level moist static energy to soil-moisture through consideration of the surface energy balance (e.g.; Eltahir 1998). However, in the present case, it arises via a distinct interplay among processes. The strong and fast increase of R net along the monsoon season is mostly explained by the surface cooling and darkening (vegetation growth), while the increase of θe involves a strong lowering of mixed layer height (lcl) associated with cooler moister conditions in the low levels, and large change in diurnal cycles. In fact, the surface incoming LW flux is not increasing but decreasing as the atmosphere becomes moister and cloudier (Figure 14, lower curve). Furthermore, the cloud shortwave radiative impact is found to be significant (several tens of W.m -2 ); nevertheless, from June to August, SW in displays a positive trend (Figure 13, upper curve), involving a weakening of the aerosol radiative impact. It is important to note that the seasonal cycle discussed above made use of data from a good monsoon year; i.e. with ample rainfall. Over the Sahel however, interannual variability of rainfall is known to be strong, from larger to smaller scales. For instance, in 2004, the rainfall amount was less than half its value of 2003 (185 against 430 mm) locally in Agoufou. The discussion above suggests that a more rainy monsoon will also be characterized by higher surface net radiation. Indeed, variability of R net from one Summer to the next is found to be strong. This is illustrated in Figure 18. The differences are the strongest in Summer. For instance, R net differs by almost 30 W.m -2 on average between August 2003 and August 2004. The interannual variability of R net is also largely explained by changes in surface properties as emphasized above. It involves the vegetation dynamics, which accounts for large interannual fluctuations of albedo [START_REF] Samain | Analysis of the in-situ and MODIS albedo variability at multiple time scales in the Sahel[END_REF]). However, processes accounting for LW up interannual variability are found to be at least as important. As mentioned above, LW up decreases sharply in response to rainfall events. At larger time scale, LW up and rainfall are also found to be strongly linked (not shown).

Overall, these results emphasize the strong couplings of the energy and water cycles taking place in the Sahel over a wide range of scales, and including also aerosols and vegetation-related processes. From a modelling side, they also help identifying the important processes at play, how they interact, when and at which scales. This provides guidance over an area where such interactions are complex, and not all complying to existing conceptual schemes.

Modelling the surface radiative budget

Modelling the surface radiative budget appears as particularly challenging in view of the major role played by physical processes in shaping this budget. This is illustrated here with a few results from the ECMWF-IFS, where the closest model grid point is examined (it corresponds to a horizontal area on the order of 35 x 35 km 2 ). Obvious limitations to such an exercise include some differences in the simulated and observed surface properties. For instance, the model albedo, which is based on prescribed albedo maps, remains higher than observed in Summer (albeit not in 2004, a particularly bad monsoon). Nevertheless, some important differences are already highlighted in this way. For the area considered, they appear to concern a larger spacial scale than only this local measurement site.

Figure 19 compares time series of observed (red) and simulated (blue) surface 10-day mean R net in 2003. The amplitude of the simulated seasonal cycle of R net is almost as large as observed, but shifted earlier in time by more than a month. On the other hand, rainfall events are frequently simulated (light blue bars) but cumulative rainfall is very weak for most of them. This is related to the difficulty of the ECMWF-IFS to simulate rainfall in the Sahelian band (Panareda et al. 2008). However, the two stronger rainfall events are followed by an exaggerated, strong and long lasting, response in surface radiative fluxes and thermodynamics (not shown), visible as a drop in R net centered around day of year 220 in Figure 19 Nevertheless, the Spring to early Summer R net is now higher than observed. This difference is not limited to one particular Sahelian site but concerns all the AMMA measurements sites, from the Soudanian zone around 9°N to the Northern fringe of the Sahel at 17°N.

Prior to the onset of rainfall, it is chiefly explained by a larger incoming shortwave flux (see illustrations in the talk), which points to a lack of clouds and/or aerosols (in 2003, the excessive aerosol optical thickness had perhaps compensated for this lack of cloudiness). During the core of the monsoon season, at the Sahelian sites where the simulated rainfall is too low, the overestimation of SW in is partly balanced by both too high SW up and LW up (this is reflected in their sum R up , see lower curve in Figure 20(d) compared to Figure 20(c)), LWin is also found to be usually slightly higher (not shown).

This behaviour consistent with a simulated atmosphere being warmer, over a simulated surface where enhanced sensible heat flux generates higher drier and less cloudy convective boundary layers than observed. It seems unlikely that aerosols alone account for the differences noted in August; however, they probably play a more important role in Spring and early Summer.

Finally, in the simulation also, LW net and lcl are strongly coupled (Figure 16(b)). In Agoufou, LW net does not reach values as low as observed, at high Plcl, corresponding to dry surface air. The simulation of nighttime turbulent mixing could contribute to such a difference (e.g.; being weaker than simulated). However, similar comparisons for other Sahelian sites do not support this "single-process" hypothesis and suggest that more subtle explanations are needed.

Overall, such comparisons point to first order deficiencies in models. In the present case, beyond an improvement of surface schemes (notably their representation of vegetation), they also emphasize the need for a better representation of surface rainfall, cloud cover and aerosols. For instance, it seems difficult for this model (and for other models not presented here), to simulate sharp-enough variations of surface radiative fluxes occurring prior to and around the Monsoon onset. Thus, the significance of the underlying processes for this onset, if any, would not be well captured anyway.

Conclusion and perspectives

West Africa is a region where modelling is very challenging, and for which improved parametrizations are critically needed. The unprecedented large amount of data collected during the AMMA 2006 field campaign will help advancing on these issues in several ways. It already contributed to provide (re)analyses of a quality that was probably never reached in the past over this data-sparse region (Panareda and Beljaars 2008), thanks in particular to the 'reactivation of the radiosonde network over West Africa' [START_REF] Parker | The AMMA radiosonde program and its implications for the future of atmospheric monitoring over Africa[END_REF]. Regarding processes involving atmospheric moisture, the development of suitable methods for the correction of humidity bias affecting different sounding types (Nuret et al. 2008, Panareda et al. 2008) also contributes to this enhanced quality.

At large scale, it appears that a framework such as AMMA-CROSS, inspired by the approaches of [START_REF] Siebesma | Cloud representation in general-circulation models over the northern Pacific Ocean: A EUROCS intercomparison study[END_REF]Peyrillé et al. (2007), is a useful tool over this continental area [START_REF] Hourdin | The AMMA-Model Intercomparison Project[END_REF]). Firstly, it constitutes an efficient way to assess the simulation of major large-scale features of the West African monsoon (monsoon flow, jets, rainbelt...). Secondly, it provides a valuable diagnostic tool for testing the impacts of new or modified parametrizations. In this respect, models of intermediate complexity such as two-dimensional zonally-symetric models (e.g.; [START_REF] Zheng | A soil moisture-rainfall feedback mechanism, 2, Numerical experiments[END_REF]Eltahir 1998, Peyrillé et al. 2007) could prove complementary. They offer a link between simpler single-column models in which feedbacks between physical and dynamical processes are limited by design and more complex three-dimensional GCMs.

On the other hand, the relationships observed between physical processes and synoptic structures such as African Easterly waves cannot be directly addressed with such a 2D methodology. From phenomenological as well as theoretical perspectives, AEWs are still the object of numerous investigations. In terms of model evaluation, within AMMA-MIP, high-frequency series of horizontal maps documenting both the surface and different atmospheric layers are currently exploited to advance on this important topic [START_REF] Hourdin | The AMMA-Model Intercomparison Project[END_REF].

Finally, extensive comparisons of analyses, re-analyses and satellite products help delineating better their limits and usefulness for assessing large-scale models. They must be used with great caution regarding largescale vertical velocity fields, but also the atmospheric low levels and surface fields.

In the future, large-scale modelling will also benefit from AMMA in other ways. For instance, improved (re)analyses and estimations of surface fluxes (e.g.; ALMIP, [START_REF] Boone | The AMMA Land Surface Model Intercomparison Project (ALMIP)[END_REF]) certainly provide a closer depiction of the reality than available previously. Long-term surface-based datasets can also be used in statistical ways to explore and to assess coupling mechanisms arising on different scales.

In addition, as in GATE, COARE and a few other field campaigns, it will be possible to estimate atmospheric budgets from the multi-day high-frequency sounding network set up in 2006. Notably eight soundings were release each day at five locations, during two multi-day periods. In the past, such datasets proved to be quite useful, and for very long, regarding the development of parametrizations. It should also be the case for this dataset documenting a new continental tropical climate of the globe. On another side and scale, mesoscale models have some capacity to simulate propagating rainfall systems, even though numerous and various difficulties are still affecting regional mesoscale modelling, e.g.; crudeness of current surface and cloud initialization methods, diurnal cycle issue... However, the utilization of a fine-resolution in such simulations (on the order of a few kilometres, i.e. able to capture deep convective cells) can lead to radically different representations of processes down to scales of a few tens of kilometres.

More analyses is needed in order (1) to assess the quality of such simulations, this can be done on the basis of AMMA case-studies for which relevant observations are available; and (2) to quantify the processes and to precisely identify the mechanisms operating within these simulations. In this context, CRMs and LES can be seen as useful complementary tools, as they are well suited for basic process and sensitivity studies. For instance, they would be helpful for identifying the effective couplings involved in the development of convective phenomena over arid and semi-arid areas.

Finally, observations collected within AMMA provide a basis for numerous, valuable, process studies. They allow advancing our knowledge, which is still limited and composite over West Africa. Therefore, they provide important guidance rather than simply a mean to evaluate models.

This was illustrated in section 4 with a quantitative analysis of the surface radiation budget for a representative Sahelian site (Guichard et al. 2008b), recalling here the importance of surface fluxes to several aspects of the West African monsoon. It shows that the Summer increase of surface net radiation is strong and largely driven by modifications of the surface via rainfall events and vegetation phenology (surface cooling and darkening), while the direct impact of atmospheric changes on the total incoming radiation is limited to shorter time scales.

Subtle balances between surface air temperature and moisture fields are found on a range of scales. For instance, during the monsoon, apart from August, their opposite daytime fluctuations (warming, drying) lead to an almost flat diurnal cycle of the low-level equivalent potential temperature θe. This feature stands out in contrast to other less arid continental regions. More broadly, the strong dynamics associated with the transition from a drier hot Spring to a brief cooler wet tropical Summer climate involves large transformations of the diurnal cycles, even within the monsoon season. The particular combination of thermodynamic and radiative variations taking place during the monsoon eventually leads to a positive correlation between θe and R net . This correlation is, in turn, broadly consistent with an overall positive soilmoisture rainfall feedback at this scale.

Observations further reveal astonishing radiative signatures of the monsoon on the incoming longwave flux at the surface. In particular, LW in does not reach its maximum during the monsoon season when the atmosphere is the most cloudy and humid, but earlier, prior to the onset of rainfall, as the dry and warmer atmosphere suddenly becomes moist. Conversely, the incoming solar radiation at the surface increases slightly from late Spring to the core monsoon season even though the atmosphere becomes moister and cloudier; this possibly involving a high aerosol optical thickness in late Spring early Summer.

Beyond these Sahelian-specific features however, and in agreement with some previous studies, strong links are found between the atmospheric humidity and the net longwave flux at the surface all year long, even across the much lower humidity ranges encountered in this region. They point to and locally quantify the major control of water vapour and water-related processes on the surface-atmosphere thermal coupling as measured by LW net . Namely, they are found to be more tightly coupled (LW net closer to 0) when the atmosphere is moister (and cloudier).

Observational results such as presented above provide valuable ground truth for assessing models over a continental area displaying a rich variety of surface-atmosphere regimes throughout the year, from a desertlike to a rainy tropical-like climate during the core of the monsoon. This was illustrated briefly with results from the ECMWF-IFS. In summary, it appears that the parametrization of cloud and rainfall processes still constitute major sources of errors in the surface energy budget, through their impact on the surface incoming solar radiation and evaporative fraction. In addition, changes in the physics of a model (in the present case a modification of the aerosol climatology) can dominate interannual variability of the surface energy budget.

A more accurate and renewed picture of the West African monsoon system is beginning to emerge from process studies carried out within AMMA. The degree to which each physical parametrization, taken separately, should be improved for an adequate modelling of the WAM is not always clear. However, a satisfactory representation of their mutual interactions and couplings with dynamical processes appears as a crucial issue, across a wide range of space and time scales. The West African monsoon thus provides a valuable test bed for physical parametrizations, particularly over continental areas. As such, it should also contribute to improve modelling over other regions.

Figure 2 :

 2 Figure 2 : Zonal wind during the core of the 2006 monsoon season (15 July-15 August) as a function of latitude, from 10°S to 30°N, and height on average over [10°W,10°E] from four meteorological analyses: (a) ARPEGE-Tropiques, (b) ECMWF, (c) NCEP and (d) NCEP2. Note that the relatively lower strength of the African Easterly jet (AEJ, around 15°N and 600 hPa) in the ECMWF compared to the other (re-) analyses around 15°N is related to the absence of the 600 hPa level in the available pressure grid.[figures prepared by F. Favot]

Figure 3 :Figure 4 :

 34 Figure 3 : Same as Figure2except for vertical velocity. North of 20°N, the differences in the strength of the horizontal gradients below 600 hPa are partly due to the differences in the horizontal interpolation grids (0.5° in 1.125° in ECMWF, and 2.5° in NCEP and NCEP2).[figures prepared by F. Favot]

Figure 5 :

 5 Figure 5: Longitude-time diagrams of simulated surface rainfall, averaged over [7°N,16°N], grey shadings for values from 1, 2, 3, 4, 5, 10, 15, 20 mm and above; the blue thick lines delineate the areas where the satellite rainfall estimate (EPSAT-SG) is greater than 2mm (3-hourly cumulative values).

Figure 6

 6 Figure 6 Longitude-time (top) and time-latitude (bottom) diagrams of two distinct satellite estimates of surface rainfall, 3-h cumulative value averaged respectively over [7°N,16°N] and [5°W,10°E], grey shadings for valuesfrom 1, 2, 3, 4, 5, 10, 15, 20 mm and above, and TRMM-3B42RT (right); the blue thick lines delineate the area where the EPSAT-SG rainfall estimate is greater than 2 mm -values are affected respectively at the end (the centre) of the 3-hourly intervals for EPSAT-SG (for TRMM-3B42RT).

Figure 7 :

 7 Figure 7: Time-latitude diagram of simulated surface rainfall, averaged over [5°W,10°E], grey shadings for values from1, 2, 3, 4, 5, 10, 15, 20 mm and above; the blue thick lines delineate the area where the EPSAT-SG rainfall estimate is greater than 2mm (3-h cumulative values).

Figure 8 :

 8 Figure 8: Simulated cumulative rainfall from early morning (6Z) to midnight using (a) a higher horizontal resolution (4 km) without parametrization of convection and (b) a lower horizontal resolution (10 km) with a parametrization of convection. (c) presents the normalized distributions of 3-h (solid lines) and 24-h (dotted line) cumulative rainfall over the spatial domain shown in (a),(b) for the two simulations, with higher (black) and lower (grey) resolution -(mesoNH simulations from N. Asencio).

Figure 9 :

 9 Figure 9 : Time series of 2-m temperature (upper curve) and specific humidity (lower curve) in 2003 (the black lines correspond to a 24-h running mean and the dark grey shadings delineate 24-h minimum and maximum values), rainfall amounts per rainy event (bottom bars) and midday solar zenith angle (light shading). -different time periods are roughly delimited by the top thick grey lines with names given above.

Figure 11

 11 Figure 11: monthly-mean daytime variations (6Z to 14Z) of the couplets (a) [q,T], (b) [T,θe] and [q,θe], and (c) [Ps-Plcl ,θe] in June (pink), July (cyan) and August (blue).

Figure 13 :

 13 Figure 13: Time series of surface surface shortwave incoming (SW in , upper curve), shortwave upwelling (SW up, middle curve) and albedo (lower curve, right y axis); the thick black line corresponds to a 10-day running mean and the thin grey line to 24-h average values -upper black bars indicate rainfall events.

Figure 14 :

 14 Figure 14: Same as Figure 9 except for surface longwave fluxes, LW up (upper curve) and LW in (lower curve).

Figure 15 :

 15 Figure 15: Time series of 10-day mean surface (a) net SW and LW fluxes (black curves), note that the lower solid line corresponds to ' -LW net ', so that the the grey shaded area enclosed within the two black curves gives the magnitude of the surface net radiation R net , (b) incoming radiative flux (R in = SW in + LW in , upper black line) and outgoing radiative (R up = LW up + SW up , lower black curve) -lower black bars are rainfall per event (right y axis).

Figure 16 :

 16 Figure 16: Scatter diagram of daily mean LW net versus (Ps-Plcl), (a): observations, data from 2002 to 2007 (single location) and (b) ECMWF-IFS.

  On the other hand, θe overall increases under moister and colder conditions, i.e. when the height of the lcl decreases (Figure 17(b)), and the co-variation of their 24-h mean values still involves the co-variation of their diurnal cycle and its changes along the Summer (Figure 11(c)).

Figure 17 :

 17 Figure 17 : Scatter diagrams of (a) R net versus (Ps-Plcl), (b) (Ps-Plcl) versus θe and (c) Rnet versus θe.

Figure 18 :

 18 Figure 18: Same as Figure 12 except for the 10-day average time series covering 2002 to 2007.

  Figure19compares time series of observed (red) and simulated (blue) surface 10-day mean R net in 2003. The amplitude of the simulated seasonal cycle of R net is almost as large as observed, but shifted earlier in time by more than a month. On the other hand, rainfall events are frequently simulated (light blue bars) but cumulative rainfall is very weak for most of them. This is related to the difficulty of the ECMWF-IFS to simulate rainfall in the Sahelian band(Panareda et al. 2008). However, the two stronger rainfall events are followed by an exaggerated, strong and long lasting, response in surface radiative fluxes and thermodynamics (not shown), visible as a drop in R net centered around day of year 220 in Figure19(a). It is explained by a large reduction of R in exceeding a coupled R up decrease (Figure20(b)). Compared to data (Figure20(b)), R in and R up are more strongly coupled in the model. Simulated rainfall did not improved since 2003 (it actually appears to be slightly lower), but the R net maximum has been shifted in time to August in more recent simulations (Figure19(b)). This feature seems to be related to the change of the aerosol climatology in October 2003 as reported in[START_REF] Tompkins | Influence of aerosol climatology on forecasts of the African Easterly Jet[END_REF]. Nevertheless, the Spring to early Summer R net is now higher than observed. This difference is not limited to one particular Sahelian site but concerns all the AMMA measurements sites, from the Soudanian zone around 9°N to the Northern fringe of the Sahel at 17°N.

Figure 19 :

 19 Figure 19: (a) Same as Figure 12 except showing both data and model in 2003, with red line (resp. blue line) for 10-day mean R net and orange bottom bars (resp. light blue top bars) showing rainfall per event, (b) same as (a) except for 2006.

Figure 20 :

 20 Figure 20: (a) same as Figure 15 except for a 40W.m -2 shift in y-axis, (b) same as (a) except for the model and (c,d) same as (a,b) except in 2006

Acknowledgements

I thank my colleagues who participated to the studies presented above, especially F. Favot, F. Hourdin and I. Musat (section 3.1), N. Asencio, O. Bock, C. Peugeot and J.-L. Redelsperger (section 3.2), and P. Hiernaux, L. Kergoat, E. Mougin and F. Timouk (section 4).


Marius Bozga
email: fbozga@imag.fr

Oded Maler
email: maler@imag.fr

Stavros Tripakis
email: tripakisg@imag.fr

E cient Veri cation of Timed Automata using Dense and Discrete Time Semantics ?

In this paper we argue that the semantic issues of discrete vs. dense time should be separated as much as possible from the pragmatics of state-space representation. Contrary to some misconceptions, the discrete semantics is not inherently bound to use state-explosive techniques any more than the dense one. In fact, discrete timed automata can be analyzed using any representation scheme (such as DBM) used for dense time, and in addition can bene t from enumerative and symbolic techniques (such as BDDs) which are not naturally applicable to dense time. DBMs, on the other hand, can still be used more e ciently by taking into account the activity of clocks, to eliminate redundancy.

To support these claims we report experimental results obtained using an extension of Kronos with BDDs and variable-dimension DBMs where we veri ed the asynchronous chip STARI, a FIFO bu er which provides for skew-tolerant communication between two synchronous systems. Using discrete time and BDDs we were able to prove correctness of a STARI implementation with 18 stages (55 clocks), better than what has been achieved using other techniques. The veri cation results carry over to the dense semantics. Using variable-dimension DBMs we have managed to verify STARI for up to 8 stages (27 clocks). In fact, our analysis shows that at most one third of the clocks are active at any reachable state, and about one fourth of the clocks are active in 90% of the reachable states. ?

Introduction

The analysis of discrete systems such as programs or digital circuits, while taking into account the temporal uncertainty associated with transition delays, is a very challenging and important task. In MP95] and elsewhere, it has been demonstrated that reasonable models of digital circuits with uncertain delay bounds can be translated systematically into timed automata AD94], which can then be analyzed using various veri cation tools. However, this remains a theoretical possibility as long as the performance bottleneck for timed veri cation remains (see the discussion in BMPY97] as well as TKB97]). During the last decade the Verimag laboratory has been engaged in development of the timing analyzer KRONOS DOTY96] and in attempts to improve its performance using various techniques.

Timed automata operating on the dense real time axis constitute an instance of hybrid automata and their analysis confronts researchers with problems usually not encountered in \classical" nite-state veri cation. These problems, such as Zeno's paradox (the possibility of making in nitely-many steps in a bounded interval) or the representation of an uncountable number of states, which are related to the foundations of mathematics, sometime give a false impression on the essense of timing analysis. We argue that this essence does not depend on the time domain, and that the di erence between dense and discrete time semantics is \epsilon", so to speak.

We demonstrate these claims by applying discrete and dense techniques to a non-trivial case-study where we obtain the best performance results achieved so far for timed automata. More precisely, we report the application of two techniques: the BDD-based veri cation using the discrete time semantics ABK + 97] BMPY97], and the \standard" DBM-based method using variable-sized matrices based on clock activity analysis DY96], to a real hardware design, the STARI chip due to M. Greenstreet Gre97]. This chip is an asynchronous realization of a FIFO bu er, composed of a sequence of stages, each consisting of two Muller C-elements and one NOR gate. According to the principles laid out in MP95], and similarly to TB97], each such stage is modeled as a product of 3 timed automata, each with 4 states and one clock. The (skewed) transmitter and receiver are modeled as two timed automata using a shared clock.

We have modeled the intended behavior of the FIFO bu er operationally as an automaton, and were able to verify that an 18-stage implementation (55 clocks) indeed realizes the speci cation. These are, to the best of our knowledge, among the best performance results for timed automata veri cation, and they show that some real circuits behave better than arti cial examples of the kind we used in BMPY97].

The rest of the paper is organized as follows. In section 2 we give a very informal survey of timed automata, their veri cation techniques and their discrete and dense semantics. In section 3 we describe STARI and its desired properties, which are then modeled using timed automata in section 4. The performance results are reported and analyzed in section 5, and future work is discussed at the end.

2 Veri cation using Timed Automata 2.1 Timed Automata Timed automata can represent systems in which actions take some unknown, but bounded, amount of time to complete, in a rigorous and veri able manner. They are essentially automata operating on the continuous time scale, employing auxiliary continuous variables called clocks. These clocks, while in a given state, keep on increasing with time. Their values, when they cross certain thresholds can enable some transitions and also force the automaton to leave a state. Temporal uncertainty is modeled as the possibility to choose between staying in a state and taking a transition during an interval l; u].

Since their introduction in 1990 AD94], Timed Automata (TA) attracted a lot of attention from the veri cation community, mainly for the following reasons:

1. They constitute a computational model in which one can faithfully represent many real-world situations where timing constraints interfere with discrete transitions. 2. In spite of the fact that their state-space is non-countable, their reachability problems (which are the essence of any veri cation problem) are decidable.

Several veri cation tools such as Kronos DOTY96], Timed Cospan AK96] and Uppaal LPY97] have been implemented, featuring various veri cation and synthesis algorithms which explore, this way or another, the state-space of TA.

The use of a non-countable state-space, Q X where jQj = m and X = 0; k] d , along with dense time, excludes immediately any veri cation method which is based on explicit enumeration of states and trajectories. All existing TA veri cation algorithms are based, either explicitly or implicitly, on the region graph construction AD94]: an equivalence relation is de ned on X, unifying clock con gurations from which the future behaviors are essentially identical (i.e. two clock valuations x and x 0 are equivalent, x x 0 , if the same sequences of discrete transitions are possible from x and from x 0 ). It turns out that in TA this relation is of nite index, and the quotient graph of a TA, modulo , is a nite-state automaton with a combination of discrete transitions and abstract \time-passage" transitions, indicating the temporal evolution of clock values from one equivalence class to another.

Veri cation tools for TA, either construct rst the region automaton (whose size is O(mk d d!) and then use standard discrete veri cation algorithms, or calculate the reachable con gurations successively while representing them as unions of polyhedra of certain restricted form. These \symbolic states", which are generated by the equivalences classes of , are polyhedra which can be represented by combinations of inequalities of the form x i c or x i ?x j c where x i , x j are clock variables, is either < or , and c an integer constant in f0; 1; : : :; k ?1g.

For convex regions, there is a canonical form based on an irredundant set of inequalities, which can be e ciently represented using an O(n 2 )-sized integer matrix, known as the di erence bounds matrix (DBM). The main computational activity in TA veri cation is the storage and manipulation of sets of these matrices during xed-point computations. The major bottleneck is due to the fact that the number and size of DBMs grows exponentially with the number of clocks and the size of k (roughly, the size of the largest constant in the TA after normalization). Moreover the representation of non-convex polyhedra as unions of convex ones is not unique. There have been many attempts to break the computational bottleneck associated with the manipulation of DBMs, such as WD94,H93,B96,DY96,LLPY97,DT98], to mention a few, and to be able to verify larger timed automata. One approach, DY96], is based on the observation that not all clocks are active at any con guration (see also SV96]). A clock x i is inactive in a con guration (q; x) if it is reset to zero before any future test of its value. In that case its value can be eliminated from the state description of the system. Consequently one can use variable-sized DBMs restricted to the relevant clocks in every region of the TA. In section 5 we will report the results of clock activity analysis of STARI and the performance of the variable-sized DBMs.

The Joy of Discrete Time

There is, however, an alternative semantics for TA based on discrete (and in fact, integer) time, which has already been discussed in early works about real-time logics (see the survey AH92]). According to this view, time steps are multiples of a constant, and at every moment the automaton might choose between incrementing time or making a discrete transition. Consider the fragment of a 2-clock timed automaton depicted at the left of Figure 1. The automaton can stay in the state and let the time progress (i.e. let the values of x 1 and x 2 grow with derivative 1) as long as x 1 u. As soon as x 1 reaches l (we assume l u) it can take a transition to another state and reset x 1 to zero. By restricting the time domain to the integers, the staying conditions (\invariants") in every state are replaced by \idle" transitions as in the right of Figure 1.

x 1 < u= x 1 := x 1 + 1 x 2 := x 2 + 1
x 1 l=x 1 := 0 x 1 l=x 1 := 0 x 1 u Fig. 1. A timed automaton and its discrete time interpretation.

Under this interpretation clocks are nothing but bounded integer variables, whose values are incremented simultaneously by time transitions and some of them are reset to zero by certain discrete transitions. Such systems are nitestate, but some components of the state-space, namely the clocks, have additional structure (addition and linear-ordering of clock values), which can be exploited by veri cation algorithms. In particular, any representation scheme for the dense semantics which is based on clock inequalities can be specialized for the discrete semantics. Since on discrete order, a strict inequality of the form x i < c can be written as the non-strict inequality x i c ?1, discrete regions can be expressed using exclusively non-strict inequalities. Hence even DBM-based methods can be tuned to work better on discrete time since the space of DBMs is smaller. A typical step in the iterative calculation of reachable states is depicted in Figure 2 for the dense (left) and discrete (right) semantics. In addition to these methods one can take advantage of the nite-state nature of discrete TA and apply techniques which cannot be applied directly to dense time. One possibility is to push clocks values into states and transform the TA into a nite automaton (either o -line or on-the-y). This provides for depthrst traversal of the state-space, as well as other search regimes. An alternative approach is the one advocated in ABK + 97,BMPY97] in which the clocks values are encoded in binary and subsets of them are written as BDDs. The advantage of this approach is that it gives a canonical representation for any subset (convex or not) of the state-space, and that it combines naturally with BDD-based representation of the control states. Most of this paper is a report of one success story of this approach, where a non-trivial system with 55 clocks has been veri ed. However, before that there is one little point to be clari ed: although discrete time veri cation is inherently more e cient than dense time, it is certainly less expressive, and one might want to know what is sacri ced in order to improve performance. Our answer, based on the results in HMP92,AMP98], which we explain below is: \not much".

Why Discrete Time Su ces

Consider two clock valuations x and x 0 sharing the same open unit square S = (c 1 ; c 1 + 1; c 2 ; c 2 + 1) (Figure 3-(a)). Clearly, every inequality of the form x i c, i 2 f1; 2g and 2 f<; ; >; g is satis ed by x i it is satis ed by x 0 . Hence a transition that can be taken at x, leading to a new valuation y, i it can be taken at x 0 leading to a point y 0 on the same square as y. For the same reasons time can progress at x i it can do so at x 0 , however unless the order among the fractional parts of x 1 and x 2 is the same in x and x 0 they might reach di erent squares as time goes by. Only if they belong to the same triangular subset of X, namely a set of the form fx : hx 1 i hx 2 ig where hx i i denotes the fractional part of x i , they will meet the same squares during time evolution (Figure 3-(b)). Combining these facts we obtain the equivalence relation on X which guarantees that all the members of an equivalence class can exhibit essentially the same behaviors.

This simple (and simpli ed) story becomes more complicated if transition guards and invariants are allowed to contain strict inequalities. In that case some transitions might be enabled in the interior of a region but not in its boundaries, and the region graph becomes a more involved mathematical object with elements of all dimensionalities from 0 to n. If, however, timing constraints are restricted to be closed (i.e. non-strict) every boundary point satis es all the constraints satis ed by the regions in its neighborhood. In particular the set of integral points, the grid f0; 1; : : :; k ? 1g n \covers" all X in the sense that it intersects the boundaries of all open full-dimensional regions and satis es all the constraints that they satisfy (Figure 3-(c)). Hence these integral points can be taken as representatives and all the (qualitative) trajectories starting from them cover all the possible behaviors of the system. To be more precise, a discrete run might be a slight variation of some of the dense runs it represents: it may sometimes have few transitions taken simultaneously while in the dense run these transitions are separated by small amount of time. Nevertheless, the following results HMP92,AMP98] underlie the soundness of discrete veri cation:

Theorem 1 (Emptiness of Closed TA). The set of dense behaviors of a closed TA is non-empty i it contains a discrete run.

Combining this with the fact that untimed properties can be expressed as TAs in which all constraints are true (which is closed), we have:

Corollary 1 (Discrete Time Veri cation). A closed TA satis es an untimed property ' i its discrete time version satis es '.

If the TA is not closed, its closure is an over-approximation and a satisfaction of any linear-time property by the closure implies satis ability by the original automaton.

3 STARI Description STARI (Self-Timed At Receiver's Input) Gre97] is a novel approach to highbandwidth communication which combines synchronous and self-timed design techniques. Generally speaking, a transmitter communicates synchronously with a receiver through an asynchronous FIFO bu er (see Figure 4). The FIFO makes the system tolerant to time-varying skew between the transmitter and receiver clocks. An internal handshake protocol using acknowledgments prevents data loss or duplication inside the queue. The functioning of STARI is based on a rather intuitive idea. The FIFO must be initialized to be half-full. During each period of the clock one value is inserted to the FIFO by the transmitter and one value is removed by the receiver. Due to the complementary nature of these actions no control is required to prevent queue under ow or over ow. Short-term uctuations in the clock rates of the transmitter and the receiver are handled by inserting or removing, more items to or from the queue.

Following the STARI model proposed by Tasiran and Brayton in TB97], which di ers slightly from the original description in Gre97], we represent the boolean values true and false by dual rail encoding (see Figure 5). An auxiliary empty value is needed to distinguish between the case of two consecutive identical values and the case of one value maintained during more than one clock cycle. The transmitter is constrained to send sequences of true and false where each two occurrences of these values are separated by an occurrence of empty. The STARI chip consists of a linear array of n identical stages, each capable of storing a data value X.

The following two properties need to be proved to ensure the correct operation of the STARI circuit: X true false empty X.t 1 0 0 X.f 0 1 0 Fig. 5. Dual rail encoding.

{ Each data value output by the transmitter must be inserted in the FIFO before the next one.

{ A new value must be output by the FIFO before each acknowledgment from the receiver We specify the desired behavior of an n-stage STARI as an ideal FIFO bu er combined with a receiver and a transmitter respecting the abovementioned convention (see Figure 6). Note that in this speci cation, every transition is labeled with a pair of put and get actions, with the intended meaning that they can occur in any order including simultaneously. The goal of the veri cation is to show that if we hide the internal operations of STARI, the realizable sequences of put's and get's conform with this speci cation.

The operation principle of a stage k can be summarized as follows: it may copy its predecessor value (X k := X k?1 ) when its successor has already copied (and acknowledged) its current value (X k = X k+1 ). Using the dual rail encoding of data values, such a behavior can be achieved using two Muller C-elements that hold the X:t and X:f components, and one NOR gate for computing the acknowledgment (see Figure 7).

A Muller C-element works as follows: when the two inputs become identical, after some delay the output takes on their value, otherwise the output maintains its previous value. Consider, for example, a situation where stages k and k + 1 hold the empty value, stage k ? 1 the true value and Ack k+1 = 0. When Ack k+1 becomes 1, the C-element for X k :f remains unchanged at 0 because its inputs are di erent (i.e. Ack k+1 = 1, X k?1 :f = 0). However, both the inputs of the C-element for X k :t are equal to 1 (Ack k+1 = X k?1 :t = 1), and after some delay, it will switch to 1. This way the true value has been copied from stage k ? 1 to stage k.

Modeling STARI by Timed Automata

The correct functioning of STARI depends on the timing characteristics of the gates (the time it takes, say, for a C-element to switch) and its relation with the central clock period and the skew between the receiver and transmitter. We model the uncertainty concerning the delay associated with gates using the bi-bounded delay model, that is, we associate with every gate an interval l; u] indicating the lower and upper bounds for its switching delay (see L89], BS94], MP95] and AMP98] for the exact de nitions).

Following MP95] we can model any logical gate with a delay l; u] using a timed automaton with 4 states (0-stable, 0-excited, 1-stable and 1-excited) and one clock. In particular, each stage of STARI is modeled by the three timed automata of Figures 8, 9 and 10.

Let us look at the automaton of Figure 8 which models the X:t component of the k th stage. Its state is characterized by two boolean variables X k :t, x k :t, the former stores the gate output and the latter stores the gate internal value, i.e. the value to which the gate \wants" to go after the delay. The stable states are those in which X k :t = x k :t. The conditions for staying and leaving stable states are complementary and do not depend on clock values: for example, the automaton leaves state (0; 0) and goes to the unstable state (0; 1) exactly when both its inputs are 1. During this transition the clock variable C k :t is reset to zero. The automaton can stay at (0; 1) as long as C k :t < u C and can change its output and stabilize in (1; 1) as soon as C k :t l C , where l C ; u C ] is the delay interval associated with a C-element. The automaton for the X:f component (Figure 9) is exactly the same (with di erent inputs) and the automaton for the NOR gate (Figure 10) is similarly characterized by two boolean variables Ack k , ack k , a clock variable C k :a and a delay bounded by l N ; u N ]. This means that an n-stage STARI can be translated into 3n automata with 3n clocks and 6n boolean variables.

In addition to the automata for modeling the stages, we need three other automata for modeling the transmitter, the reciever and their clock cycle. The global clock cycle is modeled by a simple timed automaton using one clock variable C. Whenever C reaches the cycle size p it is reset to zero. (see Figure 11).

The transmitter is modeled as a 3-state automaton (Figure 11). At each clock cycle it puts a value at the input ports of the rst stage (X 0 :t and X 0 :f), according to the convention that every pair of data items is separated by an empty item. Moreover, the transmission can be done with some skew with respect to the clock cycle, bounded by the s T constant, that is, the actual time of transmission can be anywhere in the interval p ? s T ; p].

The receiver is a 1-state automaton (see Figure 11) which reads the current output value (i.e. X n :t and X n :f) and acknowledges the reception by modifying Ack n+1 according to whether or not X n is empty. As in the transmitter, a skew bounded by s R is allowed.

Note that the receiver and transmitter skews cannot accumulate during successive cycles. They always range in an interval depending on the (perfect) global clock cycle. However, each one can vary non-deterministically from one cycle to another. This is more general than assuming a xed skew given in advance, or a xed skew chosen at start-up from a given interval. The transitions of these automata are annotated by action names such as put and get whose role is explanatory { they have no e ect on the functioning of the system.

Veri cation Results and Performance Analysis

Discrete Time and BDDs

We have modeled various instants of STARI, each with a di erent number of stages. For each instance we have composed the timed automata and then min- E,F,E F,E,F T,E,F E,T,E T,E,T F,E,T Fig. 6. The speci cation of an ideal 3-stage bu er. The states correspond to the bu er contents.

X k :f X k :t Ack k+1 C C X k?1 :t Ack k X k?1 :f Fig. 7. Stage k of STARI. X k?1 :t = 0_ Ack k+1 = 0 X k :t = 0 x k :t = 0 C k :t < u C X k :t = 1 x k :t = 0 C k :t < u C X k :t = 0 x k :t = 1 X k?1 :t = 1_ Ack k+1 = 1 x k :t = 1 X k :t = 1 C k :t l C Xk?1 :t = 1Â ck k+1 = 1 X k?1 :t = 1 _ Ack k+1 = 1 X k?1 :t = 0 _ Ack k+1 = 0 X k?1 :t = Ack k+1 = 0 = C k :t := 0 C k :t l C Xk?1 :t = 0Â ck k+1 = 0
X k?1 :t = Ack k+1 = 1 = C k :t := 0 Fig. 8. The timed automaton for the C-element X k :t. imized them by hiding the unobservable transitions. In Figure 12 one can see the automaton obtained for three stages, where in addition to the put and get actions, we left also the tick action which indicates the end of the global clock cycle. After hiding the tick we obtain a realization of the ideal FIFO as speci ed in Figure 6. We used the following concrete parameters to model the chip: l C ; u C ] = l N ; u N ) = 2; 4] for gate delays, p = 12 for the clock cycle and s T = s R = 2 for the maximal allowed skew of the transmitter and the receiver.

X k?1 :f = 0_ Ack k+1 = 0 X k :f = 0 x k :f = 0 C k :f < u C X k :f = 1 x k :f = 0 C k :f < u C X k :f = 0 x k :f = 1 X k?1 :f = 1_ Ack k+1 = 1 x k :f = 1 X k :f = 1 C k :f l C Xk?1 :f = 1Â ck k+1 = 1 X k?1 :f = 1 _ Ack k+1 = 1 X k?1 :f = 0 _ Ack k+1 = 0 X k?1 :f = Ack k+1 = 0 = C k :f := 0 C k :f l C Xk?1 :f = 0Â ck k+1 = 0 X k?1 :f = Ack k+1 = 1 = C k :f := 0
k :t = 1_ X k :f = 1 Ack k = 0 ack k = 0 C k :a < u N Ack k = 1 ack k = 0 C k :a < u N Ack k = 0 ack k = 1 X k :t = 0 X k :f = 0 ack k = 1 Ack k = 1 C k :a l N Xk :t = 0X k :f = 0 X k :t = X k :f = 0 X k :t = 1 _ X k :f = 1 X k :t = 1 _ X k :f = 1 = C k :a := 0 C k :a l N (X k :t = 1_ X k :f = 1) X k :t = X k :f = 0 = C k :a := 0
The BDD implementation is based on the model-checker SMI B97] and it uses the CUDD package S95]. The 18-stage STARI is modeled by a network of timed automata summing up to 55 clocks. It uses 286 BDD variables to encode the clocks and the states. The reachable state space is of order of 10 15 states. We were able to prove that each STARI model with n 18 stages, right initialized with m distinct values (m n=2) simulates an ideal bu er of size m.

Moreover, we veri ed that the transition graphs of the implementation and the speci cation are equivalent with respect to the branching bisimulation vGW89], if we consider only the reading and writing to be observable. The equivalence is veri ed symbolically using the method described in FKM93]. The time and the memory needed1 to perform this veri cation are presented in Figure 13.

Variable-dimension DBMs

We have also veri ed STARI, interpreted over dense-time, using the DBM representation of Kronos and the forward-analysis technique of DT98]. To overcome the explosion associated with the size and number of DMBs we have used the techniques of DY96,DT98], based on the notion of active and inactive clocks.

As one can see in Figure 8, the basic building block which is used to model a timed gate is a four-state automaton with one clock which is active only in the unstable states. So a-priori, each clock is active in half of the global control states. However, in real designs, especially when there is some natural order in which information ows in the circuit, the average over the reachable states of the number of active clocks can be much smaller.

The information concerning clock activity has been extracted automatically from the TA description and,using the variable-dimension DBM library of KRO-NOS, we were able to verify STARI with up to 8 stages (27 clocks). The main reason for the relative inferiority compared to the BDD approach is the large size of the discrete state-space (2 24 ): using DBMs, discrete variables are enumerated, whereas using discrete time and BDDs all variables (including clocks) are handled uniformly, which results in more compact representation. Future techniques, combining BDDs for the state variables and DBMs for the clocks might improve performance signi cantly.

Figure 14 shows the time performance and the number of symbolic states (discrete variables plus DBM) generated for number of stages. We have also measured the number of active clocks in each symbolic state and the results con rm our expectations that only a small fraction of clocks are active at any time. For instance, in the case of 8 stages, out of 27 clocks at most 9 were active, and this in less than 4% of the total number of DBMs generated (see diagram on the right of Figure 15). In more than 85% of the symbolic states, only 6 to 8 clocks were active. The distributions have the same shape for other STARI con gurations.

Discussion

Our performance resuts are signi cantly better than those reported by Tasiran and Brayton TB97], from whom we have adopted the model. They prove, using techniques developed in TAKB96], that every stage can be abstracted into a timed automaton having 5 states and only one clock. Using this abstract model and the tool Timed-Cospan they were able to verify an 8-stage bu er, while using the detailed model they could not verify more than 3 stages. Another attempt to verify STARI was reported by Belluomini and Myers BM98] who model the circuit using a variant of timed Petri nets which they verify using the tool POSET which employs partial-order methods. The largest example they reported was of 10 stages. Yoneda and Ryu YR99] improve these results signi cantly using circuit-speci c heuristics.

We have demonstrated that a rather large example can be veri ed by tools based on timed automata, and we hope that this will contribute to the wide adoption of timed automata as a model for quantitative timing analysis. Our results indicate that in certain cases, discretized BDD-based approaches outperform other techniques. In the future we will try to characterize the class of systems for which this is the case. It is clear, however, that in examples where large constants (or equivalently, smaller time granularity) are involved, discrete time becomes less attractive.

Fig. 2 .

 2 Fig. 2. Calculation of reachable con gurations, starting from the initial set P, for the dense and discrete timed automata of Figure 1.

  Fig. 3. a) Two points satisfying the same constraints; b) Two equivalent points; c) An integer point satisfying all the constraints satis ed by its six neighboring regions.

Fig. 4 .

 4 Fig. 4. The STARI overview.

Fig. 9 .

 9 Fig. 9. The timed automaton for the C-element X k :f.

X

Fig. 10 .

 10 Fig. 10. The timed automaton for the NOR gate Ack k .

Fig. 11 .

 11 Fig. 11. A global clock with a period p, the receiver and the transmitter.

  17

Fig. 12

 12 Fig. 12. A three-stage realizations of Stari with internal actions hidden.

Fig. 13 .

 13 Fig. 13. Time and memory consumption for STARI veri cation using BDDs.

Fig. 14 .Fig. 15 .

 1415 Fig. 14. Experimental results for STARI veri cation using DBMs.

All the results reported here were obtained on a Pentium II with 512 MB of memory.

This work was partially supported by the European Community Esprit-LTR Project 26270