Thai-Son Vu

Guillaume Ovarlez

Xavier Chateau
email: xavier.chateau@lcpc.fr

Macroscopic behavior of bidisperse suspensions of noncolloidal particles in yield stress fluids

. We also show that the effect of the particle size heterogeneity can be described by means of a packing model developed to estimate random loose packing of assemblies of dry particles. All these observations finally allow us to propose simple closed form estimates for both the elastic modulus and the yield stress of bidisperse suspensions: while the elastic modulus is a function of the reduced volume fraction φ/φ m only, where φ m is the estimated random loose packing, the yield stress is a function of both the volume fraction φ and the reduced volume fraction.

I Introduction

Many industrial processes such as concrete casting, drilling muds, food-stuff transport ... and natural phenomena, such as slurries, lava flows ... involve suspensions of polydisperse particles suspended in a non-Newtonian fluid. Knowing and predicting the rheological properties of such suspensions is thus a major issue of both industrial materials mix design and science of deformation and flow of materials. For instance, it is well known that the grading of aggregate is one of the main factor influencing the hardened concrete strength; on the other hand, it has a large impact on the workability of concrete in its fresh state [START_REF]Properties of Concrete 3rd edition[END_REF]]. Consequently, a lot of work has been devoted to predict the influence of the particle size distribution on the concrete overall properties, both in the hardened and fresh state, and then to elaborate rational mix design methods [START_REF] De Larrard | Concrete Mixture Proportioning: a scientific approach[END_REF]]. As the rheological properties of a suspension (viscosity, yield stress, ...) are increasing functions of the solid particle volume fraction, it is necessary to lower this effect in order to design concrete mixtures containing the maximum amount of solid particles possible that can be transported, placed and finished easily. For this purpose, it is better to use aggregate with a distributed grading rather than particles of similar sizes.

The behavior of polydisperse, in particular bidisperse, Newtonian suspensions has received large interest from rheologists and several works, either theoretical or experimental, have been devoted to this subject in the last few decades. Different theoretical relationships aiming at predicting the viscosity of polydisperse suspensions as a function of the solid volume fraction φ and of the particle size distribution have been proposed in the literature [START_REF] Farris | Prediction of the Viscosity of Multimodal suspension from Unimodal Viscosity Data[END_REF]; [START_REF] Chong | Rheology of concentrated suspensions[END_REF]; [START_REF] Storms | Low shear rate viscosity of bimodally dispersed suspensions[END_REF]; [START_REF] Gondret | Dynamic viscosity of macroscopic suspensions of bimodal sized solid spheres[END_REF]]. In the three last works, the influence of the particle size distribution is taken into account through the concept of maximum packing fraction even if this concept is not always rigorously defined. It seems quite natural to define the maximum packing fraction of a suspension as the volume fraction for which the rheological properties tend to diverge.

Nevertheless, the determination of the value of the solid volume fraction at which the rheological properties diverge, and its link to packing models, pose problem. In the case of monodisperse spheres, it seems to be equal to 0.57 for isotropic dispersions of particles [Mahaut et al. (2008a)], to 0.605 for anisotropic dispersions [START_REF] Ovarlez | Local determination of the constitutive law of dense suspension of noncolloidal particles through magnetic resonance imaging[END_REF]] while the random close packing of the dry particles is equal to 0.64. [START_REF] Farris | Prediction of the Viscosity of Multimodal suspension from Unimodal Viscosity Data[END_REF] has investigated the relative viscosity of bimodal suspensions in the framework of a rigorous theoretical approach, valid only if the coarse particle size is much larger than the fine particle one (i.e. when λ, the coarse to fine particle ratio, is greater than 10). When this condition is fulfilled, one can consider that the coarse particles interact with the Newtonian fine particle suspension, and thence, the relative viscosity of the bimodal suspension is equal to the product of the relative viscosities of each monodisperse suspension. Of course, Farris approach can be generalized to polydisperse suspensions or to non-Newtonian suspending fluids provided that estimates of the monodisperse suspension's overall properties exist. [START_REF] Stovall | Viscosit des suspensions multimodales[END_REF] generalized Farris approach by taking into account interactions between the particles of different size using the random close packing's model of [START_REF] Stovall | Linear Packing density model of grains mixtures[END_REF] in order to address problems where scale separation between particles of different size is not possible. Nevertheless, it is believed that this work lacks of rigor because Farris reasoning is used by the authors in a situation where particle size separation is not possible. Later, [START_REF] Phan-Thien | Differential multiphase models for polydispersed suspensions and particulate solids[END_REF] developed a multiphase model for polydisperse suspensions. The idea consists in starting from the homogeneous linear suspending material (a Newtonian fluid or a Hookean solid) and in introducing the particles by infinitesimal volume fraction in the framework of an iterative process (differential scheme). The first step actually corresponds to the Einstein approach to the overall properties of a dilute suspension. Next steps consist in removing a small volume fraction of the suspending overall medium and in replacing it by the same volume of particles. Of course, such a process is rigorous only if particle size separation is possible at each step. Then, this model is only valid for the low solid volume fractions and hence is not applicable to concentrated suspensions. By the way, [START_REF] Phan-Thien | Differential multiphase models for polydispersed suspensions and particulate solids[END_REF] found that the values of the rheological properties estimated by this model are much smaller than those experimentally measured on polydisperse concentrated suspensions.

Besides theoretical works, experimental studies have also been performed. [START_REF] Shapiro | Random packing of spheres and fluidity limits of monodisperse and bidisperse suspensions[END_REF], [START_REF] Probstein | Bimodal model of concentrated suspension viscosity for distributed particle sizes[END_REF] and [START_REF] Chang | Effect of particle size distribution on the rheology of concentrated bimodal suspensions[END_REF] used different types of viscometers to measure the steady viscosity of bidisperse suspensions. The same general trends are observed in these works. For a given value of the solid volume fraction, the viscosity of a bidisperse suspension is lower than the viscosity of a monodisperse suspension with same solid volume and the viscosity is a decreasing function of the maximum packing fraction of the particle size distribution. Interestingly, [START_REF] Chang | Effect of particle size distribution on the rheology of concentrated bimodal suspensions[END_REF] also showed that the dimensionless viscosity η(φ)/η(0) of such suspensions is basically a function of φ/φ m only, where φ is the particle volume fraction and φ m is claimed to be the maximum packing fraction of the particle mixture. [START_REF] Gondret | Dynamic viscosity of macroscopic suspensions of bimodal sized solid spheres[END_REF] have measured the finite frequency viscosity of bidisperse suspensions. They also observed that the particle size distribution influences the dynamic viscosity of bidisperse suspensions, and that the lower maximum packing density distributions correspond to the lower dynamic viscosities.

From these studies, it clearly appears that the viscosity of a polydisperse concentrated suspension is closely related to the maximum packing fraction of the suspended particles. Accordingly, the viscosity of a Newtonian suspension can be controlled by optimizing the particle size distribution [START_REF] Servais | The influence of particle size distribution on the processing of food[END_REF]].

