R G Perkins
email: perkinsr@cf.ac.uk

S Lefebvre

J Lavaud

Light response curve methodology and possible implications in the application of chlorophyll fluorescence to benthic diatoms

Chlorophyll a fluorescence has been increasingly applied to benthic microalgae, especially diatoms, for measurements of electron transport rate (ETR) and construction of rapid light response curves (RLCs) for the determination of photophysiological parameters (mainly the maximum relative ETR (rETR max ), the light saturation coefficient (E k ) and the maximum light use coefficient). Various problems with the estimation of ETR from the microphytobenthos have been identified, especially in situ. This study further examined the effects of light history of the cells and light dose accumulation during RLCs on the fluorescence measurements of ETR using the benthic diatom Navicula phyllepta. RLCs failed to saturate when using incremental increases in irradiance, however curves with decreasing irradiance did saturate. Patterns indicating photoacclimation in response to light histories were observed, with higher rETR max and E k , and lower , at high light compared to low light. However these differences could be negated by increasing the RLC irradiance duration from 30 to 60 s. It is suggested that problems arose as a result of rapid fluorescence variations due to ubiquinone, Q A , oxidation and non-photochemical chlorophyll fluorescence quenching, NPQ, which depended upon the light history of the cells and the RLCs accumulated light dose. Also, RLCs with irradiance duration of 10 s were shown to have an error possibly specific to the fluorimeter programming.

It is suggested that RLCs, using a Diving-PAM fluorimeter on benthic diatoms, should be run using decreasing irradiance steps of 30 s duration.

Introduction

Benthic microalgae communities, mainly composed of diatoms, inhabit shallow estuarine intertidal sediments where they are responsible for the major part of the photosynthetic primary production [START_REF] Macintyre | Microphytobenthos: The ecological role of the "secret garden" of unvegetated, shallow-water marine habitats. I-Distribution, abundance and primary production[END_REF]. The light environment to which the microphytobenthos are exposed is highly variable due to the tidal regime, which expose the cells to a wide range of, and rapid changes between, levels of irradiance, together with a high spatial and temporal frequency of light fluctuations.

Therefore, one the main challenges for microphytobenthic algae is to cope with fluctuations in irradiance, largely through avoidance of energy imbalance within the photosynthetic apparatus, and maintainance of an optimal irradiance to maximise photosynthetic productivity [START_REF] Underwood | Primary production by phytoplankton and microphytobenthos in estuaries[END_REF][START_REF] Perkins | Can chlorophyll fluorescence be used to estimate the rate of photosynthetic electron transport within microphytobenthic biofilms?[END_REF], Consalvey et al. 2005a). For this purpose, algae have evolved a number of mechanisms referred to as photoacclimation (MacIntyre et al. 2000, Raven and[START_REF] Raven | Adaptation, acclimation and regulation in algal photosynthesis[END_REF].

To investigate the photosynthesis of the microphytobenthos, chlorophyll a (Chl a) fluorescence measurements of electron transport rate (ETR) and related photophysiological parameters are being increasingly applied (Consalvey et al. 2005a). Studies have been used to compare measurements of primary productivity using different methodologies, principally carbon uptake (radio-labeled 14 C), electron transport rate (Chl a fluorescence) and oxygen evolution (oxygen electrodes) [START_REF] Flameling | Light dependence of quantum yields for PSII charge separation and oxygen evolution in eucaryotic algae[END_REF][START_REF] Hartig | Photosynthetic activity of natural microphytobenthos populations measured by fluorescence (PAM) and 14 Ctracer methods: a comparison[END_REF][START_REF] Barranguet | Estimating primary production rates from photosynthetic electron transport in estuarine microphytobenthos[END_REF][START_REF] Perkins | In situ microphytobenthic primary production during low tide emersion in the Tagus estuary, Portugal: production rates, carbon partitioning and vertical migration[END_REF], 2002). Others have been confined solely to the use of Chl a fluorescence as a proxy for primary productivity by measuring ETR [START_REF] Kromkamp | Determination of microphytobenthos PS II quantum efficiency and photosynthetic activity by means of variable chlorophyll fluorescence[END_REF][START_REF] Serôdio | Modelling the primary productivity of intertidal microphytobenthos: time scales of variability and effects of migratory rhythms[END_REF][START_REF] Serôdio | A chlorophyll fluorescence index to estimate short-term rates of photosynthesis by intertidal microphytobenthos[END_REF]Serôdio et al. 2005a;Underwood et al. 2005) or as a proxy for algal biomass [START_REF] Serôdio | Non-destructive tracing of migratory rhythms of intertidal benthic microalgae using in vivo chlorophyll a fluorescence[END_REF][START_REF] Honeywill | Determination of microphytobenthic biomass using pulse amplitude modulated minimum fluorescence[END_REF].

The recent technique of rapid light response curves (RLCs), defined as very short (tens of seconds) light steps of different intensity, has been widely applied for the determination of ETR versus irradiance on different photosynthetic aquatic organisms like macro-and micro-algae, seagrasses and corals [START_REF] Schreiber | Assessment of photosynthetic performance of Prochloron in Lissoclinum patella in hospite by chlorophyll fluorescence measurements[END_REF][START_REF] Ralph | In situ underwater measurements of photosynthetic activity of coral zooanthellae and other reef-dwelling dinoflagellate endosymbionts[END_REF][START_REF] Kühl | Photosynthetic performance of surface-associated algae below sea ice as measured with a pulseamplitude modulated (PAM) fluorometer and O 2 microsensors[END_REF][START_REF] Glud | Benthic diatoms of a high Arctic fjord (Young Sound, NE Greenland): importance for ecosystem primary production[END_REF][START_REF] Ralph | Rapid light curves: A powerful tool to assess photosynthetic activity[END_REF]. The short duration of each light step is an attempt to minimize the confounding effects of light acclimation encountered with "steady-state" traditional light curves (Serôdio 2004, Serôdio et al. 2005a). RLCs have been used with success on microphytobenthos assemblages isolated from the field or directly in situ [START_REF] Perkins | Can chlorophyll fluorescence be used to estimate the rate of photosynthetic electron transport within microphytobenthic biofilms?[END_REF], Serôdio et al. 2005a). However, the assessment of RLCs on intact biofilms can be disturbed, which may alter the calculation of ETR as a function of light intensity [START_REF] Perkins | Can chlorophyll fluorescence be used to estimate the rate of photosynthetic electron transport within microphytobenthic biofilms?[END_REF]. The two major sources of disturbance that have been identified are the attenuation of light in the sediment and the depth-integration of fluorescence emitted from sub-surface layers (Forster and Kromkamp 2004, Serôdio 2004), and the migration of the cells within the biofilm [START_REF] Kromkamp | Determination of microphytobenthos PS II quantum efficiency and photosynthetic activity by means of variable chlorophyll fluorescence[END_REF][START_REF] Perkins | Can chlorophyll fluorescence be used to estimate the rate of photosynthetic electron transport within microphytobenthic biofilms?[END_REF], Serôdio 2004). In addition, rapid as well as endogenous changes in photosynthesis activity, which modulate the Chl a fluorescence emission, can potentially affect ETR measurements (Serôdio et al. 2005a). In particular, the red-ox state of Q A , the primary PSII electron acceptor, and non-photochemical Chl a fluorescence quenching (NPQ) have been shown to influence the fluorescence measurements in microphytobnethic diatoms [START_REF] Consalvey | Monitoring migration and measuring biomass in benthic biofilms: the effects of dark/far-red adaptation and vertical migration on fluorescence measurements[END_REF], Serôdio et al. 2005a, 2005b). In this context, technical features of the RLCs, such as the length of each irradiance step, have been shown to be important for the assessment of ETR (Serôdio et al. 2005a).

This study aimed to further improve the use of Chl a fluorescence measurements for the construction of RLCs for application to benthic algae. We especially focused on the ability of the RLCs to relate the photoacclimation status through the assessment of ETR. By using algal cultures of the benthic diatom, Navicula phyllepta Kützing, we investigated the effect on the ETR/light relationship of: 1) the light history of the cells, 2) the RLCs light step duration and order (i.e. increasing or decreasing irradiance). The data obtained were compared with RLCs performed on separate replicates of the culture for each light step ("non sequential" light curves, N-SLCs) to assess the potential cumulative effect of rapid photoacclimation of the cells during the light curve itself. The results raise important questions with regard to potential errors in the measurement and interpretation of RLCs for cultured benthic diatoms, errors which may equally apply for in situ measurements.

Methods

Navicula phyllepta cultures

