Barrie W Jervis
email: barrie.jervis@cantab.net

Running head: A Comparison of Two Theories

Keywords: emergent gravity, gravitational dipoles, spherical galaxy, dark matter

The aim was to demonstrate the possible compatibility between the gravitational theory of Hajdukovic, which depends upon the existence of virtual particle pairs in vacuo, and that of emergent gravity according to Verlinde, and to derive new physical relationships. These theories, which avoid the necessity for postulating dark matter, and necessary, associated concepts are described. Then, assuming the validity of these theories, the following new results are obtained. Assuming a spherical galaxy model, the theories predict approximately the same radial distance from the galactic centre for the onset of enhanced gravitational fields. This agreement is used (1) to show that the virtual particle density of the vacuum at this distance depends only upon the Hubble scale and Planck's constant, (2) to calculate its value, and (3) to show that the particles consist of closely packed pions.

1 Introduction Zwicky (1933) observed anomalous velocity dispersion in the Coma cluster of galaxies, and Rubin (1970) discovered that at large radii galactic material rotates faster than predicted by Newton's Laws. Both these observations suggested the presence of stronger than expected gravitational fields. The two most popular theories to explain these, and other galactic phenomena, are the presence of undiscovered matter (dark matter) or the Modified Newtonian Dynamics theory, MOND (Bekenstein and Milgrom, 1984), of the modification of the laws of gravity.

Dark matter is postulated to consist of massive, weakly-interacting, cold, dark particles, which neither emit nor reflect light. The location of these particles, assuming they exist, has been determined by computer modelling.

Recently two alternative, promising theories of gravity have been proposed which remain to be fully tested, but have explained some of the gravitational effects of galaxies without the need for dark matter. The theory of emergent gravity is based upon a melange of the theories of thermodynamics, entropy, black holes, information, elasticity, and string theory, as described in a very recent paper (Verlinde, 2017). Gravity is shown to emerge from the quantum bits of information which characterise space-time, and is, therefore, not a fundamental property of matter. According to the second theory (Hajdukovic, 2011), the additional gravitational force associated with galaxies is contributed by the partial alignment of gravitationally polarised virtual particle pairs in an external gravitational field. The pairs of particles and antiparticles spontaneously appear very briefly and then selfannihilate, according to Heisenberg's Uncertainty Principle and Einstein's equation of equivalence between mass and energy, E = mc 2 . The antiparticles are assumed to have negative mass, as well as negative charge. This will be called the Hajdukovic theory, after its inventor. It is these two theories which are considered in this paper.

In this new work founded upon the assumed validity of these theories, it is shown that, based on a spherical galactic model, the two theories predict an enhanced gravitational effect at the same location. Then, by combining equivalent formulaic results from the two theories, it is shown that the virtual particle density in the galactic halo depends upon the Planck wavelength and the size of the universe. The particle density is calculated and the particles are shown to be pions. Some underlying concepts and the two new theories are first reviewed. The new contribution appears in Sections 4 and 5.

Underlying Concepts

The Evidence for Dark matter

Modelling shows that most galaxies are surrounded by a halo of dark matter. These haloes have a constant central surface density (Donato et al., 2009). Also studies of the dwarf galaxies Fornax and Sculptor show dark matter distributed uniformly within the central region ( Walker and Peñarrubia, 2007)]. Thus a uniform density is characteristic of dark matter, and there may be dark matter within a galaxy as well as surrounding it. Further evidence for possible dark matter is offered by the lensing effect of the Bullet Cluster of colliding galaxies (Clowe et al., 2008) and from the cosmic background microwave radiation (CMBR) (Einasto, 2011). However, the existence of dark matter has not been proved. Any new theory must account for these phenomena.

Virtual Particle Pairs

It is fundamental to Hajdukovic's theory that the vacuum of space is full of virtual particle-pairs. Their existence has been shown by the Casimir Effect (Casimir, 1948) and the Lamb shift (Lamb, 1947). It has been suggested that gravitational polarisation of these particles accounts for the dark matter explained by the MOND model (Blanchet, 2007) as well as for dark matter and dark energy (Blanchet andTiec, 2008, 2009). In Hajdukovic's theory these ideas are extended to the gravitational polarisation of the virtual dipoles.

Entropy, Information, Black Holes, and Entropic Force

These concepts are used in the theory of emergent gravity (Verlinde, 2017) and so relevant aspects are reviewed here. Thermodynamic entropy is given by the wellknown Boltzmann equation (1) in which is Boltzmann's constant, is the number of possible states, and denotes logarithm. In information theory information is conveyed in strings of binary bits. The information entropy, is given by (2)

These equations are identical in form, showing that thermodynamic entropy and information entropy are interchangeable.

Microscopically, in the domain of quantum mechanics, the binary information bits become qubits taking any value between 0 and 1. When the quantum mechanical wave function represents two states simultaneously the two states are said to be entangled. Thus, their representative qubits are also entangled. In the theory of black holes (Bekenstein, 1973) the entropy of a black hole may be regarded as the number of associated entangled qubits.

An increase in entropy, , is associated with the work done, , by the application of a force, , in moving an object through a distance . The energy increase in entropy terms is , where is the temperature. Equating these gives

(3)

3 The New Gravitational Theories

Theory of Emergent Gravity

Verlinde presented a theory of emergent gravity (Verlinde, 2017), and a nonmathematical description has been given by Visser and Vonk, (2017). According to Verlinde an empty space is filled with dark energy, which provides a volume contribution to the total entropy. It also acts as an expansive force, which drives the expansion of the universe. If some of this energy is converted into ordinary baryonic matter, the entropy change produces a force, according to equation (3). The universe is considered an elastic medium and this force results in elastic strain, which slowly relaxes over a very long timescale. At the microscopic quantum scale, black hole theory is applied, and the entropy is associated with qubits. The creation of matter displaces the qubits, leaving a vacuum in the vicinity of the mass. The qubits push to fill the vacuum, which creates an additional gravitational force. This phenomenon is significant whenever the mass is sufficiently large, and causes the large gravitational fields in the vicinity of galaxies. Thus, gravity is regarded as an emergent macro property of the microscopic behaviour of the qubits.

Verlinde has demonstrated how Newton's Laws may be derived from this theory (Verlinde, 2011).

Hajdukovic's Theory

Hajdukovic produced his theory to explain the phenomenon of dark matter (Hajdukovic, 2011). The virtual particles and antiparticles are assumed to have opposite gravitational charges and to form gravitational dipoles and opposite gravitational charges are assumed to repel each other. The concept of matter and antimatter being mutually repulsive has been investigated theoretically (Villata, 2011) with the conclusion that antigravity is predicted by the theory of general relativity.

See also (Hajdukovic, 2009). Experiments to detect negative mass by observing in which direction neutral antihydrogen atoms fall are being undertaken at CERN in the AEGIS, ALPHA, and GBAR experiments. Hajdukovic also assumes that the virtual particle pairs constitute a gas of virtual pions, which are quark-antiquark pairs (Hajdukovic, 2010). Pions may have the smallest mass possible in nature (Böhmer and Harko, 2005), and Hajdukovic argues that pions may dominate the content of the quantum vacuum (Hajdukovic, 2010). The separation between the poles of the opposite gravitational charges of the virtual dipoles , their Compton wavelength, at their equilibrium separation. Here is the velocity of light, h is the Planck constant, and is the mass of the pion. Further, according to quantum field theory, a virtual particle pair should occupy the volume (Hajdukovic, 2011). Thus, the particle pair density in the vacuum is .

These polarised particle pairs become aligned in a gravitational field to an extent which depends upon the field strength, just as electric dipoles align in an electric field. Hajdukovic used a simple spherical model of a galaxy and calculated the radial gravitational charge density. The evidence for a uniform matter density in regions of dark matter has already been mentioned above (Donato et al, 2009), ( Walker and Peñarrubia, 2011), and so regions of uniform gravitational charge density were taken to represent dark matter regions. In fact the radial distance from the centre at which the dark matter effect was to be found was determined to be (4) in which is the baryonic mass. Hajdukovic took and because he was considering pions.

Gravitational Theoriesthe Evidence

Table 1 gives a summary of the successes, √, failures, X, and unknown predictions,?, for the supposed dark matter phenomena, as known by the author at present, by the different theories in different instances.

TtTable Table 1 The MOND theory predicted that the Milky Way would exhibit a disc of dark matter, while Hajdukovic's theory did not predict one. Attempts to find it were unsuccessful (Bidin et al., 2010). The emergent gravity theory has been successfully tested for the case of gravitational lensing (Brewer et al., 2017). While much more work remains to be done, the table shows that the emergent gravity and Hajdukovic's theories look promising, whilst the MOND theory failed in two instances.

Comparing the two Theories

As Verlinde's theory of emergent gravity and Hajdukovic's theory both explain galactic haloes and gravitational lensing, they should predict the same radial distance from the centres of spherical galaxies to the onset of dark matter effects.

This distance was given in equation ( 4) for Hajdukovic's theory. Let us now apply the theory to the spherical galaxy Messier 89 (NGC4552). Its mass is kg for a half-light radius of m. Substituting for , putting kg as the mass of a pion, and using kg, gives m. This radius is a little less than the half-light radius, and suggests that some dark matter is present within the outer layers of the galaxy.