All these studies focused on the influence of the polydispersity on the viscosity of Newtonian suspensions while polydisperse non-Newtonian suspensions have been poorly studied. To our knowledge, this problem has been studied only by few authors and their studies provide extremely dispersed results. However, as explained in detail by Mahaut et al. (2008a) and Mahaut et al. (2008b), the data reported in these works do not correspond to homogeneous suspensions of particles interacting only mechanically with the suspending fluid, which is the subject we are interested in, and then are not applicable to a wide range of materials. [START_REF] Geiker | On the effect of coarse aggregate fraction and shape on the rheological properties of self-compacting concrete[END_REF] studied experimentally the effect of coarse particles volume fraction on the rheological properties of self compacting concretes; they studied suspensions of polydisperse particles of various shapes but of same grading. They assumed that the effect of aggregates on fresh concrete rheological properties can be studied by looking to concrete as a suspension of coarse particles (the aggregates) in a yield stress fluid (the mortar): coarse particles interact only by non-Newtonian hydrodynamic forces. Both the fresh concrete and the mortar behaviors are described by a Bingham law. While Geiker et al. (2002) find that the dimensionless rheological properties for the different studied particles have very different shapes when plotted vs. the reduced volume fraction φ/φ m , close examination of the results shows that divergence actually occurs at different φ/φ m < 1 for particles of different shape, in contradiction with the usual definition of the maximum packing fraction in rheology. In this study, φ m was indeed defined as the random close packing of the dry granular assembly, which may not be relevant for comparing the rheological data. Moreover, the concrete was tested in a large gap coaxial cylinder rheometer and its rheological properties were estimated from the steady-state flow. It is well known that shear induced migration of particles is likely to occur in this situation [START_REF] Ovarlez | Local determination of the constitutive law of dense suspension of noncolloidal particles through magnetic resonance imaging[END_REF]]. Then, the tested materials may not be homogeneous when the system is at steady-state and it is not clear that the experimental data of [START_REF] Geiker | On the effect of coarse aggregate fraction and shape on the rheological properties of self-compacting concrete[END_REF] can be used to estimate the rheological properties of a well defined material (i.e. a material homogeneous at the coarse particles scale with a well defined distribution of particles within the tested volume). The fact that the yield stress estimates of [START_REF] Geiker | On the effect of coarse aggregate fraction and shape on the rheological properties of self-compacting concrete[END_REF] are much larger than estimates reported by other authors or in this work also casts doubt about the validity of their procedure. [START_REF] Ancey | Yield stress for particle suspensions within a clay dispersion[END_REF] have experimentally studied the influence of adding noncolloidal and non-Brownian particles within a clay dispersion on the value of the yield stress of the suspension. The ratio of the particle size was large enough so that the clay dispersion can be considered as homogeneous at the coarse particles scale. The authors have chosen to measure the yield stress of the suspension by means of a slump test in order to avoid the classical problems encountered with Couette rheometer (migration of particles, localization of the shear rate, anisotropy of the material) [START_REF] Coussot | Rheometry of Pastes, Suspensions and Granular Materials[END_REF]; [START_REF] Ovarlez | Local determination of the constitutive law of dense suspension of noncolloidal particles through magnetic resonance imaging[END_REF]]. They showed that for well-graded materials, the monodisperse suspension yield stress does not depend on the particle characteristics (diameter, material) and that the relative yield stress diverges when the solid volume fraction value tends toward that of the maximum packing density. When the coarse particles are polydisperse, the value of the maximum packing density depends of the size distribution of the particles. Similarly to what is observed for Newtonian suspensions, the yield stress diverges for values of the solid volume fraction depending on the particle size distribution. The dimensionless yield stresses τ c (φ)/τ c (0) measured for various mixtures of bidisperse particles then seem to collapse when plotted vs. the reduced volume fraction φ/φ m . They also observed that for low reduced solid volume fraction, the yield stress can be a decreasing function of the solid volume fraction of the coarse particle. This effect was ascribed by the authors to a depletion phenomena. In the closeness of coarse particles, the clay particles are expelled from the suspending fluid. This effect induces an increase of the clay particle concentration far from the coarse particles which are embedded in a shell of viscous material (pure water) where the yield stress is naught. Then, the coarse particles can not contribute to the overall yield stress and behave as empty pores. Obviously, the observed decrease of the suspension yield stress originates from physicochemical effects. We recall that such effects are beyond the scope of this paper.

In this study, we are interested in situations where bidisperse mixtures of noncolloidal particles are dispersed in a yield stress fluid. It is recalled that yield stress fluids have a solid viscoelastic behavior below a yield stress; above this yield stress, they behave as liquids and their flow behavior is often well fitted to a Herschel-Bulkley law [START_REF] Larson | The structure and Rheology of Complex fluids[END_REF]]. The influence of monodisperse particles on the behavior of yield stress fluid has been addressed experimentally by Mahaut et al. (2008a) and Mahaut et al. (2008b), and theoretically by [START_REF] Chateau | Homogenization approach to the behavior of suspensions of noncolloidal particles in yield stress fluids[END_REF]. The main result of these studies is that, when model materials are carefully designed to correspond to the theoretical case of homogeneous and isotropic distribution of monodisperse hard spheres interacting only mechanically through a yield stress fluid, there is a theoretical relationship linking the dimensionless linear properties of such suspensions to their nonlinear properties that is in very good agreement with the experimental data. As regards their elastoplastic properties, this relationship reads

τ c (φ)/τ c (0) = (1 -φ)G ′ (φ)/G ′ (0), (1)
τ c being the yield stress, G ′ the elastic modulus, and φ the particle volume fraction. They also observed that both the elastic modulus and yield stress are monotonically increasing functions of the solid volume fraction φ which seem to diverge when φ tends toward 0.57. Furthermore, their data are well fitted to a Krieger-Dougherty like equation

G ′ (φ) = G ′ (0) × (1 -φ/φ m ) -2.5φm with φ m = 0.57 (2)
and to its nonlinear generalization obtained by putting Eq. 2 into Eq. 1

τ c (φ) = τ c (0) × (1 -φ)(1 -φ/φ m ) -2.5φm with φ m = 0.57 (3)
In this work, we again restrict to situations where there is a scale separation between the paste microstructure and the noncolloidal particles in suspension and we focus on the purely mechanical contribution of the particles to the paste behavior. For this purpose, we use the experimental procedures described in Mahaut et al. (2008a). Accordingly, the experimental investigations reported in this paper focus on the behavior of the pastes in their solid regime, i.e., on the influence of particles on the elastic modulus and yield stress.

In Sec.II, we briefly present the materials employed and the experimental setup. Elastic modulus and yield stress measurements are shown in Sec. III. Then, in Sec. IV, we present a packing model and show that it allows to account for the dependence of the rheological properties on the particle mixture composition. Finally, in Sec.V, we combine the packing model estimates with the experimental data, and we demonstrate that it is possible to accurately predict the overall properties of the studied suspensions.

II Materials and methods

In this section, we briefly present the main features of the suspensions we studied and of the experimental procedures we used for the elastic modulus and yield stress measurements. It is recalled that these procedures were designed to study the purely mechanical contribution of an isotropic distribution of particles to the yield stress fluid behavior. The interested reader is referred to [Mahaut et al. (2008a)] for a more detailed presentation.

A Materials

In order to evaluate the purely mechanical influence of the particles on the behavior of the paste, we designed materials to ensure scale separation between the matrix (the yield stress fluid) and the particles. We chose to use only inverse emulsions as a suspending fluid because Mahaut et al. (2008a) obtained the greater stability and the more reproducible results with this material in the monodisperse case. Moreover, the inverse emulsion behavior is very close to the ideal elastoplastic behavior of a yield stress fluid (see Fig. 1). The emulsion is a water-in-oil Figure 1: Shear stress vs strain when slowly shearing the material from rest at 10 -2 s -1 for a pure emulsion (squares) and for a bidisperse suspension of 30% of 80 µm polystyrene beads mixed with 70% of 315 µm polystyrene beads with φ = 0.30 in the same emulsion (stars).

