L Rodríguez-Arco
email: l_rodriguezarco@ugr.es

† M T López-López

P Kuzhir

F González-Caballero

How nonmagnetic particles intensify rotational diffusion in magnetorheological fluids

Keywords: 66.10.C-, 47.11.-j, 83.80.Hj, 83.80.Gv

In this work we propose a mechanism to explain the enhancement of the magnetic fieldinduced yield stress when nonmagnetic particles are added to magnetic particulate suspensions -i.e., bi-component suspensions. Our main hypothesis is that the nonmagnetic particles collide with the field-induced magnetic aggregates under shear flow. Consequently, supplementary fluctuations of the orientations of the magnetic aggregates occur, resulting in an effective rotary diffusion process, which increases the dynamic yield stress of the suspension. Furthermore, the collision rate and the rotary diffusivity of the aggregates should increase with the concentration of nonmagnetic particles. Rheological measurements in plateplate and cylindrical Couette geometries confirm the increase of the yield stress with the volume fraction of nonmagnetic particles. In addition, such an effect appears to be more important in Couette geometry, for which orientation fluctuations of the magnetic aggregates play a more significant role. Finally, a theoretical model based on this rotary diffusion mechanism is developed, providing with a quantitative explanation to the experimentallyobserved trends.

I. INTRODUCTION

The fluid dynamics of particles suspended in a liquid -i.e., particulate suspensionshave been extensively studied in recent decades due to their multiple applications. Special attention has been paid to diffusion, the process which governs the motion of the suspended particles, either by controlling the particles' position (translational diffusion) or their orientation (rotational diffusion) [START_REF] Van De Ven | Colloidal hydrodynamics[END_REF]. Typical fields where diffusion plays a crucial role are self-assembly and rheology/micro-rheology of complex fluids (polymer solutions, suspensions of rod-like particles or granular gases) [START_REF] Heitjans | Diffusion in Condensed Matter. Methods, Materials, Models[END_REF][START_REF] Cheng | [END_REF][4][5][6]. A special kind of particulate suspensions for which diffusion has also been studied are field-driven colloids, suspensions of polarizable particles dispersed in a liquid carrier which undergo changes of their mechanical properties in the presence of external fields [7][8][9][10][11][12]. Examples of these smart materials are ferrofluids or electrorheological and magnetorheological (MR) fluids. In the case of MR fluids, the suspended magnetizable particles build columnar-like aggregates in the direction of the applied magnetic field. Such a jamming process induces a several orders of magnitude increase of the MR fluid viscosity in the presence of the field, a phenomenon commonly known as the MR effect [START_REF] Bossis | Magnetorheology: Fluids, Structures and Rheology[END_REF][START_REF] Park | [END_REF].

The importance of rotational diffusion on the rheological (flow) properties of MR fluids is clearly evidenced when comparing such properties in the available rheometry configurations. In the particular case of a magnetic field applied in the direction perpendicular to the walls which confine the sample -for example, in plate-plate or cone-plate geometriesthe magnetic aggregates span the gap between the geometry walls, hindering the rotation of the upper plate/cone upon the application of a given stress. Nevertheless, there is a threshold value of the stress, also known as the yield stress, for which these structures are broken, losing contact with the walls, so that a practical onset of the flow takes place. Such behavior is reminiscent of the Bingham plastic behavior, the yield stress being an increasing function of the magnetic field [START_REF] Bossis | Magnetorheology: Fluids, Structures and Rheology[END_REF]. On the other hand, when the magnetic field is oriented parallel to the geometry walls -e.g., cylindrical Couette geometry or pressure-driven flows using coaxial coils-, the aggregates are theoretically oriented along the stream-lines and have in theory an infinite length due to the absence of tensile hydrodynamic forces. Consequently, the suspension should not develop any yield stress and its rheological behavior should follow Newton's law of viscosity. However, experimental results show exactly the opposite effect: the suspension develops a strong Bingham behavior [START_REF] Shulman | Magnetorheological effect[END_REF][START_REF] Takimoto | [END_REF][17][18]. In a previous work [19] we have shown that the main contribution to the appearance of such a yield stress is precisely the rotational diffusion of the field-induced aggregates. More specifically, stochastic rotary oscillations of such aggregates increase the stress level of the suspension. These oscillations are caused by many-body magnetic interactions with neighboring aggregates [19].

However, and to the best of our knowledge, the effect of rotational diffusion on the yield stress has only been studied in the case of conventional MR fluids, that is, suspensions consisting solely of micron-sized ferromagnetic particles. However, in the last decades a number of methods to enhance the applicability of MR fluids -i.e., increasing the suspension stability and the field-induced yield stress-have been described. One effective way to improve stability is the use of nonmagnetic -i.e., diamagnetic-particles in the formulation, such as clay, polymeric or silica particles [20]. Due to their lower density they contribute to a reduction of particle settling without increasing the final weight of the fluid. In addition to a better stability, its use results in an enhanced MR effect [21][22][23][24][25]. However, the physics behind such an increase still remains unclear. For example, López-López et al. [21] attributed the increase of the MR effect when dispersing iron and clay particles together to the combination of the magnetically-induced iron chains and a clay gel. Particle-level simulations in three dimensions supported the experimental enhancement of the yield stress when mixing iron particles and hollow glass beads [22]. However simulations in a monolayer of particles did not confirm the experimental trends. The authors themselves stated that a mechanistic explanation was still lacking [22]. In a second work, new simulations suggested that the nonmagnetic particles increased the size of the field-induced clusters [23].

In a previous work we showed that the enhancement of the MR effect in bi-component suspensions could be attributed to a change in the magnetic properties of the suspension when iron particles -approx. 1 µm in size-adsorbed onto a layer around poly(methylmethacrylate), PMMA, spheres -of approx.10 µm of diameter. Indeed, simulations showed that suspensions of such nonmagnetic-core-magnetic-shell composites would develop higher magnetic permeability than those of solid magnetic particles, with the same concentration of magnetic material [25]. We have given experimental evidence of such an increase in a recent work too, in which the magnetic properties and the MR effect of nickel-coated ceramic particles and solid-nickel particles were compared [26].

In this work we deal with bi-component suspensions in which adhesion between PMMA and iron particles is avoided by the use of a surfactant, but still, a strong enhancement of the MR effect appears. Therefore, in the present case, the explanation to the improvement of the MR effect could not come from a change of the magnetic properties as in refs. [25,26],

and finding an alternative explanation is the main aim of this work. Our main hypothesis is based on collisions between the nonmagnetic particles and the field-induced aggregates of magnetic particles under shear flow. Such collisions may impart supplementary fluctuations of the positions and orientations of the magnetic aggregates. In order to prove our hypothesis, we perform rheological cylindrical Couette measurements, because the effects of orientation fluctuations are more clearly evidenced in this geometry. For comparison we also show the results of plate-plate rheological measurements. Finally we develop a theoretical explanation for the experimentally observed trends.

II. MATERIALS AND METHODS

We used spherical carbonyl iron particles (BASF, HS quality) and PMMA spheres (Microbeads, Spheromers10) as magnetic and nonmagnetic particles respectively. Particle diameters were 1.0 ± 0.7 μm and 9.9 ± 0.4 μm respectively. In order to hinder adsorption of iron particles around PMMA spheres we first dispersed appropriate amounts of iron powder in silicone oil (VWR International, Rhodorsil 47V500, dynamic viscosity at 25 °C is 480 mPa•s) followed by the addition of aluminum stearate (Sigma Aldrich, technical grade), under vigorous mechanical stirring. We continued stirring for several hours to promote stearate adsorption onto iron, and finally added PMMA powder in appropriate amounts. The volume fraction of iron, Φ m , was 10 vol % for the four prepared samples. The volume fraction of PMMA, Φ n , ranged from 0 to 30 vol %. All the samples were degasified under vacuum for 15 minutes prior to rheological measurements.

Microscopic observations upon magnetic field application of diluted samples, prepared as described above, were conducted by placing an optical microscope between two Helmholtz coils that applied a homogeneous magnetic field parallel to the surfaces that confined the sample. Magnetization curves of the suspensions were obtained at 20 ºC by means of a vibrating sample magnetometer VSM 4500 (EG&G Princeton Applied Research, USA).

The rheological measurements were conducted by using a controlled-stress rotational rheometer, Haake RheoStress RS 150 (Thermo Fisher Scientific, USA). We performed measurements using cylindrical Couette and plate-plate geometries. Couette cell consisted of an inner cylinder of diameter of 20 mm and height of 30 mm. The radial distance between the surfaces of the outer and inner cylinders was 0.75 mm. We applied a uniform magnetic field with the help of a coil placed coaxially with the rheometer axis and thus, in the direction parallel to the suspension vorticity. The measuring protocol for Couette measurements was as follows: (i) Pre-shear stage at a shear rate of 150 s -1 for 60 s in the absence of field. (ii) Application of the same shear rate for 60 s upon a magnetic field of approx. 6 kA/m. (iii) Sample at rest for 3 min and magnetic field application of a desired intensity (from 6 to 30.6 kA/m). (iv) Shear rate ramp (equivalent rheological results were obtained by ramping the shear stress) from 1 to 500 s -1 upon the same field as in (iii) with duration of each step of 30 s.

At the end of stage (iv), the magnetic field was again readjusted to 6 kA/m, and stage (ii) was repeated before a new shear rate ramp at a different -increasing-magnetic field was started.

Note that a magnetic field of, at least, 6 kA/m was maintained during the whole process to reduce particle settling.

