Siwar Zouari

Laurent Ranno

Abdelwaheb Cheikh-Rouhou

Pierre Strobel
email: pierre.strobel@grenoble.cnrs.fr

Effect of mixed alkali-element substitution on structural and magnetic properties of praseodymium manganites Pr 0.9 (Na 1-x K x ) 0.1 MnO 3

Keywords: oxides, crystal structure, magnetic properties, ferromagnetism PACS Nb.:, 75.30.Cr, 75.50.Dd, 72.15.Gd

Effect of mixed alkali-element substitution on structural and magnetic properties of praseodymium manganites

Pr0.9(Na1-xKx)0.1MnO3

Introduction

Perovskite-type manganese oxides with general formula Ln 1-x A x MnO 3 , have been extensively studied for their remarkable magnetoresistive properties [1][2][3][4]. Such properties are of a considerable interest for a new generation of magnetic sensors and recording devices. The magnetic behaviour in these systems is very sensitive to the manganese valence, and it can be actually tuned by adjusting the fraction x of substituent A, usually calcium or strontium. Much fewer studies are available on systems containing alkali elements as A substituents to modify the charge distribution in these materials; we are aware of a few studies with Ln = La, Pr or Nd and A = Na or K [5][6][7][8][9][10]. Yet sodium and potassium also have appropriate sizes to occupy the A site of the perovskite structure.

Another important parameter influencing the magnetic properties of perovskitetype manganese oxides has been shown to be the size of the A cation [11,12]. In order to study this parameter independently, many groups investigated Ln 1-x A x MnO 3 systems where A itself is a combination of elements, in general (Sr x Ca 1-x ). Again, the equivalent systems with alkali metal components have been the subject of very few studies, in spite of the fact that they permit a much wider variation in size than the Ca-Sr couple: the ionic radii for 12-fold coordination vary between 1.34 and 1.44 Å for the Ca-Sr couple, compared to 1.39 and 1.64 Å for the Na-K couple [13]. In the alkaline-earth substituted systems, larger ionic radii can be supplied using barium, but to our knowledge no study of combined Ln 1-y (Sr 1-x Ba x ) y MnO 3 is available. In the La 0.85 (Na 1-x K x ) 0.15 MnO 3 system, the Curie temperature at constant doping level was found to be independent of the Na/K ratio [14]. In the equivalent praseodymium system, on the other hand, the magnetic properties have been found to be composition-dependent; they have been analyzed in terms of magnetic clusters above T c , the size of which depends on the Na/K ratio [15]. These studies show the interest of Ln 1-x A x MnO 3 compounds containing both sodium and potassium. This paper thus addresses the structural and magnetic properties in the system Pr 0.9 (Na 1-x K x ) 0.1 MnO 3 .

Experimental

Powder samples of Pr 0.9 (Na 1-x K x ) 0.1 MnO 3 with various values of x have been prepared using the solid state reaction of appropriate amounts of reagent grade praseodymium oxide (Pr 6 O 11 ), manganese dioxide (MnO 2 ), sodium and potassium carbonates (K 2 CO 3 ). The reagents were mixed and ground with mortar and pestle, and fired repeatedly for 36 hours at 1000°C, then at 1150°C in air with intermediate regrinding.

Samples were furnace-cooled to at least 300°C before removal, in order to prevent the formation of oxygen vacancies.

Phase purity, homogeneity and unit cell dimensions were determined by powder Xray diffraction at room temperature in transmission geometry, using a Bruker D8 diffractometer equipped with Cu-Ka radiation and an incident-beam monochromator.

Diffractograms were recorded in the range 21-81° using a step size of 0.02 ° and counting rate 100 s per step. Structures were refined using room-temperature X-ray data by the Rietveld method, using the Fullprof program [16]. Additional chemical analyses were carried out by EDS in a JEOL 840 scanning electron microscope (SEM).

Magnetization measurements versus temperature with magnetic field up to 8 T were recorded by an extraction magnetometer in the temperature range 2-300 K.

Results and discussion

Crystal chemistry

All samples gave X-Ray diffraction patterns indexable in an orthorhombicallydistorted perovskite-type structure. All samples contained a weak impurity identified as apatite-type praseodymium silicate Pr 9.33 Si 6 O 26 (in apatite-structure notation Pr 4.66 (SiO 4 ) 3 O [17] ). The formation of traces of a silicate impurity may be due to slight contamination in the furnace during heat treatments. This phase was included in Rietveld refinements (see Fig. 1). Its fraction was found ≤ 1.5 % in all cases. These results were confirmed by SEM-EDS analysis. The samples consisted of isotropic grains with diameter in the range 2-5 µm.

Global analyses on different samples yielded a fairly constant overall silicon contamination (ca. 1.2 at.% Si), whereas analyses on individual grains yielded either no silicon or much higher silicon contents on a few specific grains. This is consistent with the presence of isolated grains of a second phase. The influence of the apatite phase on the main perovskite phase stoichiometry was checked by freeing the praseodymium or manganese occupation in Rietveld refinements: the shifts from full occupation were found to be negligible (within standard deviations) in both cases. Given the small concentration of the impurity, the absence of manganese in it, and the negligible effect on the perovskite stoichiometry, we assume that the apatite phase does not have any significant effect on the subsequent measurements of magnetic properties.

The main results of structural refinements are summarized in Table 1. A typical Xray pattern, showing calculated and observed profiles, is given in Figure 1. The Pbnm space group was used, with cell parameters in the order c/√2<a<b, which is characteristic of a static O'-type Jahn-Teller deformation in Mn 3+ -containing perovskites [START_REF] Goodenough | Landolt-Börnstein Numerical Data and Functional Relationships in Science and Technology, group III[END_REF]. This system differs significantly from La 0.85 (Na 1-x K x ) 0.15 MnO 3 and Pr 0.85 (Na 1-x K x ) 0.15 MnO 3 [15], where all (La) or the major part (Pr) of compositions have a ≈ b ≈ c/√2, and can therefore be described in a rhombohedral perovskite structure with c 3 R space group. In the Pr 0.9 A 0.1 MnO 3 system, the cell parameter b remains significantly larger than a and c/√2 over the whole range of compositions (see Figure 2). The net result is a monotonous cell volume increase with increasing potassium content. As shown in Fig. 2, the main expansion occurs along the y-axis (b cell parameter), whereas a and c exhibit very small (and parallel) increase with potassium content. The overall variation is consistent with the increase in average ionic radius when replacing Na + by K + .

Mn-O distances are given in Table 2. The Jahn-Teller effect is rather small, as shown previously for potassium-only substitution : unsubstituted PrMnO 3 exhibits two typical long Mn-O distances of 2.16-2.19 Å, which are suppressed for 0.1 K substitution [6]. This trend is confirmed here; the longest distance observed is 2.025 Å (for x = 0.6). The angles in the MnO 6 octahedra also show a limited distortion. Whereas most adjacent O-Mn-O angles in Pr 0.9 Na 0.1 MnO 3 are 85.5 and 94.5°, this distortion decreases with the introduction of potassium : for 0.2 ≤ x ≤ 0.6, all adjacent angles lie within 1.7° from right angles. The distortion increases again at higher potassium content; this trend is especially visible in the evolution of the O1-Mn-O1(a) angle, which goes from 85/95° to 90° for x = 0.4 then to ≈ 86/94° for x = 0.8 (see Table 2).

Magnetic properties

The evolution of magnetization versus magnetic applied field for several temperatures is given in Fig. 3 for x = 0.2 . The magnetization is saturated in 1 T field but a non-negligible high field susceptibility ≈ 0.1 µ B /T is observed. The M(H) curve at 5 K for Pr 0.9 (Na 0.8 K 0.2 ) 0.1 MnO 3 is compared to that in the previously studied composition Pr 0.85 (Na 0.8 K 0.2 ) 0.15 MnO 3 at 5 K in Fig. 4, showing that M is smaller for the higher substitution level (0.15), in agreement with the decrease in spin number of Mn 4+ compared to Mn 3+ . Fig. 5 shows the evolution of spontaneous magnetization at low temperature and of the inverse susceptibility (χ -1 ) extracted from the magnetic isotherms as a function of temperature. The measured spontaneous magnetization at T = 5 K is about 3.5 µ B /f.u., compared to 3.8 µ B /f.u. for the spin-only magnetic moment as expected in a manganese oxide where the Mn orbital moment is quenched. Together with the high field susceptibility, this could indicate a slightly canted ferromagnetic structure or an antiparallel contribution for Pr 3+ ions [10]. However, M(T) data at low temperature do not show any significant anomaly as expected for the occurence of a long-range magnetic of Pr 3+ ions (Fig. 5). In addition, the saturation magnetization is governed only by the Mn 3+ /Mn 4+ ratio, which is constant in this series and almost independent of the Na/K ratio. Such behavior has been observed previously in Pr 0.85 (Na 1-x K x ) 0.15 MnO 3 , with a Mn 4+ content of 30% [15].

The inverse susceptibility curves exhibit a quasi Curie-Weiss behaviour at high temperature, and can be satisfactorily fitted to linear variation above 220 for all samples. Curie temperatures T c and extrapolated Weiss temperatures θ p values (see Table 3) are close to those reported previously for the Pr 0.85 (Na 1-x K x ) 0.15 MnO 3 series [15].The increase in T c with potassium substitution can be correlated with the decrease in Mn-O octahedron distortion -see especially the evolution of O-Mn-O bonding angles in Table 2. T c indeed goes through a maximum for intermediate (Na, K) compositions, just as the bonding angles get closer to 90°C for mixed (Na, K) compositions. The Weiss temperatures θ p are all widely positive (between 140 and 150 K), indicating that the dominating interactions are ferromagnetic. Mn 3+ and Mn 4+ , present in the Pr 0.9 (Na 1-x K x ) 0.1 MnO 3 series with average manganese valence equal to 3.20+, have spin-only moments given by g = 2 and S = 2 or S = 3/2. The measured inverse susceptibility curves give Curie constant values that are much higher than that expected ones from paramagnetic susceptibility of free manganese ion, indicating the presence of magnetic clusters. Some possible clusters of Mn 3+ and Mn 4+ together are defined in the Curie constant According to this model, and using the experimental C(T) values, it is possible to deduce the size of the manganese cluster n as a function of temperature. Fig. 6 shows that the n value decreases when T increases. The size of the cluster is about to 2-3 Mn ions. This value is smaller than in the Pr 0.85 (Na 1-x K x ) 0.15 MnO 3 system (5-8 Mn ions) [15]. The difference may be explained by the increase in Mn 4+ content in the latter series.

Conclusions