emulsion which microstructure scale is given by the droplets size, of order 1 µm from microscope observations. As the continuous phase, we use a dodecane oil in which a Span 80 emulsifier is dispersed at a 7% concentration. The dispersed phase is a 300 g/l CaCl 2 solution dispersed in the oil phase at 6000 rpm for 1 h. The particles are spherical beads. We used either polystyrene beads of density 1.05 g/cm 3 , or glass beads of density 2.5 g/cm 3 . We used bidisperse mixtures of polystyrene beads of diameter 80 µm and 315 µm (particle size ratio λ = 3.94) and bidisperse mixtures of glass beads of diameter 40 µm and 330 µm (λ = 8.25). The bimodal spherical beads are mixed together in the dry state. The particle mixture composition is defined by the fine particle proportion ξ = V f /(V f + V c ) where V f (resp. V c ) denotes the fine (resp. coarse) particle volume fraction. The particles are then dispersed in a volume V ℓ of the suspending fluid so that their total volume fraction is φ

= (V f + V c )/(V f + V c + V ℓ ).
Finally, the fluid-particle mixture is stirred manually in random directions in order to homogenize it and obtain an isotropic material. In all cases, the paste yield stress was sufficient to avoid particle sedimentation in the solid regime. The critical conditions for which a spherical object would fall under the action of gravity through a yield stress fluid at rest is obtained from the balance between the gravity force, the buoyancy and the drag force. A sphere of radius a and density ρ immersed in a yield stress fluid with yield stress τ c will not move under the action of gravity if 4/3(ρρ c )gπa 3 is lower than 4k c πa 2 τ c with k c ≃ 3.5, ρ c the yield stress fluid density and g the gravity [START_REF] Coussot | Rheometry of Pastes, Suspensions and Granular Materials[END_REF]]. In our experiments, the critical drag force is at least 30 times greater than the gravity force, which ensures stability at rest (thus for the elastic modulus measurements). When the suspension is sheared at low shear rate γ, shear-induced sedimentation may occur with a velocity V ≈ 2/9(ρρ c )ga 2 /(τ c / γ) [START_REF] Ovarlez | Three-dimensional jamming and flows of soft glassy materials[END_REF]]. Our yield stress measurements (see below) are performed at very low shear rate ( γ = 0.01s -1 ): this yields V < 0.1µm.s -1 for all the studied materials, i.e. shearinduced sedimentation can be considered as negligible over the duration of the experiments (less than 100 s). The solid line is the law Eq. 2. The dotted line is the Hashin-Shtrikman lower bound Eq. 4.

B Rheological methods

The experiments were performed within a vane in cup geometry (inner diameter d i = 25 mm, outer cylinder diameter d e = 36 mm, height H = 45 mm) on a commercial rheometer (Bohlin C-VOR 2000). In order to prevent slippage at the walls, we used a six-blade vane as an inner tool immersed in a outer rough cylinder of roughness size equivalent to the size of the largest particles. We measured the elastic modulus G ′ (φ) through oscillatory shear experiments at a single frequency in the linear regime, and the yield stress τ c (φ) through a single measurement at a small constant velocity ( γ = 0.01s -1 ) on each sample (see an example in Fig. 1). The (static) yield stress is defined as the shear stress plateau in a shear stress vs. shear strain plot (Fig. 1). It is worth noting that we carefully checked that the same yield stress is measured whatever the (low) rotational velocity chosen to drive the inner tool is (i.e. γ ≤ 0.01s -1 ). These methods were shown to provide fair estimates of the relative evolution of the elastic and yield stress properties with the particle volume fraction, and to ensure that the studied suspensions are isotropic and homogeneous [Mahaut et al. (2008a)].

III Results

In this section, we present the elastic modulus and yield stress measurements performed on all the systems we studied, and compare the results to what was observed in monodisperse suspensions. Elastic modulus and yield stress measurements of various monodisperse suspensions of beads embedded in yield stress fluids were obtained by Mahaut et al. (2008a).

A Elastic modulus measurement results

The results of the elastic modulus measurements performed on all the suspensions we designed are summarized in Tab. 1 and depicted in Fig. 2 as a function of the solid volume fraction φ. Two size ratio (λ = 3.94 and λ = 8.25 ) and several fine particle proportion values ξ were tested. 1: Dimensionless elastic modulus G ′ (φ, λ, ξ)/G ′ (0) as a function of the particle volume fraction φ for all the studied materials (all particle size ratio λ and fine particle proportion ξ).

As classically observed for polydisperse viscous suspensions of different compositions, the experimental points do not fall onto a single curve. Nevertheless, we observe that the dimensionless elastic modulus is an increasing function of the solid volume fraction φ when λ and ξ are given. Moreover, all the data points for bidisperse suspensions fall below the law Eq. 2 valid for monodisperse suspensions. These results are perfectly consistent with the findings of the literature described in the introduction. It is also worth noting that all the experimental elastic modulus points fall above the Hashin-Shtrikman lower bound [START_REF] Hashin | A variational approach to the theory of the elastic behaviour of multiphase materials[END_REF]]:

G ′ (φ)/G ′ (0) > (2 + 3φ)/(2 -2φ) (4)
which is a theoretical lower bound computed in the general case of a biphasic material (an infinitely rigid phase embedded in a linear elastic phase) isotropic both at the microscopic and the macroscopic scales.

B Yield stress measurement results

We now present the results of the yield stress measurements performed on the different suspensions we studied. The experimental data are gathered in Tab. 2 and graphically represented in Fig. 3 as a function of the solid volume fraction φ.

The dimensionless yield stress exhibits the same trends as the dimensionless elastic modulus. It is an increasing function of the solid volume fraction when the particle size ratio λ and the fine particle proportion ξ of the mixture are given. Moreover, similarly to what was observed for monodisperse suspensions [Mahaut et al. (2008a)], for a given particle mixture, the yield stress increase with the particle volume fraction is much lower than the elastic modulus increase.

IV Divergence of the rheological properties: The rigidity threshold of contact network

Although the data shown in Sec. III are scattered, we observe that all the G ′ and τ c curves have basically the same shape and tend to diverge for a value φ m of the volume fraction that seems φ for all the studied materials (all particle size ratio λ and fine particle proportion ξ).

-0,1 0,0 0,1 0,2 0,3 0,4 0,5 0,6 0,7 .5φm with φ m = 0.57 proposed by [START_REF] Chateau | Homogenization approach to the behavior of suspensions of noncolloidal particles in yield stress fluids[END_REF] for the monodisperse suspensions.

(φ) = τ c (0) (1 -φ)(1 -φ/φ m ) -2
to depend both on the size ratio λ and on the fine particle proportion ξ. As a first step towards the modelling of the rheological properties of the suspensions, it thus seems important to be able to predict the value of φ m . This is the purpose of this section.

A Packing model Mahaut et al. (2008a) have shown that the elastic modulus G ′ of an isotropic suspension of monodisperse spherical beads is well fitted to the Krieger-Dougherty like law Eq. 2 with φ m = 0.57. The quantity φ m for which G ′ diverges is most probably no more than the contact rigidity threshold of the suspension: if φ < φ m the particles interact only (hydrodynamically) through the suspending fluid. If φ ≥ φ m , the particles are close enough so that there is contact network spanning the whole material and that interparticle interactions (contact, friction, elasticity of the beads material ...) play a major role, leading to the apparent divergence of G ′ . Interestingly, the overall yield stress of monodisperse suspensions also strongly increases when φ tends towards the same value φ m = 0.57. At this stage, φ m is just a fitting parameter. However, according to the observed trends of the overall properties of the bidisperse suspensions in Sec. IIIA and Sec. IIIB, there is strong evidence that this contact rigidity threshold is closely linked to the random close packing [START_REF] Chang | Effect of particle size distribution on the rheology of concentrated bimodal suspensions[END_REF]; [START_REF] Gondret | Dynamic viscosity of macroscopic suspensions of bimodal sized solid spheres[END_REF]; [START_REF] Probstein | Bimodal model of concentrated suspension viscosity for distributed particle sizes[END_REF]; [START_REF] Frankel | On the viscosity of a concentrated suspension of solid spheres[END_REF]]. This suggests to use packing models to predict how the value of the contact rigidity threshold vary with the beads composition. Furthermore, it is largely accepted that the packing density of an assembly of monodisperse beads depends upon the small gap interparticle forces and the way the packing is produced. For example, [START_REF] Dong | Role of the interparticle forces in the formation of random loose packing[END_REF] obtained packing fractions ranging from 0 to 0.64 depending on the conditions between particles (0.64 for random close packing of frictionless cohesionless beads and 0 for random loose packing of beads involving strong van der Waals forces). When the cohesive forces between particles do not dominate over other forces, the random loose packing fraction, or more precisely, the sphere packing at its contact rigidity threshold ranges from 0.5 to 0.58 [START_REF] Cumberland | The packing of particles[END_REF]; Onoda and Liginer (1990); [START_REF] Dong | Role of the interparticle forces in the formation of random loose packing[END_REF]]. Then, the contact rigidity threshold φ m = 0.57 determined experimentally for monodisperse suspension, assuming it is representative of our mixture process, may be used as a fixed parameter of a packing model.