Plate-plate measurements were performed with a set of parallel plates (diameter of 35 mm). The gap between the two plates was 350 µm. All the quantities reported hereinafter correspond to the outer radial edge of the plate. In this second case, the magnetic field was applied with the same coil as for cylindrical Couette geometry. As a result, in this geometry the magnetic field was aligned along the velocity gradient and perpendicular to the rheometer walls. The measuring protocol consisted of three stages: (i) Pre-shear at a shear rate of 150 s -1 for 60 s. (ii) Sample at rest for 120 s. (iii) Shear rate ramp from 20 to 300 s -1 . Each step lasted 30 s. The magnetic field was activated at the beginning of (ii) and was kept switched on until the end of (iii).

III. EXPERIMENTAL RESULTS

First of all, and to discard the formation of nonmagnetic-core-magnetic-shell composites of enhanced magnetic permeability -i.e., like those of ref. [25] -we performed microscopic observations and magnetization measurements. The microscopy results obtained for diluted suspensions showed that there was not adsorption of iron particles onto PMMA ones. As a matter of fact, PMMA particles appeared uncovered and most of them were separated from the field-induced iron aggregates upon the application of an external magnetic field -Fig. 1. The thickness of these chain-like aggregates was of the same order of magnitude as the diameter of PMMA particles. In addition, nonmagnetic particles were generally not trapped into the aggregates of magnetic particles in contrast to the results shown in the inset of Fig. 1 for which aluminum stearate was not used and consequently, a strong cohesion between iron and PMMA particles existed, resulting in an increase of the MR effect with a growing content of PMMA [25]. Regarding the magnetization curves, we observed that the hysteresis loops for the different samples were practically superimposed, as seen in Fig. 2, and therefore, the addition of PMMA particles did not affect the suspension magnetic permeability. Actually, calculations of such magnetic permeability by using the ascent branch of the hysteresis loops (inset of Fig. 2) revealed differences in the magnetic permeability no bigger than approx. 5% for the different samples. Therefore, changes of the MR effect for these bi-component suspensions could not be attributed to an enhancement of the magnetic permeability because of the formation of a magnetic coating around PMMA particles.

FIG. 1.

Microscopic picture of a suspension of 1 vol % iron and 3 vol % PMMA dispersed in silicone oil and stabilized by the addition of aluminum stearate. A magnetic field of approx. 10 kA/m was applied in the direction indicated by the arrow; the bar length corresponds to 50 µm. PMMA particles (white spheres of 10 µm) appeared uncoated and separated from the iron chains. This situation was different to that observed in the inset for a suspension in which aluminum stearate had not been added to the suspension and in which adsorption of iron particles around PMMA particles took place with the formation of nonmagnetic-coremagnetic-shell composites. The picture from the inset is taken from ref. [25] and the bar length is 10 µm.

FIG. 2.

Hysteresis loops for all the suspensions. The concentration of iron particles was 10 vol % while the volume fraction of PMMA particles ranged from 0 to 30 vol %. All the curves were superimposed and therefore, there were no remarkable differences in the suspension magnetic permeability of the samples, calculated from the ascent branch of the inset.

However, and despite having removed the influence of an enhanced suspension permeability, we observed a strong enhancement of the MR effect, which seemed to be especially important in cylindrical Couette geometry. More specifically, the shear stress in the flow curves -shear stress σ vs. shear rate γ& -at given values of the external magnetic field and γ& , was higher when nonmagnetic particles were included in the formulation for both cylindrical Couette and plate-plate geometries. In addition, σ increased with the volume fraction of PMMA particles Φ n for a certain value of γ& -Fig. 3. Note that the values of the shear stress for a particular suspension were higher when using cylindrical Couette geometry in comparison with the plate-plate geometry -Fig. 3. In order to better compare both geometries and analyze the influence of the addition of PMMA on the MR effect, we estimated the yield stress. Recall that the MR effect is defined as the change of the rheological behavior from an almost Newtonian behavior in the absence of field -characterized by the equation

γ η σ & =
where η is the viscosity-to a plastic behavior when the magnetic field is activated. A plastic fluid usually follows Bingham's equation

γ η σ σ & + = Y
where Y σ is the dynamic yield stress [27]. We estimated the yield stress by performing a linear fit of the high-shear part of the rheograms ( 100

γ > & s -1
), the yield stress being the intercept of the fit with the Y-axis, i.e., zero shear rate. The fits (not shown here for brevity) were reasonably good in all cases (R 2 ≈ 0.99). With the aim of just comparing the influence of the magnetic field between both geometries, we calculated the increment of the yield stress by subtracting the yield stress at zero field to the yield stress at a given applied field, and plotted it against the external magnetic field strength, H 0 -Fig. 4. The so-estimated increment of the yield stress increased both with H 0 and Φ n for plate-plate and cylindrical Couette geometries. In cylindrical Couette geometry, however, both effects appeared more intensified. Actually, the yield stress increment exhibited a stronger increase with the PMMA concentration in cylindrical Couette geometry -3.7 times in the range 0<Φ n <0.3-as compared to the plate-plate geometry -1.9 times in the same range. To be precise, the differences between the increments of the yield stress for both geometries became more accentuated when the PMMA volume fraction increased. Indeed, the Couette yield stress increment of the sample without PMMA was almost superimposed to the equivalent plate-plate one, whereas the yield stress increment of the sample with 30 vol % PMMA was much higher for cylindrical Couette geometry -Fig. 5. However, we must keep in mind that because of the differences in geometry, the demagnetizing field opposed by the sample was different for the cylindrical Couette and the plate-plate systems. In the Couette geometry the height-to-gap ratio was very large and, as a result, the demagnetizing field along the rheometer axis was negligible. Consequently the field inside the sample, the so-called internal field, H, was almost equal to the external one H≈H 0. On the other hand, in plate-plate rheometry, the ratio of the gap height to the plate diameter was small and the resulting demagnetizing field was higher. Estimations of the internal magnetic field using Eq. (A1)

show that for the sample without PMMA, the MR effect in plate-plate geometry was considerably higher than in the case of cylindrical Couette. However, the differences between both geometries diminished as the PMMA concentration increases because of the further enhancement of the MR effect in bi-component suspensions for cylindrical Couette geometry

IV. THEORY AND DISCUSSION

A. Qualitative interpretation

The analysis of the obtained experimental results allows us to formulate the two main questions of the present work, namely: (a) What is the possible mechanism behind the enhancement of the MR effect by the addition of nonmagnetic particles to a suspension of magnetic particles? (b) Why is this enhancement appreciably higher when the magnetic field is oriented along the vorticity (cylindrical Couette) rather than along the velocity gradient (plate-plate)? In this section, we shall first give a qualitative answer to both questions, followed by the development of a theoretical model to provide a more quantitative interpretation.