Navicula phyllepta was obtained from the microalgal culture collection of the Laboratoire de Biologie Marine (ISOMer, Nantes, France). Stock cultures were grown in an artificial seawater medium [START_REF] Harrison | A broad spectrum artificial seawater medium for coastal and open ocean phytoplankton[END_REF] at low irradiance (20 µmol photons m -2 s -1 , 6h/18h, light/dark photoperiod). The original medium was complemented following De [START_REF] Brouwer | Physical characterization and diel dynamics of different fractions of extracellular polysaccharides in an axenic culture of a benthic diatom[END_REF], with the addition of Fe-NH 4citrate (1.37 µM final concentration), CuSO 4 5H 2 O (0.04 µM f.c.), folic acid (0.18 nM f.c.), nicotinic acid (0.0325 µM f.c.), thymine (0.95 µM f.c.), nM f.c.) and inositol (1.11 µM f.c.). Experiments were run with cultures grown in semi-continuous culture mode (volume: 250 mL, temperature: 15 ± 1°C) in Erlenmeyer flasks (500 mL) illuminated from below (100 µmol photons m -2 s -1 , 14h/10h, light/dark photoperiod) by a high intensity discharge lamp (Osram HQI BT, 400 W).

Rapid light response curves

Fluorescence measurements were made using a Diving-PAM fluorimeter (Walz, Effeltrich, Germany). Sub-samples of N. phyllepta cultures were incubated at either low or high light (LL or HL; 25 or 400 µmol photons m -2 s -1 PPFD respectively), in a stirred, temperature controlled (15 C) chamber, for 60 min. This light acclimation period was staggered, so that each sub-sample had been exposed for exactly 60 min prior to measurement of each RLC. After light acclimation, the culture sub-sample was transferred into a temperature controlled (15 C) Hansatech DW2 chamber, with continuous stirring to prevent settling. The Diving-PAM fibre optic probe was applied to the top aperture of the chamber so that measurements were taken from cells exposed to the actinic light level applied from the halogen internal light source, thus minimising any light gradient effect (other apertures were darkened). Cultures were dark-adapted for 5 min prior to RLCs, with measurements at 10, 30 and 60 s at each light intensity. RLCs were performed with either incremental increases ("up") or decreases ("down") in the actinic light intensity between 0 and 1850 µmol photons m -2 s -1 PPFD. Light levels were measured using the Diving-PAM quantum meter, corrected against a calibrated Li-Cor LI-189 quantum meter with a Q21284 quantum sensor.

At each light level, effective photosystem II (PSII) quantum efficiency (F q '/F m ', [START_REF] Oxborough | An instrument capable of imaging chlorophyll a fluorescence from intact leaves at very low irradiance and at cellular and subcellular levels of organization[END_REF][START_REF] Lawson | Responses of photosynthetic electron transport in stomatal guard cells and mesophyll cells in intact leaves to light, CO 2 , and humidity[END_REF][START_REF] Perkins | Can chlorophyll fluorescence be used to estimate the rate of photosynthetic electron transport within microphytobenthic biofilms?[END_REF] was measured by the saturation pulse technique, whereby a saturating light pulse of 7,600 µmol photons m -2 s -1 PPFD was applied for 400 ms to measure the maximum fluorescence yield, F m ". F q '/F m ' is equivalent to ΔF/F m ' [START_REF] Genty | The relationship between the quantum yield of photosynthetic electron transport and quenching of chlorophyll fluorescence[END_REF], however F q ' is preferred as it represents, not a change in fluorescence yield, but a difference resulting from photosynthetic quenching of yield, hence the suffix q [START_REF] Oxborough | An instrument capable of imaging chlorophyll a fluorescence from intact leaves at very low irradiance and at cellular and subcellular levels of organization[END_REF]. F q '/F m ' was calculated as (F m ' -F') / F m ', where F' is the fluorescence yield in the light adapted state, just prior to the application of the saturating pulse.

Hence F q '/F m ' is equivalent to the Genty parameter in the light adapted state [START_REF] Genty | The relationship between the quantum yield of photosynthetic electron transport and quenching of chlorophyll fluorescence[END_REF]. Relative electron transport rate (rETR) was then calculated as the product of F q '/F m ' and PPFD/2 [START_REF] Sakshaug | Parameters of photosynthesis: definitions, theory and interpretation of results[END_REF][START_REF] Perkins | In situ microphytobenthic primary production during low tide emersion in the Tagus estuary, Portugal: production rates, carbon partitioning and vertical migration[END_REF][START_REF] Perkins | Can chlorophyll fluorescence be used to estimate the rate of photosynthetic electron transport within microphytobenthic biofilms?[END_REF].

The Diving-PAM has internal programmes allowing 8-step RLCs with increasing light levels. Therefore, RLCs were performed using the remote control functions in the WinControl software (Walz, Effeltrich, Germany) from a laptop computer, so as to apply decreasing as well as increasing light levels covering 12 light increments. This also enabled examination of the transient fluorescence kinetics, by monitoring the F' signal in the chart mode, allowing determination of F' "steadystate" as well as examining changes in F' in response to application of each actinic light level.

Prior to all sets of light curves, the Diving-PAM auto-zero function was set using the Hansatech chamber filled with an equivalent volume of clear media. Light calibration was also carried out before and after all light curves due to an observed 10 % variation in halogen output over time, despite running the Diving-PAM from a mains supply. As a result light levels differed between curves by up to 10 %, with this variation accounted for in calculations of rETR.

Over-estimation of photochemical efficiency can occur when using the Diving-PAM with low biomass culture which results in an F' signal below 130 relative units (Walz Diving-PAM handbook). This low signal strength may also occur at exposure to high light due to high levels of non-photochemical fluorescence quenching (NPQ). Therefore the Diving-PAM gain setting was set to a maximum of 12 to avoid low values of F'. However at such a high gain, the auto-zero function can also result in over-estimation of quantum efficiency. A large auto-zero value will be a greater proportion of F' compared to F m ", when F' decreases as actinic light level increases. Mathematically, the same percentage change in F' and F m ' will therefore result in different values of F q '/F m " due to the weighted influence of the auto-zero.

Therefore, only measurements with a low auto-zero (< 40 relative units) were used in the construction of RLCs.

Non-sequential light response curves

To remove the cumulative effect of light history experienced during a RLC, the above methods were modified by using a different replicate sub-sample of culture for each actinic light level. The range of light intensities was also extended up to 3200 µmol photons m -2 s -1 . In addition a further RLC data point was added, with measurements made when the fluorescence signal F' reached a constant level (as observed on the Win Control software chart function). This value of F', defined here as "steady-state", was probably not a true steady-state due to time limitations and so was not defined as

F s .
Non-sequential light response curves (N-SLCs) and calculations were otherwise the same as for rapid RLCs, except that a first set of curves used cells maintained at 100 µmol photons m -2 s -1 PPFD, with no photo-acclimation to high or low light. A second set of N-SLCs were then obtained using a different original semicontinuous culture of N. phyllepta, but incorporating the HL and LL photoacclimation period. These curves were not directly comparable to the preceding datasets, due to the change in source culture.

NPQ was calculated during N-SLCs, as (F m -F m ') / F m ' (Krause and Weiss 1991; Lavaud et al. 2002a). F m ' was measured as described above, using application of the saturating pulse after 10, 30 and 60 s at each irradiance, and when F' reached an approximate "steady-state". The maximum fluorescence yield in the dark adapted state, F m , is more problematic to measure for diatoms, due to NPQ being maintained in the dark through processes such as chlororespiration [START_REF] Jakob | Unusual pH-dependence of diadinoxanthin deepoxidase activation causes chlororespiratory induced accumulation of diatoxanthin in the diatom Phaeodactylum tricornutum[END_REF][START_REF] Dijkman | Indications for chlororespiration in relation to light regime in the marine diatom Thalassiosira weissflogii[END_REF]Lavaud et al. 2002b), thus suppressing F m below its true value [START_REF] Mouget | Suitability of the Fluorescence Monitoring System (FMS, Hansatech) for measurement of photosynthetic characteristics in algae[END_REF]. The calculated values of NPQ therefore show relative changes, using an approximation of F m obtained after 5 min dark adaptation prior to each RLC.

Statistical analysis

RLCs of rETR against light intensity (PPFD) were constructed using the model of [START_REF] Eilers | A model for the relationship between light intensity and the rate of photosynthesis in phytoplankton[END_REF], estimating the maximum electron transport rate (rETR max ), the maximum light use efficiency (α) and the light saturation coefficient (E k ) calculated as (rETR max / α).

Curve fitting was achieved using the downhill simplex method of the Nelder-Mead model, and standard deviation of parameters was estimated by a bootstrap method under Fortan 77 code (Press et al. 2003). All fittings were tested by analyses of variance (P<0.001), residues being tested for normality and homogeneity of variance, and parameters significance by Student t-test (P<0.05). RLCs and photosynthetic parameter comparisons were achieved using the method of [START_REF] Ratkowski | Non linear regression modeling. A unified practical approach[END_REF] for non-linear models.

Results

Rapid light response curves

Rapid RLCs for low light (LL) and high light (HL) acclimated cultures of N.

phyllepta showed saturation and down regulation when irradiance was reduced from 1850 µmol photons m -2 s -1 (Fig. 1A,B: 10, 30 and 60 down). In contrast, when irradiance was incrementally increased, light saturation and photoinhibition (Fig.

1A,B: 10, 30 and 60 up) did not occur. When irradiance was increased or reduced, rETR above 500 µmol photons m -2 s -1 increased in proportional to the increase in length of time at each light level.

Calculated values of rETR max ,  and E k obtained from RLCs with decreasing light levels were compared between HL and LL cultures (Fig. 2). 10, 30 and 60 s RLCs for HL cultures showed rETR max and E k higher and α lower than LL cultures (P<0.001; Fig. 2A,B,C). Thus photoacclimation occurred within the 1 h light treatment period. rETR max increased significantly with the length of irradiance step for low light and high light (P < 0.01) acclimated cultures, whereas α showed no significant correlation with length of irradiance step. E k , due the nature of its derivation from (rETR max / α) showed the same increase as rETR max as a function of lengthening irradiance step (P<0.001).

RLCs with increasing light levels did not saturate for LL (Fig. 1A: 60 s) and HL cultures (Fig. 1B: 10, 30 and 60 s), preventing calculation of rETR max and E k .

Estimation of α indicated photoacclimation patterns similar to the decreasing irradiance RLCs. LL cultures had significant higher values of α compared to HL cultures (P<0.001). 10 and 30 s LCRs for LL cultures just reached saturation, and showed the same pattern in rETR max observed for decreasing RLCs, with a significant increase in rETR max (165 to 235 rel. units from 10 to 30 s respectively), an increase in E k (319 to 439 µmol photons m -2 s -1 PPFD), but no change in α (0.52 rel. units).

Non-sequential light response curves

Separate replicate N. phyllepta cultures used for each light level (Fig. 3) resulted in N-SLCs with similar patterns as rapid RLCs (Fig. 1). rETR increased significantly with length of irradiance step (P <0.001) at irradiances above 300 µmol photons m -2 s -1 , with correspondingly higher rETR max . 10, 30 and 60 s RLCs all showed light saturation and down regulation, whereas light curves when F' was allowed to reach an apparent "steady-state" at each light intensity, did not saturate. No steady state data point was possible at 1850 µmol photons m -2 s -1 as photosynthetic down regulation (presumably NPQ) resulted in a Chl a fluorescence yield (F') below the minimum value of 130 relative units required for accurate measurement of F q '/F m '.