Various models have been proposed in the literature to address granular mixture problems. For a bidisperse beads mix, the packing density is a function of the particle size ratio λ, the fine particle proportion ξ and the way the packing was obtained [Ben Aïm and Le Goff (1967), [START_REF] Dodds | The porosity and contact points in multicomponent random sphere packings calculated by a simple statistical geometric model[END_REF][START_REF] De Larrard | Concrete Mixture Proportioning: a scientific approach[END_REF]]. In most of the models of the literature, the packing process was taken into account through a scalar index. In this work, we do not need to model the mixing process because we always used the same procedure to prepare the materials. We will first compute the value of the contact rigidity threshold of our bidisperse packings taking the monodisperse contact rigidity threshold φ m as a free parameter; the value of φ m will then be fixed in the sequel as the experimentally observed value 0.57 for our mixing process. We chose to use the model of de Larrard (1999) which aims at taking the geometrical interactions between particles of different size into account. In this model, two different configurations of bidisperse mixtures are distinguished: dominant fine particle configuration when coarse particles are embedded in a fine particle matrix and dominant coarse particle configuration when fine particles fill the empty spaces between coarse particles. Furthermore, two geometrical interactions are taken into account:

Loosening effect : When one fine particle is inserted into a packing of coarse particles (which are thus dominant class) and if the fine particle is not small enough to locate in the empty space between the coarse particles, there is a loosening of the coarse particle packing which induces a decrease of the overall coarse particle density.

Wall effect : When one large particle is inserted into a local packing of fine particles (dominant fine particle configuration), the fine particle density is decreased near the coarse particle. This wall effect induces a decrease of the overall fine particle density. [START_REF] Bournonville | Modification du modle de Farris pour la prise en compte des interactions gomtriques d'un mlange polydisperse de particules[END_REF] used a slightly modified version of the model of de Larrard (1999) to estimate the packing density of dry polydisperse beads mixtures. They showed that it is possible to directly use the experimentally measured packing density associated with the particular packing process used as a free parameter of the model. Moreover, they experimentally determined the function describing the loosening and wall effects described above. While they measured random close packing for monodisperse beads ranging from 0.59 to 0.62 for particles with diameters between 50µm and 320µm, we used exactly the same equations to estimate the divergence threshold of bidisperse suspensions, the only difference being the monodisperse threshold value. Since we are interested only in bidisperse mixtures, we only give the relationships allowing to estimate the contact rigidity threshold for such a suspension. The interested reader is referred to [START_REF] De Larrard | Concrete Mixture Proportioning: a scientific approach[END_REF]; [START_REF] Bournonville | Modification du modle de Farris pour la prise en compte des interactions gomtriques d'un mlange polydisperse de particules[END_REF]] for a more detailed review of the model.

To compute the contact rigidity threshold of a bidisperse mixture of particles of respective diameters d c and d f with d c > d f , one may first calculate the fine dominant particle density φ f-dom m and the coarse dominant particle density φ c-dom m defined by

φ f-dom m = φ f m 1 -(1 -ξ) 1 -φ f m + b fc (φ f m -φ f m φ c m ) (5) φ c-dom m = φ c m 1 -ξ (1 -a cf φ c m /φ f m ) (6)
where φ f m (resp. φ c m ) denote the contact rigidity threshold of the monodisperse fine (resp. coarse) suspension, a cf (resp. b fc ) a function describing the loosening (resp. wall) effect and ξ is the fine particle proportion defined above. In the sequel, we adopt φ c m = φ f m = 0.57 as determined experimentally by Mahaut et al. (2008a). The functions a cf and b fc were determined experimentally by [START_REF] Bournonville | Modification du modle de Farris pour la prise en compte des interactions gomtriques d'un mlange polydisperse de particules[END_REF]. They only depend upon the particle size ratio λ = d c /d s .

a cf = 1 -1 - 1 λ 1.13 0.57 (7) b fc = 1 -1 - 1 λ 1.79 0.82 (8)
Finally, the bidisperse suspension contact rigidity threshold is defined by

φ m = min(φ c-dom m , φ f-dom m ) ( 9
)
Model predictions are shown in Fig. 4, where the contact rigidity threshold φ m is plotted as a function of the fine particle proportion for several values of the size ratio λ.

Note that whatever the value of the size ratio, the maximum of the contact rigidity threshold is a singular point of the contact rigidity threshold versus fine particle proportion curve. Even if such a singular point was not experimentally observed for bidisperse packing of dry particles, it seems to be the hallmark of theoretical model distinguishing two regimes [START_REF] Gondret | Dynamic viscosity of macroscopic suspensions of bimodal sized solid spheres[END_REF][START_REF] De Larrard | Concrete Mixture Proportioning: a scientific approach[END_REF]]. de Larrard (1999) corrected this undesirable effect by introducing a scalar index accounting for the packing process. Other models have been built to predict smooth variations of the packing density with respect to the fine particle proportion [START_REF] Gondret | Dynamic viscosity of macroscopic suspensions of bimodal sized solid spheres[END_REF]]. To our knowledge, it is not clear that smooth models are more accurate than non smooth ones. Furthermore, it will be shown in the sequel that Eqs. 5 to 9 are accurate enough to satisfactorily predict the influence of polydispersity onto both the elastic modulus and the yield stress of our suspensions. Then, the existence of this singular point seems to be a detail at this stage, and does not pose any problem in the framework of this study.

B Rheological properties vs Reduced solid volume fraction

In Sec. IVA, we have modelled the value of the contact rigidity threshold φ m , i.e. the volume fraction for which the suspension rheological properties should diverge. We now propose to plot the dimensionless elastic moduli G ′ (φ, λ, ξ)/G ′ (0) and the dimensionless yield stress τ c (φ, λ, ξ)/τ c (0) of all our bidisperse suspensions as a function of the predicted reduced solid volume fraction φ/φ m . These data are presented in Fig. 5 and6. We first observe that, when plotted versus φ/φ m , the dimensionless elastic modulus now falls onto a single master curve. As the experimental data for monodisperse suspensions also fall onto this curve, this curve should be fitted by a Krieger Dougherty like equation. This question is addressed in the sequel. It is not obvious that such a property holds for the dimensionless yield stress, even if the experimental data are less scaterred than when they are plotted as a function of the solid volume fraction. We observe that both rheological properties tend to diverge for φ/φ m = 1. This last observation is a strong indication that the packing model we use is able to predict correctly the impact of the particle size distribution on the value of the volume fraction for which the rheological properties diverge.

V Analysis and discussion