The solid solution systems Ln 1-y (Na 1-x K x ) y MnO 3 . allow to study the physical properties of perovskite-type manganese oxides with the A-site size as only variable, while keeping the manganese valence constant through a fixed value of y. The mixed alkali substitution allows a much wider average size variation on the a-site than the more widely studied alkaline-earth systems. Using a rather small doping level (y = 0.10), we confirm here that potassium depresses the static Jahn-Teller distortion in the praseodymium system.

Consistent with previous studies on the Pr-K-Mn-O system with variable manganese valence [6,10], this study confirms that alkali element substitution in Pr manganites induces a transition from antiferromagnetism to canted ferromagnetism. The uncommon values of Curie constants are consistent with a cluster model, with a number of Mn atoms in the cluster equal to 2-3. This is a consistent with previous results on the same system with higher doping level (y = 0.15), which correspond to larger clusters [15]. Pr 0.9 K 0.1 MnO 3 [6] 125

Figure Captions

Fig. 1 .

 1 Fig. 1. Observed (points) and calculated (continuous line) X-ray powder diffraction patterns for Pr 0.9 (Na 0.8 K 0.2 ) 0.1 MnO 3 . The lower part shows the difference Iobs-Icalc. Vertical bars indicate the positions of reflections of the perovskite phase (upper row) and of the apatite-type phase (lower row).

Fig. 2 .

 2 Fig. 2. Evolution of cell parameters with x along the Pr 0.9 (Na 1-x K x ) 0.1 MnO 3 series (a: triangles up, b squares, c/√2 triangles down).

Fig. 3 .

 3 Fig. 3. Evolution of magnetization M versus applied magnetic field at different temperatures for Pr 0.9 (Na 0.8 K 0.2 ) 0.1 MnO 3 .

Fig. 4 .

 4 Fig. 4. Comparison of M(H) curves at 5 K for two samples with same Na/K ratio and different average Mn valences : Pr 0.9 (Na 0.8 K 0.2 ) 0.1 MnO 3 (circles) and Pr 0.85 (Na 0.8 K 0.2 ) 0.15 MnO 3 (squares).

Fig. 5 .Fig. 6 .

 56 Fig. 5. Temperature dependence of the saturated magnetization and the inverse susceptibility for Pr 0.9 (Na 1-x K x ) 0.1 MnO 3 .

Fig. 1 .

 1 Fig. 1. Observed (points) and calculated (continuous line) X-ray powder diffraction patterns for Pr 0.9 (Na 0.8 K 0.2 ) 0.1 MnO 3 . The lower part shows the difference Iobs-Icalc. Vertical bars indicate the positions of reflections of the perovskite phase (upper row) and of the apatite-type phase (lower row).

Fig. 2 .

 2 Fig. 2. Evolution of cell parameters with x along the Pr 0.9 (Na 1-x K x ) 0.1 MnO 3 series (a: triangles up, b squares, c/√2 triangles down).

Fig. 3 .Fig. 4 .

 34 Fig. 3. Evolution of magnetization M versus applied magnetic field at different temperatures for Pr 0.9 (Na 0.8 K 0.2 ) 0.1 MnO 3 .

Fig. 5 .Fig. 6 .

 56 Fig. 5. Temperature dependence of the saturated magnetization and the inverse susceptibility for Pr 0.9 (Na 1-x K x ) 0.1 MnO 3 .

Table 1 .

 1 Results of Rietveld refinements for various Pr 0.9 (Na 1-x K x ) 0.1 MnO 3 compositions.

	Space group Pbnm.
	x		0	0.2	0.4	0.6	0.8
	Cell parameters (Å)
		a	5.4590(2) 5.4587(2) 5.4594(2) 5.4623(3) 5.4645(4)
		b	5.4666(2) 5.4749(2) 5.4764(2) 5.4899(3) 5.5002(4)
		c	7.7154(3) 7.7181(3) 7.7191(3) 7.7235(3) 7.7231(5)
	Positional and thermal parameters
	Pr,Na,K	x	0.997(2)	0.995(1)	0.995(1)	0.994(1)	0.995(1)
	(4c)	y	0.0271(4) 0.0298(3) 0.030(3)	0.032(3)	0.032(4)
		z	0.25	0.25	0.25	0.25	0.25
	B(Å 2 ) 0.65(4)	0.69(4)	0.70(3)	0.52(4)	0.58(5)
	Mn (4b:)	x,	0.5	0.5	0.5	0.5	0.5
		y	0	0	0	0	0
		z	0	0	0	0	0
	B(Å 2 ) 0.28(5)	0.20(5)	0.26(5)	0.41(5)	0.41(7)
	O1 (4c) †	x	0.089(7)	0.069(6)	0.074(5)	0.079(5)	0.090(6)
		y	0.482(4)	0.488(3)	0.488(3)	0.485(3)	0.473(4)
		z	0.25	0.25	0.25	0.25	0.25
	O2 (8d) †	x	0.722(6)	0.717(5)	0.724(5)	0.721(4)	0.723(5)
		y	0.288(5)	0.285(3)	0.287(3)	0.292(3)	0.269(5)
		z	0.027(4)	0.039(3)	0.040(3)	0.036(3)	0.038(3)
	Statistical parameters
	N-P+C	2905	2828	2816	2828	2856
		R wp	7.44	8.24	7.82	8.44	10.4
		R exp	6.53	3.86	3.89	7.61	5.06
		χ 2	3.68	4.56	4.04	3.82	9.52
	R Bragg	2.12	2.89	3.21	4.45	5.10
	† B fixed to 1.0.

Table 2 .

 2 Main Mn-O distances and angles throughout the Pr 0.9 (Na 1-x K x ) 0.1 MnO 3 series

	Interatomic distances (Å)
	Mn-O 1 (×2)	1.993(5)	1.971(3)	1.973(5)	1.980(4)	1.998(4)
	Mn-O 2 (×2) (a)	1.921(14)	1.936(7)	1.930(9)	1.925(9)	1.939(15)
	Mn-O 2 (×2) (b)	1.998(13)	2.005(7)	2.015(9)	2.025(9)	1.997(15)
	Interatomic angles (°)
	O1-Mn-O1	180	180	180	180	180
	O1-Mn-O2 (a)	85.0/95.0(8)	89.8/90.2(6)	90.0(6)	88.3/91.7(6)	86.2/93.8(8)
	O1-Mn-O2 (b)	86.6/93.4(9)	89.3/90.7(6)	89.1/90.9(7) 89.6/90.4(7)	89.9/90.1(9)
	O2-Mn-O2	89.1/90.9(9)	88.6/91.4(5)	88.5/91.5(7) 88.7/91.3(7) 89.3/90.7(10)

Table 3 .

 3 Curie and Weiss constants for various compositions

	sample composition	T c /K	θ p /K
	Pr 0.9 (Na 0.8 K 0.2 ) 0.1 MnO 3	130	154
	Pr 0.9 (Na 0.6 K 0.4 ) 0.1 MnO 3	135	150
	Pr 0.9 (Na 0.4 K 0.6 ) 0.1 MnO 3	137	145
	Pr 0.9 (Na 0.2 K 0.8 ) 0.1 MnO 3	140

Acknowledgments

The authors gratefully acknowledge Région Rhône-Alpes for financial support of S.

Zouari (MIRA Program).


P Strobel

J Tillier

A Diaz

A Ibarra-Palos

F Thiéry

J B Soupart

Search for new manganese-cobalt oxides as positive electrode materials for lithium batteries

Two new mixed manganese-cobalt oxides for lithium battery positive electrode materials were obtained using original synthesis routes. Compound I, "LMCO" is a new form of LiMnCoO 4 obtained by ion-exchange from NaMnCoO 4 . Compound II, "MCO" is a nanometric material with formula Mn 1-x Co x O ≈2 obtained by quenching in specific conditions. We showed recently that the electrochemical properties of this materials were dramatically enhanced by cobalt doping [Strobel et al., J. Mater. Chem. 15 (2005) 4799]. The effect of cobalt content on its electrochemical behaviour is reported in detail here. Compound I gives rise to two reversible single-phase intercalation reactions centered at 2.7 and 4.4 V on discharge, corresponding to Co 3+ /Co 4+ and Mn 3+ /Mn 4+ redox couples, respectively.

The initial capacity is 160 mAh/g at low regime, but stabilizes at ca.100 mAh/g on extended cycling. Compound II gives a single plateau with a much higher capacity. An optimum ratio of Co:Mn = 0.20 was found and gives a capacity of 175 mAh/g after 60 cycles in the potential window 2.0-4.2 V.

Introduction

LiCoO 2 with NaFeO 2 -type structure is the best positive electrode material for rechargeable lithium batteries so far. Many efforts are underway to replace part or all cobalt by cheaper and environmentally friendlier elements. Manganese is one of the most attractive alternates, and numerous manganese compounds (spinel, layered, amorphous oxides) have been considered as positive electrode materials [1,2]. Interestingly, cobalt, as a dopant, has a very positive effect on the electrochemical performances of manganese oxides. This has been established in the Li-Mn-O phases with spinel [3][4][5][6][7], birnessite [8,9], orthorhombic [10] and monoclinic LiMnO 2 [11].

This paper reports results of search for new Mn-Co oxides for lithium intercalation in two different systems. The first example concerns a new phase derived from NaCo 2 O 4 . This sodium cobaltate was first described by Jansen and Hoppe in a layered structure, space group P6 3 /mmc, a = 0.2843 nm, c = 1.0811 nm [12]. Li et al. [13] recently showed that up to 50 % Co can be replaced by Mn, yielding NaCoMnO 4 with a similar structure and a slightly expanded unit cell (c = 1.128 nm). We repeated the preparation of NaCoMnO 4 and used this phase as a precursor to obtain a lithium derivative, LiCoMnO 4 , by ion exchange. Its electrochemical behaviour as positive electrode vs. lithium will be reported here.

The second example is a nanometric MnO ≈2 . An X-ray amorphous manganese oxide was reported to form by quenching in a narrow temperature range around 370°C by Feltz et al. [14]. We recently showed that this material is in fact nanocrystalline, and that it is an interesting positive electrode material for lithium batteries ; last but not least, copper or cobalt substitution was found to induce a large improvement in capacity retention, with cobalt superior to copper as a dopant [15]. The initial dopant concentration was rather arbitrarily chosen at M:Mn = 0.20. We present here a study of the electrochemical behaviour of material for variable cobalt doping levels varying between 0 and 0.30 (as molar Co/Mn).

Experimental