For emergent gravity, with as the surface area of a sphere of radius surrounding the galactic centre, beyond which dark matter is predicted, Verlinde's equation ( 4) in (Verlinde, 2017) describes the situation by,

where is the enclosed mass, is the gravitational constant, and is the cosmological acceleration scale, given by (6) where is the Hubble scale, the radius of the universe. Upon substituting equation ( 6) into equation ( 5), putting , and rearranging gives (7)

Again, taking the case of the spherical galaxy, Messier 89, kg, while m, m 3 kg -1 , and m s -1 giving m. Again this distance is less than the half-light radius, suggesting the presence of dark matter within the outer layers of the galaxy. Taking the ratio, .

Considering that the two theories were derived from different models, this is considered to be a good agreement. See also Section 6.

Combining the two theories

The evidence in Table 1, and the agreement between and , suggest the emergent gravity and Hajdukovic theories are compatible. Then, since equations ( 4) and ( 7) give essentially the same result, they may be equated to give the new relationship (8)

This new equation may be applied to derive new results as follows. Substituting and , it is found that (9)

showing that the particle density at only depends upon known constants and the radius of the spherical universe. The Planck wavelength, , is

And so combining equations ( 9) and ( 10) gives ( 11)

We can define an area proportional to as the Planck area showing that is inversely proportional to the smallest meaningful area of space. The particle density at can be estimated from equation ( 9) as ( 12)

Substituting values gives particles m -3 . This value compares well with the value calculated directly from , which is m -3 .

So far the type of particle has not been defined. If we assume, like Hajdukovic [5],

that they are close neighbours with then m. This is comparable to for the pion ( m) and it is thought that the quantum vacuum is dominated by pions (Hajdukovic, 2011). This approximate agreement is further evidence that the two theories yield similar results and that equation ( 8) is valid. The physical meaningfulness of equation ( 11) also suggests the compatibility of the two theories.

In deriving the expression for , equation ( 4), the spacing between the virtual particle and its antiparticle was taken to be approximately according to quantum field theory, and the virtual dipole pairs were assumed tightly packed so that the particle density is . This second assumption can now be tested. Let the particle density be where . Then from equation (8)

if pions are assumed, kg, whence m, compared with m. These values agree within the factor of 2.9, suggesting the pions are indeed closely packed. This is more evidence for the compatibility of the two theories. Note that . If the theories were exact, this could infer that has been underestimated by the factor If this is not the case, then the theories yield very close, rather than exactly the same values.

Conclusion

The predicted agreements with the "observations" of dark matter, and the calculated approximate agreement shown here between the predicted radial locations of the supposed dark matter for a spherical galactic model suggest the theories of Hajdukovic and of emergent gravity are comparable. Assuming the validity of these theories and for the first time equating the two formulae for the radial location of the dark matter effect, it is shown that the virtual particle density in this region depends only upon the Hubble scale and the Planck area, . This new basic relationship is physically credible and also suggests compatibility between the two theories. Using this new relationship the number density of virtual particle pairs was calculated to be m -3 , and their separation by approximately one Compton wavelength corresponded to that of tightly packed pions.

Table 1

 1 The theoretical predictions compared to the locations of known dark matter

	Dark matter	MOND	Emergent gravity	Gravitational
	phenomenon			dipoles
	Galactic haloes	√	√	√
	Dwarf galaxies	√	?	?
	Gravitational	X	√	√
	lensing
	Milky Way disc	X	?	√

Acknowledgements

The author thanks Dr A. J. Jervis for providing some references and comments on the manuscript, and John Edwards and David Barber for feedback.


Elena V Lukovskaya

Natalya V Dyachenko

Andrey V Khoroshutin

Alla A Bobyleva

Alexander V Anisimov

Valentina A Karnoukhova

Gediminas Jonusauskas
email: gediminas.jonusauskas@u-bordeaux.fr

Yurii V Fedorov

Olga A Fedorova
email: fedorova@ineos.ac.ru

Annelated tricyclic thiophenes and their photophysical properties

ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

1

The photocyclization of stilbenes (1,2-diarylethenes) provides a convenient approach to novel planar polyaromatic compounds, and their heterocyclic analogues are of significant interest as prospective materials for electroluminescent devices, organic con ductors and photovoltaic systems. [START_REF] Fichou | Handbook of Oligo-and Polythiophenes[END_REF][START_REF] Wang | [END_REF][3] As a rule, the existing methods for the synthesis of polycyclic heteroatomic compounds are multi-stage and laborious. 4,5 Photochemical transformations of 1,2-di(het)arylethenes are now actively used for the synthesis of various classes of organic compounds that are difficult to access by alternative synthetic strategies. [START_REF]Handbook of Synthetic Photochemistry[END_REF][START_REF] Bach | [END_REF][8][9][10] Specifically, three different pathways of the initially formed tricyclic cyclohexadiene-like structure are reported, namely, the reversed reaction, as in the case of photochromic switches, 11,[START_REF] Irie | Phororeactive Materials for Ultrahigh-Density Optical Memory[END_REF] oxidation of cyclohexadiene to form tricyclic annelated aromatic scaffold, [START_REF] Bach | [END_REF][START_REF] Galangau | [END_REF]14 and [1,n]-hydro gen shift followed by the destruc tion of the periphery aromatic ring. 15,16 The course of the reaction is governed by the preorgani zation of the double bond, heterocycle type, and reaction conditions, e.g. the acid concentration. 17 Some examples of the photocyclization of 1,2-dithienyl-or 1-thienyl-2-arylethenes are known, [18][19][20][21] however the diversity of the studied compounds is low for the assessment of the importance and the potential of this reaction. For instance, photocyclization of 1-thienyl-2-phenylethenes with varied sub stituents on the phenyl side is not studied in detail yet.

In view of our experience in the synthesis of thiophene-containing stilbenes, 22 now we report the oxidative intramolecular photo cyclization of 3-styrylthiophenes containing 3,4-dimethoxy (1) and 15-crown-5 ether (2) groups attached or annelated to its phenyl side (Scheme 1) † and photophysical characteristics of the obtained polycyclic products. The starting styryl derivatives were synthesized by the diethylphosphonate procedure ensuring the E configuration of the double bond (see coupling constant for E-C=C fragment in Figures S1,S5, Online Supplementary Materials, X-ray crystallography ‡ data for compound 1 in Figure 1, and the Photolysis was carried out by irradiating 0.1 m cyclohexane solution of compounds 1 or 2 in the photoreactor with the light of a submerged mercury lamp during 30 min. The solvent was removed, the residue was purified using column chromatography (SiO 2 , ethyl acetate as an eluent). [1,2-b]thiophene 3a: yield 56%, mp 121-123 C. [START_REF] Fichou | Handbook of Oligo-and Polythiophenes[END_REF] H NMR (500 MHz, CDCl 3 ) d: 4.04 (s, 3 H, Me), 4.13 (s, 3 H, Me), 7.29 (d, 1H, H-7, 3 J 8.9 Hz), 7.48 (d, 1H, H-3, 3 J 5.4 Hz), 7.61 (d, 1H, H-2, 3 J 5.4 Hz), 7.67 (d, 1H, H-5, 3 J 8.6 Hz), 7.70 (d, 1H, H-6, 3 J 8.9 Hz), 7.74 (d, 1H, H-4, 3 J 8.6 Hz). [START_REF] Galangau | [END_REF] spin system analysis). When irradiated, styryl thiophenes undergo E-Z-isomerization at the first stage (see Scheme 1), which can be evidenced by 1 H NMR at the early stages of the reaction (for instance, see Figure S1). The Z-forms are further cyclized and an unstable non-aromatic inter mediate product is formed, 2-thienyl rather than 4-thienyl position being involved in the reaction. At the last step, this inter mediate is oxidized as two hydrogen atoms are removed giving rise to an aromatic product. Each of the starting compounds, 1 and 2, yields two photoproducts, i.e. 3a,b and 4a,b, respectively (see Scheme 1, Figures S2-S14).

R 3 = R 4 = OMe, R 2 = H (21%) R 2 = R 3 = OMe, R 4 = H (56%) R 3 + R 4 = 15-crown-5, R 2 = H (14%) R 2 + R 3 = 15-crown-5, R 4 = H (43%) R 1 = OMe R 1 + R 1 = 15-crown-5 S R 1 R 1 R 2 = R 3 = OMe, R 4 =

8,9-Dimethoxynaphtho

Yields of products 3, 4 (see Scheme 1) are resonable enough; moreover, their formation occurs from readily available styryl derivatives upon mercury lamp irradiation at room temperature for 30 min. Alternative synthetic pathways to similar fused compounds are laborious and multi-stage. Of particular interest is the fact that sterically hindered isomers 3a and 4a are formed in a higher yield. To rationalize such a preference, ground state energies of different conformers of the E-1a-d were calculated by MOPAC2016 program with PM7 Hamiltonian as well as their equilibrium amounts were calculated using the Boltzmann distribution model (Table 1).