N. phyllepta (a different culture from that used above and so not directly comparable) was then acclimated to either low (25 µmol photons m -2 s -1 ) or high (400) light as above, prior to RLCs with different replicate cultures used for each light intensity (Fig. 4). There were significant differences between the curves (P<0.001), HL and LL cultures showed a significant increase in rETR proportional to an increase in time at each irradiance step, except between 10 and 30 s HL, 30 and 60 s HL and between steady state HL and LL RLCs.

Despite changing replicate cultures for each light level, the same patterns were observed as for the rapid RLCs (Fig. 1). HL acclimated cultures had significant greater rETR max (P<0.001, Fig. 5A), and higher E k (P<0.001, Fig. 5C) than LL acclimated cultures. There were no significant differences for α (P>0.05; Fig. 5B).

However the difference in rETR max between HL and LL cells declined as the time at each RLC increment increased. There was a significant increase in rETR max and E k with the length of irradiance step for low light and high light acclimated cultures (P<0.001); α showed no significant differences for both LL and HL cultures (P>0.05).

Chl a fluorescence and NPQ kinetics

An example of the fluorescence kinetics obtained at irradiance steps above 300 µmol photons m -2 s -1 is reproduced (Fig. 6) showing the position at which saturation pulses were applied. The example is for a low-light culture (25 μmol m -2 s -1 ), transferred to 370 μmol m -2 s -1 . At 10 s the comparatively slow data acquisition time of the Diving-PAM fluorimeter (compared to the rapid induction of fluorescence quenching)

resulted in an under-estimation of F q '/F m '. This resulted from the high rate of decrease in F' following the increase in actinic irradiance. F' was recorded by the Diving-PAM prior to a further decrease before the measurement of F m '. F' and F m '

were therefore recorded at different times, resulting in under-estimation of F m ' relative to F' so that values of F q '/F m ' were underestimated and often values of zero were reported. 10 s light curves would then result in under-estimation of rETR above 300 µmol photons m -2 s -1 PPFD. This was most obvious for HL cultures, which showed a more rapid decline in F' compared to LL cultures (data not shown). The magnitude of the increase in F' on the application of the actinic light and the rate of decline after the peak in F' both increased as irradiance increased above 300 µmol photons m -2 s -1 .

Above 300 μmol photons m -2 s -1 , NPQ was induced rapidly during RLCs, with relatively high levels after 60 s at each irradiance, for both LL and HL acclimated cultures (Fig. 7). While the amplitude of NPQ increased with illumination time for LL cultures, it remained relatively similar for HL cultures. LL cultures (Fig. 7A) had similar or lower levels of NPQ compared to HL cultures (Fig. 7B) after 10, 30 and 60

s, but higher NPQ at "steady-state" (insert, Fig. 7B).

Discussion

The aims of the study were to determine the effects of light history prior to, and The data reported here suggest two stages of photoacclimation. Firstly, the acclimation resulting from exposure to low and high irradiance prior to RLCs, effectively the type of photoacclimation that a RLC attempts to detect. Secondly, the "acclimation" during the RLCs themselves; which RLC methodology should avoid. In addition, the limitations of available methodology must also be considered.

The effect of accumulated light dose on RLCs interpretation

RLCs with incremental decreases in irradiance showed saturation and a decrease in rETR max at higher irradiance due to photoinhibition (Fig. 1). In contrast, RLCs with increasing irradiance often did not saturate. This raises the first issue of RLCs methodology: the effect of accumulated light dose during the light curve, dependent upon the order of irradiances ("up" or "down") and the duration of each step (from 10 s to 2-3 min).

With increasing irradiance, there is an accumulative effect of light dosage resulting in progressive induction, occurring on a time scale of 10"s of seconds, of the different components of the photosynthetic apparatus. Ubiquinone (Q A ) oxidation, the rate limiting step in electron transport [START_REF] Dau | Molecular mechanisms and quantitative models of variable photosystem II fluorescence[END_REF] would have been faster for increasing irradiance light curves due to induction of more rapid photochemical energy transfer. Also, induction of non-photochemical Chl a fluorescence quenching, NPQ will have increased proportionally to the light dose experienced during the RLC.

In diatoms, the photosynthetic translocation of protons across the thylakoid membrane has been linked to energy dependent NPQ (Ting & Owens 1993;Lavaud et al. 2002c) associated with xanthophyll pigment synthesis [START_REF] Arsalane | Influence of the pool size of the xanthophyll cycle on the effects of light stress in a diatom: competition between photoprotection and photoinhibition[END_REF][START_REF] Olaizola | Non-photochemical fluorescence quenching and the diadinoxanthin cycle in a marine diatom[END_REF]Lavaud et al. 2002a[START_REF] Lavaud | Enrichment of the light-harvesting complex in diadinoxanthin and implications for the non-photochemical fluorescence quenching in diatoms[END_REF][START_REF] Lavaud | General features of photoprotection by energy dissipation in planktonic diatoms (Bacillariophyceae)[END_REF]Serôdio et al. 2005b). This process generates a photoprotective dissipation of excess energy in photosystem II (PSII) reducing the Chl a fluorescence yield, on a time scale of 10"s of seconds [START_REF] Macintyre | The effect of water motion on short-term rates of photosynthesis by marine phytoplankton[END_REF]Lavaud et al. 2002a[START_REF] Lavaud | General features of photoprotection by energy dissipation in planktonic diatoms (Bacillariophyceae)[END_REF][START_REF] Raven | Adaptation, acclimation and regulation in algal photosynthesis[END_REF]. Hence, Q A oxidation and NPQ will affect in complex ways, the measurement of effective PSII quantum efficiency and resultant calculation of (r)ETR.

Increasing the duration of each incremental irradiance step was also seen to induce photoacclimation. As the length of each step increased from 10 to 60 s rETR increased proportionally, often resulting in a lack of saturation for RLCs with increasing irradiance. Above 500 µmol photons m -2 s -1 , NPQ increased in importance, and the duration for each irradiance step increased the extent of NPQ (Fig. 7). In N. phyllepta, Q A oxidation was the primary cause of the change in fluorescence yield