The synthesis of LiCoMnO 4 , hereafter abbreviated LCMO, includes two steps. NaCoMnO 4 was first prepared by solidstate reaction of appropriate proportions of sodium carbonate, Co 3 O 4 and β-MnO 2 powders. The mixture was ground in an automatic grinder/mixer for 30 minutes under ethanol, then transferred to an aluminum boat and fired at 1000°C for 18 hours under oxygen flow [13]. This sequence was repeated twice to yield phase-pure NaCoMnO 4 . In a second step, the latter was treated in LiCl-LiNO 3 eutectic at 280°C for 6 hours, then rinsed in hot distilled water.

The preparation of Mn 1-x Co x O ≈2 was described previously [15]. In short, it consists in firing a freshly coprecipitated Mn-Co carbonate in air at 370 ± 5 °C, followed by quenching between metallic plates in air. The product is an oxide consisting of homogeneous microspheres with diameter ca. 1 µm [14]. Four samples were prepared with Co/Mn molar ratios 0.05, 0.10, 0.20 and 0.30; they will be we abbreviated hereafter MCO-05, MCO-10, MCO-20 and MCO-30, respectively.

All products were characterized by X-ray diffraction (XRD) using a Siemens D5000 diffractometer with Cu Kα or Fe Kα radiation, mounted in transmission geometry. Cell parameters were determined by a least squares method.

The morphology of samples was investigated using a Jeol 840 scanning electron microscope. Cationic ratios were determined by EDX analysis coupled with the SEM.

Positive electrode paste was prepared from intimate mixtures of the oxides with carbon black and PTFE emulsion in weight ratio ca. 70:20:10. The paste was laminated to 0.1 mm thickness, cut into pellets with diameter 10 mm and dried at 240°C under vacuum. These conditions were found adequate to dry completely the pellets. Typical active material masses used were in the range 5-15 mg. Electrochemical tests were carried out in liquid electrolyte at room temperature using Swagelok-type batteries at room temperature. The electrolyte was a 1 M solution of LiPF 6 in EC-DMC 1:2 (Merck Co.). Negative electrodes were 200 µm-thick lithium foil (Metall Ges., Germany). Cells were assembled in a glove box under argon with ≤ 1 ppm H 2 O. Electrochemical studies were carried out using a MacPile Controller (Bio-Logic, Claix, France) in either galvanostatic mode or by step-potential electrochemical spectroscopy (SPES), using typically 10 mV/30mn steps.

Results and discussion

Structural characterization

-LCMO : An XRD pattern of freshly prepared LCMO is shown in Figure 1. It is not single-phase. The data can be ascribed to a majority LiMO 2 -type layered phase and a minority spinel one. Refined cell parameters are: a = 0.2829(1) nm, c = 1.469(2) nm for the layered phase (most probable space group R-3m), a = 0.8229(6) nm for the spinel phase. The weight fraction of the minority phase is ca. 12 %. These results show that the hexagonal lithium phase formed has a different layer stacking from that in the sodium parent phase (c = 1.128 nm). In spite of the proximity of the second phase cell parameter with that of LiMn 2 O 4 (a = 0.824 nm), the impurity is probably an intermediate phase between CoMn 2 O 4 (a = 0.839 nm) and Co 3 O 4 (a = 0.808 nm) This can be inferred from the high intensity of the 220 reflection (at 2θ = 38.5° in Figure 1); since this reflection is essentially due to the contribution of the spinel A-site cations, it would have negligible intensity if this site was occupied by light lithium atoms.

The hexagonal phase obtained using this route differs significantly from a previously reported Li x (Co 1/2 Mn 1/2 )O 2 , which has c = 1.445 nm [16]. It is also a different phase from the spinel-type with similar stoichiometry LiCoMnO 4 , which has been obtained by direct thermal synthesis and exhibits a cubic cell parameter a = 0.8052 nm [17]. The use of a lowtemperature, topotactic synthesis route thus allowed to prepare a particular form of Li x (Co 1/2 Mn 1/2 )O 2 , which is probably metastable. First-principles calculations indeed showed that phase separation between LiMnO 2 and LiCoO 2 is expected at equilibrium [18] A close look at Figure 1 shows widely variable diffraction line widths for the hexagonal phase : compare for instance reflections 108 and 110 (in the 82-86° range for Fe Kα radiation). A detailed investigation of the structure of LCMO, including Rietveld refinement, will be published elsewhere [19].

Finally, it should be noted that this compound readily picks up water when stored in air atmosphere, and this induces remarkable changes in its XRD pattern. Thermogravimetric analysis and variable-temperature XRD measurements show that this phase transition occurs on heating at ca. 200°C, and that it is reversible. More details about these features will be described elsewhere [19]. -MCO: Figure 2 shows that all quenched MCO samples give only a few very broad diffraction peaks, whereas an unquenched sample shows distinct reflections corresponding to a mixture of Mn 2 O 3 and spinel. Electron diffraction shows that quenched MCO samples are not amorphous, but nanocrystalline [14]. A typical SAED diagram of MCO-20 is shown in Figure 3. The cobalt content is found to have a negligible on the structural and microstructural properties of MCO.

Physico-chemical characterization

SEM observation shows a very different morphology for LCMO and MCO samples (see Figure 4). The former form plate-like grains as expected for a layered material, with a wide distribution in size. On the contrary, the latter form very uniform hollow spherical aggregates with sphere diameter close to 1 µm. This particular morphology is somewhat unexpected ; it is mostly encountered in synthesis routes including the decomposition of liquid droplets, such as spray pyrolysis [20]. EDX analysis on numerous grains gave following results : in LCMO, the residual sodium was below detection level; in MCO, the Co/Mn ratios was consistent with the nominal one within experimental errors. The manganese oxidation state was checked for several MCO samples and found to be equal to 3.60 ± 0.05, whatever the cobalt content.

Electrochemical behaviour -LCMO

Slow-scanning step-potential measurements in the voltage window 2.0-4.8 V show that LCMO undergoes two separate, reversible, reactions centered at ca. 4.4 and 2.7 V on reduction (see Figure 5). The evolution of the current during potential steps in the peaks (not shown), as well as the overlap in potential between the reduction and oxidation peaks indicate that both reactions are single-phase. In view of previous data on neighbouring Mn and Co systems [16,17,20], the upper and lower potential peaks are ascribed to Co 3+ /Co 4+ and Mn 3+ /Mn 4+ redox reactions, respectively. Oddly enough, the upper reaction potential seems to shift to lower potentials with increasing cycle number (see the enlargement of the reduction curve in the 3.6-4.6 V region in Figure 5, bottom). No double current peak at 4 V typical of a transformation into spinel [21] was detected, even after 15 cycles. The corresponding S-shape plateaus on the chargedischarge curve are shown in Figure 6. The initial total specific capacity Q s is about 160 mAh/g. The capacity fraction above 4V is low (ca. 60 mAh/g), and could probably be extended by charging at higher voltages; however this voltage range leads to instabilities in the cells used.

The evolution of capacities on extended cycling is shown in Figure 7. The lower potential capacity is stable or even increases on cycling, while the upper potential one decreases. However, one cannot rule out parasitic oxidation problems at high voltage, and the present results for the upper voltage plateau may not reflect the intrinsic properties of the material. Previous reports on Li-Mn-Co-O layered materials showed capacities above 4V starting at ca.90 mAh/g and constantly decreasing [16], or higher capacities with a tendency to transformation to spinel for lower cobalt contents [21].

Electrochemical behaviour -MCO

For composition MnCo 0.2 O ≈2 (MCO-20), initial capacities as high as 180 mAh/g have been found on a single plateau at ca. 2.7 V [14]. The electrochemical behaviour of other MCO's materials with Co:Mn ratios varying between 0.05 and 0.30 is presented in figures 7 (charge-discharge cycling) and 8 (voltammetric cycling). All compounds in this series exhibit a rather similar behaviour at first glance. Some significant differences can be noted, however : Figure 8 shows that while the initial capacity is comparable for MCO-05, MCO-10 and MCO-20, it is about 15 % lower for MCO-30. On the other hand, MCO-20 shows the flattest plateau (in both discharge and charge), which also shows up as sharper peaks in the voltammogram (Figure 9). Finally, Figure 9 shows a slight, but systematic shift in the potentials of oxidation and reduction peaks as a function of cobalt content: the peak positions in Figure 9 (for both reduction and oxidation) lie at a higher potential for lower cobalt content. This result may seem surprising, but it should be recalled that XANES measurements showed that cobalt initially enters MCO-20 as Co 2+ and is inert from the redox chemistry point of view during the first discharge [15]. The shift in potential probably reflects variations in the manganese energy levels as a result of the perturbation of the Mn-O bonding due to the presence of cobalt. Regarding the behaviour on extended cycling, remarkable differences arise as a function of cobalt content. As shown in Figure 10, the capacity decreases quickly on cycling as soon as the Co:Mn ratio departs from 0.20. This effect is especially severe for Co:Mn = 0.30 which, unexpectedly, shows very strong capacity fading. The reasons for the existence of an optimum cobalt/manganese ratio are unknown so far, and probably difficult to establish precisely, given the difficulties in gathering accurate structural information about such nanocrystalline materials.

Conclusions

In this paper, we address the electrochemical performances in lithium batteries of two new manganese-cobalt oxides. The first one, rhombohedral LiMnCo 4 ("LMCO"), is a layered oxide with long-range crystalline ordering, where manganese and cobalt behave independently from the oxydo-reduction point of view. A significant capacity is obtained at high potential (ca. 4.4 V), but important capacity fade is observed in this voltage region, as in previous studies of Mn-Co oxides with neighbouring structures [16 ,20]. Oddly enough, the 3 V intercalation reaction, involving the Mn 3+ /Mn 4+ redox couple, is much more stable on cycling, in spite of the unavoidable Jahn-Teller deformation associated with the presence of the Mn 3+ oxidation state. The strains induced by the Jahn-Teller effect are probably relaxed by the presence of an important fraction of cobalt in the structure.

The second compound under study (MCO) is odd in several respects. It is nanocrystalline and forms micrometric, perfectly spherical aggregates. Electrochemically, it exhibits a single redox step centered around 2.7 V on discharge, the position of which is only slightly dependent on cobalt content. Contrary to the LCMO case, no specific plateau attributable to cobalt redox reactions is observed, even for relatively high cobalt content such as Co:Mn = 0.30.

The most remarkable feature of MCO is the excellent cycling stability of the compound with Co:Mn = 0.20, which could be cycled to 50 cycles with very small capacity fading (see Figure 11). A surprising result is the detrimental effect of higher cobalt substitution levels. Further studies are required to elucidate the exact role of cobalt, and the evolution of the cobalt valence after the first discharge.

Fig. 1 .

 1 Fig. 1. XRD pattern of LCMO. The indexation of the main reflections is indicated.