Isomerization of E-isomers leads to the corresponding Z-isomers a-d (see Scheme 1, Table 1). Due to low reactivity of C-atom in the 4-position of the thiophene residue, the participation of Z-isomers b and d in the cyclization reaction can be disregarded. Thus, the cyclic products 3a and 4a can be formed from a and c conformers of Z-isomer. Because of the low activation barrier of the rotation around a single bond, conformers b and c can easily transform into a and d, respectively. The ratio between frac tion of Z-isomers a and b leading to product 3a and fraction of Z-isomers c and d giving product 4a is 72 : 28 (see Scheme 1). This ratio is close to that observed in synthesis (2.7 : 1). Thus, the calculations are in agreement with the experiment.

Table 2 shows the measured photochemical and photophysical characteristics (for details of measurements, see Online Supplementary Materials) of the styrylthiophenes 1, 2 and products

S R R S R R S R R O O O O O 1, 3 R = OMe 2, 4 R + R = S R R H H S R R H H S R R 1, 2 (Z-a) 1, 2 (Z-c) hv S R R 1, 2 (E-b) 1, 2 (E-a) 1, 2 (E-c) S R R 1, 2 (E-d) I 2 hv H H H H H H H H H S H R R H S H R R 3a (56%) 4a (43%) I 2 3b (21%) 4b (14%) Scheme 1 O(1)
S( 1) O( 2) C( 9) C( 13) C( 14) C( 10) C( 11) C( 12) C( 7) C( 8) C( 6 In summary, we have proposed mild conditions for the photochemical cyclization of styrylthiophenes containing 3,4-dimethoxy and 15-crown-5 ether groups and conditions for the separation of the formed mixture of the photoproducts. Structures of isomeric cyclization products have been established and their photochemical and photophysical properties have been estimated.

H

  Photochemical oxidative cyclization of 3-[(E)-2-(3,4-dimethoxy phenyl)vinyl]thiophene and its 15-crown-5-analogue (15-[(E)-2-(3-thienyl)vinyl]-2,3,5,6,8,9,11,12-octahydro-1,4, 7,10,13-benzo pentaoxacyclopentadecine) affords the isomeric thiophene-containing fused aromatic compounds demonstrating photophysical pro perties different from those of initial styryl derivatives. E-Configuration of the initial styryl dye, 3-[(E)-2-(3,4-dimeth oxyphenyl)vinyl]thiophene, has been proved by X-ray analysis.

Figure 1

 1 Figure 1 General view of molecule 1 in crystal in thermal ellipsoid representation for non-hydrogen atoms (p = 50%). The minor component of the disordered thiophene ring is omitted for clarity.

  CH 2 O, 3 J 6,0 Hz), 7.23 (d, 1H, Ar,3 J 8.8 Hz), 7.45 (d, 1H, Th, 3 J 5.4 Hz), 7.58 (d, 1H, Th, 3 J 5.4 Hz), 7.65 (d, 1H, Ar, 3 J 8.3 Hz), 7.67 (d, 1H, Ar, 3 J 8.3 Hz), 7.72 (d, 1H, Ar, 3 J 8.8 Hz). 13 C NMR (APT) (100 MHz, CDCl 3 ) d: 68.83, 69.66, 70.33, 70.38, 70.43, 70.97, 71.04, 72.71 (CH 2 ), 113.64, 120.50, 123.73, 124.43, 124.69, 127.34 (C tert ), 125.12, 126.91, 131.87, 137.81, 141.61, 148.62 (C quat ). MS (ESI), m/z (%): 374 [M] + (100). Found (%): C, 64.22; H, 5.99. Calc. for C 20 H 22 O 5 S (%): C, 64.15; H, 5.92.

	C NMR (APT) (125 MHz, CDCl 3 ) d: 56.73
	(Me), 60.36 (Me), 113.20 (C 7 ), 120.60 (C 4 ), 123.77 (C 3 ), 124.51 (C 5 ),
	124.67 (C 6 ), 124.91* (C 9a ), 126.91* (C 5a ), 127.55 (C 2 ), 131.96* (C 9b ),
	137.87* (C 3a ), 142.52* (C 9 ), 149.50* (C 8 ). MS (ESI), m/z (%): 244 [M] +
	(100). Found (%): C, 68.87; H, 4.81. Calc. for C 14 H 12 O 2 S (%): C, 68.83;
	H, 4.95.
	7,8-Dimethoxynaphtho[1,2-b]thiophene 3b (also observed in a mix-
	ture 23 ): yield 21%, mp 105-107 C. 1 H NMR (500 MHz, CDCl 3 ) d: 4.04
	(s, 3 H, Me), 4.09 (s, 3 H, Me), 7.26 (s, 1H, H-6), 7.37 (s, 1H, H-9), 7.34
	(d, 1H, Th, 3 J 5.3 Hz), 7.44 (d, 1H, Th, 3 J 5.3 Hz), 7.62 (d, 1H, H-5,
	3 J 8.5 Hz), 7.72 (d, 1H, H-4, 3 J 8.4 Hz). 13 C NMR (APT) (125 MHz,
	CDCl 3 ) d: 55.92 (Me), 56.06 (Me), 103.15 (C 9 ), 107.86 (C 6 ), 120.28
	(C 4 ), 123.83 (C 5 ), 124.02 (C 3 ), 124.20* (C 5a ), 125.20 (C 2 ), 125.96* (C 9b ),
	136 30* (C 9a ), 136.33* (C 3a ), 148.94*, 149.76* (C 7,8 ). MS (ESI), m/z (%):
	244 [M] + (100). Found (%): C, 68.92; H, 4.89. Calc. for C 14 H 12 O 2 S (%):
	C, 68.83; H, 4.95.
	2,3,5,6,8,9,11,12-Octahydrothieno[3',2' 7,8]naphtho[1,2-b][1,4,7,
	10,13]pentaoxacyclopentadecine 4a: yield 43%, mp 143-145 C. 1 H NMR
	(400 MHz, CDCl 3 ) d: 3.79 (m, 6 H, CH 2 O), 3.90 (m, 2 H, CH 2 O), 3.99
	(m, 2 H, CH 2 O), 4.25 (t, 2 H, CH 2 O, 3 J 6.1 Hz), 4.31 (m, 2 H, CH 2 O), 4.49
	(t, 2 H,

Table 1

 1 Calculated values of ground state energies of E-1 conformers (see Scheme 1) and their fractions at 20 C.

	E-1 conformer	E/kcal mol -1	Calculated fraction (%) Product
	a b	-9.467 -9.263	51 21	3a
	c d	-8.929 -9.197	10 18	3b

Table 2

 2 Photochemical and photophysical characteristics of styryl dyes 1, 2 and products of their photocyclization 3a,b and 4a,b.Figure 2 TCSPC histograms of (1) instrumental response, (2) fluorescence decay of 3a in cyclohexane and (3) the best biexponential fit of fluorescence decay in log scale. Excitation with 340 nm NanoLED.

	Compound	l abs /nm	l fl /nm	F fl (%)	Stokes shift/cm -1	F E-Z , F Z-E , F Z-(cyclized products) (%)	t 1 /ns (%)	t 2 /ns (%)
	1	318	356		7.1		3360	39, 44, 2.8	0.41 (100)	-
	3a	267	367		4.5		10200	-	0.71 (91)	6.74 (9)
	3b	265	363		3.2		10200	-	0.28 (50)	1.10 (50)
	2	316	356		8.1		3560	44, 49, 4.5	0.40 (100)	-
	4a	266	365		2.8		10200	-	1.15 (97)	7.40 (3)
	4b	269	362		3.8		9550	-	0.67 (100)	-
	10000
	1000
	Counts		3
	100	1			2
		5	10	15	20	25	30
				t/ns

This work was supported by the Russian Science Foundation (grant no. 17-73-30036). The equipment from Center of Collective Facilities of A. N. Nesmeyanov Institute of Organo element Compounds was used.

 8,9,11,[START_REF] Irie | Phororeactive Materials for Ultrahigh-Density Optical Memory[END_REF]14,15,17,3' 5,[START_REF]Handbook of Synthetic Photochemistry[END_REF]naphtho [2,3-b] [1,4,7,10,13]pentaoxacyclopentadecine 4b: yield 14%, mp 138-140 C. 1 H NMR (400 MHz, CDCl 3 ) d: 3.82 (m, 8 H, CH 2 O), 4.00 (m, 4 H, CH 2 O), 4.27 (m, 2 H, CH 2 O), 4.32 (m, 2 H, CH 2 O), 7.23 (s, 1H, H-6), 7.35 (s, 1H, H-20), 7.41 (d, 1H, Th, 3 J 5.3 Hz), 7.42 (d, 1H, Th, 3 J 5.3 Hz), 7.58 (d, 1H, Ar, 3 J 8.6 Hz), 7.70 (d, 1H, Ar, 3 J 8.6 Hz). 13 C NMR (APT) (100 MHz, CDCl 3 ) d: 60.39, 68.56, 69.26, 69.33, 70.24, 71.11, 70.33, 71.04 (CH 2 ), 104.83, 109.77, 120.26, 123.85, 124.05, 125.16 (C tert ), 124.41, 126.12, 136.21, 136.28, 148.63, 149.50 (C quat ). MS (ESI), m/z (%): 374 [M] + (100). Found (%): C, 64.23; H, 5.89. Calc. for C 20 H 22 O 5 S (%): C, 64.15; H, 5.92. ‡ Crystal data for 1. Crystals suitable for X-ray diffraction were grown up by slow evaporation of solution in CH 2 Cl 2 . X-ray diffraction data were collected on a Bruker SMART APEX II diffractometer [l(MoKa) = = 0.71073 Å, w-scans, 2q < 61.53 ]. Colorless crystals of C 14 H 14 O 2 S (M = 246.31) at 120(2) K are monoclinic, space group P2 1 /c, a = = 9.0343(4), b = 7.8258(4) and c = 17.5901(9) Å, b = 97.7296(10) , V = 1232.33(10) Å 3 , Z = 4, d calc = 1.328 g cm -3 , m = 2.49 cm -1 , F(000) = 520.

Frames were integrated using the Bruker SAINT software package 24 by a narrow-frame algorithm. A semi-empirical absorption correction was applied with the SADABS 25 program using the intensity data of the equivalent reflections. Intensities of 3785 independent reflections (R int = = 0.0270) out of 12685 collected were used in structure solution and refinement. The structure was solved by direct methods and refined by the full-matrix least-squares technique against F 2 in anisotropic approximation. The positions of hydrogen atoms were calculated. Hydrogen atoms were refined in riding model with U iso (H) equal to 1.5U eq (C) and 1.2U eq (C) of the connected methyl carbon and other carbon atoms. Due to low contribution of the minor disordered component of the thiophene ring to the diffraction, the bond lengths and thermal parameters of this component were constrained to be the same as for the major component (SHELXL SAME and EADP instruc tions). The refinement converged to R 1 = 0.0410 [calculated for 3099 observed reflections with I >2s(I)], wR 2 = 0.1118 and GOF = 1.048. All calculations were performed with SHELX software package. 26 For more details, see Online Supplementary Materials.

CCDC 1811313 contains the supplementary crystallographic data for this paper. These data can be obtained free of charge from The Cambridge Crystallographic Data Centre via http://www.ccdc.cam.ac.uk.


Jorge Veiga
email: jorge.veiga@udc.es

Roberto R Expósito

Bruno Raffin

Juan Tourino

Juan Touriño

Optimization of Real-World MapReduce Applications With Flame-MR: Practical Use Cases

Keywords: Big Data, MapReduce, performance optimization, bioinformatics, visualization

come

I. INTRODUCTION

Nowadays, Big Data applications are employed in a wide range of industrial and research fields to extract meaningful information from large datasets. The adoption of user-friendly technologies like the MapReduce programming model [START_REF] Dean | MapReduce: simplified data processing on large clusters[END_REF] has allowed non-expert programmers to develop large-scale distributed applications without needing to implement lowlevel functionalities such as data movement and parallelism. This enables them to focus on the actual data processing needed to calculate the desired result.

However, MapReduce applications do not always leverage the computational capabilities of the underlying system. This is often caused by performance drawbacks in the design of popular MapReduce frameworks like Hadoop [START_REF]Apache Hadoop[END_REF], which incurs limited efficiency on resource usage and data pipelining. Moreover, non-expert programmers can introduce inefficiencies in their applications due to the unawareness of certain framework functionalities (e.g. custom data formats). Although more advanced alternatives like Spark [START_REF] Zaharia | Apache Spark: a unified engine for Big Data processing[END_REF] and Hama [START_REF] Siddique | Apache Hama: an emerging bulk synchronous parallel computing framework for Big Data applications[END_REF] would allow improving the performance of existing Hadoop workloads, they require to rewrite the source code completely, and so are not always a feasible option. To solve this problem, new inmemory frameworks have been developed to transparently improve the performance of existing Hadoop applications, such as Flame-MR [START_REF] Veiga | Flame-MR: an event-driven architecture for MapReduce applications[END_REF], [START_REF]Enhancing in-memory efficiency for MapReduce-based data processing[END_REF]. This framework allows accelerating such applications without changing their source code.

In our previous work [START_REF]Enhancing in-memory efficiency for MapReduce-based data processing[END_REF], the acceleration of Flame-MR was experimentally demonstrated by conducting performance evaluations with synthetic benchmarks. However, the performance of these benchmarks may not always correspond with the one that can be obtained in practical scenarios. This paper aims to overcome this limitation by presenting an in-depth analysis of the performance benefits provided by Flame-MR using three real-world Big Data applications. The main contributions are:

• The identification of significant differences between realworld applications and standard benchmarks, which underscores the importance of using real cases when evaluating Big Data frameworks. • A detailed description of the techniques used by Flame-MR to adapt to the characteristics of real-world applications, like custom input and output formats and data objects. These techniques provide portability while maintaining performance optimizations. • An improved version of Flame-MR that includes a new load balancing mode to speed up the processing of skewed datasets. • The optimization of three real Hadoop applications with Flame-MR to justify its efficiency by alleviating code inefficiencies and load balancing problems. Performance improvements higher than 40% are obtained in all cases. The rest of the paper is organized as follows: Sections II and III introduce the background and related work, respectively. Sections IV, V and VI analyze the optimization of three use cases based on the MapReduce model. First, Section IV describes the optimization of VELaSSCo, a visualization architecture for simulation data. Second, Section V analyzes CloudRS, a bioinformatics application for error removal in genomic datasets. Third, Section VI presents MarDRe, another genomic application that removes duplicate and near-duplicate reads. Finally, Section VII provides some general conclusions about the results gathered in the previous use cases.

II. BACKGROUND

The MapReduce programming model was originally proposed by Google in [START_REF] Dean | MapReduce: simplified data processing on large clusters[END_REF]. This model allows developing largescale Big Data workloads by keeping some implementation details such as parallelization and data communication hidden to the programmer. The only thing that has to be defined are the data processing functions, map and reduce, that operate the input data represented in form of key-value pairs. The map function processes each input pair independently to extract the Nowadays, the de-facto standard implementation of MapReduce is Hadoop [START_REF]Apache Hadoop[END_REF], an open-source Java-based framework. It mainly consists of two parts, the MapReduce data engine and the Hadoop Distributed File System (HDFS) [START_REF] Shvachko | The Hadoop Distributed File System[END_REF], which distributes the storage of large datasets over the nodes of a cluster. Hadoop workloads commonly use the MapReduce model to process textual data stored in HDFS, following several steps: input, map, shuffle, merge, reduce and output. These steps are depicted in Figure 1. As can be seen, the input dataset stored in HDFS is divided into many splits that are read by map operations to extract the relevant key-value pairs. These key-value pairs are partitioned, sorted by key and sent to the nodes where they will be merged to form the reduce input. Each reduce operation reads the pairs contained in its input partition, processing them to generate the output result that is written to HDFS.

Hadoop can adapt its behavior to the particular needs of each application, providing a wide set of configuration options to do so. This includes the setting of some software components defined via Java interfaces, modifying their implementation according to the specific computation that the user needs to perform. For example, the user can configure a different input and output formatter class if the data is not in textual format. Similarly, users can use primitive data types included in Hadoop or define their own ones by developing a custom implementation of the Writable interface. This interface establishes the methods that the custom data types need to implement, which are mandatory to serialize and compare the data objects.

Many applications use Hadoop to carry out MapReduce workloads. However, Hadoop presents some performance bottlenecks that hinder its utilization for large-scale analytics due to poor resource utilization and inefficient data parallelism. This situation has caused the appearance of several alternative frameworks like Spark [START_REF] Zaharia | Apache Spark: a unified engine for Big Data processing[END_REF] and Hama [START_REF] Siddique | Apache Hama: an emerging bulk synchronous parallel computing framework for Big Data applications[END_REF], which can be used to execute Big Data workloads with a more flexible API and increased performance. However, rewriting existing Hadoop applications to the new APIs generally requires a significant programming effort. Furthermore, the source code is not always publicly available, which precludes the users from rewriting it.

Our previous work focused on the development of Flame-MR [START_REF] Veiga | Flame-MR: an event-driven architecture for MapReduce applications[END_REF], an easy-to-use MapReduce framework that gives solution to this problem by accelerating Hadoop applications without changing the source code defined by the user. Flame-MR replaces transparently the underlying implementation of the Hadoop MapReduce data engine by an in-memory architecture that leverages system resources efficiently.

The operation of Flame-MR is based on the deployment of several Worker processes over the nodes of a cluster. Each Worker is in charge of executing multiple map and reduce operations by using an event-driven architecture shown in Figure 2. The thread pool executes the operations concurrently, scheduling them to pipeline data processing and data movement steps. The data pool allocates memory buffers in an efficient way, reducing the amount of buffer creations [START_REF]Enhancing in-memory efficiency for MapReduce-based data processing[END_REF]. Once the buffers are filled with data, they are stored into in-memory data structures to be processed by subsequent operations.

Performance is further improved by minimizing the connections needed to read and write textual data to HDFS, working with full input splits in memory. Moreover, primitive data types of Hadoop are modified to avoid the use of redundant memory copies, using instead references to the serialized data to optimize pair copies and comparisons. The Hadoop data engine is also accelerated by using efficient sort and merge algorithms. Flame-MR has been assessed by means of synthetic benchmarks, showing significant performance improvement over Hadoop and other Hadoop-based alternatives [START_REF] Veiga | Flame-MR: an event-driven architecture for MapReduce applications[END_REF] and also providing competitive results compared to Spark [START_REF]Enhancing in-memory efficiency for MapReduce-based data processing[END_REF]. Many papers in the literature have compared the performance of the MapReduce model when using different data processing engines (e.g., NativeTask [START_REF] Yang | NativeTask: a Hadoop compatible framework for high performance[END_REF]), file systems (e.g. MARIANE [START_REF] Fadika | MARIANE: using MapReduce in HPC environments[END_REF]), and network interconnects (e.g. RDMA-Hadoop [START_REF] Wasi-Ur-Rahman | High-performance RDMA-based design of Hadoop MapReduce over InfiniBand[END_REF]). These works generally evaluate their proposals by executing popular Big Data benchmarks like TeraSort or K-Means. However, the lack of performance results with realworld applications makes it difficult to determine the actual performance benefit that a user can obtain when replacing Hadoop with any of the optimized alternatives.

Regarding large-scale applications employed in real use cases, their optimization is often performed by translating their source code to a more efficient computing paradigm. For example, Kira [START_REF] Zhang | Kira: processing astronomy imagery using Big Data technology[END_REF] is a distributed astronomy image processing toolkit on top of Spark. It can obtain a 3.7× speedup on the Amazon EC2 cloud over an equivalent parallel implementation written in C and running on the GlusterFS file system. A similar approach has been employed in [START_REF] Gutsche | Big Data in HEP: a comprehensive use case study[END_REF] to adapt high energy physics workflows to Spark, obtaining improved usability and performance when compared to other existing sequential implementations like ROOT [START_REF] Brun | ROOT -an object oriented data analysis framework[END_REF]. Although these works prove to accelerate the execution of real-world applications, a considerable effort is required to translate existing applications and libraries to a new computing paradigm.

Some other works use these applications to determine the performance benefits of framework optimizations. For example, the Kira toolkit is used in [START_REF] Tatineni | Experiences and benefits of running RDMA-Hadoop and Spark on SDSC Comet[END_REF] to evaluate RDMA-Spark [START_REF] Lu | High-performance design of Apache Spark with RDMA and its benefits on various workloads[END_REF], which improves the results of standard Spark with a 1.21× speedup. In the case of Hadoop, the authors of OEHadoop [START_REF] Tang | OEHadoop: accelerate Hadoop applications by co-designing Hadoop with Data Center Network[END_REF] evaluate their proposal by simulating a Facebook job trace extracted from the SWIM project [START_REF] Chen | Interactive analytical processing in Big Data systems: a cross-industry study of MapReduce workloads[END_REF]. OEHadoop, which offloads data replication to a low-level optical multicast system, obtains better performance than the original Hadoop, although the results provided are extracted from simulations and not from empirical data.

One of the most important requirements that framework optimizations must meet is portability, as the same MapReduce application is likely to be executed in many different systems. This makes Flame-MR a good candidate to improve performance by leveraging memory resources, as it has been specifically designed to accelerate applications in a portable way. Other frameworks that employ in-memory optimizations are NativeTask [START_REF] Yang | NativeTask: a Hadoop compatible framework for high performance[END_REF] and M3R [START_REF] Shinnar | M3R: increased performance for in-memory Hadoop jobs[END_REF]. On the one hand, NativeTask is based on a native C++ implementation that replaces the task management of map and reduce functions, while also optimizing the cache awareness of the merge-sort mechanism [START_REF] Yan | Using memory in the right way to accelerate Big Data processing[END_REF]. As these optimizations are highly dependent on the underlying system, they do not keep portability. On the other hand, M3R is an in-memory framework based on the X10 programming language [START_REF] Charles | X10: an object-oriented approach to non-uniform cluster computing[END_REF]. Although it accelerates Hadoop workloads by reducing the shuffling overhead and caching intermediate data, it is restricted to Hadoop jobs that can fit in memory. These characteristics prevent the utilization of M3R for real-world Big Data use cases.

As commented in the previous section, the performance benefits of Flame-MR when executing synthetic benchmarks have already been assessed. However, the artificial nature of this kind of workloads makes it difficult to extrapolate these results to practical use cases. This paper provides an in-depth performance analysis of three real-world Hadoop applications, describing the characteristics and challenges of each workload. The main objective is to determine the performance benefits that Flame-MR is able to provide in practice without needing to change the underlying computing paradigm.

IV. VELASSCO: DATA VISUALIZATION QUERIES

This section addresses the optimization of VELaSSCo [START_REF] Lange | A Hadoop use case for engineering data[END_REF], a Big Data visualization architecture that relies on the MapReduce model to extract information from simulation datasets. More details of this project are provided in Section IV-A, while the main characteristics of the MapReduce workloads are described in Section IV-B. Section IV-C explains the main challenges of running these workloads with Flame-MR to improve their performance. The experimental configuration and performance results are then presented in Sections IV-D and IV-E, respectively. Finally, some concluding remarks are provided in Section IV-F.

A. Overview

VELaSSCo is a query-based visualization framework that aims at providing users with a tool to manipulate and visualize large simulation datasets. These datasets are generated by large parallel simulations relying on Finite Element Methods (FEM) or Discrete Element Methods (DEM). For both methods the simulation updates the properties of the nodes (FEM) or particles (DEM) at each time step. The user runs a 3D visualization client to request the execution of specific visualization algorithms on given parts of the data. The query is sent to the VELaSSCo cluster and translated into a Hadoop job that queries the input data and performs the expected transformation. The result is sent back to the client for the final 3D rendering and display. The VELaSSCo architecture can be decomposed into three subsystems: client, analytics and storage, described next.

The client subsystem provides data visualization to the user, generating a new query when the user performs an action. Each query has a certain type depending on the action performed by the user. Analytical queries are the ones that require to extract some information from the dataset by means of a MapReduce workload (e.g. calculating the bounding box of a model). The analytics subsystem is in charge of receiving these queries and determining the computation needed to complete each one. That computation is performed by a MapReduce workload on a Hadoop cluster. The workloads employed in VELaSSCo consist of a single MapReduce job that typically operates over a subset of the dataset (a few simulation time steps for instance). Finally, the data persistence is performed by the storage subsystem. This subsystem employs HDFS to distribute the data among the computing nodes of the cluster. It also relies on HBase [START_REF]Apache HBase: Hadoop distributed Big Data store[END_REF], a database system on top of HDFS, to allow the extraction of parts of the dataset without reading it entirely. This optimizes the amount of I/O operations needed to perform the computations. Instead of searching the relevant data through the entire dataset, the MapReduce workload uses the key-value format provided by HBase to fetch the required elements. The indexed system used in HBase accelerates the retrieving operation by avoiding the reading of unnecessary data.

As VELaSSCo is a real-time visualization platform, the performance of the actions executed by the user is crucial to ensure an appropriate user experience. However, Hadoop is not able to achieve this goal when dealing with largescale datasets. This use case focuses on the acceleration of the queries used in the analytics subsystem of VELaSSCo by using Flame-MR.

B. MapReduce implementation

We list below the main analytical queries included in VELaSSCo:

• GetBoundingBoxOfAModel (BB): Computes the spatial bounding box for the selected dataset, i.e the min and max coordinate of the enclosed elements in the x, y and z dimensions.

• GetBoundaryOfAMesh (BM): Computes the set of elements that are at the boundary of the selected mesh, i.e. the surface given by the triangles belonging to only one mesh cell. • GetListOfVerticesFromMesh (LVM): Obtains a list of identifiers (IDs) of the elements contained in a mesh. • GetMissingIDsOfVerticesWithoutResults (MIV): Obtains the IDs of those mesh elements that do not contain any simulation result. • GetSimplifiedMesh (SM): Obtains a simplified version of the mesh model, reducing the total dataset size by combining nearby elements.

As mentioned in the previous section, these queries are performed by MapReduce workloads that are composed of a single job. All jobs extract the input data from HBase, selecting the relevant elements according to the information provided by the user. To read the data, the MapReduce implementation is based on a custom input formatter provided by HBase, which is used by the mappers to iterate over the entries allocated to them. Once the output of the job is calculated, it is converted to text files and stored in HDFS in order to be accessible by the client subsystem.

The implementation of each query includes the definition of the map and reduce functions. These functions use custom data types defined in VELaSSCo, which implement the Writable interface required for data serialization. So, map and reduce functions are configured to use these data types when reading and writing data.

C. Challenges

The use of Flame-MR to optimize the VELaSSCo queries must take into account the characteristics that differ from standard Hadoop jobs. In particular, reading input data from HBase and using custom data types must be handled correctly to avoid incompatibility problems. This section describes how they are supported in Flame-MR.

Flame-MR is oriented to processing large textual datasets stored in HDFS, which is a common use case in MapReduce applications. Therefore, the reading of input data has been designed to make the common case fast. When launching a map operation, Flame-MR connects to HDFS and reads a full input split (e.g. 256 MB) to memory by copying the data to a set of medium-sized buffers (e.g. 1 MB) allocated in the data pool (see Figure 2). Once the input split is read, the connection to HDFS is closed and the data buffers are parsed in memory to obtain the input pairs and feed the mappers.

The in-memory parsing mechanism of Flame-MR is only possible when the input dataset is stored in HDFS in textual format. For other formats, the data source is unknown, and the software interface defined by Hadoop only allows reading the input pairs one by one. Therefore, copying an input split entirely to memory is not allowed and the reading of input data needs to be addressed differently. That is the case of VELaSSCo, which reads the data from HBase. When a map operation is launched in Flame-MR, the input formatter connects to the HBase server to read the data contained in the input split. Then, the map operation uses the interfaces provided by the input formatter class to read the input pairs, passing them to the user-defined map function. By doing this, the correct functioning of the queries is ensured. Note that this behavior can be extrapolated to any formatter class.

The use of custom data objects in VELaSSCo has also implications for Flame-MR. This happens because Flame-MR modifies the behavior of primitive Hadoop data types, like text and numerical types, in order to optimize read and write operations. These modifications include the use of in-memory addressing of serialized data to avoid the creation of data objects in sort and copy operations. When a key-value pair is stored in a buffer, a header is added to indicate the pair and key lengths, which will be used to read data without creating the objects. Therefore, the implementation of primitive data types in Flame-MR is extended with additional methods to obtain the length of data objects before writing them to the buffer. As VELaSSCo implements specific data objects inside each query, Flame-MR must adapt its behavior to comply with the standard Writable interface defined by Hadoop, which does not provide any information about the length of the objects. The serialization mechanism of Hadoop primitive data types in Flame-MR is shown in Figure 3a. The pair and key length are calculated before writing the key-value pair to the buffer. To obtain the same results with custom Writable objects, Flame-MR performs the mechanism shown in Figure 3b. Pair and key lengths are unknown beforehand, so their positions must be skipped, writing the key-value pair after them. Once the data has been written, the lengths are calculated according to the writing position after copying the key-value pair. The lengths are then written by going backwards on the data buffer to the original position. This mechanism ensures compatibility with all types of Writable objects, while maintaining the inmemory optimizations of Flame-MR.

D. Experimental configuration

This section describes the experimental testbed used in the comparison between Hadoop and Flame-MR when executing the VELaSSCo queries. The experiments have been conducted in the Grid'5000 infrastructure [START_REF]Grid'5000: large-scale resource provisioning network[END_REF]. Two cluster sizes (n) have been used: 17 and 25 nodes with 1 master and n-1 slaves. These nodes are equipped with 2 Intel Haswell-based processors with 8 physical cores each (i.e. 16 cores per node), 128 GB of memory and 2 local disks of 558 GB each (see Table I for more details).

The experiments have used HBase 1.2.4, Hadoop 2.7.3 and Flame-MR 1.1 (available at http://flamemr.des.udc.es). The configuration of the frameworks has been carefully set up by following their user guides, taking into account the characteristics of the systems (e.g. number of CPU cores, memory size). The most important parameters of the resulting configuration are shown in Table II, including a brief explanation of each one.

The VELaSSCo queries used in the evaluation are the ones described in Section IV-B. The input dataset has been extracted from a FEM simulation that represents the wind flow in the city of Barcelona with an eight-meter resolution. This dataset has 12,089,137 vertices and occupies 367 GB. For each query, the graphs show the median elapsed time of 10 executions, although the standard deviations observed were not significant.

E. Performance results

Figures 4a and4b show the execution times of the VE-LaSSCo queries using 17 and 25 nodes, respectively. Flame-MR widely outperforms Hadoop with both cluster sizes, showing an average reduction in execution time of 87% with 17 nodes and 88% with 25 nodes. This reduction is due to the more efficient architecture of Flame-MR, which can better leverage the memory and CPU resources of the system. Note that each Worker process in Flame-MR can schedule multiple map and reduce operations, allocating them to the cores available as they become idle. Therefore, the Worker can use the same HBase connection for all map operations. Instead, Hadoop allocates a single Java process to each map and reduce task, and so it creates an HBase connection for each one, increasing the overhead. This enables Flame-MR to process more HBase requests per unit time compared to Hadoop, which is reflected in the information counters provided by HBase.

F. Remarks

This section addressed the optimization of analytical queries that process datasets stored in HBase. These queries implement custom input formats and data types by using the class interfaces provided by Hadoop. Flame-MR is able to adapt to these characteristics without hindering the optimizations implemented in its underlying in-memory architecture. Using Flame-MR, the performance of the queries is improved by

V. CLOUDRS: ERROR REMOVAL IN GENOMIC DATA

This section addresses the optimization of CloudRS [START_REF] Chen | CloudRS: an error correction algorithm of high-throughput sequencing data based on scalable framework[END_REF], a bioinformatics tool that detects and corrects errors in large genomic datasets, following the same structure as Section IV.

A. Overview

The datasets generated by Next Generation Sequencing (NGS) platforms are composed of a large number of DNA sequence fragments, which are small pieces of genomic information contained in a string of characters (called reads). Each character of a read represents a DNA base, namely Adenine (A), Cytosine (C), Guanine (G), and Thymine (T). The analysis of these datasets is performed by processing the sequences and identifying relationships between them.

During the generation of genomic datasets, NGS sequencers often introduce errors by placing incorrect bases in the reads. This can affect the quality of the results obtained by downstream analysis, and so it is usually minimized by introducing an error correction phase in the preprocessing stage of the NGS pipeline. In fact, this is a critical step in NGS workflows like de novo genome assembly or DNA resequencing. CloudRS is a popular tool for performing this preprocessing task, being based on the ReadStack (RS) algorithm [START_REF] Gnerre | High-quality draft assemblies of mammalian genomes from massively parallel sequence data[END_REF]. This algorithm makes use of the characteristics of NGS datasets to identify common patterns in the sequences and correct the mismatching ones.

The DNA sequences that compose a dataset are not necessarily disjoint, as they can share information due to the overlap of reads performed by the sequencer. CloudRS takes advantage of this characteristic to identify redundant information in the sequences and correct errors in the bases. First, it splits each sequence into several subsequences. Second, it compares the different candidates for each subsequence, choosing the one that appears most of the times.

CloudRS is implemented with the MapReduce model by operating over datasets stored in HDFS. As it is a common step in large NGS workflows, its performance is crucial to obtain the results of the analysis in a reasonable time. For that reason, it has been chosen to be optimized with Flame-MR. Further details about its implementation are provided in the next section.

B. MapReduce implementation

CloudRS is an iterative workload that follows several phases to process the input dataset, explained below:

1) LoadReads: This phase prepares the input dataset to be processed, discarding noisy information and converting the sequences into a more suitable format for Hadoop.

In order to avoid the comparison of very repetitive sequences, it also builds a list of the most frequent subsequences. Later, this list is used to filter them out and avoid workload imbalance. 2) PreCorrection: Each sequence is split into different subsequences that are candidates in the next phases. The candidates for each subsequence are aligned to allow their comparison, using a wildcard pattern. 3) ErrorCorrection: The set of subsequence candidates is iterated through by using the information obtained in the previous phases. First, the most frequent subsequences are filtered out. Then, the candidates are compared by emitting a vote for each position. When all the votes have been emitted, the correct alternative is chosen by majority. This calculation repeats several times until the obtained subsequences remain invariant. 4) Screening: Once the correct subsequences have been calculated, the input dataset is reprocessed to fix the errors, replacing each subsequence with its corresponding correct alternative. 5) Conversion: The output dataset is converted to a standard format in order to be processed by subsequent NGS applications (e.g. sequence alignment). Using these five phases, the execution of CloudRS involves a total of 11 MapReduce jobs, some of them being repeated during the ErrorCorrection phase. Their implementation uses an old version of the Hadoop API, although this only affects the interfaces used by the source code of the workload. CloudRS also takes advantage of the DistributedCache feature provided by Hadoop to make the list of most frequent sequences available to the mappers during the ErrorCorrection phase.