for RLCs with 10 s steps, however for 30 s and above, the level of NPQ became most significant. As discussed below, the relative importance of Q A oxidation and NPQ is species and light history dependent, and in diatoms the relationship between PSII redox-state and NPQ is species specific [START_REF] Ruban | The super-excess energy dissipation in diatom algae: comparative analysis with higher plants[END_REF]Lavaud unpublished results).

For decreasing irradiance steps, the accumulative light dose effect described above was reduced relative to increasing irradiance RLCs. However, decreasing the irradiance and hence immediate exposure to high irradiance did not appear to induce photodamage. Two observations support this, the low amplitude of NPQ for 10 and 30 s illumination duration at high irradiances, and the fact that rETR below 500 µmol photons m -2 s -1 was similar to that obtained with increasing irradiance. The use of decreasing irradiance therefore reduces the over-estimation of rETR and is likely to be more representative of the photophysiological state of the diatom cells prior to application of the RLC, which is the state that the RLC aims to ascertain.

Despite changing the culture used for each irradiance step (N-SLCs), the same patterns in data were observed as for rapid RLCs (Fig. 3,4). rETR increased as a function of the length of irradiance during the light curve, such that even when F' was allowed to reach an approximation of "steady-state", RLCs failed to saturate. The N-SLCs indicate that the effect of light dose on the fluorescence measurements occurred rapidly, within the duration of each irradiance step. This observation confirms the impact of combined Q A redox state and NPQ on the Chl a fluorescence kinetics and acquisition of F' and Fm' for the calculation of rETR (see Fig. 6). [START_REF] Ralph | Rapid light curves: A powerful tool to assess photosynthetic activity[END_REF] conducted a recent similar investigation on the higher aquatic plant Zostera marina. They did not report a lack of saturation of the rETR curves, but in some cases did report a lack of down regulation post saturation.

This lack of down regulation occurred for plants after low light treatment, and [START_REF] Ralph | Rapid light curves: A powerful tool to assess photosynthetic activity[END_REF] suggested that their capacity for down regulation was exceeded. This differs from the data reported in the present study, where a lack of saturation in rETR was greater for high light compared to low light treatments, despite a higher capacity for NPQ in the former. We suggest that the lack of saturation of RLCs observed with N. phyllepta is an additional indication (see also [START_REF] Ruban | The super-excess energy dissipation in diatom algae: comparative analysis with higher plants[END_REF]) that rapid photoacclimatory processes occur in diatoms which can greatly affect fluorescence measurements, and especially the velocity of fluorescence transients [START_REF] Ruban | The super-excess energy dissipation in diatom algae: comparative analysis with higher plants[END_REF]). Rapid processes known to occur to a higher extent and with more rapid induction kinetics in diatoms are the xanthophyll cycle [START_REF] Jakob | Unusual pH-dependence of diadinoxanthin deepoxidase activation causes chlororespiratory induced accumulation of diatoxanthin in the diatom Phaeodactylum tricornutum[END_REF][START_REF] Lavaud | General features of photoprotection by energy dissipation in planktonic diatoms (Bacillariophyceae)[END_REF], NPQ (Lavaud et al. 2002a;[START_REF] Ruban | The super-excess energy dissipation in diatom algae: comparative analysis with higher plants[END_REF], Serôdio et al. 2005b) and the PS II electron cycle (Lavaud et al 2002b).

The effect of light history on RLC interpretation

The effects of the order and the duration of each RLC irradiance step were greatest for high light (HL) acclimated cultures (Fig. 1,4). The light history, to which the cells were exposed, modified the speed of response of photochemistry to short changes in irradiance. HL cells had a greater capability to respond quickly to an increase in irradiance, most likely due to a greater availability in electron acceptors from photochemical reactions, increasing the speed of Q A oxidation. The more rapid kinetics for NPQ in HL cells can be explained by the basal level of NPQ developed after 1 h exposure at 400 µmol photons m -2 s -1 , which did not relax during the 5 min dark adaptation (Lavaud et al. 2002c;[START_REF] Ruban | The super-excess energy dissipation in diatom algae: comparative analysis with higher plants[END_REF] In diatoms, NPQ amplitude and kinetics are closely related to the amount of xanthophylls (Casper-Lindley and Bjorkman 1998; Lavaud et al. 2002aLavaud et al. 2002c)), and are dependent upon light history (Willemoes and Monas 1991; [START_REF] Mouget | Long-term photoacclimation of Haslea ostrearia (Bacillariophyta): effect of irradiance on growth rates, pigment content and photosynthesis[END_REF][START_REF] Mouget | Acclimation of Haslea ostrearia to light of different spectral qualities -Confirmation of "chromatic adaptation" in diatoms[END_REF][START_REF] Lavaud | Enrichment of the light-harvesting complex in diadinoxanthin and implications for the non-photochemical fluorescence quenching in diatoms[END_REF], the state of growth [START_REF] Arsalane | Influence of the pool size of the xanthophyll cycle on the effects of light stress in a diatom: competition between photoprotection and photoinhibition[END_REF]) and the species [START_REF] Lavaud | General features of photoprotection by energy dissipation in planktonic diatoms (Bacillariophyceae)[END_REF]Serôdio et al. 2005b). Thus, all these aspects have to be taken into account in the potential effects of NPQ during the RLC acquisition and interpretation.

Consequences for photophysiological parameters calculated from the RLCs

An expected pattern was observed when comparing rETR max ,  and E k between HL and LL cultures (Fig. 2). The 1 h acclimation resulted in higher rETR max and E k and lower  for HL compared to LL cells. Higher rETR max and E k are typical for high light acclimated cells which have modified their light harvesting to utilise the high levels of light to which they are exposed. Conversely, low light acclimated cells modify their photophysiology to maximise light harvesting efficiency and hence have higher values of α. However the light dose effect experienced during the RLCs reduced or even negated these differences in rETR max . Similarly, for N-SLCs, the differences in photophysiological parameters reduced as a function of increasing length of each irradiance period. As a result, no difference was observed in rETR max by "steady-state" (Fig. 5). This implies that long irradiance steps caused a photo-dose effect that reduced or even negated the real level of 1 h photoacclimation. It remains surprising though that cultures of N. phyllepta acclimated to 25 or 400 µmol photons m -2 s -1 did not saturate at 1850 µmol photons m -2 s -1 . N. phyllepta may have a high capacity to respond quickly to high light, probably through regeneration of ADP and NADP + and as a result of alternative electron pathways known to be active in diatoms [START_REF] Caron | Chlorophyll fluorescence transients from the diatom Phaeodactylum tricornutum: relative rates of cyclic phosphorylation and chlororespiration[END_REF]Lavaud et al. 2002b;Wilhelm et al. 2004). This is possibly a common feature of benthic diatoms, which may often experience rapid variations in incident light intensity.

Although the dataset was obtained from measurements on diatom cells in culture, the data suggest possible ecological implications with regard to diatom acclimation to light environment fluctuation in situ (Serôdio et al. 2005b). It would appear that N. phyllepta has a high ability to acclimate quickly to increasing irradiance. This would obviously be an advantage to cells inhabiting an open mudflat environment in which rapid changes could occur, e.g. as a result of cloud induced light flecking. Any energy dependent photoprotective acclimation, being more rapid than downward migration, would not only precede migration [START_REF] Underwood | Patterns in microphytobenthic primary productivity: Species-specific variation in migratory rhythms and photosynthesis in mixed-species biofilms[END_REF] should high irradiance persist, but would also prevent wasteful short-term migrations requiring production and excretion of extracellular polymeric substances (carbohydrates generically described as EPS) used in migration (Consalvey et al. 2005b and references there-in).

Specificity of the RLCs acquisition with the Diving-PAM methodology

Analysis of the fluorescence kinetics from N. phyllepta indicated an aspect of methodology, which may be particular to the Diving-PAM, and which can generate an error in the measurement of F m ' and hence rETR for 10 s irradiance steps (see the description in the Results section, Fig. 6). To summarise, the time delay between measurement of F' and the corresponding F m ' used in calculation of the quantum efficiency resulted (during this study) in an under-estimation of F m ' relative to F' and hence a falsely low efficiency. The example illustrated was for a low light culture at 25 μmol m -2 s -1 , transferred to 370 μmol m -2 s -1 . This is an abrupt change, however the effect was greatest for HL acclimated cultures and at high irradiances, when the rate decay in F' (presumably resulting from interaction between Q A oxidation and NPQ induction) was greatest. As such the level of this error is a function of light dose and hence the light history to which the cells were exposed. This problem was not encountered with the higher aquatic plant Zostera [START_REF] Ralph | Rapid light curves: A powerful tool to assess photosynthetic activity[END_REF] presumably because the transients in fluorescence yield in plants are slower than in diatoms, although NPQ relaxation is slower in diatoms [START_REF] Ruban | The super-excess energy dissipation in diatom algae: comparative analysis with higher plants[END_REF]).