Fig . 2 .

 2 Fig .2. XRD pattern of MCO samples with various cobalt contents (Co:Mn molar ratios indicated). The pattern of standard MnCO 3 recorded in the same conditions, is included for comparison (top).

Fig. 3 .

 3 Fig. 3. Selected area electron diffraction pattern of a crystallite from sample MCO-20.

Fig. 4 .

 4 Fig. 4. SEM micrographs of typical grains of LCMO (top, 40 µm full scale) and MCO (bottom, 18 µm full scale).

Fig. 5 .

 5 Fig. 5. Top: slow-scanning voltammogram (10 mV/30 mn) of LiCoMnO 4 in the potential range 2.0-4.8 V vs. Li/Li + ; bottom: enlargement of the first reduction peak region for cycles 1 to 3 (cycle numbers indicated).

Fig. 6 .

 6 Fig. 6. First charge-discharge cycle of LCMO at C/10 regime.

Fig. 7 .

 7 Fig. 7. Evolution of cycling capacity of LCMO with cycling (C/10, potential window 2.0-4.8 V).

Fig. 8 .

 8 Fig. 8. First charge-discharge cycles at C/20 of MCO materials for Co:Mn ratios 0.05 to 0.30.

Fig. 9 .

 9 Fig. 9. Slow-scanning voltammograms(10 mV/30 mn steps) of MCO materials for Co:Mn ratios 0.05 to 0.30. All curves are normalized to 10 mg active material.

Fig. 10 .

 10 Fig. 10. Comparison of the capacities on 1st, 2nd and 10th discharge as a function of cobalt content (C/20 regime).

Fig. 11 .

 11 Fig. 11. Comparing the evolution of capacity on cycling for layered LiCoMnO 4 (C/10) and X-ray amorphous MnCo 0.2 O 2 (C/20). Potential windows as in Figures 6 and 8.

  Fig. 11. Comparing the evolution of capacity on cycling for layered LiCoMnO 4 (C/10) and X-ray amorphous MnCo 0.2 O 2 (C/20). Potential windows as in Figures 6 and 8.

Acknowledgments

The authors thank C. Darie and S. Pairis for their assistance in SEM measurements.


Tanguy Raynaud

Julien Subercaze

Delphine Boucard

Vincent Battu

Frédérique Laforest

Fouilla: Navigating DBpedia by Topic

Navigating large knowledge bases made of billions of triples is very challenging. In this demonstration, we showcase Fouilla, a topical Knowledge Base browser that offers a seamless navigational experience of DBpedia. We propose an original approach that leverages both structural and semantic contents of Wikipedia to enable a topic-oriented filter on DBpedia entities. We devise an approach to drastically reduce the query time and to ensure a seamless browsing experience to the end user. We demonstrate how our system offers a novel and meaningful experience of DBpedia browsing by challenging the user to search for relevant information within the Knowledge Base in different use cases.

INTRODUCTION

The construction of Knowledge Bases is a very active domain in both industry and academia. Within the Semantic Web community, a large movement emerged to automatically or manually build Knowledge Bases, especially using Wikipedia as input. Projects such as DBpedia [START_REF] Lehmann | DBpedia-a large-scale, multilingual knowledge base extracted from Wikipedia[END_REF], Yago [START_REF] Suchanek | Yago: a core of semantic knowledge[END_REF], Wikidata [START_REF] Vrandečić | Wikidata: a free collaborative knowledgebase[END_REF] are the most famous representatives of this movement. These Knowledge Bases are stored using some triple representation such as the Resource Description Format (RDF) standard. The DBpedia 2014 instance contains for example more than 3 billion triples and serves as one of the central interlinking hubs in the Linked Open Data on the Web [START_REF] Lehmann | DBpedia-a large-scale, multilingual knowledge base extracted from Wikipedia[END_REF]. These data were intended for machine-to-machine exploitation; but a suitable presentation makes them also relevant directly for end users. For instance a list of facts concerning a famous person can be more constructive than reading a long biography, particularly if this list is restricted to a particular topic that interests the most the reader. For example, one can be interested in Yannick Noah's music, his navigation should be restricted to the topic of Music, even if he is also well known as a tennis player. However, finding relevant information among the several billions of triples contained in those datasets is a tedious task for the end-user. For instance, the DBpedia Italy page alone contains several thousands triples, displayed without order. Such an amount of triples generally leads to user resignation, considering the time needed to find the required piece of information.

In this paper, we introduce the concept of Topical browsing. Our aim is to enable browsing among large Knowledge Bases, by displaying to the end user, for each topic, only pertinent elements. The end user can therefore find adequate information without SPARQL knowledge. Faceted browsing [START_REF] Ross | A faceted query engine applied to archaeology[END_REF] has been extensively covered by the semantic web community [START_REF] Dali | Query-independent learning to rank for RDF entity search[END_REF][START_REF] Ding | Finding and ranking knowledge on the Semantic Web[END_REF][START_REF] Hogan | Reconrank: A scalable ranking method for semantic web data with context[END_REF], it consists of filtering data by several criteria (i.e. date, language, etc.) restricted to the ontology classes and properties. In Topical Browsing, the user selects a topic (e.g. History), navigates among entities related to this topic and sees only the triples that concern this topic. For example, a user is interested in Italy through the prism of Sports while another through the prism of Word War II. For each of these topics, the relevant triples of the Italy entity differ. In such circumstances, faceted browsing offers no solution to retrieve the entities relative to a defined topic if the knowledge graph does not explicitly contain an adequate relation (such as ' Romans partOf History'). On a huge dataset like DBpedia, topical browsing presents its very own challenges:

Topics. Identifying topics, delimiting their boundaries in terms of relevant items are the main encountered issues.

Efficient browsing. Despite the size of the dataset, the user shall not wait endlessly for queries to complete.

We demonstrate a fully functional system called Fouilla [fuja], aiming to provide to end users a meaningful browsing experience among the billions of triples of DBpedia. To build the topical dataset, our approach uses both the structural and semantic information present in Wikipedia. For each navigation action, Fouilla returns only entities and triples relevant to the chosen topic and offers a seamless browsing experience. Moreover, it allows users with no SPARQL experience to efficiently browse Knowledge Bases made of several billions of triples. Readers can experiment Fouilla at the following url: http://demo-satin.telecom-st-etienne.fr/fouilla/.

The paper is organized as follows. Section 2 presents our approach to identify topics, extract and rank relevant facts. Section 3 deals with scalability issues with ranking queries.Section4 discusses our demonstration settings.

TOPICS BUILDING AND PROVISIONING

Topical browsing experience relies on two major criteria. First, the topics titles and their content must be understandable as they are by the users, they must reflect common sense expectations. Second, the elements must be displayed in a meaningful order, that is, the elements must appear ranked by their relevance to the topic. Figure 1 presents an overview of the three steps involved in Fouilla for the creation of the topical database.

Topic Identification

To identify the set of topics, we leverage the bijective link between DBpedia and Wikipedia: each DBpedia resource URI corresponds to a Wikipedia article name. Wikipedia contains structural and navigational information that are not present in DBpedia. Such information is the raw material for topic identification. Structural and navigational information encompass all Wikipedia resources that do not offer encyclopedic content but have been created to structure the online encyclopedia and to ease the navigation of the end user. Fouilla uses different kinds of Wikipedia structural information to compute the Topic Identification step: Portals carry semantics about the pages they link to. A portal serves as en entry point to navigate Wikipedia in a specific area e.g. Geography, or more precisely, China. As we write this paper, Wikipedia offers more than 1490 portals and among them, 173 are featured portals. Featured portals2 have been cherry picked by Wikipedia editors as high-quality portals about general subjects and are therefore good candidates for our set of topics.

Outlines are special pages that provide a hierarchical list which presents the more relevant articles and categories associated with a given subject. The resources linked by Outlines can per consequent be safely considered as highly relevant to the corresponding subject. Outlines are categorized in a main page 3 .

Lists are meta pages that provide a list of articles which are, in one way or another, relevant to a common subject.

In order to define the set of topics, Fouilla takes advantage of the aforementioned information contained in Wikipedia. In order to identify the topics automatically, the structure of Wikipedia is entirely analyzed, and data from featured portals, top level categories, and outlines are extracted and combined to finally obtain a list of 50+ topics. This list is available at the following URL: http://datasets-satin.telecom-st-etienne.fr/traynaud/Topics.html.

Topic Delimitation

Our next step is to determine which DBpedia triples are of interest for each topic. The huge number of triples, namely several billions, makes this task clearly the main challenge in the creation of our topical browsing system. In order to associate topics with the corresponding DBpedia triples, our approach consists of two steps.

The first step aims to bind topics with highly relevant pages by taking advantage of the structural and navigational information provided by Wikipedia. Our topic delimitation method uses a combination of data extracted from the Outlines and a supervised crawling of the Categories. Even if Outlines in Wikipedia do not follow a fixed format, they offer a great entry point for each corresponding topic: an empirical analysis has shown that all articles, categories and Lists of articles linked from Outlines can be considered as of the utmost interest regarding a topic. A supervised crawling on the Categories is then used to complement the set of relevant articles. In order to avoid the insertion of unrelated articles, a recursive crawling filters any branch that leads to a cycle, and The second step enlarges the set of relevant articles obtained in step 1. While structural and navigational information provides us with highly relevant pages, due to their very nature, relevant articles may not be enlisted in these resources. The initial set was constructed using structural information from Wikipedia. To offer a complementary approach, this second step relies on the content of articles: we include additional articles that are semantically close to the articles extracted at step 1. For this purpose, we use Latent Semantic Analysis (LSA) [START_REF] Wiemer-Hastings | Latent semantic analysis[END_REF]. LSA bases the similarity measure on a matrix of word count for each article, processed with the method of cosine distances. To ensure high quality results, we leverage the pagerank distribution of articles within a topic. We experimentally noticed that pagerank follows a similar distribution across the topics; Figure 2 shows this distribution. We then use the most relevant pages as input to the LSA, that is, we leverage derivative information to induce a cut before the pagerank score stagnation. We observe that half the articles obtained by LSA are not redundant with those obtained in the first step. This semantic expansion allows us to obtain the desired result: increasing recall while not having to trade for precision.

Triples Ranking & Filtering

After the expansion step, we operate a final cut to ensure that irrelevant entities and triples are discarded. During the topic identification step, we computed a per-topic pagerank on the subgraph of articles obtained from structural information. We here recompute such a pagerank, including elements obtained with LSA. This pagerank provides us with a relevance score for each article within the topic. We consider as significant within a topic, the pages that are strongly related within the graph, using a similar technique as the one to restrict the LSA input, i.e. based on the derivative of the distribution. This cut approach based on the derivative is generic and enables us to compute a per-topic threshold as opposed to a global threshold, that would lead to poor results. Once again, regarding the pagerank distribution, we consider as semantically unrelated any article located beyond curve stagnation.