The input and output formatter classes in CloudRS are standard ones that operate over textual data stored in HDFS. Instead of using a custom formatter, CloudRS formats the data within the user-defined map and reduce functions. CloudRS uses standard Hadoop Text objects to represent the data as strings, separating the different fields by using special characters. Note that this is a very inefficient implementation compared to the use of a custom formatter that can represent in-memory data as binary objects. The approach of CloudRS requires to parse data objects from textual data, while also having to convert them to strings when writing the output.

C. Challenges

As explained in the previous section, CloudRS is an iterative workload that executes several MapReduce jobs to obtain the final result. The resource management of Flame-MR adapts better to this kind of computation than Hadoop, thus providing better performance. On the one hand, Hadoop allocates one Java process per map/reduce task. Therefore, Hadoop needs to create many map and reduce processes at the start of each job, stopping them when the job is finished. On the other hand, Flame-MR deploys a single Java process per Worker and uses a thread pool to execute the map and reduce functions (see Figure 2). These processes are reutilized between MapReduce jobs until the entire workload is finished. Note that Flame-MR also benefits from the reutilization of internal data structures like the allocation of memory buffers.

Regarding data input and output, Flame-MR is oriented to the processing of large textual datasets, as mentioned in Section IV-C. Therefore, it uses optimized input and output formatters that minimize the amount of connections to HDFS. Similarly, the implementation of textual data objects used in Flame-MR reduces the amount of memory copies and object creations when performing sort and copy operations. CloudRS makes use of both characteristics, and so it is especially well suited to be optimized with Flame-MR. However, the inefficient data formatting explained in the previous section is intrinsic to CloudRS, as it is performed inside the map/reduce functions. The goal of Flame-MR is to improve applications' performance without modifying their source code, and so we cannot modify those user-defined functions. Therefore, the inefficiency of the data formatting will also be present in Flame-MR, although it is alleviated by using its efficient implementation of textual data objects.