In Sec. IV, we have shown that plotting the dimensionless rheological properties of bidisperse suspensions as a function of the reduced solid volume fraction φ/φ m allows to obtain curves diverging when the reduced solid volume fraction tends toward 1. The purpose of the present section is to provide close-form estimates for the rheological properties of the bidisperse suspensions. for all bidisperse suspensions (all particle size ratio λ and fine particle proportion ξ). The contact rigidity thresholds φ m were calculated using the modified de Larrard model Eqs. 5 to 9.

A Elastic modulus

We have observed that dimensionless elastic moduli of all bidisperse suspensions plotted as a function of the reduced solid volume fraction φ/φ m fall onto a single master curve. Then, by slightly modifying Eq. 2 so that the exponent does not depend on φ m , we obtain a new estimate for the elastic modulus of bidisperse suspension

G ′ (φ, λ, ξ)/G ′ (0) = (1 -φ/φ m ) -1.43 (10)
which is shown as a solid line in Fig. 5. Satisfactorily, experimental data are very well fitted to Eq. 10. As we have 1.43 = 2.5 × 0.57 for the exponent value in Eq. 10, the Krieger-Dougherty like Eq.10 agrees with Eq. 2. However, even if a good agreement between the experimental data and the theoretical equation is obtained, it has to be noted that first order series expansion of Eq. 10 with respect to the variable φ yields the [START_REF] Einstein | Eine neue bestimmung der molekldimensionen[END_REF] relation

G ′ (φλ, ξ)/G ′ (0) = 1 + 2.5φ + O 2 (φ) (11)
only for monodisperse suspensions, i.e. when φ m = 0.57. Discrepancy between estimates of the viscosity of concentrated suspension of solid particles and Einstein's equation is classical [START_REF] Chang | Effect of particle size distribution on the rheology of concentrated bimodal suspensions[END_REF]; [START_REF] Frankel | On the viscosity of a concentrated suspension of solid spheres[END_REF]]. Eilers formula [START_REF] Stickel | Fluid mechanics and rheology of dense suspensions[END_REF]] complies with both the Einstein equation and high concentration limit, but of course, this equation does not write as a single function of the normalized solid volume fraction φ/φ m because Eq. 11 does not. As our experimental data are well fitted to the closed form estimate Eq. 10, we leave this problem aside in this work. In Fig. 7, we plot the experimentally measured dimensionless elastic moduli G ′ (φλ, ξ)/G ′ (0) as a function of the fine grain proportion ξ, for fixed size ratio λ = 3.94, for two solid volume fraction φ = 0.4 and φ = 0.5. These experimental data are gathered in Tab. Table 3: Dimensionless elastic modulus G ′ (φ, λ, ξ)/G ′ (0) and dimensionless yield τ c (φ, λ, ξ)/τ c (0) stress as a function of the fine particle proportion ξ, for particle size ratio λ = 3.94.

Experimental G ′ (φλ, ξ)/G ′ (0) shows a minimum at a value of ξ close to 0.40. This minimum should thus correspond to the optimal mixture of particles of size ratio λ = 3.94. The experimental data are also compared with Eq. 10 in Fig. 7, the contact rigidity thresholds being computed thanks to the model presented in Sec. IV.

The agreement between the experimental data and Eq. 10 is rather good meaning that the granular packing model combined with the elastic Krieger-Dougherty equation capture the essential features of the studied system. However, the theoretical dimensionless elastic modulus has a minimum at ξ = 0.30 while the smallest elastic modulus was measured for suspension with ξ close to 0.4. This discrepancy possibly comes from the packing model which was validated on dry The dot (resp. solid) line is Eq. 10 computed for φ = 0.4 (resp. φ = 0.5). The contact rigidity thresholds φ m were calculated using the modified de Larrard model Eqs. 5 to 9.

beads packing experiments, whereas beads are suspended in a fluid in this work. Finally, close inspection of the data suggest that the dimensionless elastic modulus vs fine particle proportion curve is smooth while the tangent to the theoretical curve is discontinuous at the point where G ′ (φ, λ, ξ)/G ′ (0) reaches its minimal value. As pointed out in Sec. IV, this singularity in the theoretical curve clearly originates from the packing model. Even if the packing model could be improved to obtain smooth theoretical curves, it is believed that the model used in this work is accurate enough given the dispersion of experimental data.

B Elastic modulus vs yield stress

Proposing estimates for the overall properties of a suspension of particles dispersed in a non-Newtonian fluid is challenging. However, [START_REF] Chateau | Homogenization approach to the behavior of suspensions of noncolloidal particles in yield stress fluids[END_REF] have recently shown that it is possible to relate the overall yield stress of a suspension of particles isotropically dispersed in a yield stress fluid to its overall elastic modulus in its solid regime, provided that the heterogeneities of the strain rate field over the suspending fluid domain can be neglected (see Eq. 1). To obtain this relationship, it was assumed that the particles are rigid, noncolloidal and that there are no physicochemical interactions between the particles and the paste. It is recalled that our experimental procedure was designed to fulfill all these hypotheses [Mahaut et al. (2008a)]. In this case, the apparent viscosity η app of the suspension sheared at a macroscopic shear rate γ reads

η app (φ, γ) = G(φ) G(0) × η app 0 ( γeff ) (12)
where η app 0 is the apparent viscosity of the suspending fluid sheared at an effective strain rate γeff that accounts for the shear rate locally experienced by the pure suspending fluid, and G(φ) is the elastic modulus of the same suspension of particles (i.e. same size and same position) dispersed in an elastic material. Eq. 12 simply says that in a nonlinear (non-Newtonian) medium, the viscosity increase of the suspension with the particle volume fraction φ is the same as in a linear (Newtonian or elastic) medium whose viscosity would be the apparent viscosity η app 0 ( γeff ) of the sheared suspending fluid; in this case, an additional dependence of the apparent viscosity on φ comes from the γeff dependence on φ. As the solid particles do not deform, the shear correction factor γeff / γ is greater than one. It can be shown in the framework of a rigorous upscaling approach to this problem that the optimal estimate of this quantity reads [START_REF] Chateau | Homogenization approach to the behavior of suspensions of noncolloidal particles in yield stress fluids[END_REF]

] γeff / γ = G(φ)/G(0) (1 -φ) (13)
in which the quantity 1 -φ appears because the shear rate experienced by the suspending fluid is linked to the overall shear rate by means of an average equation over the interstitial fluid only. This explains why nonlinear properties cannot depend simply on the reduced solid volume fraction φ/φ m . This approach allows in particular predicting the value τ c (φ)/τ c (0) of the dimensionless yield stress of suspensions of noncolloidal particles in yield stress fluids. The apparent viscosity of a perfect plastic yield fluid indeed reads τ c / γ. Putting this equation into Eq. 12 combined with Eq. 13 finally yields Eq. 1.

This analysis still allows to physically explain why the relative yield stress increase is lower than the relative elastic modulus increase. Indeed, while the relative apparent viscosity of the suspension is equal to its relative elastic modulus, the shear rate experienced by the suspending fluid is greater than the overall shear rate prescribed to the suspension. As the apparent viscosity of a perfect yield stress fluid is a decreasing function of the shear rate, the localization of the shear rate lowers the consolidating effect of adding solid particles.

We have plotted in Fig. 8 the dimensionless yield stress τ c (φ, λ, ξ)/τ c (0) -1 as a function of the dimensionless quantity (1 -φ)G ′ (φ, λ, ξ)/G ′ (0) -1 in logarithmic coordinates for all the systems we studied in order to check that Eq. 1 is still valid. We observe an excellent agreement between our experimental results and the micromechanical estimate Eq. 1 (which is plotted as a straight line y = x in these coordinates).

These results show that the experimental data are consistent with the hypothesis that a uniform estimate of the strain rate over the suspending fluid domain allows to accurately estimate the overall yield stress of a bidisperse suspension from its overall elasticity.

C Yield stress

Putting the estimate Eq. 10 for the overall linear properties of the suspension into Eq. 1 yields the estimate for the overall yield stress of the suspension:

τ c (φ, λ, ξ)/τ c = (1 -φ)(1 -φ/φ m ) -1.43 (14)
We have plotted in Fig. 9 the experimental dimensionless yield stress τ c (φ, λ, ξ)/τ c (0) -1 as a function of the dimensionless quantity (1 -φ)(1 -φ/φ m ) -1.43 -1 in logarithmic coordinates for all the systems we studied in order to check that Eq. 14 accurately describes the experimental data.

Even if the fit is not perfect, it is believed that Eq. 14 is accurate enough to predict the yield stress of the bidisperse suspensions studied in this paper.

In order to compare the accuracy of Eq. 14 as an estimate of the overall yield stress of the suspensions with the accuracy of the elastic modulus estimate Eq. 10, we have plotted in Fig. 10 the experimental dimensionless elastic modulus as a function of (1 -φ/φ m ) -1.43 .

At first sight, both estimates seem to accurately fit the experimental data. To quantitatively assess this point, we have computed the least square error for both the dimensionless yield stress for all the bidisperse suspensions studied (all particle size ratio λ and fine particle proportion ξ). The figure's coordinates were chosen so that the y = x line represents the theoretical relation Eq. 1.

-1,5 -1,0 -0,5 0,0 0,5 1,0 for all the bidisperse suspensions studied (all particle size ratio λ and fine particle proportion ξ). The figure's coordinates were chosen so that the y = x line represents the theoretical relation Eq. 14.

-1,0 -0,5 0,0 0,5 1,0 1,5 2,0 2,5 Figure 10: Dimensionless elastic modulus G ′ (φ, λ, ξ)/G ′ (0) as a function of (1 -φ/φ m ) -1.43 for all the bidisperse suspensions studied (all particle size ratio λ and fine particle proportion ξ). The figure's coordinates were chosen so that the y = x line represents the theoretical relation Eq. 10.

(Fig. 9) and dimensionless elastic modulus (Fig. 10). For quantity y the least square error reads with N , the number of measured points, y exp i , the ith experimentally measured point and y th i the associated theoretical value. We found Err G = 0.0071 for the elastic modulus estimate and Err τc = 0.018 for the yield stress estimate. Both computed errors being of the same order of magnitude, it can be concluded that the yield stress estimate Eq.14 is quite as precise than the elastic modulus estimate Eq. 10.

VI Conclusion

We have studied the elastic modulus and yield stress of an isotropic bidisperse suspension of noncolloidal particles in a yield stress fluid. We focused on the purely mechanical contribution of the noncolloidal particles to the overall properties of the yield stress fluid. To do this, we used materials and procedures designed by Mahaut et al. (2008a) to study the case of monodisperse suspensions. We observed that, as it is classically observed for particles suspended in a Newtonian fluid, the elastic modulus and yield stress of bidisperse suspensions are lower than the same quantities measured for monodisperse suspension of same solid volume fraction. We showed that the equation τ c (φ, λ, ξ)/τ c (0) = (1 -φ)G ′ (φ)/G ′ (0) of [START_REF] Chateau | Homogenization approach to the behavior of suspensions of noncolloidal particles in yield stress fluids[END_REF] linking the overall yield stress, the overall elastic modulus and the solid volume fraction still applies when bidisperse suspensions are considered. Additionally, we showed that the effect of the particle size heterogeneity onto the overall rheological properties of the yield stress suspension can be described by means of a packing model developed to estimate random loose packing of assemblies of dry particles. We have finally proposed closed form estimates for both the elastic modulus and the yield stress. This shows that it is sufficient to determine φ m and the dependence of the elastic modulus of monodisperse suspension on φ to predict the behavior of bidisperse suspensions; this should remain true for more complex polydisperse cases. An extension of this study to the cases of anisotropic particle distribution and more complex polydisperse suspensions is planned for the future.

Figure 2 :

 2 Figure2: Dimensionless elastic modulus G ′ (φ, λ, ξ)/G ′ (0) as a function of the particle volume fraction φ for all the studied materials (all particle size ratio λ and fine particle proportion ξ). The solid line is the law Eq. 2. The dotted line is the Hashin-Shtrikman lower bound Eq. 4.

  φ λ = 1.00 λ = 3.94 λ = 3.94 λ = 8.25 λ = 8.25 λ = 8.25 λ = 8

φλ

  = 1.00 λ = 3.94 λ = 3.94 λ = 8.25 λ = 8.25 λ = 8.25 λ = 8

Figure 3 :

 3 Figure3: Dimensionless yield stress τ c (φ, λ, ξ)/τ c (0) as a function of the particle volume fraction φ for all the studied materials (all particle size ratio λ and fine particle proportion ξ). The solid line represents the law τ c (φ) = τ c (0) (1 -φ)(1 -φ/φ m ) -2.5φm with φ m = 0.57 proposed by[START_REF] Chateau | Homogenization approach to the behavior of suspensions of noncolloidal particles in yield stress fluids[END_REF] for the monodisperse suspensions.

Figure 4 :

 4 Figure 4: Contact Rigidity threshold φ m of bidisperse suspensions as a function of the fine particle proportion ξ, for several size ratio λ = 2, λ = 3.94, λ = 8.25 and λ = 20.

Figure 5 :Figure 6 :

 56 Figure5: Dimensionless elastic modulus G ′ (φ, λ, ξ)/G ′ (0) as a function of the reduced solid volume fraction φ/φ m for all bidisperse suspensions (all particle size ratio λ and fine particle proportion ξ). The contact rigidity thresholds φ m were calculated using the modified de Larrard model Eqs. 5 to 9.

Figure 7 :

 7 Figure7: Dimensionless elastic modulus G ′ (φ, λ, ξ)/G ′ (0) vs fine particle proportion ξ for suspensions of 80 µm and 315 µm polystyrene beads with solid volume fraction φ = 0.4 (filled triangle) and φ = 0.5 (filled square). The dot (resp. solid) line is Eq. 10 computed for φ = 0.4 (resp. φ = 0.5). The contact rigidity thresholds φ m were calculated using the modified de Larrard model Eqs. 5 to 9.

Figure 8 :

 8 Figure8: Dimensionless yield stress τ c (φ, λ, ξ)/τ c (0) as a function of (1 -φ)G ′ (φ, λ, ξ)/G ′ (0) for all the bidisperse suspensions studied (all particle size ratio λ and fine particle proportion ξ). The figure's coordinates were chosen so that the y = x line represents the theoretical relation Eq. 1.

Figure 9 :

 9 Figure 9: Dimensionless yield stress τ c (φ, λ, ξ)/τ c (0) as a function of (1φ)(1 -φ/φ m ) -1.43 for all the bidisperse suspensions studied (all particle size ratio λ and fine particle proportion ξ). The figure's coordinates were chosen so that the y = x line represents the theoretical relation Eq. 14.

Table 2 :

 2 Dimensionless yield stress τ c (φ, λ, ξ)/τ c (0) as a function of the particle volume fraction

	.00	1.00	1.00	1.00	1.00	1.00	1.00	1.00
	0.10			1.10
	0.15	1.11					1.11
	0.20			1.13
	0.30	1.26		1.32			1.31
	0.40	1.65		1.54			1.60
	0.45	2.26	1.68	1.73	1.75	1.73	1.69	1.69
	0.48	2.87		2.16	1.94	1.65	1.99	1.74
	0.50	3.53	2.45	2.35	2.32	2.03	2.01	1.94
	0.53	5.32	2.81	2.91	3.26	2.16	2.24	2.10
	0.55	8.00	4.27		4.23	2.43	2.41	2.54
	0.57		6.13	4.06	5.34	2.77	2.81	2.59
	0.60			4.58	5.96		3.26	5.07
	0.64			7.30	11.72	7.21		9.06
	0.68						5.64