SCALABILITY AND USER EXPERIENCE

Data storage relies on an open-source RDBMS, following the schema depicted in Figure 3. Each DBpedia concept is assigned a unique integer ID through the table pagedictionary, their pagerank per topic are to be found in the table pagerank. The triples are represented in the table dbpedia_statements. Querying the database is very efficient for listing top-k entities for a given topic, thanks to indexes on pagerank. However, for listing top-k triples for a specific topic, the database must compute a slow query: an aggregated score is computed for each triple, then the results are sorted and displayed. The table pagerank contains more than 20M rows. Even with a carefully tuned server and NVM-E disks, these queries run in over 15 seconds, which is not acceptable for the end user experience. To address this issue, we rely on the pagerank distribution presented in Figure 2. Our intuition is that removing the tail of the pages in each topic will not affect the ordering of the top-k, for reasonable values of k. For this purpose, we experimented different cuts in the data, based on the pagerank value. We evaluated their influence on the rank, as well as the query speedup. To take fully advantage of the cut, we added an index on (topic_id,pagerank) on table pagerank.

To evaluate the influence of cuts on ranking, we use the normalized discounted cumulative gain (NDCG), which is a standard measure in information retrieval. The NDCG (∈ [0, 1]) measures the quality of a ranking against an ideal ranking. In our case the ideal ranking is the one obtained without limit on the pagerank values. The second valuable measure is the query speedup obtained via the cut. Table 1 summarizes our experiments, for NCDG up to the 100th item, which is equivalent to 10 pages of browsing. The experiments validate our intuition insofar as for the first value of the cut (5.10 -5 ), we are able to obtain a significant average speedup of 6 times against a minimal impact on the NDCG (0.99). For greater values, the trade-off becomes less acceptable. One of the most important insights from Table 1 is that, the larger the topic, the greater the speedup. For instance for the topic Politics containing 1.2M items, the speedup is much greater than the average over all topics. From a practical point of view, this means that the slowest queries are the ones that benefit the most from the cut. Since the number of items is greatly reduced, the n • loд(n) sorting time that dominates the query follows.

To summarize, the browsing of topics uses a pagerank cut at 5.10 -5 to ensure a seamless user experience. For entity level browsing, the selectivity on the entity being very high, the cut is not required and would be a disadvantage as it would reduce the number of displayed items.

SYSTEM DEMONSTRATION

We have developed a Web Interface to the topical database. It is available at the following url: http://demo-satin.telecom-st-etienne. fr/fouilla/. Users can experience the various navigation paths, and evaluate the added value of our system when dealing with DBpedia contents on different scenarios.

Browsing Efficiency The visitor at our booth chooses a topic of his/her interest and searches the relevant pages using the standard DBpedia Web Interface. Since it is not tailored for this type of search, the user will have difficulties in finding relevant information on the topic.In order to demonstrate the efficiency of our approach, the user is asked to restart the experience, but through our Fouilla interface : he/she gets accurate results in a few clicks.

Topic Exploration What are the most important facts and entities related to a topic? We here showcase the visitor how our system can be used to explore the facts regarding a given topic. Once the topic is selected, its corresponding top-ranked entities are retrieved and displayed on the web interface. Then, the user can navigate through the entities, predicates and triples using the provided controls. For instance, Wikipedia and DBpedia icons located close to the entities names allow fast navigation to the corresponding pages.

Entity View DBpedia entities (such as cities, countries, years, etc...) consist of a large and various number of triples of any kind. Such entities commonly contain many thousands of triples. Thus, they are difficult to visualize. For instance, finding relevant information on the topic Word War II in Italy is practically impossible with the DBpedia Web interface, because of the random display of thousands of triples. We here present the user the filtering and domain delimitation capability of our system. Figure 4 depicts such an example of the entity Italy viewed from two topics: Sports and Word War II. As one can see, our system retrieves only triples that are relevant for both topics. The hyperlinks on entities are entry points for further topical navigation.

Finally, several sample queries are available and runnable with and without pagerank filtering. The visitor can judge the gain on the user experience as well as the negligible impact on ranking.

CONCLUSION

In this paper, we introduce the concept of Topical Browsing, and propose the demonstration of Fouilla, the first topical browser on DBpedia. We automatically extracted a set of 50+ topics from Wikipedia structural and semantic content and we delimited subgraphs for each topic within DBpedia using both ranking and machine learning techniques. We experimentally validated our pagerank cut that enables to drastically reduce the application response time, without loss of ranking quality. Our system offers a novel browsing experience in the billions of triples of the Knowledge Base. The proposed topical delimitation approach allows the user to find a needle in a very large haystack without any SPARQL knowledge.

Figure 1 :

 1 Figure 1: Overview of the three steps involved in the creation of the topical database.

Figure 2 :

 2 Figure 2: Examples of Topics Pagerank Score Distribution by Rank

  Figure 3: Database Layout

Figure 4 :

 4 Figure 4: Views of the entity Italy from two (very) different topics

Table 1 :

 1 Experimental result for various pagerank (PR) cuts. NDCG@100 and query speedup are presented for sample topics and in average.

		PR < 5.10 -6	PR < 10 -5	PR < 5.10 -5
		NDCG Speedup NDCG Speedup NDCG Speedup
	Arts (1.6)	.99	26.89	.96	52.8	.58	122
	Politics (1.2)	1	19.87	1	36.08	.76	84.35
	. . .	. . .	. . .	. . .	. . .	. . .	. . .
	WW1 (0.1)	1	.97	1	1.71	.99	3.24
	Average	.99	6.19	.96	10.02	.68	22.75

never explores a branch with a depth greater than four starting from the seed category.

https://en.wikipedia.org/wiki/Category:Wikipedia_categories

https://en.wikipedia.org/wiki/Wikipedia:Featured_portals

https://en.wikipedia.org/wiki/Portal:Contents/Outlines


Vinicius Freitas

Alexandre De L Santana

Márcio Castro

Laércio L Pilla

A Batch Task Migration Approach for Decentralized Global Rescheduling

Keywords: High Performance Computing, Global Rescheduling, Load Balancing, Performance Evaluation, Parallel Algorithms

Effectively mapping tasks of High Performance Computing (HPC) applications on parallel systems is crucial to assure substantial performance gains. As platforms and applications grow, load imbalance becomes a priority issue. Even though centralized rescheduling has been a viable solution to mitigate this problem, its efficiency is not able to keep up with the increasing size of shared memory platforms. To efficiently solve load imbalance today, and in the years to come, we should prioritize decentralized strategies developed for large scale platforms. In this paper, we propose our Batch Task Migration approach to improve decentralized global rescheduling, ultimately reducing communication costs and preserving task locality. We implemented and evaluated our approach in two different parallel platforms, using both synthetic workloads and a molecular dynamics (MD) benchmark. Our solution was able to achieve speedups of up to 3.75 and 1.15 on rescheduling time, when compared to other centralized and distributed approaches, respectively. Moreover, it improved the execution time of MD by factors up to 1.34 and 1.22 when compared to a scenario without load balancing on two different platforms.

Introduction

Parallel machines are at their best when the workload is evenly distributed among compute nodes, and idle time is merely a myth. Unfortunately, strong scaling applications for these platforms has been a challenge as long as they have existed. In this context, uneven workload distribution and high communication overheads are the main villains when developing parallel applications [START_REF] Deveci | Fast and high quality topologyaware task mapping[END_REF]. Concerns towards these problems increase as systems grow in size and performance, consuming more resources, specially power, to solve some of the most complex problems in scientific computing [START_REF] Mair | Quantifying the energy efficiency challenges of achieving exascale computing[END_REF][START_REF] Padoin | Using power demand and residual load imbalance in the load balancing to save energy of parallel systems[END_REF].

Applications such as simulations of molecular dynamics (MD) and hydrodynamics suffer from load imbalance due to their intrinsic dynamic and iterative nature [START_REF] Mei | Enabling and scaling biomolecular simulations of 100 million atoms on petascale machines with a multicoreoptimized message-driven runtime[END_REF][START_REF] Karlin | Exploring traditional and emerging parallel programming models using a proxy application[END_REF]. Although rescheduling algorithms have been able to greatly improve the performance of these applications [START_REF] Mei | Enabling and scaling biomolecular simulations of 100 million atoms on petascale machines with a multicoreoptimized message-driven runtime[END_REF], new approaches are needed to guarantee their performance as parallel systems grow. Since mapping tasks to processing elements (PEs) is an NP-Hard problem [START_REF] Garey | Computers and Intractability: A Guide to the Theory of NP-Completeness[END_REF], the increase in application data and platform size makes centralized rescheduling approaches inefficient. This creates a need for scalable and decentralized rescheduling approaches, avoiding both excess of data to process and network contention [START_REF] Trahay | A scalable and generic task scheduling system for communication libraries[END_REF].

The two main paths to achieve scalability in global rescheduling for iterative applications are hierarchical and distributed approaches. Hierarchical load balancing explores parallelism using different approaches for fine-grain and coarse-grain steps [START_REF] Zheng | Periodic hierarchical load balancing for large supercomputers[END_REF]. Although scalable, hierarchical schedulers are often tied to the same limitations of centralized approaches, as data is still aggregated in parent nodes. On the other hand, distributed load balancing approaches seek to achieve scalability through multiple smaller, decentralized scheduling decisions. Albeit more scalable than hierarchical approaches, decentralized schedulers have limited system information and often incur in higher amounts of communication.

Despite their notable effectiveness, few are the distributed strategies in the domain of global rescheduling [START_REF] Willebeek-Lemair | Strategies for dynamic load balancing on highly parallel computers[END_REF][START_REF] Menon | A distributed dynamic load balancer for iterative applications[END_REF]. In this paper, we present the concept of Batch Task Migration and a novel distributed global rescheduling algorithm that applies this technique, called PackDrop. Our approach is based on the idea of grouping tasks in batches prior to migration decisions, decreasing the communication overhead in the scheduling decision time and preserving the locality of migrated tasks [START_REF] Paudel | On the merits of distributed work-stealing on selective locality-aware tasks[END_REF].

In this paper, we present the following contributions:

1. A highly scalable Batch Task Migration approach for distributed rescheduling algorithms;

2. A novel distributed rescheduling algorithm, PackDrop, using our Batch Task Migration approach;

3. An implementation of our algorithm in a wellknown parallel programming model as well as a performance evaluation of this implementation.