The use of the old Hadoop API is also supported in Flame-MR by connecting old classes and methods with its corresponding counterparts in the new API. Furthermore, Flame-MR supports the use of the DistributedCache by copying the data files required by the mappers to the computing nodes where they are being executed, thus making the data available to the application.

D. Experimental configuration

This section describes the experimental configuration used to evaluate CloudRS with Hadoop and Flame-MR. As genomic applications are executed in many kinds of systems, the evaluation has considered two different scenarios: a private cluster with 9 nodes, Pluton, and a public cloud platform, Microsoft Azure [START_REF]Microsoft Azure: cloud computing platform & services[END_REF], using 17 and 25 instances. As in the case of VELaSSCo, each cluster size n corresponds to 1 master and n-1 slaves.

The hardware and software characteristics of Pluton and Azure are shown in Tables III and IV, respectively. Pluton nodes are equipped with 16 cores each, 64 GB of memory and one local disk of 1 TB, being interconnected via InfiniBand FDR and Gigabit Ethernet (GbE). The experiments in Azure The experiments have used Hadoop 2.7.4 and Flame-MR 1.1. The configuration has been adapted to the characteristics of the systems, resulting in the parameters shown in Tables V and VI for Pluton and Azure, respectively. These parameters have been described in Table II. Furthermore, the frameworks have used the IP over InfiniBand (IPoIB) interface available in Pluton, which allows taking advantage of the In-finiBand network via the IP protocol. Finally, some parameters such as the HDFS block size have been experimentally tuned to obtain the best performance on each system.