David J Meder
email: meder@ipd.uni-karlsruhe.de

Walter F Tichy
email: tichy@ipd.uni-karlsruhe.de

Parallelizing an Index Generator for Desktop Search

Keywords: index generator, multicore, parallel software design, parallelization

Experience with the parallelization of an index generator for desktop search is presented. Several configurations of the index generator are compared on three different Intel platforms with 4, 8, and 32 cores. The optimal configurations for these platforms are not intuitive and are markedly different for the three platforms. For finding the optimal configuration, detailed measurements and experimentation were necessary. Several recommendations for parallel software design are derived from this study.

Introduction

Developing multi-threaded applications for multicore computers is challenging. Numeric applications have been parallelized for a wide range of platforms, starting with the Cray vector computer in 1976. Over the years, numeric applications have been ported to all kinds of parallel platforms, including SIMD computers, shared-memory multiprocessors, clusters, grids, multicores, and GPUs. Consequently, the parallelization of numeric applications is well understood, at least in principle. However, little is known about parallelizing the vast number of applications that are non-numeric in nature. Multicore chips now power servers, desktop, and laptop computers and these are primarily used for non-numeric applications. To learn how to parallelize these applications, it is appropriate to perform case studies. By documenting these studies, such as the BZip2 example [START_REF] Pankratius | Parallelizing BZip2: A Case Study in Multicore Software Engineering[END_REF] or the applications covered by Schäfer et al. [START_REF] Schäfer | Engineering Parallel Applications with Tunable Architectures[END_REF], an effective process for parallel software design might emerge. To add to this growing set, we conducted and documented an in-depth study of parallelizing desktop search. Desktop search is performed on PCs, laptops, smart phones, or similar. In its simplest form, it returns a list of files that contain a given combination of search terms. The search uses an inverted index that lists the files in which a given term occurs.

We chose desktop search for several reasons: It is a wide-spread, non-numeric application available on virtually every computing device with a file system, and it is worth parallelizing. The application is simple enough to permit experimenting with alternatives, yet challenging enough in that the optimal solution is not obvious. It is also an I/O intensive application. In an earlier study, Pankratius et al. [START_REF] Pankratius | Does Transactional Memory Keep Its Promises? Results from an Empirical Study[END_REF] conducted a competition among student teams to parallel desktop search. Surprisingly, the team with the best performance used software transactional memory, while the team in second place used locks. However, the two solutions were incomparable, because the teams stored different amounts of data in the index. Furthermore, the competition was performed under time pressure. Quite naturally the question arose what the best performance would be, given enough time to try out several alternatives.

We present our approach on how to parallelize the index generation of desktop search using locks. We provide results for three different platforms: a 4-core and a 8-core Intel platform in our lab and a 32-core Intel platform made available through Intel's public manycore testing lab [START_REF]Intel Manycore Testing Lab[END_REF].

What to Parallelize and how?

Before writing any concurrent code, one has to identify the components that can and should be parallelized. In case of the index generator, there are at least three parts that could be parallelized independently or in combination.

Filename generation: Traverse the directory hierarchy to generate the names of the files to be indexed. Term extraction: Scan files and extract terms. Index update: Add the extracted terms to an index structure.

At the outset of the project, we faced a number of questions: Which of those parts are the dominant ones and worth parallelizing? Is it traversing the file system from some root, opening and scanning individual files, or building the index? Or is the disk the slowest part, in which case there is no hope for significant speed up? None of these questions was answerable without measurement. Furthermore, it was unclear how to parallelize the filename generation and the index update.

Filename Generation

Traversing the directory hierarchy from a given root is an I/O intensive process, whose performance depends on variables such as the number of directories, the number of files contained in directories, the number, transfer rate, and seek times of the installed drives, and the buffering of the operating system. Parallelizing directory traversal is difficult, because directory trees are unbalanced. Another problem is how to distribute the filenames to multiple term extractors in a balanced way, since the file lengths are uneven. Work queues, round-robin distribution, assignment based on file lengths, or work stealing are the main options considered. Concurrent access to the filename data structure or the work queues was likely to slow everything down. We didn't even know whether it was worth parallelizing filename generation.

Term Extraction

The most I/O intensive job of the index generator is reading the files. It was unclear how many threads could be employed for this job before the file system bottlenecked; furthermore, the best configuration was likely to be dependent on platform characteristics, such as clock rate of cores, size of caches, and I/O performance. A single configuration was not going to be optimal for all platforms. Another question was how to handle duplicates of terms: Terms typically appear multiple times in a given document. Should a term be entered into the index every time it is found, or should the term extractor construct a condensed word list without duplicates from each file and then insert the list of terms all at once? The former technique might overwhelm the index with locking requests, while the latter approach might simply duplicate work that the index was well prepared to handle anyway.

Index Update

The main question concerns the relative speeds of index update and term extraction. Would it be enough to let the extractor threads update the index with a synchronized update method, or would it pay to have a separate process for index update that received sets of terms via a buffer? Is synchronization the bottleneck? If so, there is a way to avoid synchronization entirely, by applying a pattern we call "Join Forces". The idea behind this pattern is to let each term extractor build its own index and join the indices at the end. This approach would eliminate all synchronization, except for a barrier before the join operation. Would it be enough to join the indices with a single thread, or should a parallel reduction setup with multiple joining processes be used?

Parallelization

To answer some of the questions posed in the previous section, we needed to get some facts about the performance of the three parts named above. The first step was to set up a benchmark. It consists of about 51.000 ASCII text files and the file size distribution corresponds with file size distribution on a typical personal computer (see [START_REF] Agrawal | A five-year study of filesystem metadata[END_REF] and [START_REF] Douceur | A Large-Scale Study of File-System Contents[END_REF]). On the whole the file set contains about 869 MB of data, created by extracting plain text versions from word processor files. Handling complex word processor formats directly in the term extractor would have been too distracting at the time, even though it would be an interesting extension now. Plain text made scanning faster, but it also made the parallelization problem harder: the faster the term extractor runs, the less opportunity for speedup exists.

Next, we implemented a sequential version of the index generator and timed the individual parts. The execution times are shown in Table 1. Generating filenames only takes 5 seconds, or between 2 to 5 percent of total runtime. With this information, it was clear that parallelizing the file system traversal was unnecessary. To avoid synchronization operations, we decided to use a single thread for the filename generation, which would generate the complete set of filenames in main memory before starting term extraction. The next question was whether scanning the files was worth parallelizing, or whether the whole program was I/O-bound. To decide this, we built an empty scanner, i.e., a loop that simply reads each file byte by byte, but without any term extraction. Reading the benchmark from start to finish takes between 50-80 seconds on the three platforms. Extracting the terms adds another 7-14 seconds. (For more complex formats, this part would take longer.) Now it was obvious that the sequential version was not I/O bound. For confirmation, a back-ofthe envelope comparison with disk transfer and seek times confirmed that there was enough I/O bandwidth for reading multiple files in parallel. However, we still needed a balanced work distribution. After trying a distribution that took file sizes into account, we found that simply assigning files round-robin was the fastest approach. Given k term extractors, the filename generator fills k vectors with filenames in round-robin fashion. Each term extractor then processes its private vector of filenames without any interference or synchronization. Running the filename generator concurrently with the term extractors proved to be highly inefficient, because of a pair of lock operations for every filename inserted or removed from a shared buffer.