The remainder of this paper is divided as follows. Section 2 discusses recent work in dynamic rescheduling of scientific applications. Section 3 presents our novel approach and the developed algorithms. Section 4 presents a complexity analysis of our distributed algorithm (PackDrop). Section 5 displays implementation details, execution environments and benchmarks used in this paper. Section 6 presents our performance evaluation methodology and discusses the obtained results. Finally, Section 7 presents the conclusion of this work and our plans for future research.

Related Work

Global rescheduling is a well-studied problem in High Performance Computing (HPC) [START_REF] Deveci | Fast and high quality topologyaware task mapping[END_REF][START_REF] Willebeek-Lemair | Strategies for dynamic load balancing on highly parallel computers[END_REF][START_REF] Menon | A distributed dynamic load balancer for iterative applications[END_REF][START_REF] Pilla | Asymptotically optimal load balancing for hierarchical multi-core systems[END_REF][START_REF] Catalyurek | Hypergraph-based dynamic load balancing for adaptive scientific computations[END_REF][START_REF] Jeannot | Topology and affinity aware hierarchical and distributed load-balancing in charm++[END_REF][START_REF] Benson | Scheduling matters: Area-oriented heuristic for resource management[END_REF]. Redistributing the workload among PEs of a parallel system is a way to mitigate load imbalance created by dynamic applications. This is done in order to achieve strong scalability, and thus, efficient use of computing resources. In this section, we will discuss how different approaches seek to perform load balancing in distributed systems, why they lack scalability, and how we intend to mitigate migration, communication, and scalability issues in our proposed solution.

In the centralized domain, strategies implement a variety of heuristics in order to achieve an homogeneous distribution of load. Although centralized algorithms are used the most, their sequential and data dependent approach lacks scalability, as load balancing overheads exceeds its benefits with the increasing amount of input data. Different scheduling approaches are designed to tackle this scalability problem, being hierarchical and distributed the most widespread ones.

Hierarchical algorithms approach load balancing in different granularity levels, exploring parallelism and delivering better performance [START_REF] Zheng | Periodic hierarchical load balancing for large supercomputers[END_REF][START_REF] Unat | Trends in data locality abstractions for HPC systems[END_REF]. These strategies are able to acquire as much static system information as the centralized techniques, while exploiting system parallelism. Some hierarchical strategies have used topology-aware approaches to increase mapping affinity [START_REF] Pilla | Asymptotically optimal load balancing for hierarchical multi-core systems[END_REF][START_REF] Jeannot | Topology and affinity aware hierarchical and distributed load-balancing in charm++[END_REF]. Others rely on a hypergraph representation to precisely describe application communication patterns [START_REF] Catalyurek | Hypergraph-based dynamic load balancing for adaptive scientific computations[END_REF]. However, these approaches still tend to create communication bottlenecks and may incur undesired overheads to aggregate the required information for rescheduling. As parallel systems grow, the amount of system data increases, and so does the cost of querying this information, which leads hierarchical approaches to be inefficient in larger systems.

Work stealing is one of the most broadly used distributed techniques for balancing load in parallel systems [START_REF] Yang | Scheduling parallel computations by work stealing: A survey[END_REF][START_REF] Al-Omairy | Dense matrix computations on numa architectures with distance-aware work stealing[END_REF][START_REF] Janjic | How to be a successful thief[END_REF]. The essence of work stealing makes it a very effective solution for highly irregular parallel and distributed applications. However, work stealing may not be as effective, since its concurrent and randomized nature may interfere with iterative application execution cycle [START_REF] Beri | Prosteal: A proactive work stealer for bulk synchronous tasks distributed on a cluster of heterogeneous machines with multiple accelerators[END_REF].

Also in the distributed domain, diffusive techniques have been used to irradiate work in an iterative fashion among PEs [START_REF] Willebeek-Lemair | Strategies for dynamic load balancing on highly parallel computers[END_REF]. Although such an approach is interesting, since it may not impact much communication costs, it may also have a high convergence time, rapidly becoming inefficient in very imbalanced scenarios. Refinement-based distributed techniques, on the other hand, are able to provide fast and efficient rescheduling decisions without knowing too much about system information [START_REF] Menon | A distributed dynamic load balancer for iterative applications[END_REF]. The main disadvantage of these techniques is the lack of affinity in migrated tasks, diminishing task locality, and thus, increasing total communication workload.

In the loop scheduling domain, a Bin Packing oriented approach has been able to exploit iteration affinity by adaptively partitioning loops [START_REF] Penna | BinLPT: A workload-aware parallel loop scheduler for largescale multicore platforms[END_REF]. Due to its greedy approach, this strategy can efficiently distribute work among chunks before scheduling, increasing the overall application performance.

In this work, we propose a new approach for the distributed rescheduling domain named PackDrop. We adopt an approach similar to Bin Packing in order to preserve task affinity and diminish communication overheads in a decentralized fashion. Thus, our novel rescheduling approach intends to take profit from both distributed and affinity oriented scheduling policies.

Batch Task Migration Approach

The role of the global rescheduler is to ultimately reduce the application makespan. Thus, the scheduler policy must incur low overheads as to not overshadow its benefits. Moreover, we envision that a Batch Task Migration approach can ensure a quick and informed remapping of tasks, basically reducing the amount of messages during the scheduling decision process. Therefore, this section is dedicated to present our PackDrop strategy as a distributed refinementbased technique that implements our proposed Batch Task Migration approach.

Overall, our approach intends to:

1. Reduce unnecessary communication between PEs;

2. Exploit locality among tasks in the same PE through grouped migrations;

3. Accelerate the decision making process;

4. Reduce the application makespan.

We will first explain two algorithms that are used by PackDrop: BatchAssembly (Algorithm 1) and BatchSend (Algorithm 2). Then, the complete strategy, called PackDrop, will be presented in Algorithm 3. The PackDrop algorithm will be executed on each PE and communicates with other remote PackDrop instances via message passing. For clarity, all symbols used in the algorithms are listed in Table 1.

BatchAssembly Algorithm

The BatchAssembly algorithm is presented in Algorithm 1. It uses an estimated batch size (s), a set of local tasks (T ), the current PE load and a threshold for PE loads (v), to create a list of leaving packs (LT ). The threshold is used to calculate an upper bound of the average system load (load avg ), using Equation 1. The load of any set of tasks is given by Equation 2.

ub(load, v) = (1 + v) × load (1)
load set (T ) = ∑ t∈T load task (t) | T is a set of tasks (2)
With this information, each PE will take the task with the smallest load within its pool, and add it to a set of tasks (L) (lines 3 -5). Then, if the sum of all tasks in the pack (L) is greater than the expected batch size (s), the batch is assembled and the strategy starts creating another one (lines 6 -9). The process is repeated until the load of the set becomes greater than the upper bound (line 2).

Any unfinished packs should be sent even if these are not complete. This is done in order to prioritize migration from overloaded PEs, even if they cannot assemble a complete batch. A PE that receives this load will not receive as much load as others, but since the PE will not overload, it should not be prejudicial to global system balance.

BatchSend Algorithm

The BatchSend algorithm is presented in Algorithm 2. The algorithm will use the LT s, produced by BatchAssembly, and the set of Targets, produced by an Input: s, load threshold of a batch; T , set of local tasks; load avg , average global PE load; v, imbalance tolerance ratio. Output: LT , list of packs leaving this PE.

1 L ← ∅, LT ← ∅ 2 while load set (T ) > ub(load avg , v) do 3 t ← a ∈ T | a is the lower bound of T 4 T ← T \ {t} 5 L ← L ∪ {t} 6 if load set (L) > s then 7 LT ← LT ∪ {L} 8 L ← ∅ 9 end 10 end 11 LT ← LT ∪ {L}
Algorithm 1: BatchAssembly information propagation step (Gossip [START_REF] Demers | Epidemic algorithms for replicated database maintenance[END_REF]), in order to schedule packs on remote PEs. This will produce a set of expected Batch/Target (BG) pairs, which should be confirmed by the remote target.

For each subset b ∈ LT (as assigned in Algorithm 1), the algorithm will select a random target from G (line 3). It will invoke a remote Send procedure on the target g (line 4), and register its attempt in a pair (b, g). This pair is then stored in the expecting confirmation set (BG) (line 5).

Input: LT , set of tasks leaving the local PE; G, set of possible migration targets. Output: BG, set of expected migrations.

1 BG ← ∅ 2 foreach b ∈ LT do 3 g ← rand(G) 4 Send(b) → g 5 BG ← BG ∪ {(b, g)} 6 end
Algorithm 2: BatchSend

In case of negative responses from remote Send procedures, Algorithm 2 may initiate another round of sends with the failed attempts so every member of LT is migrated.

PackDrop Algorithm

The PackDrop strategy is presented in Algorithm 3. For the sake of simplicity, packs will be a short for "set of leaving tasks" in this algorithm (recall Sections 3.1 and 3.2).

PackDrop will run individually on each PE, in a distributed fashion. It will produce a new mapping (M ) using a current local mapping of tasks to PEs (M), a local load (load), a local PE identification (Id l ) and the global set of PEs (P). The mapping of tasks is defined as M : T → P, which describes the relation of each task to its corresponding physical location. A local mapping of tasks contains only tasks that are assigned to the current PE.

The first part of the algorithm (lines 1 -6) is the information sharing and setup process. This process is done through 2 global reductions of average PE load (line 2) and global number of tasks (line 3). In this implementation we used two constants: (i) v is set to 0.05 in order to limit the imbalance at 5% (line 5); and (ii) in Equation 3, a constant is set to 2, in order to determine ps.

ps = 2 - |P| ttc (3)
This configuration aims to both increase communication efficiency (later explained in Section 4) and ensure precise balancing. Finally, as ps grows, so does the communication efficiency, but in order to do so, finegrain migrations are compromised.

Next, PEs are divided between two different workflows (line 7). At this time, overloaded PEs will start the BatchAssembly algorithm (line 8), which was previously explained in Algorithm 1. Meanwhile, underloaded PEs will initiate a Gossip Protocol [START_REF] Demers | Epidemic algorithms for replicated database maintenance[END_REF] in order to inform other elements they are willing to receive work (line 11). Gossip is a well-known epidemic algorithm used to spread messages on a system, providing fast convergence and near-global awareness of shared information.

Once information propagation is done, each PE must synchronize to start the remapping process (line 13). At this point, PEs will send their packs using BatchSend (Algorithm 2) asynchronously (line 14). After a pack is sent, PEs will accept or reject it based on their current load. This is done via a three-way handshake, so both parts confirm the migration.