Conclusions

The present work indicates that light dose and light history strongly affect fluorescence measurements used in RLC acquisition. These features have to be taken into account in the acquisition and interpretation of Chl a fluorescence RLCs. For cultured benthic diatoms, and presumably for in situ mixed biofilms for the same reasons, extreme care should be taken in choice of light curve methodology.

Parameters measured will be functions of light history and light exposure during the light curve itself and the extent of this will in turn be dependent upon the light history prior to the RLC. It is suggested that it is not always possible to answer the question posed above: what is being measured for light curves of different length of actinic irradiance? It is not possible to extrapolate these results to make general comments for all diatom species, nor to say that the changes suggested will occur for in situ measurements. Indeed, no methodology is perfect and in many cases measurement itself induces a change, thus making the commonly stated "non-intrusive" nature of fluorescence measurements incorrect. For example, an increasing RLC induces photoacclimation, however a decreasing RLC will allow dissipation of photophysiological state (e.g. high light induced NPQ) as light level is reduced:

neither method is devoid of experimental error. However it is suggested that the changes induced during a RLC should be carefully considered during interpretation of results. In general, RLCs of 60 s or those with increasing incremental irradiance steps may not detect differences in photophysiological state caused by light history, µmol photons m -2 s -1 . Light curves were run using different sub-samples of culture for each light curve step and with irradiance durations of 10, 30 and 60 s, followed by a final measurement when F' reached approximate "steady-state" after 2 to 3 minutes.

Curves were constructed using the model of [START_REF] Eilers | A model for the relationship between light intensity and the rate of photosynthesis in phytoplankton[END_REF] followed by curve fitting following the Nelder-Mead model (Press et al., 2003).

Figure 4. Non-sequential light response curves (mean  s.e., n = 3) for N. phyllepta cultures grown at an irradiance of 100 µmol photons m -2 s -1 and exposed to 1 h light acclimation period of low (A, 25 µmol photons m -2 s -1 ) or high (B, 400 µmol photons m -2 s -1 ) light. Light curves were run using different sub-samples of culture for each light curve step, and with irradiance durations of 10, 30 and 60 s, followed by a final measurement when F' reached approximate "steady-state" after 2 to 3 minutes. Curves were constructed using the model of [START_REF] Eilers | A model for the relationship between light intensity and the rate of photosynthesis in phytoplankton[END_REF] followed by curve fitting following the Nelder-Mead model (Press et al., 2003).

  accumulated light dose during, a light response curve (RLC) obtained using Chl a fluorescence. It was expected that the light dose experienced by the algal cells over different time scales during RLCs, would affect the Chl a fluorescence measurements obtained, and hence modify the resulting RLCs and photophysiological parameters derived. The data obtained raise important questions with regard to the measurement and interpretation of Chl a fluorescence rapid RLCs. The primary question is, what is being measured for light curves of different length of actinic irradiance steps?

  Figure Legends

Figure 2 .

 2 Figure 2. Rapid light response curve parameters for light curves obtained using

Figure 3 .

 3 Figure 3. Non-sequential light response curves for N. phyllepta cultures grown at 100

Figure 5 .

 5 Figure 5. Non-sequential light response curve parameters (mean ± s.e., n = 3) for

Figure 6 .

 6 Figure 6. Example of fluorescence kinetics obtained for a sub-sample of N. phyllepta

Figure 7 .

 7 Figure 7. Non-photochemical Chl a fluorescence quenching (NPQ) calculated as (F m -


Karol Desnos

Safwan El Assad

Aurore Arlicot

Maxime Pelcat

Daniel Menard

Efficient Multicore Implementation of An Advanced Generator of Discrete Chaotic Sequences

Keywords: Chaotic generator, pseudo-random number generator, multicore implementation, performance analysis, dataflow model of computation I

This paper details the design and implementation performances of an efficient generator of chaotic discrete integer valued sequences. The generator exhibits orbits having very large lengths compared to those given in the literature. It is implemented in C language and parallelized using the Parameterized and Interfaced Synchronous Dataflow Model of Computation (PiSDF MoC). The proposed structure is shown to be scalable, parallel and time efficient. The resulting implementation combines a very long minimal chaotic sequence o min > 7*2 128 32-bit samples and a very high throughput of 173Mbps on 4 cores of a General Purpose Processor.

INTRODUCTION

Many information hiding and security systems such as: cryptosystems, key generation, steganography and digital watermarking systems need pseudo-random number generators (PRNGs) to achieve their objectives. An unpredictable physical process such as plasmonic or resonant systems and quantum physics [START_REF] Hartmann | Practical guide to computer simulations[END_REF] can be used to produce a non-deterministic random number (or bit). Process-based algorithms are used to generate numbers (bits) deterministically [START_REF] Blum | A simple unpredictable pseudo random number generator[END_REF][3] [START_REF] Elaine | Recommendation for random Number Generation using deterministic random bit generators[END_REF]. In the last two decades, a class of PRNGs called chaotic PRNGs has attracted much attention. Indeed, this class presents some desirable properties such as: very big sensitivity to the initial conditions and the parameters of the system, ergodicity, and ease of implementation, that make them very good candidates for use in information hiding and security systems.

We propose in this paper an efficient implementation of a generator of discrete pseudo-chaotic sequences using N = 32 bits finite precision. The proposed structure integrates three techniques: recursion, disturbance and cascading to avoid the dynamical degradation. It is also very efficient in terms of robustness and data rate. The generator results from a French patent [START_REF] Assad | Generator of chaotic Sequences and corresponding generating system[END_REF] and its PCT Extension.

Dataflow modeling and global multicore scheduling are used to generate a parallel executable for the chaotic random generator. Dataflow modeling consists in breaking the computation into independent processes that communicate through First-In First-Out (FIFO) data queues. Global multicore scheduling consists of choosing a core for executing each process and ordering their execution on each core. In this paper, the chaotic generator is described by a Parameterized and Interfaced Synchronous Dataflow graph (PiSDF) [START_REF] Desnos | PiMM: Parameterized and Interfaced Dataflow Meta-Model for MPSoCs Runtime Reconfiguration[END_REF] that serves as an input for the PREESM rapid prototyping tool [6].

PREESM is an open-source Eclipse-based tool that can simulate and generate multicore code for a given topology, i.e. organization of cores, and parallelism of architecture within minutes.

The applications of such efficient generator are numerous in the field of information hiding and security. The paper is organized as follows. Related Works are presented in Section 2 and the description of the proposed chaotic generator in Section 3. Section 4 describes the proposed techniques of optimization. Experimental results are given in Section 5, before concluding in Section 6.

II. RELATED WORK

Chaos can be generated by any non-linear dynamical system. In discrete-time non-linear dynamical system the generation of chaos is governed by a set of difference equations, namely a chaotic map. In the literature, the number of well-known one, two and three dimensional chaotic maps is surprisingly limited, in spite of the fact that they are widely used in many applications related-data security. In [START_REF] Assad | Design and analyses of efficient chaotic generators for crypto-systems[END_REF], we studied some of them, namely, the Logistic map, the piecewise linear chaotic map (PWLCM), the Frey map, and we designed others, specifically, x cos(x), x exp[cos(x)], and 2-D Tmap. We demonstrated that, when used alone, these chaotic maps don't exhibit very good statistical properties and especially their cycle length is limited. These observations are generally available for the others well-known chaotic maps such as: 1-D Skew tent [START_REF] Hasler | An introduction to the synchronization of chaotic systems: coupled Skew tent maps[END_REF], 2D-Standrd map, 2D-Cat map, 2D-Baker map [START_REF] Fridrich | Symmetric Ciphers Based no Two-Dimensional Chaotic Maps[END_REF] used in many cryptosystems to achieve the confusion/diffusion effects, or Lozi maps [10] and 3-D Lorenz map [START_REF] Senouci | Implementation and evaluation of an hyperchaos-based PRNG[END_REF] used as chaotic generator. Lian et al. [START_REF] Lian | Security analysis of a chaos-based image encryption algorithm[END_REF] studied in detail the performance of the 2-D Standard, Cat and Baker maps. They demonstrated that the Cat map has the smallest key space, but the highest key sensitivity and that it is suitable for cryptosystems using a different key in every iteration (dynamic keys). In this manner the key space is enlarged and key sensitivity is increased. The key spaces for Standard map and Baker map are both larger than that of Cat map. But to keep high key sensitivity, the number of iterations should be larger than 4 for the Standard map and bigger than 12 for the Baker map. These maps are more suitable for cryptosystems in which the same key is used in different iterations.

However, to keep a good confusion property, the average distance change in the whole image must be greater than 40%, and then, the number of iterations of the Cat map must be no smaller than 6.

To enhance the statistical properties of the generated sequences, the main ideas are based on the introduction of a technique of disturbance of the pseudo-chaotic orbit and also on the mixing of different components.

In [START_REF] Hasler | An introduction to the synchronization of chaotic systems: coupled Skew tent maps[END_REF], René Lozi introduced new models of very weakly coupled logistic and symmetric tent maps, based on a matrix of disturbance and using single or double precision numbers. He demonstrated that the 3-coupled tent maps with small value of perturbation can be used as a generator of pseudo-chaotic numbers with a uniform distribution over the interval [-1, +1]. The generated sequences have orbits of very long period, greater than 109 and less than 1012.

In [START_REF] Tkacik | A hardware random number generator[END_REF], Thomas E. Tkacik proposed a 32-bit hardware random number generator based on a Linear Feedback Shift Register (LFSR), and a Cellular Automata Shift Register (CASR). The LFSR uses a primitive polynomial of degree equal to 43 and then gives a cycle length of 243-1. The CASR is based on 37-bit with a CA150 at cell site 28, and CA90s at all other cell sites. So, it has a maximal length of 237-1. The output of the generator is formed by 32 bits, selected and permuted from the LFSR and the CASR, and then xored together. The cycle length of the generator is close to 280. The bit rate of such system depends on the maximum oscillators frequencies that can be used, but the authors don't give any information about this important question. [START_REF] Dirscherl | Pseudo random number generator[END_REF], proposed a pseudorandom generator including a first non-linear feedback shift register (NLFSR 1) with R memory cells combined with a second one with S memory cells by a multiplication operator. The result is then xored with a third NLFSR with T memory cells to obtain a final signal representing a pseudorandom number. The period length of the output sequences is equal to (2R-1) (2S-1) (2T-1), but there is no information related to the bit rate performance.

Gerd Dirscherl et al. in their patent

Most of chaos-based generators of the literature rely on floating-point data operations. This property leads to a problem when the resolution or the rounding method is different on the sender and on the receiver side. In a cryptographic system the chaotic sequences generated by the emitter and by the receiver will then be different. To avoid this problem, the generator presented in this paper works on a fixed finite precision of N bits. However, with a finite precision N, the chaotic dynamics are degraded and short cycles can appear.

III. DESCRIPTION OF THE PROPOSED CHAOTIC GENERATOR

A. Architecture of the proposed chaotic generator

The architecture of the proposed chaotic generator is given in Figure 1. It consists of: 28 basic chaotic generators, 4 analogical multiplexers 8 to 1, 3 XORs; a linear feedback shift register (LFSR), an operation of elimination of a percentage of samples and a block of quantification on Nq < N.

The proposed structure is modular, scalable, generic, and it produces a very long orbit with a large secret key.

Every basic chaotic generator of Figure 1 integrates a perturbation technique, based on linear feedback shift register (LFSR), of the chaotic orbit which increases its cycle lengths by a factor (2k-1), where k is the degree of the primitive polynomial of the LFSR.

B. Structure of the basic chaotic generator

Figure 2 shows the recursive structure of each basic chaotic generator (P-G) in the case of third order recursive filters. The discrete Skew-tent map (NLF1) and the discrete piecewise linear chaotic map (PWLCM, NLF2) are used as a non-linear functions. The output (integer pseudo-chaotic values) of each basic chaotic generator X (n) is given by the following equations.

() 1 () 2 () = ⊕ X n Xc n Xc n , (1)
{ The discrete equations of the Skew tent and the PWLCM maps are given by [START_REF] Masuda | Chaotic block ciphers: from theory to practical algorithms[END_REF] [START_REF] Lian | A chaotic stream cipher and the usage in video protection[END_REF]. The secret key of each basic generator is formed by : 6 initial conditions Xc1(n-1), Xc1(n-2), Xc1(n-3), Xc2(n-1), Xc2(n-2), Xc2(n-3) (6N bits); 2 initial conditions of the LFSRs (ks + kp bits) 6 parameters of the recursive cells [START_REF] Senouci | Implementation and evaluation of an hyperchaos-based PRNG[END_REF]

} [ ] 3 1 1 1( ) 1( 1), 1 1
1( 1) mod 1 1( ) , 2 = = - ⊕   - = + × -       ∑ N i i Xc n skewtent F n P Q F n In c Xc n i , (2) { } [ ] 3 2 1 2( ) 2 ( 1), 2 2 2( 1) mod 2 2( ) , 2 =
= - ⊕   - = + × -       ∑ N i i Xc n pwlcm F n P Q F n In c Xc n i (3) 1 () , 2 () () 1 , 2 1   ∈ -  N Xc n

C. Sequence of execution of the chaotic generator

The proposed generator of Figure 1 is running as follows:

1) Initialization of the twenty eight perturbed generators and the LFSR.