The most difficult part concerned the interaction with the index. With a few tests, it became clear that having a single index for all threads was not always a good choice, but we didn't know what the right balance was. It was unclear not only how many threads to use, but also whether the filename generation and the index update should use the same or a different thread count. There are multiple system properties that affect this choice. Filename generation and term extraction largely depend on the number of drives and disk performance. The more drives and the better their performance, the more threads can be employed to scan files. Index update, on the other hand, is mainly influenced by the clock rate of the CPU. A fast CPU can write more terms into the index, so we need fewer threads for this part. The number of available processors, the scheduling policies of the operating system and the size of the caches affect the total number of threads that can be used profitably. Using too many threads typically slows an application down. Only experimentation would answer these questions. The next section provides some of the data points. In some of the experiments, we used the auto-tuner by Schäfer et al. [START_REF] Schäfer | Engineering Parallel Applications with Tunable Architectures[END_REF], but couldn't use it throughout, because this auto-tuner was built for C#, while our implementation was written in C++ for extra speed.

The problem of how to handle term duplicates was not answered by measurement, but by analysis. The question was whether each term extractor should implement a private index for eliminating duplicates, or whether term extractors should insert terms immediately (and potentially repeatedly) into a shared index. The latter solution would be similar to the distributed map-reduce implementation in [START_REF] Dean | MapReduce: Simplified Data Processing on Large Clusters[END_REF]. But we thought that the former solution had higher performance potential. The lookup time would be about the same for both methods. However, the shared index must also store the filename associated with the term. This requirement means that once a term has been looked up in the index, a search must check whether the pair (term, filename) had been added previously (duplicate). This (linear) search for duplicates is eliminated entirely if the term extractor first builds a list of terms for a given file, without duplicates. This list is then entered en bloc, with the filename added. Since each file is scanned exactly once, we need not check whether the filename already exists in this case. We chose to implement this approach in all configurations. This choice also has the benefit of passing large chunks of data from term extractor to index, which reduces the number of buffering and locking operations. Perhaps the distributed map-reduce implementation of index generation would also benefit from this technique.

We implemented the index with a hash map provided by the Boost C++ Library. The duplicate elimination in the term extractors uses a hash set. Both data structures use the FNV1 hash function [START_REF] Noll | FNV hash[END_REF] to calculate the hash values.

Performance Results

The following three alternative designs of the index generator were compared: Design 1: Use a single shared index and lock it on update. Design 2: Replicate the shared index and join the replicates at the end. Design 3: Same as Design 2, but don't join indices (because the search can work with multiple indices in parallel).

We ran implementations of those designs on three systems: A 4-core Intel machine (Intel Core2Quad Q6600, 2.4 GHz, 4 GB RAM, Windows 7 64 bit), a 8-core Intel machine (Intel Xeon E5320, 1.86 GHz, 8 GB RAM, Ubuntu 8.10 64 bit), and a 32-core Intel machine (Intel Xeon X7560, 2.27 GHz, 8 GB RAM, RHEL 4 64 bit). Each of the implementations was run using different numbers of threads for term extraction, index update, and index joining, as discussed in section 2. Any combination of thread counts -for example Design 2 running with 3 threads for term extraction, 3 threads for index update, and 1 thread for joining indices -was run 5 times on each system. We report the averages per platform. The efficiency presented in Tables 2,3, and 4 is defined as The sequential implementation on the 4-core machine takes about 220 seconds. All three parallel designs achieve nearly the same speed-up of about 4.7 (see Table 2). Note the super-linear speed-up, probably due a larger effective cash. The 8-core machine executes the sequential implementation in about 105 seconds, which is almost twice as fast as the 4-core machine. The parallel designs achieve different speed-ups as shown in Table 3. Design 1 takes the most time to execute whereas design 3 achieves the best speed-up of about 2.12 on this machine. For all three, there are more term extractor threads than index threads, compensating for the slower speed of term extraction.

E(p) = S (
On the 32-core machine, the sequential implementation takes about 90 seconds, which is significantly faster than on the 4-core machine. The reason for the runtime difference may be the better I/O performance. In contrast to the 4-core system, the parallel designs achieve different speed-ups, see Table 4. The performance results for this system show that design 1 takes longest to execute with a speed-up of about 1.96, while design 3 achieves a speed-up of 3.5. Because more processors are being used, efficiency is down.

What would happen if all three machines used the same configurations? Table 5 shows the results when using the configurations that proved best on the 4-core computer. Not surprsingly, designs 1 and 2 on the 32-core machine now differ by only 1 second from the 4-core machine; design 3 takes 4.5 seconds less than on

The main lessons from this case study is that even in a simple application such as index generation, the choreography of the various parallel steps is important. There are typically many ways to parallelize a given application, and their performance characteristics can be quite different. Moreover, there is no such thing as the optimal parallel configuration for all platforms. A single, fixed configuration that runs optimally on one platform might run sub-optimally on others, especially when the number and speed of the cores and I/O performance differ.

To arrive at a fast parallel design, one should proceed as follows:

1. Use benchmarks and measurement to identify the components with the highest parallelization potential. 2. Beware of bottlenecks, such as I/O operations and shared data structures with locks. 3. Develop alternative parallel designs, especially those that reduce or eliminate locking. 4. Use back-of-the-envelope analysis with data from 1. to explore alternatives. 5. Experiment with alternatives, where necessary. In particular, test different thread allocations. 6. Use an auto-tuner to speed up exploring the design space.

We presented a rational design process; however this is not how it really happened. We went through a number of dead ends caused by some of the reasons pointed out by Parnas et al. [START_REF] Parnas | A rational design process: How and why to fake it[END_REF]: A lot of design details emerged while implementing the application, and we were influenced by design ideas from previous experience. But presenting a rational process is beneficial nevertheless, as Parnas pointed out [START_REF] Parnas | A rational design process: How and why to fake it[END_REF]: "Those who read the software documentation want to understand the programs, not to relive their discovery. By presenting rationalized documentation we provide what they need."

By contributing this case study we hope to help make parallel software design a more rational and goal-oriented process.

In the future we will analyze how to integrate the search query functionality and parallelize it as well, for instance by using multiple indices. Better work distribution strategies, more file formats, larger benchmarks, and more platforms are additional work items as well as the optimization at runtime.

  p) p with S(p) is the achieved speed-up using p cores and p = min(Number of Threads, Number of Cores).

Table 1 .

 1 Execution times for sequential index generation.

			Execution time (s)
		filename generation	read files	read files and extract terms	index update
	4-core platform	5.0	77.0	88.0	22.0
	8-core platform	4.0	47.0	61.0	29.0
	32-core platform	5.0	73.0	80.0	28.0

Table 2 .

 2 Execution time (seconds), speed-up, and efficiency for the best configurations on the 4-core machine. Each configuration tuple (x, y, z) describes the number of threads used in term extraction, index update, and index join, resp.

			4-core Intel machine
		config. exec. time	speed-up	efficiency
	Sequential	-	220.0	-	-
	Design 1	(3, 1, 0)	46.7	4.71	1.18
	Design 2	(3, 5, 1)	46.9	4.70	1.18
	Design 3	(3, 2, 0)	46.4	4.74	1.19

Acknowledgments. We thank Dr. Victor Pankratius for many fruitful discussions and Christoph Schäfer for experiments with his auto-tuner. We also thank Intel for making the Manycore Testing Lab available.

Table 3. Execution time (seconds), speed-up, and efficiency for the best configurations on the 8-core machine. Each configuration tuple (x, y, z) specifies the number of threads used in term extraction, index update, and index join, resp. the 4-core machine. On the 8-core machine, all three designs run 14 to 28 seconds slower than on the other two machines. By comparison with the preceding tables, the optimal configurations for the 8 and 32 core platforms run significantly faster, so the choice of the optimal configuration matters. One configuration does not fit all platforms! Table 5. Comparison of the execution time (seconds) and speed-up for identical configurations on the 4-core, 8-core, and 32-core Intel machine. The last column shows the execution time differences (expressed as a percentage) of the 8-core machine and 32-core machine compared to the 4-core machine.