If one or more packs were not successfully exchanged, an overloaded PE must attempt a new BatchSend, in order to achieve load balance, as specified in Section 3.2. Once PEs know their new mappings, tasks are migrated and the strategy is finished, requesting the confirmed migrations to the underlying runtime PackDrop intends to remap tasks to PEs in a distributed, workload-aware fashion. This approach may be the basis for new batch task migration distributed strategies that might take other factors into account.

Input: M,

Analysis of the Algorithm

This section presents an analysis of PackDrop (Algorithm 3). Symbols presented in this section are available on Tables 1 and2. The complexity of the information propagation (Gossip) has being evaluated as O(log f out n) [START_REF] Menon | A distributed dynamic load balancer for iterative applications[END_REF], where f out is the Gossip fanout and n is the number of PEs in the system. Here we use f out = 2, in order to avoid network congestion.

For the sake of simplicity, in the remainder of this analysis, the number of tasks in the system will be re-

Communication base cost C(A)

The complexity class of a given function A m Number of tasks in the system m l max(|T |) in an overloaded PE ferred to as m, and the costs for computation and communication will be represented as p c and c c , respectively. We also assume c c > p c for all concurrent scenarios, since communication costs are several orders of magnitude higher than computational costs. C(A) is referred here as the complexity class of a given workload A, similar to its total cost. Unmentioned lines are assumed to have non-varying costs, and thus will not interfere in the asymptotic analysis. Lines 2 and 3 are global reductions, which have a well-known cost of O(log n). Lines 8 and 11 are concurrent, so their cost will be the maximum among them:

max(C(BatchAssembly),C(Gossip)) (4)
We also know that the worst case for BatchAssembly (Algorithm 1) is rather unrealistic, since it would assume that a single PE contains m tasks and a single task may have a load greater than the average system load, being O(m -1), assuming 1 would not be migrated, asymptotically, O(m).

Thus, the cost of lines 8 and 11 is:

max((p c × m), (c c × log n)) (5)
and since c c is several orders of magnitude bigger than p c , we could assume C(BatchAssembly) ∈ C(Gossip), which makes the complexity of these lines to O(log n). Finally, line 14 will have a complexity equal to the largest number of packs migrated by an overloaded PE. Let ps be the average number of tasks inside of an LT , and m l the maximum number of tasks in a given overloaded PE. At this step, a solution without Batch Task Migration would have a cost of c c × m l , while our approach will divide this complexity by ps. This is the most expensive part of Algorithm 3, and as such it is the most interesting one to optimize. Our final asymptotic complexity is:

C(PackDrop) = O(m l /ps) + O(log n) (6)
This shows that determining a good ps value is crucial to achieve the best performance with this algorithm. Higher values of ps will lower communication complexity, but may lead to an imprecise scheduling. In our implementation, we chose to vary the value of ps around a base value of 2, according to system load and characteristics, as described in Equation 3. BatchAssembly (Algorithm 1) stores tasks in LT in an increasing load order. So, even though our average pack should have around 2 tasks, as their load vary, we are able to include more tasks at a lower communication cost. This way, we attempt precise load balance, while still preserving task locality after migration.

It is important to note that different applications may react differently to different values of ps. This is specially related to application load variance. The ps factor may be fine-tuned to each specific application and platform, but we believe a reasonable, generic, approach such as the provided by Equation 3 is enough to provide balance to most applications and systems, while still harvesting the advantages of the Batch Task Migration approach.

Implementation

PackDrop was implemented as a load balancing strategy in Charm++1 , a parallel programming model that provides a load balancing framework based on migration of its parallel, message-driven objects, the chares [START_REF] Acun | Power, reliability, and performance: One system to rule them all[END_REF]. Chares are mapped as tasks to PEs and the Charm++ RTS provides the load information needed for our rescheduling strategy.

The Charm++ RTS allows for the desired asynchronous behavior of PackDrop. It also provides the necessary reduction and quiescence detection mechanisms used in this implementation. Reductions are used to evaluate the total number of chares and the average load in the system, while the quiescence detection is necessary to finalize the information propagation step of the algorithm.

Charm++ provides application-independent load balancing, which means that any application may use global rescheduling strategies implemented for this RTS. This way, any of the available applications for Charm++ can be used to evaluate and compare our strategy to other load balancers in this RTS.

During load balancing in the Charm++ RTS, each instance of PackDrop runs as an individual chare. Remote procedures in the algorithms (→) were implemented as messages exchanged between objects. Reductions (⇒) used the RTS provided interface (CkReduction). The three-way handshake, necessary to acknowledge a Send, was implemented with message exchanges. Finally, synchronization barriers in our algorithms use either quiescence detection or reductions.

Benchmarks

We experimented our strategy with 2 benchmarks that are publicly available for Charm++. The first one is a synthetic benchmark called LB Test. It simulates work with a variety of communication topologies, such as ring, meshes and randomized patterns. LB Test is known to have a low migration cost, with light chares, and most of its load bound to computation, instead of communication.

The second one is a molecular dynamics application called LeanMD2 . This application simulates the behavior of atoms and it mimics the force computation done in the state-or-the-art NAMD application, which was the winner of the Golden Bell Award [START_REF] Mei | Enabling and scaling biomolecular simulations of 100 million atoms on petascale machines with a multicoreoptimized message-driven runtime[END_REF]. LeanMD uses geometric decomposition in a three-dimensional (3D) simulation space. However, since the number of simulated atoms in each region affects the number of exchanged messages, it has an irregular and dynamic communication pattern, even though it respects the geometric distribution.

Other schedulers

We compare the performance of PackDrop to other strategies available on Charm++. More specifically, strategies that may be selected by Charm++'s workloadaware Meta-balancer [START_REF] Menon | Adaptive load balancing for HPC applications[END_REF]. An overall description of each one of these load balancing strategies is presented below:

• Re f ine is a refinement-based strategy that tries to minimize the number of migrated tasks, exchanging load among PEs. This strategy is specially efficient if the system imbalance is low, and may not be able to deal with high imbalance due to its limited migration approach.

• Greedy creates two heaps, one for tasks (max-min) and one for PEs (min-max). Then, it assigns tasks to PEs, associating the most work-heavy tasks with the least loaded PEs. This strategy provides a good load balance, but may incur in high migration overhead.

• Distributed, also known as Grapevine, is a distributed strategy based on epidemic communication and probabilistic transfer of work. This strategy has good scalability, but does not perform as well as centralized ones in smaller scenarios.

• Dummy, a centralized load balancer that does not remap tasks but still gathers system information as other centralized approaches. This is the representative of a scenario without load balancing.

Performance Evaluation

We used two platforms to evaluate the performance of PackDrop:

• Platform 1: A cluster called Graphene from Grid'5000 with 4 PEs per node and a Gigabit Ethernet interconnection network.

• Platform 2: A subset of a larger computational cluster called Santos Dumont from the Brazilian National Laboratory for Scientific Computing (LNCC) with 24 PEs per node and an Infiniband interconnection network.

All applications were compiled with gcc with the following flags: -std=c++11 -O3. Details of both platforms are available on Table 3.

In the next sections we present the metrics used to compare PackDrop with Greedy, Re f ine, Distributed and Dummy. Then, we discuss the results obtained in both platforms presented in Table 3 and the scalability of PackDrop. All raw data of our results, as well as parsing scripts for analysis are publicly available3 .

Metrics

Application time (makespan) is one of the most relevant metrics to evaluate load balancers. Since migrations may induce high overheads and could impact communication costs, a bad load balancing strategy may present fast decision times, while increasing load imbalance considerably. Thus, the overall execution time of the application will also be increased. This is a powerful metric to measure both load balancing precision and the overall impact of the strategy on parallel applications.

Load balancer decision time, on the other hand, is an indicator of its scalability. Some centralized schedulers, such as Greedy, work very well on local machines, with a reasonable data input. However, when executing on distributed memory environments, the scalability of centralized strategies is limited due to their high decision time in these scenarios. Throughout this section, load balancer decision time will also be referred to as rescheduling time.

Evaluation on Platform 1

All experiments executed on Platform 1 were compiled with Charm++ using the --with-production option, combined with the specifications detailed on Table 3. Overall, 32 homogeneous compute nodes were used, with a total of 128 PEs.

Evaluation with Synthetic Load

LB Test experiments had a total of 18, 990 tasks, executed over 150 iterations, performing load balance every 40 iterations. Task loads varied from 30ms to 9, 000ms, which provides reasonable load imbalance, causing global rescheduling to be useful in this case. Ring, 2D mesh and 3D mesh communication topologies were used to provide different levels of migration impact and communication costs. Each configuration of the benchmark was executed 15 times, with results depicted in Table 4. Observed application times present a maximum 2% standard deviation from the mean. Results for Greedy show how different communication topologies affect the scheduling performance. Since Greedy migrates many tasks, the more they communicate, the more migrations impact the application time.

The increased in communication cost can be verified among all scheduling strategies, but in none as much as in Greedy. Our novel approach (PackDrop) has outperformed the other decentralized strategy (Distributed) in the LB Test case in this scale. However, since the platform is not large enough to present all of the potential gains of decentralized strategies, Re f ine still outperformed any other scheduler in this benchmark. Nevertheless, this indicates a good scalability potential for PackDrop, specially in a cluster with high communication overhead due to its Gigabit Ethernet connection.

Evaluation with Molecular Dynamics

LeanMD experiments generated a 9 × 9 × 9 space, with a total of 27, 702 tasks. Each execution ran 500 iterations, with a first rescheduling step at the 10th iteration. Rescheduling periods (RP) of every 30 (short) and every 60 (long) iterations were used, providing different impacts of rescheduling on the application. Greedy and Dummy were excluded from this evaluation due to their high cost in an application such as LeanMD.

Each configuration of LeanMD was executed 10 times, making a total of 5, 000 iterations per configuration and are depicted in Table 5. Observed application times presented a standard deviation from the mean lower than 2% for all results presented.

Results show a better overall performance of PackDrop, outperforming the other strategies in the two The Rescheduling Time, presented in Table 5, shows the time taken by the periodical rescheduling (LB), task migration and the first iteration after the LB call. It shows the increased cost of Re f ine, which is due to both information aggregation costs and dealing with the high amounts of application data in a centralized fashion. PackDrop displays its effectiveness in rescheduling time, outperforming the other strategies and resulting in an overall better application time.

Evaluation on Platform 2

All experiments executed on Platform 2 were compiled with Charm++ using the --with-production option, combined with the specifications detailed on Table 3. Different numbers of homogeneous 2 × 12 PEs compute nodes (2 NUMA-nodes with 12 cores each) were used to evaluate the scalability of PackDrop. We ranged from 16 (384 PEs) to 32 (768 PEs) unique nodes in our evaluation. In this platform, we focused on the LeanMD application, since LB Test's synthetic behavior is well represented in Section 6.2.1.