Regarding question (a) we must keep in mind that whatever the composition of the suspension-i .e. with or without nonmagnetic particles-the dynamic yield stress arises from hydrodynamic dissipation on the field-induced particle aggregates upon shear [START_REF] Bossis | Magnetorheology: Fluids, Structures and Rheology[END_REF][START_REF] Shulman | Magnetorheological effect[END_REF]. In addition to it, magnetic interactions between aggregates may induce stochastic fluctuations of their orientation and result in a supplementary contribution to the yield stress, coming from stochastic interaction torques. These fluctuations may be regarded as an effective rotary diffusion process, which is likely responsible for the unexpectedly high yield stress when the magnetic field is parallel to either the suspension velocity or the vorticity [19,[START_REF] Kuzhir | [END_REF].

Our main hypothesis is that under shear flow, the nonmagnetic particles may collide

B. Stochastic interactions and rotational diffusion

In order to give a quantitative answer to the above stated-questions we shall provide here an expression for the yield stress in bi-component suspensions which takes into account the influence of collisions among the nonmagnetic particles and the magnetic aggregates that result in an additional rotary diffusion process. For this purpose we consider a bi-component suspension subjected to a simple shear flow between two infinite plates in the presence of an external magnetic field, H 0 , oriented either perpendicularly to the plates -configuration similar to the plate-plate geometry-or parallel to the plates along the vorticity -similarly to cylindrical Couette geometry. Both possibilities are shown in the sketches of Figs. 6(a) and 6(b). The relationship between H 0 , and the internal magnetic field H, is described in the Appendix. The applied magnetic field provokes the appearance of aggregates of magnetic particles, which are surrounded by a suspension of nonmagnetic particles in the liquid carrier.

The axes of the Cartesian reference frame, "1", "2" and "3", are oriented along the fluid velocity, the velocity gradient and the vorticity respectively. The aggregate orientation is described by a unit vector e, oriented along the aggregate major axis. The orientation distribution is described by second-and fourth-order tensors, As mentioned above, misalignments of a given aggregate from its equilibrium orientation are induced by magnetic forces exerted by the neighboring aggregates. Since the aggregates are irregularly spaced and polydisperse in size, the forces and torques (interaction torques) that they exert on their neighbors vary in a stochastic manner when they displace relative to each other in a shear flow. This mechanism leads to random oscillations of their orientation and can be described as a rotational diffusion process with a diffusion constant, D m , defined by a random walk model as follows [START_REF] Van De Ven | Colloidal hydrodynamics[END_REF]: The neighboring aggregates moving around a given aggregate induce some stochastic variation of the magnetic field at the location of a given aggregate because of irregular spacing between their magnetic poles under shear flow. The stochastic field randomly fluctuates during time, such that st = H 0, while its quadratic mean value is supposed to vary as the square of the suspension magnetization: with μ 0 =4π•10 -7 H/m being the magnetic permeability of vacuum; χ a is the aggregate magnetic susceptibility, V a =2πA 2 L is the aggregate volume, Φ and Φ a are the volume fraction of particles in the suspension and the internal volume fraction of aggregates, supposed to be equal to π/6 for a simple cubic structure; the ratio (Φ/Φ a ) stands for the concentration of aggregates in the suspension. Performing the necessary substitutions we arrive to the following expression for the rotary diffusivity: = is the form-factor describing the hydrodynamic resistance of the aggregates and coming from the slender body theory [30]; / e r L A = is the aggregate aspect ratio. Because we are able to estimate only the order of magnitude of the stochastic field and of the interaction torque, we need to introduce a dimensionless correction factor α 1 into Eq.

2 2 2 int m r T D t f ω γ ∝ Δ ∝ & (1)
2 2 2 0 1 0 1 a m a H D μ χ α η β γ ⎛ ⎞ Φ = ⎜ ⎟ Φ ⎝ ⎠ & (2)
(2) which describes the intensity of the stochastic magnetic interactions between aggregates and which will be taken as an adjustable parameter.

Note that the aggregates can be destroyed by tensile hydrodynamic forces once they are misaligned from the flow or the vorticity direction. More specifically, the aggregate size, and consequently its form-factor β, is defined by a compromise between the destructive hydrodynamic and magnetic cohesive forces [31,32]. By applying the force balance (whose general expression is given in [19]) to both studied configurations (Figs. 6a and6b), we arrive to the following expression for the form factor:

2 0 4 2 3ln e a m r f β ξ η γψ Φ ≡ = & (3)
where ψ is a numerical factor depending on the orientation state of the suspension and equal to ( ) ( )

2 2 3 3 1 / 2 e e -
for the field parallel to the vorticity (cylindrical Couette geometry, Fig. 6a) and / e e e for the field parallel to the velocity gradient (plate-plate geometry, Fig. 6b); f m is the magnetic force between neighboring particles constituting the aggregates, per unit cross-sectional area of the particle. The magnetic force f m and the aggregate magnetic susceptibility χ a , intervening into Eqs. ( 2) and ( 3) are functions of the magnetic field, their field dependences being given in the Appendix.

The above considered random fluctuations of the aggregate orientation are attributed to long-range magnetic interactions between aggregates. As already stated, such a fieldinduced diffusion may be substantially enhanced by the collisions of the magnetic aggregates with the nonmagnetic particles. The diffusivity of this second collision-induced diffusion mechanism, D c , is supposed to be linear with both the concentration of nonmagnetic particles,

Φ n , and with the collision rate, and thus, with the shear rate γ& . The approximation γ

∝ & c D
was introduced by Folgar and Tucker [33], and has been successfully employed up to now for the description of the orientation state of nonBrownian fibers undergoing shear-induced collisions. Both diffusion mechanisms are supposed to be additive, so that the effective diffusion constant would be the sum of two respective diffusivities:

2 2 2 0 1 2 2 2 m a r m c n a m H D D D f μ χ α ψ γ α γ ⎛ ⎞ Φ = + = + Φ ⎜ ⎟ Φ ⎝ ⎠ & & (4)
The first term of Eq. ( 1) is obtained by replacing the form-factor β in Eq. ( 2) by the expression (3). As in the case of magnetically induced diffusion, we are unable to provide an exact relationship for the collision-induced diffusivity D c . This quantity is therefore defined up to a dimensionless phenomenological constant α 2 , which describes the intensity of collision-induced angular fluctuations and depends on microscopic details of the process discarded in the present model. This constant is taken as the second adjustable parameter of the model.

C. Orientation distribution

The orientation state of the aggregates is described by the equation of evolution of the second statistical moments, i k e e , which is conventionally derived by multiplying the Fokker-Planck equation for the orientation distribution function by i k e e , and averaging over all possible orientations. In the case of long aggregates possessing an induced magnetic moment, this equation reads [19,[START_REF] Kuzhir | [END_REF][START_REF] Pokrovskiy | Statistical mechanics of diluted suspensions[END_REF]:

2 2 0 0 2 (1 / ) 2 2 3 2 (1 / ) i k il l k i l lk il l k i l lk i k l m lm a a i l l k k l l i i k l m l m r ik i k a a d

e e e e e e e e e e e e e e dt H h h e e h h e e e e e e h h D e e

ω ω γ γ γ

μ χ δ η β χ ⎡ ⎤ ⎡ ⎤ = - + + - ⎣ ⎦ ⎣ ⎦ -Φ Φ ⎡ ⎤ ⎡ ⎤ + + - + - ⎣ ⎦ ⎣ ⎦ + -Φ Φ ( 5
)
where t is the time;

(1/ 2) ( / / )

ik i k k i v x v x γ = ⋅ ∂ ∂ +∂ ∂ and (1/ 2) ( / / ) ik i k k i v x v x ω = ⋅ ∂ ∂ -∂ ∂ are
the rate-of-strain and vorticity tensors, respectively; h i is the i-th component of the unit vector h oriented along the internal magnetic field H; ik δ is the Kronecker delta. In our case, we have only two nonzero components of the rate-of-strain and vorticity tensors, The last reduces to the following system of algebraic equations for the steady state upon application of the quadratic closure approximation [START_REF] Doi | The Theory of Polymer Dynamics[END_REF]

, i k l m i k l m
e e e e e e e e ≡ , and using expressions ( 3) and ( 4) for the form-factor β and the rotary diffusivity respectively: (

ψ ψ ψ α ψ ψ ψ α ψ ψ ψ α ψ ψ ψ α ⎧ - - + + Φ - = ⎪ ⎪ - - + + Φ - = ⎪ ⎨ - - + + Φ - = ⎪ ⎪ ⎪ - - - + Φ = ⎩ (6) where 2 2 2 2 1 1 0 /(2 ) m a a m C H f α μ χ ⎡ ⎤ = Φ Φ ⎣ ⎦ and 2 2 2 0 (1 / ) /[2 (2 (1 / ))] a m a a m a m a C H f μ χ χ = -Φ Φ Φ + -Φ Φ
e e e ψ ψ ψ ψ

⎡ ⎤ = - ⎣
⎦ for the field oriented along the vorticity (Fig. 6(a)).

It is important to remark that, due to the fact that the rotary diffusivity D r is linear in the shear rate (Eq. ( 4)) and the form-factor β is inversely proportional to the shear rate (Eq.

(

)), the shear rate vanishes from equations ( 6) describing the statistical moments at the steady-state condition; the orientation distribution is therefore independent of shear rate, at least in the limit of long aggregates, 1 e r  considered here. This result agrees with the classical models of magnetorheology, discarding any dispersion in aggregate orientation and predicting an angle between the aggregates and the flow independent of shear rate [START_REF] Shulman | Magnetorheological effect[END_REF]32].

The system of Eq. ( 6) is solved numerically with respect to the four unknown second statistical moments, 2 In Fig. 7, we inspect the behavior of the second statistical moments as a function of the volume fraction Φ n of nonmagnetic particles at a fixed content of magnetic ones, Φ m =0.1 and for an intensity of the applied external magnetic field, H 0 =18.3 kA/m. At the considered set of free parameters (chosen to provide the best fit to the experimental yield stress, cf. Figs. 4 and8), the orientation state seems to be moderately influenced by collisions with nonmagnetic particles but slowly evolves to an isotropic state with an increase of the concentration Φ n . All the statistical moments, exhibit a somewhat stronger variation for the magnetic field oriented along the vorticity (in cylindrical Couette geometry) (Fig. 7(a)), as compared to the case of the field oriented along the velocity gradient (plate-plate geometry) (Fig. 7(b)). This should contribute to a more pronounced effect of the nonmagnetic particle content, Φ n , on the stress level in Couette geometry.

D. Suspension stress

The stress tensor developed in the nonBrownian bi-component magnetic suspension can be estimated assuming that the long aggregates of magnetic particles are immersed in an effective medium composed of a homogeneous suspension of nonmagnetic (PMMA) particles dispersed in a suspending liquid of viscosity η 0 . The effective viscosity of such a medium can be estimated using the Krieger-Dougherty equation for concentrated hard sphere suspensions [START_REF] Larson | The Structure and Rheology of Complex Fluids[END_REF]:

2.5 0 (1 / ) max e n m a x η η -Φ = -Φ Φ , with 0.64 max Φ ≈
being the random close packing fraction of the hard spheres. Under such condition, we may use the well-known expression for the stress tensor in the semi-dilute suspensions of axisymmetric particles [START_REF] Brenner | [END_REF], which, being applied to the case of long aggregates with induced magnetic moments, reads [20,30]:

μ β η δ χ Φ ⎧ ⎫ ⎡ ⎤ = - + + + - + ⎨ ⎬ ⎢ ⎥ Φ ⎣ ⎦ ⎩ ⎭ Φ -Φ Φ Φ ⎡ ⎤ ⎡ ⎤ + - + - ⎣ ⎦ ⎣ ⎦ Φ + -Φ Φ Φ (7)
where p is the pressure in the suspension and the solvent viscosity η 0 appearing in the original expression for the stress tensor has been replaced by the effective medium viscosity η e .

Replacing the diffusion constant and the form-factor β by appropriate expressions (Eqs. [START_REF] Cheng | [END_REF] and ( 4)), the shear rate vanishes from the last three terms of Eq. ( 7) and we recover the Bingham rheological law for the shear stress (σ 12 component of the stress tensor): ∝ & (cf. Eq. ( 4)). Note that deriving Eq. ( 8), we did not take into account eventual colloidal interactions in the suspension, which result in an off-state yield stress of the real suspension. Accordingly, the yield stress presented in Eq. ( 8) should be considered as the increment of the yield stress. Finally, to explain the appearance of the yield stress in both considered geometries, we must recall that the aggregate aspect ratio is a decreasing function of the shear rate, , appear to be independent of the shear rate, at least in the limit of long aggregates, 1 e r  , not spanning the rheometer gap [START_REF] Shulman | Magnetorheological effect[END_REF]32]. Because of such independence, the aggregate stress is considered to be the dynamic yield stress (Eq. ( 8)) of the suspension.

E. Comparison with experiments

Both the theoretical and experimental increments of the yield stress show a monotonic growth with the field. Such effect can be attributed to increasing magnetic interactions between the magnetic particles inside the aggregates -Fig. 4. Curiously, the field dependency becomes sub-linear at magnetic fields H 0 >20 kA/m in the case of the cylindrical Couette geometry (Fig. 4(a)). Such a behavior can be explained by a similar sub-linear field dependency of the magnetic force f m , as inferred from finite element method simulations. This effect is not observed in the plate-plate geometry at the same range of magnetic fields (Fig.

4(b))

. This is likely because the magnetic component of the yield stress (second term in Eq. ( 8), proportional to H 2 ) is more important in this particular geometry than in cylindrical Couette geometry, and masks the sub-linear trend of f m .

As expected, the theory predicts an increase of the yield stress increment with the content of nonmagnetic particles for both geometries. The two free parameters α 1 and α 2 , characterizing the intensity of the field-induced and collision-induced angular fluctuations of the aggregate orientation, are used to fit the theory to the experimental curves. The first parameter, α 1 , is fitted to the experimental curve corresponding to Φ n =0. The second parameter, α 2 , is fitted to the experimental curves at Φ n >0 keeping the parameter α 1 fixed. The best fit corresponds to the following values of the free parameters: α 1 =1.5; α 2 =0.2 for the plate-plate geometry and α 1 =0.2; α 2 =0.4 for the cylindrical Couette geometry. Therefore we can see that the collision contribution to the rotary diffusivity, α 2 , is more important in Couette geometry, which explains the stronger effect of the PMMA addition in this case.

The effect of adding nonmagnetic particles on the suspension rheology can be better analyzed in Fig. 8 where the dependencies of the yield stress increment on the concentration of nonmagnetic particles are plotted. As already noticed, the yield stress increment exhibits a stronger increase with the concentration of PMMA in the cylindrical Couette geometry. An alternative measure of the effect of the nonmagnetic particles on the yield stress is the magnitude, [ ] Finally note that, despite its simplicity, the present model captures the enhancement of the MR effect in bi-component suspensions without specific interactions between both species. Because of the opacity of the suspensions, it seems to be quite difficult to verify the hypothesis of the collision-induced fluctuations using classical optical microscopy. Direct numerical simulations might also elucidate the role of the nonmagnetic particles on the structure of the flowing suspension and give more precise expressions for the rotary diffusivities as a function of the concentration and the size ratio of both species of particles.

( ) (
Nevertheless, and in contrast to our experiments, the existing numerical results of refs. [22,23] have revealed only a moderate (a few dozens of percents) enhancement of the MR effect by the addition of nonmagnetic particles. This is probably because a low-shear regime was considered in simulations. In this regime, the moving aggregates span the channel width, which likely hinders their orientation fluctuations. In our study, we have dealt with higher shear rates, where the aggregates are not-gap spanning and have more freedom for interactions with their neighbors as well as with nonmagnetic particles.

V. CONCLUSIONS

In this work we have shown that bi-component suspensions consisting of magneticiron-and nonmagnetic -poly(methylmethacrylate), PMMA-particles displayed an enhancement of the magnetorheological (MR) effect with respect to a suspension of just iron particles with the same volume fraction of magnetic material, both in cylindrical Couette and plate-plate geometries. Such an enhancement took place even when presumably there was no adhesion of iron particles onto PMMA ones, because the former particles were covered with a surfactant layer. Magnetization measurements showed that the magnetic permeability was not affected by the addition of PMMA which is also attributable to the absence of adsorption between both types of particles. We conclude therefore that the MR effect enhancement does not come from an increase of the magnetic interactions, something which would take place if the iron particles formed a shell structure around the nonmagnetic PMMA particles [25].

We have explained the observed phenomenon under the hypothesis of collisions among the nonmagnetic particles and the field-induced aggregates of magnetic particles. Such collisions are supposed to give rise to an enhancement of the fluctuations of the aggregate orientation that increases with the volume fraction of nonmagnetic particles. This process contributes to augment the total level of stress in the suspension and therefore, the MR effect.

We have shown that in cylindrical Couette geometry, this mechanism is predominant in comparison to the case of plate-plate geometry, in which it plays a minor role. As a result, the improvement of the MR effect in bi-component suspensions is more noticeable for cylindrical Couette geometry, in agreement with experiments.

APPENDIX. RELATIONSHIP BETWEEN THE INTERNAL, H, AND THE EXTERNAL, H 0 , MAGNETIC FIELDS

In the case of the magnetic field oriented along the vorticity (cylindrical Couette geometry, Fig. 6(a)), the internal field is equal to the external applied magnetic field H 0 . In the case of the magnetic field perpendicular to the walls (plate-plate geometry, Fig. The aggregate magnetic susceptibility χ a and the magnetic force f m (intervening into Eqs. (3), ( 4) and ( 8)) are calculated as a function of the magnetic field H using finite element simulations [18,[START_REF] Kuzhir | [END_REF] The simulation results for f m and χ a , have been fitted by the following expressions, valid in the range of the magnetic field intensities, 0

FIG. 3 .

 3 FIG. 3. Flow curves of the bi-component suspensions in cylindrical Couette (a) and plate-plate (b) geometries at the same concentration of iron particles, Φ m =0.1 and different concentrations of PMMA particles Φ n . The intensity of the external magnetic field was H 0 = 12.2 kA/m for both geometries. As observed, the shear stress increased when Φ n was increased. Note that the shear stress was generally higher for cylindrical Couette geometry.

FIG. 4 .

 4 FIG.4. Experimental (symbols) and theoretical (lines) dependencies of the yield stress increment on the intensity of the external magnetic field for the cylindrical Couette (a) and the plate-plate (b) geometries at the same concentration of iron particles, Φ m =0.1 and different concentrations of PMMA particles, Φ n . The yield stress increased with both the magnetic field strength and the volume fraction of PMMA. Both effects appeared to be more pronounced in Couette rheometry. The theoretical predictions (see section IV) are obtained for values of the free parameters of α 1 =1.5; α 2 =0.2 for the plate-plate geometry, and α 1 =0.2; α 2 =0.4 for the cylindrical Couette geometry. The collision contribution to the rotary diffusivity α 2 is thus more important in the second case.

FIG. 5 .

 5 FIG.5. Comparison of the magnetorheological effect observed in plate-plate and cylindrical Couette geometries at the same concentration of iron particles, Φ m =0.1 and four different concentrations of PMMA particles, namely Φ n =0 (a), Φ n =0.1 (b), Φ n =0.2 (c) and Φ n =0.3 (d). The differences between the curves of both geometries increased with Φ n .

  FIG. 6 (color online). Sketch of the problem geometry. The external magnetic field provokes the appearance of aggregates of magnetic particles which are surrounded by a suspension of nonmagnetic particles in the liquid carrier. The magnetic field H is oriented either parallel to the plates along the vorticity -i.e., cylindrical Couette geometry (a) or perpendicularly to the plates -i.e., plate-plate geometry (b).

  tensors are constructed by the basic projections of the vector e, and are called the statistical moments of the orientation distribution function, or, briefly, statistical moments.

  friction coefficient of an aggregate of length 2L and radius A; η 0 is the suspending liquid viscosity and ξ is the dimensionless hydrodynamic screening length.

1 h

 1 and the one nonzero component of the field unit vector: either 3 = for the field oriented along the vorticity (Fig. 6(a)) or 2 1 h = for the field oriented along the velocity gradient (Fig. 6(b)).

  field oriented along the velocity gradient (Fig.6(b)) and [ ]

FIG. 7 .

 7 FIG. 7. (Color online) Theoretical dependencies of the second statistical moments on the volume fraction of nonmagnetic particles for the cylindrical Couette (a) and the plate-plate (b) geometries. For both geometries, the intensity of the external magnetic field is H 0 =18.3 kA/m and the concentration of the magnetic particles is Φ m =0.1. The free parameters are chosen to provide the best fit with experimental data on the suspension yield stress (see Figs. 4 and 8) and are equal to α 1 =1.5; α 2 =0.2 for the plate-plate geometry and α 1 =0.2; α 2 =0.4 for the cylindrical Couette geometry.

, ψ and 11 ψ

 11 . The dynamic yield stress is thus given by the following expression, valid for both considered geometries: , characterizing the aggregate orientation state are found from solution of Eqs.(6). The first term on the right-hand side of Eq. (8) is the hydrodynamic part of the aggregate stress. The second term corresponds to the external torque exerted on the aggregates by the magnetic field H. The third term is the diffusion stress coming from the stochastic magnetic torques exerted on the aggregates by neighboring aggregates. Finally the fourth term stands for the diffusion stress coming from the collisions between aggregates and nonmagnetic particles. This last component marks the contribution of the nonmagnetic particles to the suspension yield stress and depends on the applied magnetic field, being proportional to the magnetic force between particles f m . This is not surprising because the aggregate aspect ratio is an increasing function of the applied field,2 / induce a stronger viscous dissipation when subjected to random collisions. As a result, the collision-induced stress scales as

  and the rotary diffusivity is proportional to the shear rate,

FIG. 8 .

 8 Fig.8). (b) They cause a supplementary viscous dissipation by enhancing random fluctuations of aggregate orientation -i.e., last term of Eq. (8). Analyses show that the second mechanism appears to be dominant in the yield stress enhancement at the considered experimental conditions.

  6(b)), the internal field is related to the external field H 0 through the following expression: where μ 22 is the diagonal component (along the field axis "2") of the magnetic permeability are the components of the magnetic permeability of the suspension whose aggregates are, respectively, aligned or perpendicular to the applied field.

  are dimensionless factors; the coefficients ψ ik are functions of the second statistical moments and are equal to

	[	11	22	33	12	]	2	2	2	2	2	2

ACKNOWLEDGEMENTS

We would like to acknowledge Dr. G. Bossis for helpful discussions. This work has been supported by projects FIS2013-41821-R (Ministerio de Economía y Competitividad) and "Factories of the Future" (Grant No. 260073, DynExpert FP7). In addition, L. Rodríguez-Arco acknowledges financial support by Secretaría de Estado de Educación, Formación Profesional y Universidades (MECD, Spain) through its FPU and Estancias Breves programs.


Antoine Bertout
email: antoine.bertout@lifl.fr

Julien Forget
email: julien.forget@lifl.fr

Richard Olejnik
email: richard.olejnik@lifl.fr

Minimizing a real-time task set through Task Clustering

In the industry, real-time systems are specified as a set of hundreds of functionalities with timing constraints. Implementing those functionalities as threads in a one-toone relation is not realistic due to the overhead caused by the large number of threads. In this paper, we present task clustering, which aims at minimizing the number of threads while preserving the schedulability. We prove that our clustering problem is NP-Hard and describe a heuristic to tackle it. Our approach has been applied to fixed-task or fixed-job priority based scheduling policies as Deadline Monotonic (DM) or Earliest Deadline First (EDF).

Introduction

In this paper, we focus on real-time systems programming. Designs of such systems often consist of several hundreds of high-level functionalities (or computational nodes) with timing constraints. For example, the number of nodes ranges from 500 to 1000 in the flight control system of an aircraft or of a space vehicle [START_REF] Boniol | A framework for distributing real-time functions[END_REF][START_REF] Forget | A Synchronous Language for Critical Embedded Systems with Multiple Real-Time Constraints[END_REF]. When implementing such systems, real-time programmers can not directly implement each of the nodes as a thread (or task) because real-time operating system usually do not support such a high number of threads. This limitation stems from the fact that having a huge number of tasks in a system induces important overheads, such as time overhead due to context switches [START_REF] Scheickl | Automotive real time development using a timing-augmented AUTOSAR specification[END_REF][START_REF] Lee | The problem with threads[END_REF] and a bigger memory footprint (e.g. task control block, size of the stack, etc.) Thus, to cope with this limitation, real-time developers have to group several nodes together into the same thread. This work is generally performed manually and may be tedious and error prone regarding the number of nodes involved. We are concerned here with the automation of this process.

In our work, we address this question from the scheduling point of view. We model a system as a set of tasks with real-time constraints, where each task is characterized by an execution time, an activation period and a deadline, in the same way as Liu and Layland's task model [START_REF] Liu | Scheduling algorithms for multiprogramming in a hard-real-time environment[END_REF]. With respect to this model, nodes can simply be considered as finer grain tasks, while threads (which may consist of several nodes) are just coarser tasks. Thus, mapping nodes to tasks amounts to gathering several tasks into a single one, which we call task clustering. Clustering several tasks implies to choose only one deadline for the cluster, which may reduce some task deadlines. As a consequence, we have to check that the system schedulability is preserved after the clustering.

Related Works In the literature, task clustering is most often studied in the context of distributed systems implementation, where it consists in distributing a set of tasks over a set of computing nodes (processors or cores). This is different from our context, because in the distributed systems context a cluster corresponds to the set of tasks allocated to the same computing resource. For instance, works [START_REF] Ramamritham | Allocation and scheduling of precedence-related periodic tasks[END_REF][START_REF] Ahmadinia | Temporal task clustering for online placement on reconfigurable hardware[END_REF] aim at minimizing communications by clustering tasks that communicate a lot. The approaches in [START_REF] Palis | Task clustering and scheduling for distributed memory parallel architectures. Parallel and Distributed Systems[END_REF][START_REF] Guodong | Task clustering and scheduling to multiprocessors with duplication[END_REF] cluster tasks based on communications, in order to reduce the system makespan. The number of tasks of the resulting implementation is however not reduced.

Task clustering is known as runnable-to-task mapping and is identified as a step of the development process in the augmented real-time specification for AUTomotive Open System ARchitecture (AUTOSAR) [START_REF]RTE Standard Specifications[END_REF]. This document and [START_REF] Scheickl | Automotive real time development using a timing-augmented AUTOSAR specification[END_REF] also provide guidelines defining under which conditions runnables can be grouped to the same tasks. In that context, authors of [START_REF] Monot | Multisource software on multicore automotive ecuscombining runnable sequencing with task scheduling[END_REF] proposed two heuristics for multicores architecture. The first one allocates runnables to cores considering dependencies, locality constraint and core load. The second one constructs the sequencing of the runnables through one dispatcher (or sequencer) task per core. They consider implicit deadlines and fixed task-priority scheduling. In the same context, authors of [START_REF] Wozniak | An optimization approach for the synthesis of autosar architectures[END_REF] formulate the task clustering problem as an optimization problem. Authors present a first technique based on mixed integer linear programming (MILP) and a second one based on the genetic algorithms (GA) to optimize end-to-end responses and memory consumption. Runnable-to-task mapping is a step of the work of [START_REF] Zhang | Optimization issues in mapping AUTOSAR components to distributed multithreaded implementations[END_REF], but it is restricted to functionalities that have deadlines equal to their periods.

In a model-driven development context, authors of [START_REF] Mzid | Dpmp: a software pattern for real-time tasks merge[END_REF] aims at reducing the number of priority levels by gouping tasks. They propose a technique based on MILP to reach a specific number of priority levels that the target RTOS can handle. In [START_REF] Curic | Implementing Lustre Programs on Distributed Platforms with Real-time Constrains[END_REF][START_REF] Pagetti | Multi-task implementation of multiperiodic synchronous programs[END_REF], the authors study the multi-task implementation of multi-periodic synchronous programs and must allocate the different elements of the program to tasks. The clustering is out of the scope of [START_REF] Pagetti | Multi-task implementation of multiperiodic synchronous programs[END_REF], while the heuristic proposed in [START_REF] Curic | Implementing Lustre Programs on Distributed Platforms with Real-time Constrains[END_REF] is very specific to the language structure. The necessity of the task clustering is also emphasized by Zheng and Di Natale in [START_REF] Zeng | Schedulability analysis of periodic tasks implementing synchronous finite state machines[END_REF]. They claim that mapping each functional node of their system design to a task is not realistic regarding the context switch over-heads. Santinelli et al. [START_REF] Santinelli | A grouping approach to task scheduling with functional and non-functional requirements[END_REF] propose to reduce the number of real-time tasks in a uniprocessor system. They consider tasks with precedence constraints and their main objective is to cope with the high complexity of the schedulability analysis with a large set of tasks. They mostly consider functional requirements and temporal constraints are limited to monoperiodic task sets. Their model is based on latency constraints while we work with multi-periodic system on a deadline-based model.

This research

In this paper, we propose a technique to minimize the number of tasks in a real-time system while preserving timing constraints and schedulability. This work aims at exploring the task clustering in simple settings so as to better comprehend the problematic before tackling task clustering with precedences constraints. Unlike existing works, we consider both fixed task-priority and fixed job-priority scheduling policies. We also propose conditions under which tasks can be grouped without affecting the schedulability. This research follows the work we made in [START_REF] Bertout | A heuristic to minimize the cardinality of a real-time task set by automated task clustering[END_REF] where we laid the basis for the task clustering and proposed a first heuristic. In this paper, we mainly develop four improvements. First, we emphasize the necessity of the task clustering by examining the impact of having a huge number of threads. To this intent, we achieved experiments on the effect of the clustering on context switches and preemptions. Second, we prove the NP-Hardness of the task clustering. Third, we propose conditions under which clustering does not require further schedulability test. Finally, we prove the sustainable unschedulability of classic schedulability tests (basically the reverse property of sustainable schedulability introduced in [START_REF] Burns | Sustainability in realtime scheduling[END_REF]), which enables us to limit the search space of the heuristic. A slightly different variant of the heuristic consists in stopping the minimization to the number of tasks the RTOS can handle.

Organization The rest of the paper is organized as follows. In Section 2, we inspect the overhead caused by a large number of threads in a real-time operating system. We define the way we cluster tasks in Section 3. Section 4 is dedicated to the influence of the task clustering on the schedulability. The NP-Hardness of the task clustering is proved and a heuristic to cope with it is described in Section 5. Section 6 contains experimental results on the task clustering and evaluation of its impact in terms of context switches and preemptions.

Overhead of numerous threads

Designs of real-time embedded systems consist of hundreds of threads. The task clustering aims at grouping a large number of nodes into a reduced set of tasks. In this section, we examine the impact of having a high number of threads.

Scheduling overhead 2.1.1 Scheduler level

In a real-time operating system, the scheduler is responsible for the allocation of processes (or tasks) on the processing unit by applying real-time scheduling algorithms, such as Deadline Monotonic (DM) [START_REF] Leung | On the complexity of fixed-priority scheduling of periodic, real-time tasks[END_REF] or Earliest Deadline First (EDF) [START_REF] Liu | Scheduling algorithms for multiprogramming in a hard-real-time environment[END_REF]. Scheduler implementations may vary, but commonly the scheduler handles two queues: one called the run/dispatch/ready queue and the other called the delay queue. The ready queue holds the tasks ready to be executed, ordered by priority. The delay queue holds the suspended tasks. A task enters the suspended state when the scheduler switches from that task to another, in other words at a context switch. Manipulating a delay queue with a large number of tasks induces an additional cost (cf. [START_REF] Burns | Real-Time Systems and Programming Languages: Ada, Real-Time Java and C/Real-Time POSIX[END_REF]), because at each clock interrupt the delay queue is scanned and tasks are inserted into the ready queue sorted according to their release time.

Context switches and preemptions

The context of a task generally consists at least of registers, a program counter and a stack pointer. Each time the scheduler selects a task to be executed, the system has to store the previous task context and to retrieve the next one. This involves several processor instructions.

A context switch occurs each time a job has completed its execution. It also occurs when a task of high priority is released and interrupts the execution of a lower priority task before its completion. This is called a preemption. Thus, a preemption necessarily results in a context switch but not all context switches are due to preemptions. Our experiments in the Section 6.2 show that the clustering highly reduces the total number of context switches but that the number of preemptions remains essentially similar.

Memory

The memory footprint for having a large number of tasks can be considered at two levels. First, each task obviously consumes its proper portion of memory and second, the scheduler also needs some memory to store task queues.

Task level

The memory footprint of a task depends highly on the real-time operating system implementation. Nevertheless, a task generally consists of a structure (sometimes called Process Control Block (PCB)) with a stack, registers, pointers, its state, etc. The global memory allocated to tasks is usually linear with the number of tasks. We experimented the memory consumption of tasks on the FreeRTOS operating system on a TMS570, a Texas Instrument (TI) microcontroller designed for critical applications. This cost is relatively small but may not be negligible with a large number of tasks on a controller with a limited RAM. For instance, considering the constant memory used by a task, clustering 100 tasks to 10 on the TMS570 amounts to reducing the RAM utilization by approximately 13.5 KB on a total of 160 KB available RAM, that is to say a reduction of approximately 150 bytes per task.

Scheduler level

In the worst case, fixed task-priority policies assign as many priorities as tasks (e.g if all deadlines are distinct). Hence, the number of priorities needed to schedule a task set naturally increases with a large number of tasks. This has a cost because usually scheduler implementations require one queue by level of priority. Moreover, having many unique priority levels leads to an additional amount of stack space as the number of preemptions is high. Nevertheless, mechanisms for limiting preemptions such as non-preemption groups [START_REF] Davis | How embedded applications using an rtos can stay within on-chip memory limits[END_REF] or preemption thresholds [START_REF] Wang | Scheduling fixed-priority tasks with preemption threshold[END_REF] can reduce the number or priorities.

o i.0 Ci d i.0 D i o i.1 Ci d i.1 D i o i.2 0 T i T i Figure 1: Task Diagram.

Task Clustering

In this section, we explain how we cluster tasks. For this purpose, we define our task model and we present the clustering of two tasks.

Real-time task model

Our model, illustrated in Figure 1, is based on Liu and Layland's model [START_REF] Liu | Scheduling algorithms for multiprogramming in a hard-real-time environment[END_REF]. A system consists of a synchronous (i.e. with offsets equal to zero) set of real-time tasks

S = ({τ i (C i , D i , T i )} 1≤i≤n
) where C i is the worstcase execution time (WCET) of τ i , T i is the activation period, D i is the relative deadline with D i ≤ T i . We denote τ i.k the (k + 1) th (k ≥ 0) instance, or job, of τ i . The job τ i.k is released at time o i.k = kT i . Every job τ i.k must be completed before its absolute deadline

d i.k = o i.k + D i
In this paper, we focus on priority-based scheduling policies, either fixed job-priority with EDF or fixed taskpriority policies with DM.

Let J denote the infinite set of job J = {τ i.k , 1 ≤ i ≤ n, k ∈ N}. Given a priority assignment Φ, we define two functions s Φ , e Φ : J → N, where s Φ (τ i.k ) is the start time and e Φ (τ i.k ) is the completion time of τ i.k in the schedule produced by Φ.

Definition 1 Let S = ({τ i } 1≤i≤n ) be a task set and Φ be a priority assignment. S is schedulable under Φ if and only if:

∀τ i.k , e Φ (τ i.k ) ≤ d i.k ∧ s Φ (τ i.k ) ≥ o i.k
In the sequel, we will also rely on the notion of worst-case response time.

Definition 2 The worst-case response time R i indicates the maximum time elapsed between the release of any job of τ i and its completion.

Clustering model

Definition 3 Clustering tasks τ i and τ j , where D i ≤ D j , produces a cluster τ ij with the following parameters:

C ij = C i + C j T ij = T i = T j D ij = Dj if ((Dj -Cj ≤Di)∨(Rj -Cj ≤Di)) (1a)
Di otherwise.

(1b)

Notice that, executing τ ij consists in executing sequentially τ i and then τ j . In the following, τ i ′ and τ j ′ denote respectively the parts of τ i and τ j in τ ij . By restriction, we only group tasks with identical periods. In industrial practices, functionalities of different periods are sometimes grouped together, especially when these functionalities interact a lot, to minimize communication as explained in [START_REF] Schliecker | System level performance analysis for real-time automotive multicore and network architectures[END_REF]. This possibility makes the clustering more complex because it requires to manage scheduling inside a cluster. For this reason, we do not deal with this option in this paper. Nevertheless, we could relax this assumption via, e.g., hierarchical scheduling [START_REF] Lipari | A methodology for designing hierarchical scheduling systems[END_REF][START_REF] Mzid | Dpmp: a software pattern for real-time tasks merge[END_REF] or by sequencing tasks offline through a sequencer task similarly to [START_REF] Monot | Multisource software on multicore automotive ecuscombining runnable sequencing with task scheduling[END_REF].

In the sequel, case (1a) refers to clustering with deadline D j and case (1b) to clustering with deadline D i . We choose the cluster deadline D ij (cf. Equations (1a) and (1b)) in such way that both tasks of the cluster still respect their initial deadlines after clustering. This is stated formally as follows:

Theorem 1 Let S = ({τ i (C i , D i , T i )} 1≤i≤n
) be a synchronous task set and two tasks τ x and τ y with D x ≤ D y and T x = T y . Let Φ be a priority assignment and

S ′ = ({S \ {τ x , τ y }} ∪ τ xy ). S ′ is schedulable under Φ ⇒ S is schedulable under Φ. Proof 1 (Case (1a)) Trivially, τ j ′ respects its initial deadline D j . τ i ′ respects its initial deadline D i when D j -C j ≤ D i : S ′ schedulable under Φ ⇒ ∀τ ij.k , e Φ (τ ij.k ) ≤ d ij.k ⇒ e Φ (τ i ′ .k ) + C j ≤ d ij.k As D j ≤ D i + C j , e Φ (τ i ′ .k ) + C j ≤ d i.k + C j And thus e Φ (τ i ′ .k ) ≤ d i.k When R j -C j ≤ D i : S ′ schedulable under Φ ⇒ ∀τ ij.k , e Φ (τ ij.k ) ≤o ij.k + R ij e Φ (τ i ′ .k ) + C j ≤o ij.k + R ij As R ij = R j , e Φ (τ i ′ .k ) + C j ≤o ij.k + R j As R j ≤ D i + C j , e Φ (τ i ′ .k ) + C j ≤o ij.k + D i + C j e Φ (τ i ′ .k ) + C j ≤d i.k + C j And thus e Φ (τ i ′ .k ) ≤d i.k (Case (1b))
Trivial.

Cluster Schedulability

In this section, we first stress that a task set may become unschedulable after a clustering. Then, we present existing schedulability tests to assess whether a task set is still schedulable after a clustering or not. Finally, we determine the conditions under which schedulability does not need to be re-checked after clustering.

Impact on schedulability

Remark 1 In case (1b), S schedulable under Φ S ′ schedulable under Φ.

A schedulable system might become non schedulable after clustering under the minimum deadline of the two tasks, as illustrated in Figure 2. Indeed, we notice in Subfigure 2(b) that the task τ b misses its first deadline after the clustering of tasks τ a and τ c . Thus, we must check the resulting task set schedulability after clustering. In the following, we consider that a clustering that leads to a unschedulable task set is not valid: Definition 4 Let S = ({τ i } 1≤i≤n ) be a task set and τ x and τ y be two tasks of S such that D x ≤ D y . We say that τ xy is a valid cluster if and only if the task set obtained after clustering is schedulable.

Schedulability tests

In this section, we review existing schedulability tests that can be used during clustering for DM and EDF scheduling policies. First we highlight their complexity and then, we examine if they may provide a clue of the remaining "schedulabiliy margin" of the task set, i.e. how much more we can reduce deadlines during further clustering before the task set becomes unschedulable.

A schedulability test is called sufficient if all task sets considered schedulable by the test are actually schedulable. In the same manner, a schedulability test is called necessary if all task sets considered unschedulable by the test are in fact unschedulable. Schedulability tests that are both sufficient and necessary are referred to as exact.

We only consider exact or sufficient tests, which ensures that the task sets obtained after clustering are schedulable. Indeed, applying sufficient tests means that we might not get the minimum number of clusters but we are sure to obtain a valid clustering. Remember that we work with synchronous (with offsets equal to zero) task sets that have constrained deadlines (i.e. with D i ≤ T i ).

Exact schedulability tests

In the same manner as in [START_REF] Davis | Efficient exact schedulability tests for fixed priority realtime systems[END_REF], we distinguish two types of tests: Boolean schedulability tests and response time tests. On the one hand, Boolean tests give a Boolean answer, determining only whether a task set is schedulable or not, for instance with Processor Demand Criteria (PDC [START_REF] Baruah | Preemptively scheduling hard-real-time sporadic tasks on one processor[END_REF]) or Quick convergence Processor-demand Analysis (QPA) [START_REF] Zhang | Schedulability analysis for real-time systems with edf scheduling[END_REF]. On the other hand, exact tests based on Response Time Analysis (RTA [START_REF] Joseph | Finding response times in a real-time system[END_REF][START_REF] Audsley | Applying new scheduling theory to static priority pre-emptive scheduling[END_REF]) provide the worst response time for each task.

RTA of a task τ i is based on the concept of level-i busy period that is presented more fully in Section 5.1.1. RTA for fixed task-priority (FTP) systems as DM can be performed with a pseudo-polynomial time algorithm. On the contrary to FTP systems, the worst response time is not necessarily found on the first processor busy period in a task set scheduled by EDF [START_REF] Spuri | Analysis of deadline scheduled real-time systems[END_REF]. Thus, computing RTA for EDF is more complex and has an exponential complexity.

Sufficient schedulability conditions

In order to reduce the complexity of the computations, we also considered linear sufficient schedulability tests. Audsley [START_REF] Audsley | Deadline monotonic scheduling[END_REF] and Devi [START_REF] Devi | An improved schedulability test for uniprocessor periodic task systems[END_REF] propose sufficient but not necessary schedulability tests, respectively for DM and EDF in O(n) complexity. Those two sufficient tests actually provide an approximate worst response time for each task. They can be considered as an approximate RTA analysis.

Zero-cost clustering

In this section, we prove that in the case 1a, a clustering preserves the schedulability of the task set. A clustering that can be done without re-running a schedulability test is called a zero-cost clustering.

Theorem 2 Let S = ({τ i (C i , D i , T i )} 1≤i≤n ) be a synchronous task set and two tasks τ x and τ y with D x ≤ D y , T x = T y and (D y -C y ≤ D x ) ∨ (R y -C y ≤ D x ). Let Φ be a priority assignment and S ′ = ({S \ {τ x , τ y }}∪τ xy ).

In the case (1a), S schedulable under Φ ⇔ S ′ schedulable under Φ.

Proof 2 (Only if part)

By definition,

D i ≤ D j . S schedulable under Φ ⇒ ∀τ i.k , e Φ (τ i.k ) ≤ d i.k ∧ ∀τ j.k , e Φ (τ j.k ) ≤ d j.k From (1a), d i.k ≤ d ij.k ∧ d ij.k = d j.k
The rest of the proof follows.

(If part) Proved in Theorem 1.

Minimizing the number of tasks

After having defined how to correctly cluster tasks, we now go to the heart of the matter: finding the minimum schedulable task set using task clustering. In this section, we present the theoretical complexity of the problem, a heuristic to tackle it and some results related to the sustainable (un)schedulability tests that serve this heuristic.

Sustainable unschedulability

In this section, we prove that a task set that is unschedulable remains so after clustering. This allows us to cut the search space when looking for the minimum valid cluster. Burns and Baruah [START_REF] Burns | Sustainability in realtime scheduling[END_REF] defined the notion of sustainable schedulability, which means that a task set deemed schedulable by a schedulability test remains so with "better" timing constraints (e.g increased deadlines and periods, decreased execution time). If so, this test is considered sustainable. In a similar manner, we study in this section how an unschedulable task set behaves, in "worse" conditions, with decreased deadlines, periods or increased execution times. We examine the sustainable unschedulability in the context of uniprocessor preemptive scheduling, with synchronous tasks under fixed task-priority and fixed job-priority assignment.

Fixed task-priority assignment

In the sequel, we rely on the existing exact test based on RTA. Worst response time R i of a task τ i is based on the concept of level-i busy period. Intuitively, the level-i busy period is the maximum continuous time interval during which a processor executes tasks of higher or equal priority to the priority of the considered task τ i . RTA computes for each task its worst response time denoted by R i . Equation for finding R i is based on the fact that, if a task τ i is released at time t where t is a critical instant, there must be time for τ i and for every higher priority job to complete in the interval (t, Ri]. The equation for R i is solved by the following recurrence relation:

w n+1 i = j∈hp(i) w n i T j × C j (2)
For all i, hp(i) denotes the set of higher priority tasks than τ i . The recurrence holds until w n+1 i = w n i and then R i = w n+1 i . Notice that w 0 i can be initialized to C i and that the task set is not schedulable if a task τ i exists such that R i > D i .

Theorem 3 (Sustainable unschedulability) A task set deemed unschedulable with RTA remains so with smaller relative deadlines.

Proof 3 By contrapositive. Let S be a task set deemed unschedulable by RTA. Let S ′ be a task set identical to S except that some tasks have shorter deadlines. Assume that S ′ is schedulable. As RTA is sustainable, this would mean that S is schedulable (because S is obtained by increasing some deadlines of S ′ ). Thus we have a contradiction. Lemma 1 A system that is unschedulable with RTA remains so with smaller periods and longer execution times.

Proof 4 Considering the RTA, we can trivially observe in Equation (2) that decreasing a period T i and increasing C i will increase R i .

Fixed job-priority assignment

In this section, we use the method PDC that provides an exact test for a task set scheduled by Earliest Deadline First (EDF) to prove the sustainable unschedulability for fixed job-priority assignment. The PDC is based on the processor demand bound function (dbf). For synchronous task set, dbf (t) corresponds to the cumulative execution requirement by the jobs that have their absolute deadlines before or at t. It is given by the following formula:

dbf(t) = n i=1 t + T i -D i T i × C i (3)
A synchronous task set is EDF-schedulable iff the demand bound never exceeds the available time t:

∀t ≥ 0, dbf(t) ≤ t (4)
Theorem 4 A system using deemed unschedulable with PDC remains so with smaller deadlines, smaller periods and longer execution times.

Proof 5 Simply observe that in Equation (3) the function dbf is monotonically non-decreasing with respect to decreasing D i , decreasing T i and increasing C i .

Task Clustering is NP-Hard

In [START_REF] Bertout | A heuristic to minimize the cardinality of a real-time task set by automated task clustering[END_REF], we gave a practical idea of the high complexity of the task clustering. Our experiments showed that an exhaustive search is not achievable due to the exponential number of partitions to explore. Indeed, the number of partitions to assess to find the minimum task set is equal to m i=0 B i where B i is the exponential Bell number [START_REF] Rota | The number of partitions of a set[END_REF] of the set of tasks with period i and m is the number of different periods of the task set. However, we did not address the problem in terms of computational complexity theory. Thus, we prove here that our problem is NP-hard.

Let us first define the clustering problem more formally. Let S = ({τ i (C i , D i , T i )} 1≤i≤n ) be a synchronous task set. Let C(S) denote the set of schedulable task sets obtained by recursive valid task clusterings of S. The problem we want to address is the following: Given S, find the task set with minimal cardinality in C(S).

Notice that this problem is defined with respect to a given schedulability test. In the following we call RTAclustering the problem defined with respect to RTA (fixedtask priorities) and DBF-clustering the problem defined with respect to DBF (fixed job-priorities).

We first recall the bin-packing problem, and its variant, the bin-packing with fragile objects (BPFO) introduced in [START_REF] Bansal | Bin-packing with fragile objects[END_REF], which we will reduce to our problem.

Bin-packing

In the bin-packing problem, objects of different sizes must be packed into a set of bins. Let a finite set of objects {p i } 1≤i≤n of size a i and a finite set of bins {b j } 1≤j≤m of size v j , with a i , v j ∈ Z+. Let B k denote the set of objects assigned to bin k. Each bin content must not exceed its capacity: ∀k,

1 ≤ k ≤ m, ∀p i ∈ B k , a i ≤ v k .
The bin-packing problem (decision version) is stated as follows:

Is it possible to place all the n objects into m bins respecting the necessary condition cited above for each bin ?

The optimization version of this problem consists in computing the minimum number of bins in which we can fit the objects. Bin-packing is known to be NP-Complete in the decision version and NP-Hard in its optimization version. BPFO is a more general version of the Binpacking where each object has a fragility f i and the validity condition is replaced by: ∀k, Proof 6 To prove the NP-hardness, we reduce BPFO to our problem by showing that any instance of BPFO corresponds to an instance of our problem. Given an instance of BPFO, we make the following correspondences: each object p i corresponds to a task τ i , f i corresponds to D i , a i corresponds to C i and a bin B k corresponds to a cluster τ k . Now, checking the fragility condition does not directly correspond to checking clusters validity. Indeed, this would correspond to checking that ∀k, 1 ≤ k ≤ m, ∀τ i ∈ τ k , C i ≤ min{D i }, which is not a sufficient validity (schedulability) condition. However, both RTA and DBF tests require to check at some point properties of the form f ({C i }, . . .) ≤ g({D i }, . . .) where f and g are functions with higher complexity than in the validity condition of BPFO.

1 ≤ k ≤ m, ∀p i ∈ B k , a i ≤ min{f i }.

Heuristic

In this section, we detail our approach for minimizing the size of the initial task set by successive clustering. Due to the NP-Hardness of the problem, we rely on a heuristic instead of an exact algorithm.

Principle

We start from an initial task set where each task is considered a cluster with one element, we gradually try to group more and more clusters together to minimize the cardinality of the task set, as depicted in the example of Figure 3. At each step, we try to group each cluster with each other and we have several candidates that fulfill conditions of a valid cluster. We must select the best candidate among them. This is done using a heuristic cost (or evaluation) function that estimates which candidate will most likely lead to the best clustering. The sustainable unschedulability allows us to not consider descendants of unschedulable task sets. We propose to achieve task clustering using classic optimization heuristics based on cost functions.

Cost function

We need a schedulability test to determine valid clustering because grouping tasks may make the resulting task set more and more difficult to schedule due to reduced deadlines. Moreover, we need a relevant heuristic cost function to determine the best candidate for the clustering. Thus, we want a schedulability test that exhibits some features that might allow us to compare the potential of two task sets. Therefore, in this section, we explore the compatibility of the tests presented in Section 4.2 with a heuristic based on a cost function.

Boolean exact tests only give a Boolean answer on the schedulability of a task set. Thus, they do not exhibit any clear feature that could be considered a heuristic cost function. Exact tests based on RTA gives worst response times for each task while sufficient tests for DM and EDF presented in Section 4.2.2 are based on a pessimistic approximation of the RTA. Considering a task τ k with its worst response time denoted R k , the closer to one R k D k is, the less we have margin to group the task τ k with another. Thus, we can use the sum of each task response time divided by its respective deadline as heuristic cost function. Then, we have a heuristic cost function h(S), such that

h(S) = |S| k=0 R k D k

Algorithm

Several heuristics based on a cost function exist such as greedy best-first search (greedy BFS), A* algorithm, simulated annealing, etc. We do not aim in this paper at comparing their different performances. We chose a simple heuristic based on greedy BFS [START_REF] Russell | Artificial Intelligence: A Modern Approach[END_REF] detailed in Algorithm 1. The choice of the heuristic (BFS here) is not central in this work. The main idea is the heuristic cost function that may also be applied with other heuristics, as those cited above.

As described in Algorithm 1, we recursively enumerate partitions. At each recursive call, we first try to apply a zero-cost clustering on each generated child. If the zero-cost condition is respected we make a recursive call with the new cluster, if not, we accumulate a 3-tuple containing the task set and indices of the two tasks we want to group in a buffer. Finally, if no zero-cost clustering has been made during this step of partitions enumeration, we choose the most promising task set with non zero-cost clustering. The most promising child is selected according to the heuristic cost function of Section 5.3.2. Notice that, as we cluster one more task by recursive call, we can easily stop the algorithm if a target number of tasks is reached instead of searching for the minimum task set. Practically, it consists in introducing a counter of the number of recursive calls and to stop the recursion as soon as the desired number of tasks is reached.

Lemma 2 The complexity of Algorithm 1 with linear tests is O(n 4 ) and pseudo-polynomial with pseudo-polynomial tests (RTA for DM).

Proof 7 The number of children (or direct successors) generated from a partition of i elements is equal to i × (i -1)/2. We only explore one among all visited children at each step with our greedy heuristic. Thus, the maximum number of visited partitions is equal to

n i=0 i×(i-1) 2
.

This sum corresponds to the sum of the first n triangular numbers (also called tetrahedral numbers) and its closedform expression is f (n) = n(n+1)(n+2) 6 [START_REF] Sloane | The On-Line Encyclopedia of Integer Sequences[END_REF]. Hence, this sequence complexity is O(n 3 ). We apply a sufficient schedulability test in O(n) complexity (whether with DM or EDF) on each visited partition, so the heuristic complexity is O(n 3 ) × O(n) = O(n 4 ). In a similar way, applying schedulability tests with a pseudo-polynomial complexity gives a pseudo-polynomial complexity to the whole algorithm.

6 Experiments

Task set generation

We chose the following model to generate random task sets:

• U i : each task utilization ( Ci Ti ) is computed following the classic UUnifast [START_REF] Bini | Biasing effects in schedulability measures[END_REF] method. We denote as u the overall utilization factor of the processor.

• T i : each task period is uniformly distributed between a set of a maximum of 10 different periods by task set using method [START_REF] Goossens | Limitation of the hyperperiod in real-time periodic task set generation[END_REF], ensuring that the simulation can be limited to a reasonable hyper-period

• C i = T i × U i • D i = round((T i -C i ) × rand(d1, d2)) + C i with 0 ≤ d1 ≤ d2.
This computation comes from [START_REF] Goossens | Limitation of the hyperperiod in real-time periodic task set generation[END_REF] and use the following functions: rand(d1, d2) which returns a pseudo-random real number uniformly distributed in the interval [d1, d2] and round(x) which returns the closest integer to x. We notice that d1 = d2 = 1 corresponds to implicit deadlines and d1 ≤ d2 = 1 to constrained deadlines.

Context switches and preemptions

We simulate the schedule to obtain the total number of context switches using the scheduling simulator SimSo [START_REF] Chéramy | SimSo: A simulation tool to evaluate real-time multiprocessor scheduling algorithms[END_REF] and our task clustering heuristic to evaluate the number of context switches and preemptions before and after task clustering under DM. Our experiments did der EDF observed in Figure 4(b) are more encouraging. This difference probably comes from the pessimism of the sufficient test under EDF used in the previous work, especially when the utilization factor was high. It also comes from the efficiency of the zero-cost clustering that highly reduces the number of tasks. Thus, the RTA for EDF that has a high complexity is more able to handle this restricted number of tasks. Nevertheless, experiments shows that we can not get results in a reasonable time from 200 tasks with the RTA for EDF. In the case of larger task set, the sufficient test may be preferred. The results of clustering under DM and EDF are quite similar. Finally notice that globally, the higher the utilization factor is, the less the tasks are clustered.

Conclusion and Future work

In this paper, we studied the impact of implementing a real-time system as numerous threads. We emphasized that clustering several functionalities in the same thread highly reduces the number of context switches and, to a lesser extent, also reduces memory consumption. We proposed a heuristic to minimize the number of threads of the implementation, while preserving timing constraints and schedulability. This heuristic improves over our previous work, thanks to the zero-cost clustering and sustainable unschedulability that enables us to limit the search space. We presented experimental results of this heuristic under DM and EDF scheduling policies. Concerning future works, we would like to propose solutions based on classic optimization techniques such as mixed integer linear programming (MILP). We are currently working on task clustering applied to tasks with precedence constraints and plan to extend that work to a multi-processor setting.

Acknowledgments

We would like to thank Mélanie Lelaure for her experiments on the TMS570 microcontroller carried out during her internship. We also thank Sanjoy Baruah and Robert I. Davis for their valuable advice during the last RTNS conference.

  Initial schedulable system of tasks τa,τ b and τc under DM.

  Resulting unschedulable system after clustering of tasks τa and τc.

Figure 2 :

 2 Figure 2: Influence of task clustering on system schedulability.

Theorem 5

 5 RTA-clustering and DBF-clustering are NP-Hard.

Figure 3 :

 3 Figure 3: Recursive generation of partitions.

  Task clustering under EDF.

Figure 4 :

 4 Figure 4: Results of task clustering.

Figure 5 :

 5 Figure 5: Average results on task clustering.

for i = n -1 to 0 do for not exhibit the clear main factors (utilization factor, deadlines, number of tasks, etc) that impact the number of context switches and preemptions. Thus, we use the following settings. The number of tasks is fixed to 200. Results are averaged on 1000 executions. Deadlines are uniformly distributed between bounds d1 = 0 and d2 = 1 and the utilization factor of the processor is randomly generated between 0.20 and 0.80 for each generated task set. We observe in Table 1 that the total number of context switches is reduced on average by 90% and that the number of preemptions remains similar after clustering.

Number of tasks

In this section we present the number of tasks obtained after clustering. We cannot compare our heuristic with an optimal solution because the task clustering is not achievable with an exhaustive search among all partitions. Instead we compare our results with our previous work [START_REF] Bertout | A heuristic to minimize the cardinality of a real-time task set by automated task clustering[END_REF].

We also present the part of zero-cost clustering performed in the clustering. Task sets range from 50 to 300 tasks for DM or 200 tasks for EDF by step of 50 tasks. Maximum utilization factor is fixed at 0.80 and deadlines are uniformly distributed between bounds d1 = 0 and d2 = 1. We only take into account task sets that are initially schedulable. We compute average results by executing several times the heuristic on randomly generated task sets with the same parameters. We observe in Figure 4(a) that we are able to cluster many tasks under DM. Results are slightly better than in our previous work and most of the clustering is performed by zero-cost clustering as showed in Figure 5(a). Consequently, this results in an important gain of execution time. For example, experiments conducted on a 2.3GHz Intel Core i7 quad-core with 4GByte memory show that we are able to cluster a set of 1000 tasks in a few seconds while clustering an initial set of 500 tasks took more than one hour of computation in our previous work. Nonetheless, compared to our previous work, results un-