2) In every state 1, 2,..., 7 j = of the LFSR (implemented by the following primitive polynomial: 3 () 1 = ++ gx x x and commended by the clock Ck), the length of the chaotic sequence at output y 7 is given by the least common multiple (lcm) of several secondary outputs. For example:

min 5 1 2 ,   =   j j j o lcm o o (4)
is the length of the chaotic sequence at output y 5 where:

{ } ( 2 1) ( 2 1) ( 2 1) ( 2 1) 1 2 1 ,2 1 - - - -     = -× -×     j j j j ks kp j ks kp o lcm ∆ ∆ (5)
is the length of the chaotic sequence at output y 1 and

{ } (2 ) (2 ) (2 ) (2 ) 2 2 1 ,2 1     = -× -×     j j j j ks kp j ks kp o lcm ∆ ∆ (6)
is the length of the chaotic sequence at output y 2 and so on.

The minimal length of the chaotic sequence at output y is:

[ ] min 7 1 % = × - Ck o o p (8)
It is extremely long.

IV. PROPOSED METHODS FOR OPTIMIZING IMPLEMENTATION To obtain an efficient implementation of the chaotic generator, parallelization at different levels is carried out. A data flow description is used to parallelize the different actors and the actor execution time is minimized by optimizing the actor C code.

A. Dataflow description

A dataflow description is used to model the application as a directed graph. Dataflow descriptions provide advanced semantics for expressing parallelism in an algorithm regardless of the targeted hardware architecture. The directed edges of the description model the flow of the data and the actors, corresponding to the graph nodes, model the transformations applied to the data. The hierarchical PiSDF description of the algorithm is transformed by PREESM into a single-rate graph that exposes the maximum parallelism from the graph. This graph is displayed in Figure 3. It contains actors for PWLCM and SkewTent nonlinear functions, XOR operations as well as a key source actor "ReadKeys" and a sequence sink actor "WriteResults". The "Fork" actor is a generated actor that automatically distributes data tokens to make the right data available for each actor. In case of large generated sequences, the processing time is dominated by the PWLCM and SkewTent nonlinear functions. In the studied setup, 4 PWLCM and 4 SkewTent functions can be executed in parallel, bringing useful parallelism to the execution. In our experiments, the large amount of data to send between processes limits this parallelism to 2.24 on 4 cores (see Section 5.C). The parallel code generation process is described in [START_REF] Pelcat | PREESM: A Dataflow-Based Rapid Prototyping Framework for Simplifying Multicore DSP Programming[END_REF]. One C thread is generated for each core and synchronized with the other threads. Communications are implemented via shared memory and synchronization.

B. Actor C code optimization

To minimize each actor execution time, the actor C code is optimized. After a code profiling analysis, the optimizations focus on repetitive structures (loops) and mathematical functions, which consume a significant part of the total execution time. Loop parameters are set to constant values at the compile-time to benefit from compiler optimization dedicated to loop. Loop unswitching is carried-out to remove conditional structures from loop kernels. This optimization eliminates over-cost due to tests and conditional branching. Instead of using functions from the mathematical library, functions, like modulo, are rewritten and simplified for our specific use case. These different code optimizations combined with compiler optimizations allow reducing the actor execution time of one order of magnitude.

V. EXPERIMENTAL RESULTS

A. NIST test and mapping

NIST test consists of a battery of 188 tests (globally 15 different tests) to conclude regarding the randomness or nonrandomness of binary sequences [START_REF] Rukhin | A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic applications[END_REF]. We generated 100 sequences each with a different secret key and containing one million bits, and then we performed on them the NIST test. The proposed generator passes all the tests and therefore, it is robust against statistical attacks.

B. Bit rate Performance