Evaluation with Molecular Dynamics

LeanMD experiments generated a 10 × 15 × 10 space, with a total of 171K tasks. Each execution ran 100 iterations, with a first rescheduling step at the 9th iteration. Rescheduling was performed every 30 iterations and each configuration of LeanMD was executed 10 times, making a total of 1, 000 iterations per configuration.

Results of mean application and rescheduling time are displayed in Figure 1 (to the left and right, respectively), both in a log scale to better exhibit the differences between Distributed and PackDrop. In this Distributed benefits from this platform due to Infiniband's low latency communication costs, which reflects on improved total application times, as seen in Figure 1. PackDrop followed it closely and we can see that its rescheduling time in larger systems outperforms Distributed.

The rescheduling and application time results of LeanMD in this platform highlight the importance of using scalable approaches to balance system load, as well as using available parallelism in execution environments. This is specially visible in Greedy results on Figure 1, where the application performance was decreased after the global rescheduling process. Increased migration costs and higher hop counts in communication, consequences of load balancing, heavily impacted LeanMD in this case.

Performance Evaluation Overview

Most scientific applications today seek strong scaling, increasing their computational platforms to solve problems faster. Our results showed that, to achieve such an objective, an application must implement efficient load balancing strategies. We presented PackDrop as a solution for scalable rescheduling of work in distributed memory systems. Section 6.2.1 showed that PackDrop is able to effectively balance the load. Results highlight the importance of load balancing even in synthetic loads. The LB Test benchmark used has very low migration and communication overhead, and most of its work is done locally, which is optimal for rescheduling evaluation of raw computational workload. Moreover, LB Test is known for having a very low migration cost and simple tasks, which enhances the effectiveness of centralized approaches such as Re f ine. These results also portray the addition of communication overheads in different topologies (2, 4, and 6 communication edges for Ring, Mesh2D, and Mesh3D, respectively). As communication affects the application time more, migrations impact the total application time more, as we can see in the Greedy results.

In Sections 6.2.2 and 6.3.1, we evaluated PackDrop in LeanMD (better described in Section 5.1). This represents "a real world-like" scenario, in which applications may have dynamic communication patterns and high migration overhead. Results presented here highlight the overhead of centralized rescheduling approaches when joined with large-scale applications (171K tasks) and big environments, which increases work and information aggregation costs, respectively.

Distributed outperformed our approach in Platform 2, due to its more refined take on load balancing and high-speed network interconnection. However, the results show that PackDrop and its locality friendly batching of tasks for migration guarantees better performance in Platform 1, which portrays a Gigabit Ethernet interconnection. Finally, PackDrop was able to efficiently scale applications among all observed platforms, and had a faster rescheduling time than Distributed in most of the observed cases.

Conclusion

In this paper we have presented the Batch Task Migration approach for distributed global rescheduling. It intends to preserve task communication locality, migrating multiple work units from a source to the same destination, in order to balance system load. This preserves communication efficiency, while other workload-aware strategies perform rescheduling without considering task locality.

Our approach also mitigates communication costs during algorithm execution time. We guarantee this by transmitting information about multiple migrations at a time, in batches. Thanks to this, our novel scheduler (presented in Section 3.3) has an increased performance in high communication overhead platforms, discussed in Section 6.2.

We have evaluated our strategy in two different execution environments. The first was a high communica-tion cost, 4 cores/node cluster, executing over 32 cores. In this scenario, PackDrop had a rescheduling speedup of up to 3.75 and 1.15 when compared to centralized and distributed approaches, respectively (Section 6.2).

The second scenario was a highly coupled cluster with low communication overhead, with 24 cores/node. We executed our experiments varying platform size from 16 to 32 nodes. In this scenario, rescheduling time of PackDrop and Distributed were very similar, although both had a time up to 3 orders of magnitude faster than any centralized approach. This reinforces the relevance of work in the distributed scheduling domain, and approaches such as our Batch Task Migration.

Future Work

Future work on this theme includes the use of Batch Task Migration in the communication-aware domain. Since our approach already has locality-based benefits, combining this with communication pattern information may incur on even greater performance increase in applications [START_REF] Unat | Trends in data locality abstractions for HPC systems[END_REF][START_REF] Hoefler | An Overview of Topology Mapping Algorithms and Techniques in High-Performance Computing[END_REF]. We believe a novel strategy focused on the Stencil programming model is something to be considered, prioritizing migration of edges among PEs, instead of random parts of the stencil [START_REF] Reguly | Loop tiling in large-scale stencil codes at runtime with ops[END_REF].

Further work will also be developed in order to increase performance in heterogeneous clusters. These may have heterogeneous processing capacities and network capabilities, which enhances complexity of load balancing significantly [START_REF] Beri | Prosteal: A proactive work stealer for bulk synchronous tasks distributed on a cluster of heterogeneous machines with multiple accelerators[END_REF][START_REF] Cheriere | Considerations on distributed load balancing for fully heterogeneous machines: Two particular cases[END_REF]. In this given scenario, enhancing rescheduling decision processes may be crucial to ensure gains in application performance. Finally, we also intend to evaluate the impact of fine-tuning the ps factor in different computing platforms.

8 packs← 11 G

 811 BatchAssembly(s, T (M), load, v) ← (Gossip → P) // Targets for migration 12 end 13 ---SynchronizationBarrier ---/ * Requests are processed as they are received back * / 14 R ← BatchSend(packs, G) // Implicit synchronization in TaskMap 15 TaskMap(R, M, M , Id l ) Algorithm 3: PackDrop system (RTS) on line 15. The TaskMap function will take care of informing the new mapping (M ) to all tasks received via Send and removed via BatchSend.

Table 1 :

 1 List of symbols, variables and functions.

	Symbol	Meaning	Definition
	v	Load threshold in %	Equation 1
	ub(load, v)	Upper bound of load with threshold v	Equation 1
	load	Compute load of the local PE
	load task (t)	Compute load of a task t	Equation 2
	load set (T )	Load of a set (T )	Equation 2
	T	Set of tasks	Equation 2
	ps	Estimate number of tasks in a LT	Equation 3
	ttc	Total number of tasks in the system	Equation 3
	→	Remote procedure call	Section 3
	⇒	Reduction process	Section 3
	load avg	Average system load of a PE	Section 3.1
	rand(S)	Random element of S	Section 3.2
	M	Mapping of tasks	Section 3.3
	P	Global set of PEs	Section 3.3
	Gossip	Start of information propagation	Section 3.3
	pack	Set of leaving tasks	Section 3.3
	LT	List of sets of tasks leaving a PE	Algorithm 1
	L	Set of tasks assemblying a batch, subset of T Algorithm 1
	s	Threshold of load in a batch of tasks	Algorithm 1
	G	Target for task receiving	Algorithm 2
	BG	Pairs expecting migration ack	Algorithm 2
	Send(T ) → G Send a set T to target G	Algorithm 2
	Id l	Local PE identifier	Algorithm 3
	TaskMap	Call runtime system to start migrations	Algorithm 3

  local mapping of tasks; load, local PE load; P, set of all PEs in the system; Id l , local PE identifier. Output: M , new mapping of local tasks. 1 M ← ∅ 2 load avg ← (AveragePeLoadReduction(load) ⇒ P) 3 ttc ← (TotalTaskCountReduction(|M|) ⇒ P)

	4 ats ←	load avg ttc
	// Average task size
	5 v ← 0.05
	// 5% precision on balance
	6 s ← ats × ps	// Pack
	load

7 if load > ub(load avg , v) then

Table 2 :

 2 List of symbols used in the Analysis of the Algorithm.

	Symbol Meaning
	f out	Gossip protocol's fanout
	p c	Computational (processing) base cost
	c c

Table 3 :

 3 Overview of the experimental platforms.

	Characteristics	Platform 1	Platform 2
	# of nodes	32	16 -32
	# of CPUs/node	4 (UMA)	2 × 12 (NUMA)
	CPU Model	Intel Xeon X3440 Intel Xeon E5-2695v2
	CPU Freq.	2.53GHz	2.4GHz
	RAM/node	16GB	64GB
	Network	Gigabit Ethernet	Infiniband FDR
	OS	Ubuntu 14.04	RedHat Linux 6.4
	GCC version	5.4.0	5.3.1
	Charm++ version 6.8.1	6.8.1
	Communication	UDP	MPI 3.1.0

Table 4 :

 4 Average application time for LB Test on Platform 1.

	Scheduler	Network Topologies
		Ring	Mesh2D Mesh3D
	Distributed 47.493s 48.648s 49.055s
	Greedy	46.541s 49.560s 51.068s
	Dummy	52.430s 53.172s 53.941s
	PackDrop	46.816s 47.371s 47.974s
	Re f ine	45.491s 46.293s 47.219s

Table 5 :

 5 Average application time for LeanMD on Platform 1.

	Scheduler	Rescheduling Period Rescheduling Time
		Short	Long
	Distributed 69.356s	68.360s	167.044ms
	PackDrop	55.984s	55.516s	143.103ms
	Re f ine	59.357s	55.899s	539.836ms
	scenarios chosen. Since our strategy migrates groups of
	tasks, it preserves locality of tasks after migration. Be-
	cause of that, it was able to outperform Distributed.

  Re ine had a very low efficiency, being slower than Greedy in the 384 PEs scenario. It was able to perform better as we increased the number of PEs, but was ultimately unable to compete with distributed approaches.

	Mean Rescheduling Time (s)	1 2 3 4 5	• 384	• 480	• 576	• 672	• 768
				Number of PEs
	Figure 1: LeanMD execution results on Platform 2, dis-
	played in logarithmic scale.
	evaluation,

Available at: https://github.com/viniciusmctf/ packdrop-code/tree/SBAC-Release

Available at: http://charmplusplus.org/miniApps

Available at: https://github.com/eclufsc/ packdrop-data-analysis

ACKNOWLEDGEMENTS

The authors acknowledge the National Laboratory for Scientific Computing (LNCC/MCTI, Brazil) for providing HPC resources of the SDumont supercomputer, which have contributed to the research results reported within this paper (see http://sdumont.lncc.br).

Experiments presented in this paper were carried out using the Grid'5000 testbed, supported by a scientific interest group hosted by Inria and including CNRS, RE-NATER and several Universities as well as other organizations (see https://www.grid5000.fr).

‡ This work was partially supported by the Brazilian Federal Agency for the Support and Evaluation of Graduate Education (CAPES) and by the Brazilian Council of Technological and Scientific Development (CNPq), project grant 401266/2016-8.