The input dataset used in the experiments is SRR921890, which has been obtained from the DDBJ Sequence Read Archive (DRA) [START_REF]DDBJ Sequence Read Archive (DRA)[END_REF]. It is composed of 16 million sequences of 100 bases each (5.2 GB in total). The results shown in the following section correspond to the median elapsed time of 10 executions. The standard deviations observed were not significant.

In this use case, the experiments have been conducted by using the Big Data Evaluator (BDEv) tool [START_REF] Veiga | BDEv 3.0: energy efficiency and microarchitectural characterization of Big Data processing frameworks[END_REF] (version 3.1, available at http://bdev.des.udc.es). This tool allows automating the configuration and deployment of the frameworks and the execution of the workloads.

E. Performance results

Figure 5 shows the performance results of CloudRS. As can be seen, Flame-MR clearly outperforms Hadoop in both testbeds. In fact, Flame-MR obtains a 78% reduction in execution time in Pluton. In the case of Azure, it obtains a reduction of approximately 40% for both cluster sizes. Note that Hadoop presents a huge performance improvement when scaling from Pluton with 9 nodes to Azure with 17 nodes. In addition to the double amount of slave nodes, this improvement is due to the better node characteristics of Azure. Compared to Pluton, Azure provides a more recent CPU microarchitecture and doubles the available memory, while the SSD disk decreases I/O waiting times. Furthermore, the execution time of Flame-MR with 9 nodes in Pluton is almost the same as using Hadoop in Azure with 17 nodes. Therefore, Flame-MR allows reducing the execution time of CloudRS without needing to increase the computational resources, obtaining a performance improvement equivalent to using a double-sized cluster in this specific case, minimizing incurred costs in public cloud platforms such as Azure.

F. Remarks

The use of Flame-MR to optimize CloudRS has shown an important reduction in execution time. Taking into account that the data formatting inefficiency of the source code of CloudRS cannot be avoided, this use case is a good example of how Flame-MR can reduce the performance impact of those inefficiencies, without redesigning the software or employing further computing resources.

VI. MARDRE: DUPLICATE READ REMOVAL IN GENOME SEQUENCING DATA

This section addresses the optimization of MarDRe [START_REF] Expósito | MarDRe: efficient MapReduce-based removal of duplicate DNA reads in the cloud[END_REF], a bioinformatics application that removes duplicate reads in large genomic datasets, following the same structure as Sections IV and V.

A. Overview

As explained in Section V-A, genomic datasets generated by NGS sequencers contain redundant information due to the existence of overlapped reads. This characteristic causes the appearance of duplicate or near-duplicate sequences in large datasets, which neither provide new information nor improve the results of analytical processes. However, processing them consumes system resources and wastes execution time. Therefore, they are often removed to decrease the overall runtime of the downstream analysis.

MarDRe is a MapReduce application that is used to detect and remove duplicate sequences in genomic datasets stored in HDFS. It is based on a prefix-clustering mechanism that groups the sequences by similarity. Then, the sequences within a group are compared by using an optimized algorithm that discards the sequences that do not provide new information.

As in the case of CloudRS, MarDRe is usually performed in the preprocessing stage. Therefore, reducing its execution time can have a significant impact on the performance of the overall NGS pipeline. Further details of its implementation are provided in the next section.

B. MapReduce implementation

The MapReduce workload used in MarDRe performs a single Hadoop job to process the data stored in HDFS. In contrast to CloudRS, MarDRe supports input datasets stored in FASTQ/FASTA, which are standard formats commonly employed in genomic datasets.

The map phase is used to cluster the DNA sequences into groups. Each mapper reads the data belonging to its input split by using a custom formatter that reads the sequences in FASTQ/FASTA format. The input sequences are then divided into prefix and suffix to group the ones that share the same prefix. During the shuffle phase, the prefix is used as key to partition and sort the map output pairs. The value of the pair contains the sequence information by using a custom data type defined in MarDRe. Next, the map output pairs are sent to the reducer nodes where they are processed. Once the reducers receive all the assigned sequences, they carry out the comparison to filter out the duplicates by using the optimized algorithm presented in [START_REF] González-Domínguez | ParDRe: faster parallel duplicated reads removal tool for sequencing studies[END_REF]. This algorithm does not compare all the sequences within each group, but uses the first one as a reference for the rest. If the number of mismatches of a sequence with respect to the first one is higher than a user-defined threshold, the sequence is discarded. Moreover, the bases of the sequences are not compared one by one. Instead, a 4-bit encoding is used to represent the bases, determining the differences by using a bit-wise XOR operation. After that, the output of the reducers containing the remaining sequences without duplicates is written to HDFS in FASTQ/FASTA format.

MarDRe is especially well suited to the MapReduce model, as the main part of its clustering algorithm is performed by the underlying grouping-by-key mechanism of Hadoop. Furthermore, its implementation leverages the use of custom formatters and data objects to avoid inefficient parsing of the input dataset. Although MarDRe shows good performance with balanced workloads, real-world datasets are highly skewed, with lots of sequences that share a common prefix. This situation introduces important load balancing problems in the reduce phase due to the comparison of large sets of sequences. This causes some reducers to have excessive execution times. As a MapReduce job has to wait for all reducers to finish, the load balancing problem in the reduce phase affects the

C. Challenges

Flame-MR must adapt to the characteristics of MarDRe when optimizing its performance. As in the VELaSSCo use case, the use of custom formatters and data objects in MarDRe requires the utilization of the standard API provided by Hadoop, while keeping the in-memory optimizations, as explained in Section IV-C.

Regarding the load balancing problem explained before, the standard behavior of Flame-MR emulates the way Hadoop processes the data without modifying the operation of the map and reduce functions. Therefore, load imbalance also affects Flame-MR. To alleviate it without changing the source code of the application, a new load balancing mode has been developed in Flame-MR version 1.1. During the reduce phase, large partitions are detected and split into several chunks. In doing so, the computation is parallelized and the execution time of heavy-loaded reducers is decreased.

Figure 6 illustrates the operation of the load balancing mode. Instead of processing a large partition with a single reduce operation, the data is split into different chunks with a maximum size calculated upon the number of chunks defined by the user. Next, each chunk is reduced in parallel, writing the output to HDFS. Note that this mechanism is likely to introduce changes in the output results of the reduce phase, as the input pairs are passed to the reduce function in different groups. Therefore, the load balancing mode is only applicable to those Hadoop jobs that can support modifications in the reduce partitioning without affecting the logic of the application, even if the final output suffers slight variations. In the particular case of MarDRe, the splitting of partitions leads to different comparisons to be done between sequences. Although this may modify the actual sequences that are filtered in the end, it does not affect the purpose of the workload as long as the percentage of sequences filtered does not vary significantly. For example, in the experimental results shown in Section VI-E, the amount of duplicate reads filtered did not vary more than 0.02% when using the load balancing mode.

This mode can be activated by the user via configuration, using a single parameter to indicate the number of chunks in which partitions should be split. By default, this value is set to the number of cores per Worker.

D. Experimental configuration

MarDRe and CloudRS are both executed as preprocessing steps of an NGS analysis on Big Data infrastructures. Therefore, the evaluation of MarDRe has employed the same experimental configuration as CloudRS using Pluton and Azure as testbeds (see Tables III-VI in Section V-D), and the BDEv tool to conduct the evaluation. However, the computational requirements of CloudRS are significantly higher than those of MarDRe, and so a larger dataset was used in these experiments: SRR377645. This dataset is composed of 214 million reads of 100 bases each (67 GB).

The evaluation includes the results of Hadoop, Flame-MR and Flame-MR with the load balancing mode activated (labeled as Flame-MR-LB in the graphs). In the experiments, the number of chunks of the load balancing mode has been tuned for improved performance, splitting each partition in 13 and 9 chunks for Pluton and Azure, respectively.

E. Performance results

Figure 7 shows the execution times of MarDRe with Hadoop, Flame-MR and Flame-MR-LB. As can be seen, Flame-MR outperforms Hadoop by 43% in Pluton and by approximately 24% in Azure for both cluster sizes. The improvement provided by Flame-MR-LB is even better, reducing the execution time of Hadoop by 66% both in Pluton and Azure (17 nodes), and by 77% when using 25 nodes in Azure. This huge improvement demonstrates the effectiveness of the load balancing mode explained in Section VI-C, together with the efficient in-memory architecture of Flame-MR.

Note that the execution times of Hadoop and Flame-MR in Azure using 25 nodes are higher than with 17 nodes, which is due to the load balancing problem. With more nodes and thus more reducers, the load per reducer is decreased, but the reducers that process the largest partitions require the same time. This issue, together with the additional overhead of managing more nodes, hinders the performance of both frameworks. However, Flame-MR-LB does not present this problem, obtaining slightly better results with 25 nodes than with 17. In order to provide more information about the load balancing problem of MarDRe, Table VII shows the processing time of the fastest, median and slowest reducer compared to the overall execution time. As can be seen, the time consumed by the slowest reducer is clearly correlated with the overall execution time of the application. Furthermore, there exist huge differences between the fastest and slowest reducers. In the case of Hadoop and Flame-MR, the use of more nodes in Azure decreases the processing time of the fastest and median reducers. This does not always happen with the slowest reducer, which consumes more time with 25 nodes than with 17 for both frameworks. This fact causes the overall execution time to be higher. Flame-MR-LB shows a different behavior. When using 25 nodes, the fastest and median reducers remain almost invariant, while the slowest one consumes less time. This, in turn, reduces the overall execution time of Flame-MR-LB.

F. Remarks

This section has shown the benefits of optimizing MarDRe with Flame-MR. Without modifying its source code, it obtains significant performance improvements by better leveraging the system resources. Furthermore, the new load balancing mode available in Flame-MR has demonstrated its usefulness to reduce the impact of skewed loads in the reduce phase, reducing up to 77% the execution time of Hadoop.

VII. CONCLUSION

The MapReduce computing model and Hadoop are commonly used by many applications to extract valuable information from datasets stored in HDFS. Although other alternatives such as Spark can provide improved performance over Hadoop, the effort of adapting existing MapReduce applications to new APIs can be significant (provided that the source code is available). Flame-MR solves this problem by providing huge performance improvements in a transparent way without needing to change the applications.

This paper has shown three different real-world use cases from two application domains: visualization queries (VE-LaSSCo) and preprocessing of genomic datasets (CloudRS and MarDRe). On the one hand, Flame-MR improves the execution time of the analytical queries of VELaSSCo by adapting its behavior to the custom input formats and data objects defined in the workload. On the other hand, the iterative algorithm performed by CloudRS is significantly accelerated, overcoming some of the inefficiencies of its underlying implementation. Finally, the use of Flame-MR in MarDRe has not only optimized the underlying Hadoop data engine but also alleviated its load balancing problems.

The execution of several use cases with distinct characteristics, together with the assessment of real-world datasets on different systems, have proved the significant performance benefits provided by Flame-MR over Hadoop.

Figure 1 :

 1 Figure 1: Hadoop data flow with multiple map and reduce tasks

Figure 2 :

 2 Figure 2: Flame-MR Worker architecture

Figure 3 :

 3 Figure 3: Data object serialization in Flame-MR

Figure 4 :

 4 Figure 4: Execution times of VELaSSCo queries with Hadoop and Flame-MR

Figure 5 :

 5 Figure 5: Execution times of CloudRS with Hadoop and Flame-MR

Figure 6 :

 6 Figure 6: Load balancing mode in Flame-MR

Figure 7 :

 7 Figure 7: Execution times of MarDRe with Hadoop, Flame-MR and Flame-MR-LB

Table I :

 I Node characteristics of Grid'5000

	Hardware configuration	Software configuration
	CPU model	2 × Intel Xeon E5-2630 v3 (Haswell) OS version	Debian Jessie 8.5
	CPU speed (Turbo)	2.40 GHz (3.20 GHz) Kernel	3.16.0-4
	Cores	16 Java	Oracle JDK 1.8.0 121
	Memory	128 GB DDR4 2133 MHz
	Disk	2 × 558 GB HDD
	Network	4 × 10 Gbps Ethernet

Table II :

 II Configuration of the frameworks in Grid'5000

		Hadoop MapReduce
	Mapper/Reducer heap size	7.25 GB Maximum heap size for Mapper/Reducer processes
	Mappers per node	8	Maximum number of map tasks per node
	Reducers per node	8	Maximum number of reduce tasks per node
	Shuffle parallel copies	20	Parallel transfers per Reducer during shuffle phase
	IO sort MB	1600 MB	Total amount of memory to use while sorting files
	IO sort spill percent	80%	Memory threshold to spill memory data to disk
			Flame-MR
	Worker heap size	44 GB	Maximum heap size for Worker processes
	Workers per node	2	Number of Worker processes per node
	Cores per Worker	8	Number of CPU cores per Worker
	Data pool size	30.8 GB	Total amount of memory to store data buffers
	Data buffer size	1 MB	Amount of memory allocated to each data buffer
			HDFS
	HDFS block size	256 MB	Logical block size for distributed files
	Replication factor	3	Number of distributed copies per block

Table III :

 III Node characteristics of Pluton

	Hardware configuration	Software configuration
	CPU model CPU speed (Turbo)	2 ⇥ Intel Xeon E5-2660 (Sandy Bridge) OS version 2.20 GHz (3 GHz) Kernel	CentOS release 6.8 2.6.32-642
	Cores	16 Java	Oracle JDK 1.8.0 45
	Memory	64 GB DDR3 1600 MHz
	Disk	1 TB HDD
	Network	InfiniBand FDR & GbE
		Table IV: Node characteristics of L16S instances in Azure
	Hardware configuration	Software configuration
	CPU model	Intel Xeon E5-2698B v3 (Haswell) OS version	CentOS release 7.4
	CPU speed	2 GHz Kernel	3.10.0-514
	Virtual cores	16 Java	OpenJDK 1.8.0 151
	Memory	128 GB
	Disk	2.7 TB SSD
	Network	4 × 10 Gbps Ethernet

Table V :

 V Configuration of the frameworks in Pluton

	Hadoop MapReduce	Flame-MR	HDFS
	Mapper/Reducer heap size	3.4 GB Worker heap size 11.8 GB HDFS block size 256 MB
	Mappers per node	8 Workers per node	4 Replication factor	3
	Reducers per node	8 Cores per Worker	4
	Shuffle parallel copies	20 Data pool size	8.3 GB
	IO sort MB	841 MB Data buffer size	512 KB
	IO sort spill percent	80%

Table VI :

 VI Configuration of the frameworks in Azure

	Hadoop MapReduce	Flame-MR	HDFS
	Mapper/Reducer heap size	6.7 GB Worker heap size	24 GB HDFS block size 128 MB
	Mappers per node	8 Workers per node	4 Replication factor	3
	Reducers per node	8 Cores per Worker	4
	Shuffle parallel copies	20 Data pool size	16.8 GB
	IO sort MB	1704 MB Data buffer size	512 KB
	IO sort spill percent	80%
	have been carried out using L16S virtual instances located
	in the West Europe region. These instances have 16 virtual
	cores per node, 128 GB of memory and a virtual SSD disk of
	2.7 TB.

Table VII :

 VII Load balancing in MarDRe

			(a) Pluton (9 nodes)
		Fastest reducer Median reducer Slowest reducer Execution time
	Hadoop	25.7 s	136 s	972.2 s	1168.3 s
	Flame-MR	14.9 s	19.7 s	435.7 s	662.5 s
	Flame-MR-LB	0.004 s	1.1 s	184.2 s	394.7 s
			(b) Azure (17 nodes)
		Fastest reducer Median reducer Slowest reducer Execution time
	Hadoop	12.7 s	22.1 s	259.4 s	316.4 s
	Flame-MR	11.8 s	15.8 s	203.1 s	243.9 s
	Flame-MR-LB	0.001 s	1.1 s	60.5 s	106.3 s
			(c) Azure (25 nodes)
		Fastest reducer Median reducer Slowest reducer Execution time
	Hadoop	8.9 s	13.8 s	346.3 s	398.7 s
	Flame-MR	6 s	8.2 s	254.9 s	299.5 s
	Flame-MR-LB	0.001 s	0.8 s	29.1 s	88.1 s

ACKNOWLEDGMENT

This work was supported by the Ministry of Economy, Industry and Competitiveness of Spain (Project TIN2016-75845-P, AEI/FEDER/EU) and by the FPU Program of the Ministry of Education (grant FPU14/02805). The Grid'5000 testbed used in this paper is supported by Inria, CNRS, RENATER and several French Universities. The authors would like to thank Iván Cores for his contribution to the deployment of VELaSSCo, and also Pierre Neyron and Michael Mercier for their help in the use of the Grid'5000 platform. Also thanks to Microsoft Research for awarding this work with a sponsored Azure account (ref. MS-AZR-0036P).