TABLE I gives the measured mean bit rate (in Mbits/s) of the complete generator, with delay equals to 3, for the sequential implementation and the parallel implementation. The tests are made on a computer with quad-core Intel Xeon E31225 @ 3.1GHz. A very high bit rate of 173 Mbit/s is obtained on 4 cores. 4 shows the bit rate of the random generator for core numbers between 1 and 4 and different sequence lengths ranging from 1 to 32768 32-bit samples. A sequence is a list of samples generated by a single iteration of the algorithm. One may remark that a fair speedup of up to 2.24 is obtained between sequential execution and execution on 4 cores. The performance obtained on 3 cores is very equivalent to the one on 2 cores due to unbalanced core loads. A minimal sequence length is required in order to obtain enough parallelism for the multicore execution. In our use case, a generated sequence of 4K samples = 128Kbits provides a near maximum parallelism. For short sequences, the amount of communication dominates the computation in terms of time. Figure 5 displays the memory necessary to compute the random sequence generator. For generated sequences over 256 samples, the memory needs grow linearly at a rate of about 128 Bytes/sample. The used dataflow parallelization method provides a quasi-constant memory requirement when the number of cores increases.

2 1 N

 21 Xc n and X n, Where P1 and P2 are the control parameters for the Skew tent map, ranging from 1 to 2 1 Nand for the PWLCM map ranging from are and 1 to 1 --respectively. Q1 and Q2 are the perturbing signals produced by the LFSRs, ranging respectively from ks and kp are the degrees of the primitive polynomials of the LFSRs used to disturb the skew tent map and the PWLMC map. The coefficients 11

Figure 1 .

 1 Figure 1. General architecture of the proposed chaotic generator

Figure 2 .Figure 3 .

 23 Figure 2. Structure of a single basic chaotic generator (P-G)

(

  6N bits); 2 parameters of the skew tent and pwlcm maps (P1 + P2 bits) and 2 inputs In1, In2 (2N bits). With N = 32, ks = 23, kp = 21, the size of the secret key of the basic chaotic generator is 555 bits. The size of the secret key of the generating system of figure1is therefore:

  1 to 28) are respectively the nominal periods of the first and the second cells of the basic chaotic generator without perturbation. The period of the clock Ck of the LFSR is given by:

Figure 4 .

 4 Figure 4. Bit rate performance (in bit/s) versus the size of the generated sequence (in 32-bit samples)

Figure 5 .

 5 Figure 5. Necessary memory (in Bytes) versus the size of the generated sequence (in 32-bit samples) VI. CONCLUSION We presented in this paper a generator of discrete chaotic sequences and its efficient multicore implementation. The resulting implementation combines a very long minimal chaotic sequence 128 min 72 >× o samples and a very high throughput of 173Mbps on 4 cores. A possible future work is the extension of the algorithm to obtain higher parallelism for equivalent cycle length properties.

TABLE I .

 I BIT RATE PERFORMANCE

	Sequential implementation	77
	2-core implementation	148
	4-core implementation	173
	C. Details of the Multicore Execution Performances
	Figure

Implementation

Bit rate (Mbit/s)

The authors wish to thank the French National Research Agency ANR, the AtlanSTIC-CNRS FR2819 Federation and the SATT organization. This work is carried out within the framework of the research project ACSCOM (Apport du Chaos dans la Sécurité des systèmes Communicants Optiques et Mobiles), the AtlanSTIC research cluster and the GenSeq project)


Manceaux Antoine
email: antoine.manceaux@univ-lorraine.fr

Bril El-Haouzi Hind

Thomas André
email: andre.thomas@univ-lorraine.fr

Pétin Jean-François
email: jean-francois.petin@univ-lorraine.fr

Dynamic Rebalancing of an Assembly Line with a Reachability Analysis of Communicating Automata

Keywords: Assembly Line Balancing, Dynamic, Reconfiguration, Automata, Discrete Event Systems, Reachability analysis

This article proposes a method for dynamically rebalance an assembly line when disturbances occur, by reassigning the tasks to the line's workstations. The method is based on reachability analysis of an automata network that represents the tasks and workstations to be performed. The execution trace leading to the desired state provides one feasible solution to rebalance the assembly line. The method is illustrated by an industrial case study.

Context

Assembly lines are flow-oriented production systems. They are still typical in industrial production systems of high quantity standardized products. In this kind of systems, the problem of properly assigning operations to workstations is called assembly line balancing problem (ALBP). The ALBP is older than 1960 and has been tackled by Operational Research over several decades as can be seen in surveys [START_REF] Becker | A survey on problems and methods in generalized assembly line balancing[END_REF][START_REF] Boysen | Assembly line balancing: Which model to use when?[END_REF]. Furthermore, several classifications were proposed for this kind of problem, [START_REF] Boysen | A classification of assembly line balancing problems[END_REF][START_REF] Battaïa | A taxonomy of line balancing problems and their solutionapproaches[END_REF] contributing to fill the gap between real problem and academic ones [START_REF] Falkenauer | Line balancing in the real world[END_REF]. Scholl, in 1999, [START_REF] Scholl | Balancing and sequencing of assembly lines[END_REF] gives three levels in line balancing problems that correspond to long and medium-term decisions in case of yet-to-be-built assembly line for a 2 -5 years horizon, line re-engineering for 6 months -2 years horizon (for example in [START_REF] Grangeon | Heuristics for the re-balancing of a vehicle assembly line[END_REF][START_REF] Makssoud | Reconfiguration of Machining Transfer Lines[END_REF]), and rebalancing engineering due to a market dimension change for a 1 month -1 year horizon. This classification does not deal with short planning horizon balancing. Indeed, for this horizon (less than 1 month) the decision is mainly made on scheduling or sequencing decisions (master scheduling or daily sequencing) rather than a line rebalancing. For example, the 2005 ROADEF's Challenge aim was to find a solving algorithm car sequencing which better fits the existing line balancing for a daily production objective [START_REF] Estellon | Two local search approaches for solving reallife car sequencing problems[END_REF].

Our objective here is to introduce dynamic rebalancing for short time horizon when disturbances occur, such as shortage, shutdown or when the theoretic production durations differ from the realized ones. We assume that the manual assembly line is initially balanced (computed by a predictive balancing process) and the sequencing is fixed. To face the disturbances, a modification of the tasks' assignment will be proposed in such a way that the line is kept balanced. The aim is to quickly react to disturbing events with an on-line algorithm even if the new obtained balancing is not optimal. To initiate this kind of on-line dynamic rebalancing, real-time information about the work in progress must be available, leading to put this study in the intelligent manufacturing systems context (IMS) where resources and products can share and update their own data.

This paper explores the use of communicating automata to deal with dynamic rebalancing of a manual assembly line. In section 2 a formal description of the problem is presented. Following, the reachability analysis to resolve an ALBP is presented and explained in section 3. An industrial application from Trane Company and its results are discussed in section 4. Finally, section 5 concludes and displays some future works.

Problem Formalization:

A well-balanced assembly line is one where all the workstation loads are smoothed with a working time very close to the takt time. It is defined by the available time divided by the number of products to do. This takt time leads to define a moving frequency and synchronization events where products move from a workstation to the next one. The following section provides some notations for the balancing problem that is addressed by the paper.

Data

• T = {t i , i ≤ Tmax ∈ ℕ} is the set of tasks (t i is the task identifier and Tmax the number of tasks). • Dt = {dt i ∈ ℕ, i ≤ Tmax ∈ ℕ} is the set of task durations.

• W = {w i , i ≤ Wmax ∈ ℕ} the set of workstations (w i is the workstation identifier and Wmax the number of workstations).

• Dw = {Dw i , ∈ ℕ, i ≤ Wmax ∈ ℕ} is the set of workstation durations, that is defined by the sum of task durations that are assigned to this workstation.

• E = {e i , i ≤ Emax ∈ ℕ} is the set of synchronization events, i.e. the instants when the products change of workstations (e i is the event identifier and Emax the number of events in the studied period).

2.2

Constraints and objective

Assignment is given by a surjective function A: T → W that defines for each task ∈ , the workstation ∈ where is assigned: = (one task must be assigned on one and only one workstation, a workstation can host several tasks). Two kinds of constraints must be fulfilled for a proper line rebalancing:

• Takt Time (C1): The assignment of the task t i to the workstation w k is possible only if the remaining available capacity of w k (takt time minus the sum of assigned task durations dw k ) is upper or equal to the task duration dt i .

• Precedence (C2): this constraint is given by the precedence matrix P where P ij equals "1" if t i must precede t j , 0 otherwise, for a couple of tasks (t i , t j ) ∈ T 2 .

The reconfiguration (rebalancing of the assembly line) consists in finding one feasible solution (a new task assignment "A w ") that respects the previous constraints and with a short computing time compliant with the workshop time scale.

Related works

Dynamic rebalancing problem can be addressed by traditional constraint solving methods using scheduling and operational research theories. Due to its complexity, most of the addressed solving approaches are based on metaheuristics ( [START_REF] Grangeon | Heuristics for the re-balancing of a vehicle assembly line[END_REF][START_REF] Makssoud | Reconfiguration of Machining Transfer Lines[END_REF]). Even if these approaches are efficient in engineering steps, their computing time is often not compliant with production time scale when applied for purely reactive solutions. Faced to these classical approaches, methods based on Discrete Event Systems (DES) theory are emerging to model and solve scheduling problems. More particularly, the efficiency of Timed Automata (TA) and reachability analysis techniques have been demonstrated by [START_REF] Behrmann | Production scheduling by reachability analysis-a case study[END_REF] and [START_REF] Subbiah | Short-Term Scheduling of Multi-Product Batch Plants with Sequence-Dependent Changeovers Using Timed Automata Models[END_REF]. The basic underlying idea is to use reachability analysis and model-checking tools [START_REF] Clarke Andclarke | Design and synthesis of synchronization skeletons using branching time temporal logic[END_REF] in order to find a possible path for reaching an expected state (i.e. the state where all the tasks has been reassigned in such a way the line is kept balanced). The trace from initial state to the expected state provides one admissible balancing solution. Main benefits of DES approaches rely on the modular and parametric way of modeling, and finally, the ability to find feasible solutions with a computing time that is compliant with on-line constraints.

Using Reachability Analysis for rebalancing

Our approach is based on two models using a set of communicating automata:

• The task model TM defines the tasks that have to be assigned,

• The workstation model WM defines the ability of a workstation to accept an assignment, taking into account the constraints C1 and C2. • The synchronization between task and machine models is supported by a competing request/answer mechanism [START_REF] Lemattre | Allocation de fonctions de commande de systèmes critiques par recherche d'atteignabilité dans un réseau d'automates communicants[END_REF].

Used Formalism

Communicating Automata are a subclass of the Timed Automata formalism defined by Alur and Dill in 1994 [START_REF] Alur | A theory of timed automata[END_REF] that share variables and are synchronized by transition labels. A communicating automaton A is an N-tuple A = (D, X, L, T, Q m , q 0 , v 0 ), where:

• Q is a finite set of locations; • X is a finite set of integer variables; • L is a set of synchronization labels, decomposed into three separated sets: reception labels (noted label?), emission labels (noted label!) and local labels; • T is a set of transitions (q, l, g, m, q') ∈ Q × L × G × M × Q where G is the set of guards (conditions on the variables of X) and M is the set of updates of the valuations of variables; l, g and m are optional but a transition must contain at least a label or a guard;

• Qm ⊆ Q is the set of marked locations; • q0 ∈ Q is the initial location; • v0: X ← ℕ is the initial valuation of the variables. A network NA = A 1 || A 2 || … || A n of n (n ∈ ℕ *
) is defined as the synchronous product of all the A i automata. A state of the network is defined by a couple (q; v) where q ∈ Q and v ∈ X. Two kinds of evolution of the automata network NA(q, v) → (q', v0) may occur:

• only one transition is fired in one automaton, if this transition contains only local label or if its guard is satisfied;

• two transitions , of a pair of automata ( , ) with containing the emission label ∈ (noted !) and containing the emission label ∈ (noted ?) such that = are fired simultaneously, providing that the guards of these transitions are satisfied.

Note that simultaneous firing of transitions is possible only when two transitions of two different automata are considered; no broadcast mechanism that implies more than two automata is possible. Notation conventions are as follows: initial locations are indicated by a source arc, location names are in bold, label names are in italics and followed by the symbol "!" (resp. "?") for emission (resp. reception) labels, variables updates are underlined, and guards are denoted by brackets.

Task Generic Model.

The generic task model TM (Figure 1.a) defines a task t i which has to be assigned and is composed by three locations.

In the initial location, the task t i is waiting for an assignment on a workstation w k . The transition that can be fired corresponds to the emission of an assignment request on the workstation w k .

Once this request has been emitted, the model is waiting in the "waiting for a workstation answer" location for an answer from a workstation model that can be:

• a refusal: in this case, the task comes back in its initial location, ready for another possible question; • an acceptance: in this case, the template attains the last location;

The last location "task assigned" represents an assigned task which could not make another request (uniqueness of the assignment).

Workstation Generic Model.

The generic workstation model WM (Figure 1.b) is composed by two locations. It defines a workstation w k which accepts or refuses task assignments according to defined constraints (C1 and C2). In the initial location, the workstation w k is waiting for an assignment request. Once a request is received from a task model TM, the location called "Computing answer" is reached. From this location "Computing answer", there is two transitions with exclusive guards containing the two constraints depending from the current workstation capacity:

• if C1 and C2 are false, the workstation rejects the assignment by sending a refusal to the task t and returns to its initial location. • if C1 and C2 are true, the workstation accepts the assignment by sending an acceptation message. If the request is accepted, the assignment parameters are recorded as the list of already assigned with A(t i ) = w k .

Fig. 1. Generic models of tasks (a) and workstations (b)

The Assembly Line Generic Model and the Initialization of the Model. The complete model is a network of communicating automata that is composed of (Tmax -m) instances of the task model (where m represents the number of tasks that are already finished when the rebalancing is done), and Wmax instances of the workstation model. The initial capacity of workstations is set according to the already finished tasks. The correct synchronization is ensured by sending and receiving message ("Assignment Requested", "Rejected", "Accepted"). To avoid inconstancies (the sender task must be the same that the one who receive the workstation answer), the request/answer mechanism must be designed as a critical section protected by a semaphore represented by logical variable Lock involved in the guards.

Obtaining a Solution.

An acceptable solution is obtained if a trace reaches a state where all tasks are in their final location "task assigned" exists. If such a trace exists, the recorded assignment parameters constitute the searched solution. Model-checking is a formal technique that explores the state space of a DES model to identify some properties, expressed using temporal logics, is enforced (or not) in the whole or partial state space. This technique can easily be used for reachability issue with a depth-first strategy to avoid explosion. The property can be expressed using CTL expression (Computation Tree Logic) [START_REF] Clarke Andclarke | Design and synthesis of synchronization skeletons using branching time temporal logic[END_REF] as: EF("All tasks are assigned") where E is the exist path quantifier, F the eventually temporal quantifier. This property means: there exists a path where "all the tasks are assigned" will be true one day.

4

Case Study: Trane's application

Case Study Description

This approach is evaluated using an industrial case study given by Trane Company.

Trane is a firm selling cooling and heating air conditioning products and services. This firm's particularity is that the production is organized in manual assembly mixed model lines according to the DFT (Demand Flow Technology) basics. Because of the products' dimensions, a well-balanced assembly line is mandatory to avoid stocks between assembly process and its feeders. A well-balanced line must respect a production pace, the takt time.

The considered case study first three steps of a 14 operations assembly line are considered to be sure to finish a product's part before the test mandatory performed on the fourth workstation. The description and the duration of some tasks are given in Table 1 and the precedence graph is given on Figure 2. The targeted takt time is 67 minutes (4020 seconds). The initial line balancing is assumed to be known as depicted on the Figure 3 (maximum takt deviation = 228 seconds).

4.2

Results

Example 1.

For the first example, the delay is detected during the task t 3 on the first workstation (this task is longer than planned, but it can't be moved, because it is already started). The two first tasks assigned to the first workstation are already finished. As a consequence, the remaining available capacity is reduced.

With a delay of 60 seconds a new assignment is found: the task t 9 could be moved from the first to the second workstation leading to the following balancing (Figure 4) (maximum takt deviation = 280 seconds, Fig. 4). For the second example, the delay (120 seconds) is detected during the task t 15 on the second workstation. The 15 first tasks assigned to the two first workstations are already finished. According to these constraints no new better solution could be found (maximum takt deviation = 280 seconds). With a delay superior to 165 seconds, there is no acceptable solution agreeing with precedence constraints and the takt time constraint. (In this case, we must raise the takt time constraint value to obtain a solution.)

Conclusions, Future Works and Perspectives

In this article, we have shown how the reachability analysis could be used for an assembly line rebalancing. This algorithm is inserted in a predictive/reactive process in an intelligent manufacturing system context. It quickly gives an acceptable solution to adapt locally the predictive optimal balancing. But sometimes, if there is no free space left, delays could not be absorbed by a simple reassignment of tasks. That is why our future works would deal with the parallelization of tasks. Furthermore, the cost of the reconfiguration would be included in the model. In fact, sometimes moving a task is more expensive than just dealing with the delay. Of course, this new approach will be compared with other methods concerning its ease of initialization, and the execution speed.

Fig. 3 . 4 .

 34 Fig. 3. Initial Line balancing Fig. 4. First disturbance, 60s delay, corrected line balancing

Table 1 .

 1 Some Tasks desciption

	Name Description	Duration (minutes)	Duration (seconds)
	1	Prépa & pose Base	3,3	198
	2	Pose Evaporateur	6,4	384
	15	Pose compresseurs C1	22,55	1353
	16	Pose compresseurs C2	2255	1353	Fig. 2. Precedence Graph
	17	Brasage ligne Compresseur C1	16,2	972