J M Citerne

Orlac&apos

O Fujita

J.-L Consalvi

J L Torero

G Legros

J M Orlac'

A Guibaud

J M Orlac'h A

Broadband modulated absorption/emission technique to probe sooting flames: Implementation

Keywords: Soot, Broadband diagnostic, Soot volume fraction, Soot temperature

A new optical setup and its associated post-processing have been designed in an effort to map soot related quantities in an axisymmetric flame spreading over solid samples in microgravity environment where setup compactness constraints are stringent. Extending the well-established spectral modulated absorption/emission (S-MAE) technique that uses lasers as light sources together with a sophisticated optical arrangement, LEDs have been associated with broadband optics to enable the broadband modulated absorption/emission (B-MAE) technique. The design and the cautious assessment of the original B-MAE setup are reported in the present paper. Algorithms that need to be reformulated for broadband integration are first validated retrieving both two-dimensional soot temperature and volume fraction fields produced by numerical simulations. Then, these fields are measured with both B-MAE and S-MAE techniques in a largely documented steady laminar non-premixed coflow ethylene/air flame established at normal gravity. Thus, outputs delivered by the B-MAE technique can be compared with those obtained with the S-MAE setup. Both soot temperature and volume fraction are shown to be decently measured by the B-MAE technique. As the spread of the non-buoyant flames to be investigated in the near future is especially driven by radiative heat transfer, the discrepancies between both techniques outputs are commented in the light of the fields of local radiative loss computed from the fields measured by both techniques. As a result, the fields delivered by the B-MAE technique are expected to provide ground-breaking insights into the control of flame spread in the absence of buoyancy, therefore manned spacecraft fire safety.

Introduction

Fire spread mechanisms in microgravity environment is still poorly understood [1] . Yet, with the rapid development of ambitious manned missions, which require long travel duration, the risk of a fire-related accident increases dramatically. In the absence of buoyancy forces, most fire detection and control apparatuses developed on earth are inefficient [START_REF] Ruff | Halon Options Tech. Working Conf[END_REF] . To get a better understanding of the risks, flame spread rate over solid samples in microgravity has been studied by various methods such as flame front or solid-phase temperature tracking [START_REF] Zhao | [END_REF][START_REF] Nagachi | Proc. Comb. Inst[END_REF] . Ongoing unique experiments over large flat samples aim at the fine characterization of fire spread over solid samples [START_REF] Jomaas | [END_REF] . Latest reports suggest that intuitions driving the current material standard tests are not valid [START_REF] Marcum | International Conference on Environmental Systems[END_REF] . These observations are attributed to the shift in predominant heat transfer from natural convection to radiation, as soot residence time in the flame increases [START_REF] Ross | Microgravity Combustion: Fire in Free Fall[END_REF][START_REF] Legros | [END_REF] . These conclusions are supported by findings delivered by other experimental setups [9] that have highlighted specific interactions between neighboring flames only revealed in microgravity environment. Still, the radiative properties of the flames, dominated by the continuum spectrum of soot particles [START_REF] Ross | Microgravity Combustion: Fire in Free Fall[END_REF] , have not been properly quantified in non-buoyant flame configurations. Estimations have been performed from local and usually intrusive measurements [START_REF] Jomaas | [END_REF] . An experimental setup able to produce spatially resolved fields over solid samples in microgravity has never been reported. Consequently, a crucial step in the further understanding of flame behavior in microgravity is the development of an optical diagnostic to quantify soot related quantities in the flame. This paper aims at filling this important gap.

Analysis of soot particles formation and release in non-premixed flames at normal gravity is currently a hot topic due to their impact on human health and global warming [10][11][12][13] . As a result, a wide range of sophisticated diagnostics has been developed at normal gravity, and could be extended to microgravity environment. To conduct experiments aboard microgravity facilities, constraints in terms of total microgravity duration, safety standards, and overall experimental setup compactness reduce the range of possible designs.

Current state-of-the art laser-based techniques can map soot volume fraction, temperature, and characteristic sizes of soot particles. Laser Induced Incandescence (LII) techniques, widely implemented for both laminar and turbulent flames [14] , extract temperature from laser heated soot particles radiation [15,16] . This requires a careful characterization of the wavelength dependence of the soot emissivity [17] but ignores some physicochemical processes likely to occur at the surface of the soot during the laser heating, leading to large uncertainties in the evaluation of the actual soot temperature. Also several limitations have been highlighted [18] , in particular the difficulty to measure wide areas.

Implemented for droplets in droptower facilities, deconvolution with light-extinction/ gravimetric calibration lacks the corresponding temperature fields required to infer the local radiative balance. Also, 3-color pyrometry was not adopted because the flame is then considered an optically-thin medium [19] .

Probing flames with laser energy levels that are non-intrusive, the Modulated Absorption/Emission (MAE) technique [20] is considered. Local spectral soot absorption coefficients are directly evaluated from the laser absorption measurements. Using Mie theory in the Rayleigh limit, the absorption coefficient is converted into the local soot volume fraction using a soot refractive index model. Then soot temperature is evaluated from the ratio of the local spectral emission rates captured within two different spectral ranges. This way, the technique provides self-calibrated temperature measurements that do not dependent on the soot refractive index selected. Recently, the MAE technique was extended to deliver twodimensional axisymmetric fields [21] , thus allowing simultaneous measurements of soot temperature and volume fraction distributions over wide areas. This technique is consequently able to convey the information required to quantify radiative heat transfer, but needs a very large experimental setup.

A similar yet more compact technique is the Cone Beam Tomographic Three Color Spectrometry (CBT-TCS) [22] . Using a CMOS color camera, red, green, and blue intensities emitted by soot particles are discriminated and maps of soot temperature, volume fraction, and mean particle diameter can then be obtained by comparing the different signals. In contrast with the MAE, CBT-TCS does not account for soot re-absorption along the line-of-sight. As a result, errors can dramatically increase when the flame is optically thick [23] , a situation expected in microgravity [START_REF] Legros | [END_REF]24] .

Combining the pros of the different methods, the approach outlined in the present paper extends the aforementioned spectral MAE (S-MAE) technique to a broadband optical arrangement, referred to as broadband MAE (B-MAE), where the collection of the signals can be performed by a single camera. Sticking to a non-intrusive diagnostic enables the reacting flows to be probed without any perturbation. Among other relevant configurations, non-buoyant flame spread is to be studied over the coating of cylindrical electric wires during parabolic flights [9] . This axisymmetric configuration especially allows for the cylindrical deconvolution procedure associated with the B-MAE technique. Consequently, this paper first presents the theoretical background underlying the B-MAE technique. Then, the associated methodology is carefully assessed step by step and tested against fields delivered by a numerical simulation of a documented configuration, i.e. a buoyant axisymmetric laminar coflow non-premixed ethylene/air flame. Finally, both S-MAE and B-MAE experimental results are contrasted with each other probing a flame established over a Santoro burner. Some key assumptions are then identified. The performance of the B-MAE technique is examined in respect of measuring local radiative loss, since quantifying this effect will significantly aid understanding of flame spread in microgravity.

Broadband modulated absorption/emission technique

Theoretical background

Details about the basics of the MAE technique and its updated extension to two-dimensional axisymmetric fields can be further found in the papers by Jenkins and Hanson [20] and Legros et al. [21] .

Because characteristic times and length scales identified here are of a similar order of magnitude as those of the configuration used for the validation of the S-MAE technique, the same set of assumptions is adopted. This allows for relevant comparisons of resulting soot volume fraction and temperature fields. In particular, scattering is neglected while soot re-absorption is accounted for. The Radiative Transfer Equation (RTE) is integrated along a straight light beam crossing an axisymmetric flame [START_REF] Modest | Radiative Heat Transfer[END_REF] . The energy carried at a given wavelength λ and impacting a pixel at a distance x from the optical axis is computed in two situations: either for a flame alone, or for a flame that is probed by an emitting source. In the first case, considering κ λ ( y ) the local spectral absorption coefficient and B λ ( y ) the local spectral blackbody radiative intensity, the energy d E o λ collected per unit time over a pixel of surface S p through optics of overall collection efficiency η can be approximated as follows:

d E o λ = S p η y M y m (κB) λ (y ) e - y M y κ λ (y ) dy dy (1)
In this equation, y is the coordinate along the optical pathway crossing the flame between y m and y M . The exponential term models the soot-related re-absorption. With an emitting source whose initial intensity per unit area is φ λ , an additional flux impinges the pixel and complements

d E o λ , resulting in d E | λ : d E | λ = d E o λ + S p η φ λ e - y M y m κ λ (y ) d y d λ (2)
From the principle of superposition, the total intensity collected by a pixel of a broadband sensor is the result of spectral integration of d E o λ and d E | λ , multiplied by the transfer function f λ of the optical sensor, what the following equations state:

E o = λ f λ d E o λ ; E | = λ f λ d E | λ (3)
The objective is to extract both κ λ and B λ from these equations and to model their dependence with local soot properties. Because the purpose of this paper is not to propose a soot model, details of chemistry are ignored. Soot radiative heat transfer is modeled without requiring any assumptions regarding soot formation, growth and destruction pathways in ethylene chemistry. It is assumed soot particles radiative properties behaves as black bodies radiating in the Rayleigh limit of the Mie theory. The Rayleigh regime of the radiative theory links soot absorption coefficient κ λ to the soot volume fraction f v , while Planck's law links thermal radiation B λ of a soot particle to local temperature T .

κ λ = 6 π E f v λ and B λ = 2 h π c 2 λ 5 e h c λ k T -1 (4)
E being a function of the complex refractive index of soot m , which in turn depends on wavelength. Some authors [22] consider an averaged refractive index independent of λ, because various sets of experiments have led to different profiles of soot refractive index [START_REF] Chang | [END_REF]27] . The model of Chang and Chalampopoulos [START_REF] Chang | [END_REF] , which accounts for the spectral dependence of the refractive index over the range of interest, i.e. from 380 nm to 710 nm, is considered in the following. Two difficulties arise when trying to isolate successively κ λ and B λ : (1) the need for absolute measurement of η; (2) the impossibility to inverse the spectral integration. The first problem is circumvented considering solely ratios of signals, as in the S-MAE technique. The second issue, which is the original level of complexity that the present paper tackles, requires cautious developments detailed below.

Methodology

Two successive deconvolutions are required to recover first the soot volume fraction field f v , and then the temperature one T . Integrals described in Eqs. ( 1) and ( 2) are spatially discretized using the natural pixel grid provided by the camera sensor. Because the flame illustrates an axi-symmetric problem a line-by-line process along the axis of Please cite this article as: A. Guibaud et al., Broadband modulated absorption/emission technique to probe sooting flames: Implementation, validation, and limitations, Proceedings of the Combustion Institute (2018), https://doi.org/10.1016/j.proci.2018.06.199 symmetry is implemented, and each line is decomposed in concentric layers via an onion-peeling method. Each layer is assumed to have uniform properties. Then iterations are run from the outer layers toward the axis of the flame.

κ λ is first retrieved by measuring the absorbed signal from the backlight. For a given sensor, the transmission field is obtained by subtracting E o to E | , thus removing the spontaneous emission from the flame, and dividing by the intensity of the backlight in the absence of the flame. f v can be recovered by finding at each point the value that generates a transmission field closest to the experimental data. Because the extinction coefficient is proportional to the soot volume fraction (see Eq. ( 4) ), the unique solution at each layer is isolated by dichotomy search.

Once a two-dimensional map of soot volume fraction is obtained, temperature is the only unknown left and is found by analyzing the emission field. The camera efficiency η being unknown, absolute emission cannot be quantified. Consequently, temperature is found from the signal ratio of flame spontaneous emission within two different spectral ranges. Again, the temperature that generates numerical ratios closest to the experimental data is retained at each step. However, the complex impact of temperature on the value on the ratio leads to a more careful numerical optimization. Details about issues encountered are further expressed in Section 5.1 .

Self-consistency of the method

Before investigating experimental data, algorithms are tested against f v and T fields produced by a numerical simulation of an axisymmetric laminar non-premixed coflow ethylene/air flame [28] to assess the robustness of the methodology. These fields are shown on the right in Fig. 1 . Like for the assessment of the S-MAE technique [21] , synthetic frames are computed from the f v and T fields, then these frames are used as inputs of the methodology outlined in Section 2.2 . Figure 1 demonstrates the very good correlations between original and retrieved data, both in terms of soot volume fraction (top) and temperature (bottom). Both quantities are recovered with almost perfect accuracy: volume fraction discrepancies are only round-up errors, and temperature ones are lower than 20 K. Temperature deconvolution uses the recovered soot volume fraction, so temperature errors are only estimated at locations, where f v is higher than 0.1 ppm for a reasonable signal-to-noise ratio.

Maximum temperature discrepancies are located on the central axis, due to the combined effect of a low local soot volume fraction and the accumulation of the round-up errors from the external layers. These errors are negligible as compared to the level of noise expected with the experimental diagnostics. burner. Ethylene is injected through the vertical central brass duct, which has a 11 mm effective diameter d F of injection. The air flow is introduced into the concentric 102 mm inner diameter brass cylinder. Fuel and air flow rates are set to 0.229 Nl min -1 and 60 Nl min -1 , respectively. Both mass flow rates are controlled by Bronkhorst EL-FLOW devices. Further details about the burner can be found in [START_REF] Legros | Proc. Combust. Inst[END_REF] . In the following, the vertical burner's axis of symmetry is referred to as O h and its origin is located at the nozzle exit plane, defining the height above the burner h . The cross-stream coordinate is r , which is the distance from the axis of symmetry.

Optical setup

The flame is captured using a JAI AT-140CL digital tri-CCD camera that images the incoming light on three different matrices of 512 × 1396 pixels 2 . This set of matrices enables the discrimination of the contributions from the blue (380 ≤ λ ≤ 510), green (460 ≤ λ ≤ 610), and red (550 ≤ λ ≤ 680) spectral bands. The camera is equipped with a telecentric lens that limits the light collection to beams parallel to the optical axis, what the deconvolution process implemented requires. With this arrangement, the spatial resolution of the projected data is 96 μm for each spectral band. The spectral sensitivity of each band is carefully established prior to any experiment, using a THR 1000 monochromator with a 5 nm step. A similar careful spectral profiling is conducted for the backlighting to find the profile φ( λ), also crucial in the equations.

On the opposite side of the camera, a backlighting produced by LEDs is set up. A diffusive screen made of polished polycarbonate is inserted between the LEDs and the flame to homogenize the backlighting intensity. The LEDs are selected to make the backlighting spectrum and that of the flame as similar as possible, thus allowing for an optimized use of every CCD dynamics range. The intensity of the backlighting is tuned by adjusting the current flowing through the LEDs.

To obtain the absorption and emission fields that are the inputs of the B-MAE methodology, four frames are required, imaging the flame with backlight I F, L , the flame without backlight I F, L 0 , the backlight without flame I F 0, L , and the background noise I F 0, L 0 . Reminding the ambitious goal to obtain time-resolved fields along flame spread, the analysis is performed using only one I F, L and one I F, L 0 frames. Static data I F 0, L or I F 0, L 0 are averaged over 50 acquisitions to restrict the noise influence. Given the spectral profile of the flame spontaneous emission, the exposure times for the blue ( t B expo ), green ( t G expo ), and red ( t R expo ) sensors are adjusted separately to allow for maximum signal amplitude in each spectral range. Settings for the present validation are t R expo = 225 μs, t G expo = 751 μs, and t B expo = 6 . 76 ms. This new optical setup is tested against the S-MAE technique [21] . It is worth mentioning that the S-MAE camera has a higher spatial resolution, i.e. 36 μm/pixel, and each image processed is the average over 100 successive frames.

Comparison with S-MAE

The soot volume fraction fields are obtained from the local absorption coefficient field delivered at λ= 645 nm by the S-MAE technique on one hand, and by the red CCD sensor of the B-MAE setup on the other hand, in order to compare data extracted from similar spectral ranges. Temperature is obtained considering ratios between data obtained at 785 and 645 nm for the S-MAE technique, and between data delivered by the red and green bands for the B-MAE diagnostic.

Soot volume fraction

The fields of soot volume fractions are displayed in Fig. 3 . Both methods deliver very similar fields, though the S-MAE one produces slightly higher soot volume fraction. This difference can be explained by the arbitrary choice of spectral dependence of the soot coefficient E , which has a direct impact on soot volume fraction given Eq. ( 4) and its integration over the red band required by the B-MAE method.

Looking now at the overall topology, the B-MAE method recovers properly all the main features of the distribution, i.e. a thin region of higher soot volume fraction on the wing close to the flame sheet, a peak at approximatively the same height (46.31 mm for S-MAE versus 45.60 mm for B-MAE), and values on the central axis that increase gradually with the height above the burner.

Please cite this article as: A. Guibaud et al., Broadband modulated absorption/emission technique to probe sooting flames: Implementation, validation, and limitations, Proceedings of the Combustion Institute (2018), https://doi.org/10.1016/j.proci.2018.06.199 The B-MAE approach displays more intense highfrequency spatial fluctuations that can be possibly filtered out by regular signal processing strategies.

Soot temperature

The soot temperature fields are shown in Fig. 4 . Both fields show similar gradients directed downwards and toward the centerline. The B-MAE technique overestimates the temperature near the central axis, yet within an acceptable range. In addition, the obvious difference in external contours is not relevant as it concerns pixels with negligible soot volume fraction.

The two methods do not have the same spatial discretization due to different cameras. As a result, errors cannot be quantified through the direct evaluation of local discrepancy between both fields. Consequently, populations of soot temperature/volume fraction measurements in flames are reported in Fig. 5 . The higher B-MAE temperatures are located roughly 50 K above those of the S-MAE technique but in a region of low f v . The peak soot volume fractions hardly differ from each other, given the S-MAE uncertainty of ± 0.5 ppm. Ultimately, these discrepancies may hardly affect the field of local radiative losses.

Radiative losses

To quantify the local radiative loss, the divergence of the radiative flux at every location where soot volume fraction and temperature are measured can be computed. To do so, the RTE is solved in its non-scattering formulation for the radiative intensity I λ using the Finite Volume Method proposed by Chui et al. [START_REF] Chui | [END_REF] for axisymmetric coordinates with a 12 × 16 angular mesh. For the laminar ethylene/air flames investigated, radiation by soot over the whole spectrum was found to prevail over that by gaseous species [24] . Consequently, the contributions of gaseous products (mainly CO 2 and

Discussion

The B-MAE data processing described above is a quite straightforward extension of the existing S-MAE deconvolution process. Nevertheless, two major theoretical points are worth being highlighted to account for the main difficulties addressed.

Re-absorption

Re-absorption by soot along the collection lineof-sight has led to a dramatic increase in complexity of the algorithms. However, given the high soot volume fraction expected in microgravity environment, developing a procedure that takes reabsorption into account was mandatory to avoid major errors, especially in the inner layers of the flame. Re-absorption coupled with broadband integration leads to an issue that has not been reported yet -to the authors' knowledge -when investigating temperature. As color ratios are considered, two temperatures are mathematical solutions of the minimization problem. Though two distinct temperatures lead to two different signals in both red and green spectral ranges, they can result in the same red/green signal ratio once re-absorption is considered. Because though the green signal is expected to grow faster as temperature increases due to the λ dependency of B , it is also the signal that is the most damped by re-absorption as κ ∼ 1/ λ. Figure 7 illustrates for a profile extracted from the numerical flame investigated in Section 2.3 a tricky situation where the two solutions are at some locations so close that noise can mislead the deconvolution algorithm. Starting from the most outer layer, which is not affected by the re-absorption issue, the algorithm finds a unique temperature T 0 , then from pixel to pixel only the mathematical solution closest to T 0 is kept. If the algorithm ever deviates to the virtual solution, the temperature drop shown in the inset of Fig. 7 reveals. In such a case, and should the drop value be over a threshold temperature difference corresponding to experimental noise quantification, the algorithm is sent back to previous pixels where it can recapture the physical solution.

Influence of size parameter

Ref. [22] discusses the influence of the Rayleigh limit on absorption efficiency. At the lowest wavelengths of the blue channel (around 380 nm), the B-MAE underlying assumptions stipulating that (1) soot particles radiate in the Rayleigh regime and (2) scattering is neglected are not valid everywhere in the flame, as the ratio x = π d/λ, where d is a characteristic diameter of the size distribution, increases along the flame height [31] . Assuming primary particles diameter of 40 nm from TEM experiments [32] and 380 nm < λ < 680 nm implies 0.18 < x < 0.33. The deviation from the Mie model is reasonable as long as x is below 0.3, i.e. λ > 420 nm . As a result, only red and green CCDs data are considered in the present analysis. Analyzing data from the blue spectral band would require additional information on soot particles such as a characteristic length or structural feature. The lack of this information does not tarnish the scope of the present study as particle size distribution hardly affects the evaluation of the local radiative balance that is especially dominated by the contributions at large wavelength, i.e. at relatively small size parameter.

Moreover, the selection of the soot refractive index model may not be as controversial as expected provided that measurements only serve to compare local radiative properties of flames spreading on solid samples under different external conditions of oxygen concentration, oxidizer flow rate or pressure for instance. As a result, adopting an arbitrary but single model is not a rough approximation. Soot particles are treated as independent monodisperse primary particles. As this first simple step proves to be consistent, quantification of polydisperse particles or fractal aggregates that requires more sophisticated hardware could be worth developing.

Conclusion

The performances of the new B-MAE technique have been assessed with some success. Both twodimensional fields of soot temperature and volume Please cite this article as: A. Guibaud et al., Broadband modulated absorption/emission technique to probe sooting flames: Implementation, validation, and limitations, Proceedings of the Combustion Institute (2018), https://doi.org/10.1016/j.proci.2018.06.199 fraction are very similar to those delivered by the original S-MAE technique when a steady buoyant laminar coflow ethylene/air non-premixed flame is probed. It is worth noticing that the discrepancies between the S-MAE and B-MAE fields are of the order of magnitude of the uncertainties attributed the S-MAE technique, i.e. ± 50 K for temperature and ± 0.5 ppm for soot volume fraction.

As these fields are expected to provide crucial inputs for a finer evaluation of the radiative heat transfer that governs flame spread over solid samples in microgravity, they have been used as inputs for the computation of the local radiative losses in the aforementioned buoyant flame. Although discrepancies reveal in regions of low soot volume fraction and/or low temperature, the major contributions to the flame radiative losses are captured. As a result, new and finer information to predict potential fire spread rate over different materials should be soon delivered. The B-MAE experimental setup has already been implemented in a microgravity test rig to study flame spread over the coating of cylindrical wires.

Fig. 1 .Figure 2

 12 Fig. 1. Data retrieved by B-MAE algorithms as a function of the original data provided by a numerical simulation [28] . Straight black solid lines indicate the ideal locations of the points. Blue dots indicate an ideal noiseless situation, while red dots assume a level of random noise in the process, relevant to that of the optical setup used. On the right, the original fields are displayed in the physical space. r = 0 is the simulated flame's axis of symmetry, h the height above the coflow burner, and d F the fuel tube inner diameter. (For interpretation of the references to color in this figure legend, the reader is referred to the web version of this article.)

Fig. 3 .

 3 Fig. 3. Soot volume fraction fields obtained using the S-MAE technique (left) and the B-MAE one (right). Black dots indicate the locations of the peak f v .

Fig. 4 .

 4 Fig. 4. Temperature fields obtained using the S-MAE technique (left) and the B-MAE one (right).

Fig. 5 .

 5 Fig. 5. Populations of soot temperature/volume fraction measurements in the flame. Only locations with soot volume fraction over 1 ppm and local radiative loss above 20% of the peak are selected as trustworthy data.

Fig. 6 .

 6 Fig. 6. Fields of local soot-related radiative loss obtained using the S-MAE data (left) and the B-MAE ones (right).

H 2 O

 2 ) can be neglected. Thus, the numerical computations require a model for the spectral dependence of E (see Eq. (4) ). Again, the model of Chang and Charalampopulos[START_REF] Chang | [END_REF] is selected. The fields of local radiative loss are shown in Fig. 6 . These are in good agreement with each other, as the temperature gaps recorded near the axis are weighted by the low level of soot volume fraction in this region. It can be concluded that the B-MAE provides information that are accurate enough to decently assess the radiative heat transfer in the flames investigated. Please cite this article as: A. Guibaud et al., Broadband modulated absorption/emission technique to probe sooting flames: Implementation, validation, and limitations, Proceedings of the Combustion Institute (2018), https://doi.org/10.1016/j.proci.2018.06.199

Fig. 7 .

 7 Fig. 7. At a given height, temperature deconvolution is performed from peripheral pixel layers toward center ( x = 0). Black line represents the original field. Blue dots indicate the physical solution and red dots the second mathematical solution. The inset displays the unrealistic local temperature drop allowing for the systematic identification of a deviation of the algorithm at pixel 33 here. At this position, the other potential temperature is automatically selected. Green dots indicate the solution obtained if re-absorption is ignored. Results sharply diverge near the axis of the flame. (For interpretation of the references to color in this figure legend, the reader is referred to the web version of this article.)

Supplementary material

Supplementary material associated with this article can be found, in the online version, at doi: 10. 1016/j.proci.2018.06.199 .


Achour Mostefaoui

Matthieu Perrin

Michel Raynal

Jiannong Cao

Achour Mostéfaoui

Crash-Tolerant Causal Broadcast in O(n) Messages

Keywords: Asynchronous system, Backward recursion, Broadcast abstraction, Causal broadcast, FIFO message delivery, Message-passing, Process crash failure

published or not. The documents may come   L'archive ouverte pluridisciplinaire

1 Introduction: Computing Model and Causal Broadcast 1.1 Computing Model Process model The system is made up of a set of n processes denoted p 1 , ..., p n . Each process is sequential (which means it executes one step at a time), and asynchronous (which means it progresses at its own speed, which can vary with time and remains always unknown to the other processes).

Any number of processes can crash. A crash is a premature halt (after it crashed, if it ever does, a process executes no more steps). A process that does not crash is called correct. A process that crashes is called faulty.

Communication model Processes can send and receive messages through channels. It is assumed that any pair of processes is connected by a bidirectional channel. Channels are reliable and asynchronous. Reliable means that messages are neither corrupted, nor duplicated, nor lost. Asynchronous means that, albeit finite, the transit duration of a message is arbitrary.

The sending and the reception of a message are atomic steps. The processes can also use a broadcast macro-operation, denoted broadcast (msg) where msg is a message, which is a shortcut for "for each j ∈ {1, ...n} do send (msg) to p j end for". Let us observe that this macro-operation is not reliable, namely, if the sender crashes while executing it, an arbitrary subset of processes (possibly empty) receive the message.

A message created at the application level is called application message. A message generated by the algorithm implementing causal broadcast is called protocol message. When clear from the context, we use only the term message.

Causal Broadcast

Definition Causal broadcast was introduced by K. Birman and T. Joseph in a pioneering work on fault-tolerant distributed systems [START_REF] Birman | Reliable communication in the presence of failures[END_REF]. It is a communication abstraction that provides the processes with two operations denoted causal_broadcast() and causal_deliver(), that allow to broadcast and deliver messages. When a process invokes causal_broadcast(m), we say it c-broadcasts the message m; similarly when the invocation of causal_deliver() returns the message m, we say it c-delivers the message m (or m is c-delivered). Without loss of generality, it is implicitly assumed that all messages c-broadcast by the processes are different (this can be easily realized by associating a pair -local sequence number, sender identity -with each message, as done in this article). Formally, causal broadcast is defined by the following properties.

• Validity. If a process c-delivers a message m from a process p i , p i previously c-broadcast m.

• Integrity. A process c-delivers a message m at most once.

• Causal Delivery. If a process c-broadcasts a message m and later c-broadcasts a message m , or a process c-delivers a message m and later c-broadcasts a message m , no process c-delivers m before c-delivering m.

• Termination. A message c-broadcast by a correct process is c-delivered by all correct processes.

Validity states that no spurious message can be c-delivered. Integrity states there is no message duplication. Causal Delivery states that the messages are c-delivered according to the causal links relating their c-broadcasts and c-deliveries [START_REF] Lamport | Time, clocks, and the ordering of events in a distributed system[END_REF]. Finally, Termination states that the correct processes c-deliver at least the messages they c-broadcast.

Example A simple example of a causal broadcast execution is presented at the left of Fig. 1. Because they are c-broadcast by the same process p 1 , no process can c-deliver m 1 before m 0 . The same holds for m 3 and m 4 which are c-broadcast by p 2 : no process can c-deliver m 4 before m 3 . As the c-broadcasts of m 2 and m 1 are not causally related, they can be c-delivered in a different order at distinct processes. The same holds for m 2 and m 3 . Hence, the execution depicted in the figure satisfies the c-broadcast properties. Differently, if the message m 2 (i) had been delivered at p 2 before it issued the broadcast of m 3 , and (ii) delivered before m 3 at process p 1 , the execution would be incorrect. This is because m 3 would causally depend on m 2 and consequently no process would be allowed to deliver m 3 before m 2 .

Figure 1: A causal broadcast execution and its message precedence graph A short historical perspective As already said, causal broadcast was introduced by K. Birman and T. Joseph in [START_REF] Birman | Reliable communication in the presence of failures[END_REF]. Its first implementation was done in the ISIS system [START_REF] Birman | The ISIS project: real experience with a fault tolerant programming system[END_REF], where each message was required to carry its full causal past. A more efficient implementation was then introduced [START_REF] Birman | Lightweigt causal and atomic group multicast[END_REF]. While it is now well accepted as a meaningful communication abstraction, causal broadcast initiated a controversy in the operating system community (see e.g., [START_REF] Birman | A response to Cheriton and Skeen's criticism of causal and totally ordered communication[END_REF]). Several causal broadcast algorithms have been presented in the literature (e.g., see the textbooks [START_REF] Ch | Reliable and secure distributed programming[END_REF][START_REF] Raynal | Fault-tolerant message-passing distributed systems: an algorithmic approach[END_REF]), which use an underlying reliable broadcast abstraction.

Efficient implementations of causal broadcast for failure-free systems are presented in several articles and textbooks (e.g., [START_REF] Raynal | Distributed algorithms for message-passing systems[END_REF][START_REF] Raynal | The causal ordering abstraction and a simple way to simple to implement it[END_REF][START_REF] Schiper | A new algorithm to implement causal ordering[END_REF][START_REF] Schwarz | Detecting causal relationships in distributed computations: in search of the Holy Grail[END_REF]). Formal characterizations of causal broadcast can be found in [START_REF] Kshemkalyani | Necessary and sufficient conditions on information for causal message ordering and their optimal implementation[END_REF][START_REF] Murty | Characterization of message ordering specifications and protocols[END_REF][START_REF] Raynal | Distributed algorithms for message-passing systems[END_REF].

A more low-level approach was introduced in [START_REF] Peterson | Preserving and using context information in interprocess communication[END_REF], where is defined the notion of a conversation, close to causal broadcast. The presentation of this paper is operating system-oriented and no precise definitions (i.e., properties-based) are given.

Motivation All the causal broadcast algorithms suited to crash-prone asynchronous message-passing systems we know are based on an underlying reliable broadcast abstraction. To ensure that each application message c-delivered by a correct process is c-delivered by all correct processes, all reliable broadcast algorithms use O(n 2 ) protocol messages for each application message. However, while it is sufficient, it has never been proved that reliable broadcast was necessary to implement causal broadcast. Hence our investigation on the implementation of causal broadcast, which has given rise to the simple algorithm presented in this paper. This algorithm requires O(n) protocol messages for the c-broadcast of an application message. This is obtained at the price of protocol messages sometimes carrying a few application messages (this depends on the application communication pattern). Hence, the proposed algorithm seems suited to the case where application messages are small. The principle that underlies the algorithm is the use of a precedence graph, which captures the causality relation on application messages. In some sense, the proposed algorithm can be seen as a variant of a reliable broadcast algorithm customized to causal broadcast.

Precedence graph Such a graph G is associated with each execution. Its vertices are the application messages. As far as its edges are concerned, there is a directed edge from a message m to a message m if (i) the invocations of causal_broadcast(m) and causal_broadcast(m ) are consecutive invocations by the same process p i , or (ii) the c-delivery of m and the invocation of causal_broadcast(m ) by a process p j are consecutive in the sense there is no invocation of causal_broadcast() by p j between them. The figure depicts the precedence graph of the execution on its right. If the directed edge (m, m ) belongs to G, we say that m causally depends (directly) on m, or m is an immediate causal predecessor of m . If there is a directed path from m to m , we say that m depends (transitively) from m, or m is a causal predecessor of m. Two messages m and m that are not causally related are said to be independent. The causal past of a message m is the set of all the messages m such that there is a directed path from m to m.

An Efficient Causal Broadcast Algorithm

Algorithm 1, described below, implements causal broadcast. The messages that are c-broadcast are called application messages, while the messages generated by the algorithm are called protocol messages. As already indicated, this algorithm ensures that each invocation of causal_broadcast() generates n protocol messages.

Local variables at a process p i Each process manages two local variables.

• sn i is an integer variable, initialized to 0, used to associate a sequence number with each message c-broadcast by p i .

• copr i (for compressed predecessors is a sequence of triplets m, j, sn such that the message m has been c-broadcast by process p j with sequence number sn. A triplet m, j, sn is contained into copr i if p i c-delivered m after its last c-broadcast and did not c-deliver any more recent message from p j later (see Fig. 2). 1The symbol denotes the empty sequence, and ⊕ denotes the concatenation of a new element at the end of the sequence. Considering a process p i , the meaning of copr i is illustrated on Fig. 2, in which p i invoked first causal_broadcast(m 1 ) and later causal_broadcast(m 2 ). Moreover, between these two consecutive invocations, p i c-delivered the messages m, m , and m (in this order). This means that, to ensure a correct message c-delivery order, (i) no process must c-deliver m 2 (i) before m 1 (because m 2 was c-broadcast later by the same process p i ), and (ii) before the messages m, m , and m (because their c-deliveries at p i causally precede the c-broadcast of m 2 ). Hence, copr i is used to register all the messages c-delivered by p i between any two consecutive invocations of causal_broadcast() it issues.

On the client side: the operation causal_broadcast (m) The code of this operation is pretty simple. Process p i first increases sn i , and then broadcasts the message seqmsg, which contains the sequence copr i ⊕ m, i, sn i (lines 1-3). Let us notice that the triplet associated with the last message previously c-broadcast by p i is suppressed from copr i before the broadcast of seqmsg. As p i did not crash during the previous broadcast, this message is received by all processes, and the only ordering information needed is its sequence number, namely (sn i -1), which is explicitly encoded in the triplet m, i, sn i .

Let us observe that any protocol message seqmsg contains at least one triplet. The sequence of triplets copr i will be used as a causal barrier imposing to c-deliver all its messages before m. As just indicated, the sequence number sn i will be used to ensure that the previous message c-broadcast by p i is c-delivered before m.

operation causal_broadcast (m) is (1) sni ← sni + 1;
(2) if -, i,belongs to copri then suppress it from copri end if;

(3) broadcast (seqmsg) where seqmsg = (copri ⊕ m, i, sni ); (4) copri ← . % empty sequence % when seqmsg = m1, i1, sn1 , • • • , m , i , sn is received do (5) for x from 1 to do [START_REF] Kshemkalyani | Necessary and sufficient conditions on information for causal message ordering and their optimal implementation[END_REF] if (mx not yet c-delivered) then [START_REF] Lamport | Time, clocks, and the ordering of events in a distributed system[END_REF] wait(m, c-broadcast by pi x with seq. nb. (snx -1), is c-delivered); [START_REF] Murty | Characterization of message ordering specifications and protocols[END_REF] if m, ix, snx -1 belongs to copri then suppress it from copri end if; (9) causal_deliver (mx); [START_REF] Raynal | Distributed algorithms for message-passing systems[END_REF] copri ← copri ⊕ mx, ix, snx [START_REF] Raynal | Fault-tolerant message-passing distributed systems: an algorithmic approach[END_REF] end if (12) end for.

Algorithm 1: Efficient causal broadcast (code for p i )

On the server side: Message reception When a process p i receives a protocol message seqmsg containing a sequence m 1 , i 1 , sn 1 , • • • , m , i , sn , it considers each of its triplet, one after the other ( "for" loop, lines 5-12). Let m x , i x , sn x the current triplet. It means that m x was c-broadcast by p ix , and its sequence number is sn x . There are two cases.

• If m x has already been locally c-delivered, p i proceeds to the next triplet, if any.

• If m x has not yet been locally c-delivered, p i first waits until the previous message (say m) cbroadcast by p ix is c-delivered (we can assume that each protocol message reception generates a new thread in charge of the triplets in seqmsg). This is made possible thanks to the sequence number sn x (line 7). After this message m has been c-delivered, it is suppressed from copr i (line 8). This is due to the fact that the causal dependence between this message m and the next message c-broadcast by p i must be updated, namely replaced by the new causal dependence between m x and the next message c-broadcast by p i (line 8). Finally, m x can be c-delivered (line 10).

As we can see, each iteration step of the "for" loop (lines 5-12) has a backward recursive flavor, captured by the "wait" statement at line 7. This statement entails a recursive messages delivery, whose aim is to guarantee causal delivery.

Proof of the Algorithm

Lemma 1 Each local variable copr i contains at most n triplets.

Proof A local sequence copr i is initialized to the empty sequence , and reset to this value each time p i invokes causal_broadcast(). Then, when p i adds a new triplet m x , i x , sn x to copr i (line 10), it previously suppresses the triplet -, i x , sn x -1 if it is in copr i (line 8). Hence, for any i x , copr i contains at most one triplet -, i x , -, which proves the lemma.

2 Lemma 1

The next corollary is an immediate consequence of the previous lemma and lines 2-3.

Corollary 1 A protocol message contains at most n triplets.

Lemma 2 Let us consider any two consecutive application messages m and m c-broadcast by a process p j . No process p i c-delivers m before m.

Proof The proof is an immediate consequence of the "wait" statement of line 7, which imposes a FIFO delivery order between each pair of processes. • after p j(2) c-delivered m 1 , it c-broadcast m 2 , which was c-delivered by p j(3) (in fifo order), etc.,

• after p j(k) = p j c-delivered m k-1 (in fifo order), it c-broadcast m = m k .
Due to lines 7 and 9-10, and the definition of seqmsg at line 3, it follows that, for any x ∈ [1.

.k], copr j(x) includes, for each process p y , the last causal predecessor of m x c-broadcast by p y (if any). Hence, when a process receives seqmsg = -, -, -, • • • , m , j, -, the triplets in seqmsg capture the messages that must be c-delivered by p j before m , and one of these triplets is equal to -, i, sn where sn ≥ sn. It follows that p j cannot c-deliver m before m.

2 Lemma 3

Remark The previous lemma shows that, from a "basic principles" point of view, Algorithm 1 is a reduction of message causal delivery to (process-to-process) FIFO message deliveries.

Lemma 4 If a correct process (i) c-broadcasts a message m, or (ii) c-delivers a message m and later c-broadcasts a message m , the message m is c-delivered by all correct processes.

Proof Proof of (i). Let us assume by contradiction that there are application messages c-broadcast by correct processes that are never c-delivered by some correct process. Let m be a message and p j its correct sender, such that m is the first message that is not c-delivered by a correct process p i , while p i c-delivers all its causal predecessor messages. This permanent blocking occurs at line 7. As p j is correct, it broadcast a protocol message seqmsg = (copr ⊕ m, j, sn ). As m is the "first" (as defined above) message entailing the permanent blocking of p i , all the messages in the prefix sequence copr, are c-delivered2 . Consequently, the processing of all triplets in copr terminates, and p i processes then m, j, sn ) (last iteration of the "for" loop). When this occurs, p i remains blocked forever waiting for the previous message (say m ) c-broadcast by p j . But this permanent blocking means that m is not the first message for which p i waits forever. This contradicts the assumption on m, and consequently, there is no "first" message from p j never c-delivered by p i . Proof of (ii). If a process p i c-delivers a message m from a (correct or crashed process) p j , it adds the triplet m, k, sn (where p k is the sender of m, and sn its sequence number) to copr i at line 10. Hence, this triplet will be broadcast when p i will issue it next invocation of causal_broadcast().

2 Lemma 4

Theorem 1 Algorithm 1 implements the Causal Broadcast abstraction. Moreover, an invocation of causal_broadcast() costs n protocol messages, and each protocol message carries at most n application messages.

Proof The Validity property follows directly from the text of the algorithm and the reliability of the network (none of them creates messages nor modifies their content). The Integrity property follows from line 6. The Causal Delivery property follows from Lemma 3 and the Termination property follows from part (i) of Lemma 4. The message cost properties follows from Lemma 1 and Corollary 1. 2 T heorem 1

Ensuring a Stronger Termination Property

A stronger termination for crashes during an invocation of broadcast() As already indicated, if a process crashes while executing broadcast(seqmsg), some processes can receive seqmsg, while others do not. Let P 1 be the former set of processes, and P 2 the later. If the correct processes of P 1 (if any) do not issue new invocations of causal_broadcast() (whose internal broadcast() will forward messages in seqmsg to the processes of P 2), the correct processes of P 2 would never c-deliver messages in seqmsg sent by processes that crashed during their last invocation of broadcast(). This raises the following question. In addition to the basic termination property, how to ensure the following stronger termination property:

• Strong Termination. If a correct process p i c-delivers a message m, the message m is c-delivered by all correct processes. This Strong Termination property ensures that all correct processes c-deliver the same set of messages. If the message m has been c-broadcast by a correct process, the basic termination property ensures strong termination. So, we have only to consider the case where the sender of m crashed while it was executing the unreliable macro-operation broadcast(). Hence, answering the question amounts to ensure that any message that (i) is broadcast by a process that crashes and (ii) is c-delivered by a correct process, is c-delivered by all correct processes.

A look at Lemma 4 To this end, we rely on part (ii) of Lemma 4. This lemma states more than the termination property, which demands only that, if a correct process c-broadcasts a message m, all correct processes c-deliver m. It additionally states that, if a correct process c-delivers a message m and later c-broadcasts a message m , the message m is c-delivered by all correct processes. In particular, if all correct processes repeatedly c-broadcast messages during an infinite execution, then the algorithm ensures strong termination.

From termination to strong termination It follows from the previous discussion that the strong termination property can be obtained as follows. Let p i be a process that after some time does no longer invoke causal_broadcast(). This process is then required to c-broadcast a control application message (encoded in a default value, e.g., ⊥), only if its variable copr i contains non-⊥ application messages. According to the algorithm, this invocation entails the required forwarding of the compressed predecessor application messages (which always succeeds if p i is not a faulty process). 3A note on complexity For each message m c-broadcast by a process p i , at most one message ⊥ might be c-broadcast by any other process p j . Therefore, in the worst case, this strategy might lead to the same number of messages as causal broadcast algorithms based on reliable broadcast. However, in practice, there are common situations in which the complexity would be much lower: [START_REF] Birman | A response to Cheriton and Skeen's criticism of causal and totally ordered communication[END_REF] processes that repeatedly c-broadcast messages never need to c-broadcast ⊥ messages, and (2) one ⊥ message can be used to forward up to n -1 messages. In particular, in an execution where processes first jointly cbroadcast and c-deliver x ≥ n messages, and only then c-broadcast one ⊥ message each, O(nx) protocol messages will be exchanged between processes, compared to O(n 2 x) messages for an algorithm based on reliable broadcast.

Conclusion

This article has presented a causal broadcast algorithm for asynchronous message-passing systems in which any number of processes can crash. Differently from causal broadcast algorithms based on reliable broadcast (which requires O(n 2 ) protocol messages for each causal broadcast), the proposed algorithm generates only n protocol messages per causal broadcast. To this end, it replaces "early message forwarding" used in reliable broadcast by "late message forwarding", and reduces causal message delivery to fifo message delivery.

Figure 2 :

 2 Figure 2: Meaning of the sequence copr i

2 2 Lemma 3

 223 Lemma Let us consider any two application messages m and m such that causal_broadcast(m) causally precedes causal_broadcast(m ). No process c-delivers m before m.Proof If m and m are c-broadcast by the same process, the proof follows from Lemma 2. Let us now consider the case where m and m are c-broadcast by different processes p i and p j . Let sn be the sequence number associated with m. As causal_broadcast(m) causally precedes causal_broadcast(m ), there is a directed path of messages in the precedence graph m = m 1 , m 2 , ..., m k = m , where k ≤ n -1, and an associated sequence of distinct processes p j(1) = p i , p j(2) , ..., p j(k) = p j such that• m = m 1 has been c-broadcast by p j(1) = p i and c-delivered by p j(2) (in fifo order),

The timstamps associated with messages of copri are the one that compose compressed vector clocks in[START_REF] Birman | The ISIS project: real experience with a fault tolerant programming system[END_REF]. Let us observe that the compressed predecessors of pi include at most one messages from pj if pi, but can contain none of them. Said differently, |copri| ≤ n.

Let us observe that it is possible that the message seqmsg broadcast by pj carries a triplet m , k,such that p k crashed while broadcasting the sequence of triplets -, -, -, • • • , m , k, -, and this sequence was never received by pi. But in this case, if any, p k did not crash during its previous invocation of broadcast() and consequently, pi eventually receives the last message c-broadcast by p k before m .

A similar issue occurs when one has to solve early-deciding consensus in crash-prone synchronous message-passing systems. When a process attains a round r in which it knows the decision estimates of all the processes that were not crashed at the beginning of round r, it can compute the decision value and decide it. But, as it has no means to know if the other processes know the same set of estimate values, it must execute an additional round during which it propagates the decision value before terminating (see[START_REF] Raynal | Fault-tolerant message-passing distributed systems: an algorithmic approach[END_REF] for more details).

Acknowledgments

This work was partially supported by the French ANR project 16-CE40-0023-03 DESCARTES devoted to layered and modular structures in distributed computing. The authors want to acknowledge the referees for their constructive comments.


Nan Hu

Zhiguang Chen

Yunfei Du

Yutong Lu
email: yutong.lu@nscc-gz.cn

Mimir+ : An Optimized Framework of MapReduce on Heterogeneous High-Performance Computing System

Keywords: High-performance Computing, MapReduce, Heterogeneous

In this paper, we present an optimized data processing framework: Mimir+. Mimir+ is an implementation of MapReduce over MPI. In order to take full advantage of heterogeneous computing system, we propose the concept of Pre-acceleration to reconstruct a heterogeneous workflow and implement the interfaces of GPU so that Mimir+ can facilitate data processing through reasonable tasks and data scheduling between CPU and GPU. We evaluate Mimir+ via two benchmarks (i.e. the WordCount and large-scale matrix multiplication) on the Tianhe-2 supercomputing system. Experimental results demonstrate that Mimir+ achieves excellent acceleration effect compared with original Mimir.

Introduction

With the continuous development of information technology, the data generated in daily life, industrial productions and scientific researches are exploding. The convergence of high-performance computing and big data processing is becoming a promising solution to efficiently tackle with the massive data.

MapReduce is a programming paradigm popularized by Google [START_REF] Dean | MapReduce: simplified data processing on large clusters[END_REF] which presents a parallel computing model and method for large-scale data processing. Implementations of MR-MPI [START_REF] Plimpton | Mapreduce in mpi for large-scale graph algorithms[END_REF] have given practical and feasible solutions to transplant MapReduce to high-performance computing system. However, MR-MPI suffers from a severe shortcoming which is its simple memory management. In our previous work, we presented Mimir [START_REF] Gao | Mimir: Memory-efficient and scalable mapreduce for large supercomputing systems[END_REF] which is an optimized framework based on MR-MPI. Mimir redesigns the execution model to incorporate a number of sophisticated optimization techniques that achieve similar or better performance with significant reduction in the amount of memory used. Nevertheless, we can see that MR-MPI and Mimir mainly perform their calculation in CPUs.

Among the latest TOP500 list published in June 2018, Summit captured the number one spot with a performance of 122.3 petaflops on High Performance Linpack. Each node of Summit is equipped with two 22-core Power9 CPUs, and six NVIDIA Tesla V100 GPUs. Summits championship demonstrated the capabilities and potentiality of heterogeneous high-performance computing system. Although MapReduce-MPI and Mimir can implement the MapReduce model well on high-performance computing system, their lack of heterogeneous architecture will cause a problem that the heterogeneous resources cannot be fully utilized.

We continued the work of Mimir and present Mimir+ in this paper. This work targets to promote the calculation speed of Mimir and support heterogeneous GPU acceleration on high-performance computing system.

The remainder of the paper is organized as follows. Section 2 introduces the optimizations of Mimir+. Section 3 describes the experimental environment and results. Other research related to our paper is presented in Section 4. We conclude this paper in Section 5.

Design of Mimir+

In this section, we introduce the main optimizations and designs in Mimir+.

Heterogeneous Workflow

The original Mimir designs two special objects called KV containers and KMV containers to help manage the intermediate data < key, value > pairs between map phase and reduce phase. Similar to Mimir and MR-MPI, Mimir+ still adopts the KV containers and four basic phases: map, aggregate, convert and reduce. However, in order to further improve the computation speed, we reconstruct a heterogeneous workflow for Mimir+. Specifically, Mimir+ integrates the map phase and the aggregate phase into one process called MAP, and the convert phase and the reduce phase are integrated into another process called REDUCE.

Fig. 1 shows the reconstructed workflow of Mimir+. The first thing to do in MAP is to process the input data according to a user-defined callback function.

Here, we implement a new interface for GPU to perform the map jobs and users can select whether to perform the calculation on the GPU or on CPU by using the corresponding interfaces. Then, Mimir+ performs the MPI Alltoallv function to exchange the KVs and stored them in KVCs through an interleaved execution model. When the MAP process ends, the REDUCE process starts and Mimir+ converts < key, value > in KVC to < key, < value1, value2, value3... >> into the KMVC. Mimir+ also has two types of interfaces in reduce phase for users to determine whether they will use GPU to calculate the reduce jobs or not. A user-defined reduce GPU function implemented in CUDA is needed to start the data processing in GPU and the final output data will be transferred back from GPU memory.

Design of GPU Acceleration Modules

When we implement the heterogeneous workflow of Mimir+, we can't simply load the map/reduce tasks and data into GPU because GPU is not suitable for receiving fragmented data. Here we propose a concept of Pre-acceleration. Preacceleration actually refers to the operations we perform before we use GPU to calculate data. Specifically, operations like data partitioning, data communication and data transmission required before GPU acceleration can all be regarded as a part of Pre-acceleration. In combining the concept of Pre-acceleration, we divide the GPU acceleration process into four modules to achieve an efficient and convenient management. Fig. 2 shows a brief architecture of Pre-processing Module, Transmission Module, Calculation Module and Feedback Module.

Evaluation

In this section, we evaluate the acceleration effect of Mimir+ and compare it with the original Mimir.

Performance Comparison

We perform WordCount (WC) and matrix multiplication on 4 nodes of heterogeneous computing system: Tianhe-2. Each node in Tianhe-2 is equipped with a 2-way 8-cores Intel Xeon CPU E5-4640, 128 GB memory, running at 2.40 GHz.

The GPU equipped on the node is NVIDIA Tesla K80 GPU with two sets of 12 GB GDDR5 memory (24 GB in total), 4992 stream processors, the memory bandwidth is 240 GB/s. Each node installs a 64-bit Linux 3.10.0 operating system, and we use mvapich2-2.2, gcc-4.8.5 and CUDA 8.0 to conduct the tests on Mimir+.

The results of WC are shown in Fig. 3 (a). As we can notice, Mimir+ obtains a comparatively good acceleration effect on WC. With the increase of test data, the acceleration effect achieved by Mimir+ is becoming more and more obvious. Because the tasks of WordCount in MapReduce do not require intensive computing, the effect of acceleration in Mimir+ is not fully reflected. Since the tasks of matrix multiplication vary from the map phase and the reduce phase, we tested and compared the two phases separately in the other experiment. Moreover, in order to compare the difference between the calculation of heterogeneous systems and pure parallel GPU computing, we performed the matrix multiplication in GPU alone using CUDA with the same input data and put the result into comparison. The results are shown in Fig. 3 (b). In the map phase, because of the little calculation, the effect of acceleration is not good. However, in the reduce phase which contains a huge amount of calculation, Mimir+ achieves a considerable speedup of about 7.4 compared with Mimir. After comparing Mimir+ and Mimir in map and reduce phase, we performed an overall test and the whole framework can achieve a speedup of about 8.1 to 8.3. Nevertheless, the calculations performed in GPU alone achieved a speedup of about 8.5 which is close to Mimir+.

Related Work

MapReduce is an extremely popular model and many researches intend to improve the performance of MapReduce jobs on heterogeneous system.

Phoenix [8] [6] proposed by Colby Ranger et al. from Stanford University is a MapReduce implementation on shared memory system targeting threadbased parallel programming. Shared memory minimizes indirect costs caused by parallel task spawning and data communication. Mrphi [START_REF] Lu | Mrphi: An optimized mapreduce framework on intel xeon phi coprocessors[END_REF] is also a MapReduce implementation optimized for the Intel Xeon phi. Different from these systems, Mimir+ works on large-scale distributed-memory systems.

Mars [START_REF] He | Mars:a mapreduce framework on graphics processors[END_REF] is a MapReduce implementation totally deployed on GPUs. In Mars, there are a large number of threads running in parallel on the GPUs. Each thread computes a KV pair at a time. To avoid multi-threaded write conflicts, Mars uses a lock-free strategy to ensure that parallel programs are correct, with minimal synchronization costs.

On high performance computing system, Kuen Hung Tsoi et al. developed a heterogeneous computing system, Axel [START_REF] Tsoi | Axel:a heterogeneous cluster with fpgas and gpus[END_REF], which consist of FPGAs and GPUs, and they implemented a MapReduce framework on Axel which significantly promoted the speed of calculation.

Conclusion

In this paper, we propose an optimized MapReduce framework on heterogeneous high-performance computing system: Mimir+. This framework inherits the core idea of MR-MPI, reconstructs a heterogeneous workflow and implements the GPU acceleration interfaces so that we can accelerate the data processing of MapReduce jobs and make full use of resources on heterogeneous high-performance computing system. Our results on the Tianhe-2 supercomputer prove that Mimir+, compared to the original Mimir, significantly improves the speed of data processing during the computing phase for data-intensive applications.

Fig. 1 .Fig. 2 .

 12 Fig. 1. Workflow of Mimir+

Fig. 3 .

 3 Fig. 3. Performance Comparison on WordCount and Matrix Multiplication

Acknowledgments. We are grateful to the anonymous reviewers for their valuable suggestions that will be used to improve this paper. This work is partially supported by National Key R&D Program of China 2017YFB0202201, National Natural Science Foundation of China under U1611261, 61433019, U1435217, 61872392 and the Program for Guangdong Introducing Innovative and Enterpreneurial Teams under Grant NO. 2016ZT06D211.


Grégoire Bonin
email: gregoire.bonin@etu.univ-nantes.fr

Achour Mostéfaoui
email: achour.mostefaoui@univ-nantes.fr

Matthieu Perrin
email: matthieu.perrin@univ-nantes.fr

Brief Announcement: Wait-Free Universality of Consensus in the Infinite Arrival Model

In classical asynchronous distributed systems composed of a fixed number n of processes where some proportion may fail by crashing, many objects do not have a wait-free linearizable implementation (e.g. stacks, queues, etc.). It has been proved that consensus is universal in such systems, which means that this system augmented with consensus objects allows to implement any object that has a sequential specification. In this paper, we consider a more general system model called infinite arrival model where infinitely many processes may arrive and leave or crash during a run. We prove that consensus is still universal in this more general model. For that, we propose a universal construction based on a weak log that can be implementated using consensus objects.

Introduction

Maurice Herlihy proved in [START_REF] Herlihy | Impossibility and universality results for wait-free synchronization[END_REF] that consensus is universal in classical distributed systems composed of a set of n processes. Namely, any object having a sequential specification has a wait-free and linearizable implementation using only read/write registers (memory locations) and some number of consensus objects. For proving the universality of consensus, Herlihy introduced the notion of universal construction. It is a generic algorithm that, given a deterministic sequential specification of any object, provides a concurrent implementation of this object. Since then, many universal constructions have been proposed for several objects [START_REF] Raynal | Distributed universal constructions: a guided tour[END_REF], assuming the availability of hardware special instructions that provide the same computing power as consensus, like compare&swap, Load-Link/Store-Conditional etc.

This last decade, first with peer-to-peer systems, and then with multi-core machines and the multithreading model, the assumption of a closed system with a fixed number n of processes and where every process knows the identifiers of all processes became too restrictive. Hence the infinite arrival model introduced in [START_REF] Merritt | Resilient consensus for infinitely many processes[END_REF]. In this model, any number of processes can crash (or leave, in a same way as in the other model), but any number (be it finite or not) of processes can also join the network. When a process joins such a system, it is not known to the already running processes, so no fixed number of processes can be used in the implementations as a parameter. Let us note that, at any time, the number of processes that have already joined the system is finite, but can be infinitely growing.

Problem statement The aim of this paper is to extend universality of consensus to the infinite arrival model. The question is thus "is it possible to build a universal wait-free linearizable construction based on consensus objects and read/write atomic registers?" This is not trivial for different reasons. First, although the lock-free universal constructions still work in the infinite arrival model because they ensure a global progress condition, this is no more the case for wait-free universal constructions. Second, wait-free implementations rely on what is called help mechanism, that has been recently formalized in [START_REF] Censor-Hillel | Help![END_REF]. This mechanism requires any process, before terminating its operation, to help processes having pending operations, in order to reach wait-freedom. One of the difficulties in the infinite arrival model is that helping is not obvious. Indeed, helping requires at least that a process needing to be helped Algorithm 1: Wait-free weak log using consensus is able to announce its existence to other processes willing to help it. Due to the infinite number of potential participating processes over time, it is not reasonable to assume that each process can write in a dedicated register, and to require helping processes to read them all. When only consensus and read/write registers are accessible to a process, a newly arriving process must compete with a potentially infinite number of other arriving processes on either a consensus object or a same memory location; and may fail on all its attempts.

The Weak Log Abstraction

Similarly to [START_REF] Fatourou | Highly-efficient wait-free synchronization[END_REF] which first proposes a Collect object that will be used as a building block for a universal construction, we propose a weak log object that is used as a list of presence where a process that arrives registers. A weak log can then be used in Herlihy's universal construction [START_REF] Herlihy | Impossibility and universality results for wait-free synchronization[END_REF] instead of the array of registers to achieve wait-freedom. In an instance of the weak log, each process p i proposes a value through an operation append(v i ), that returns the sequence of all the values previously appended. The weak log is wait-free but not linearizable. Instead, it is specified by the following properties.

Definition 1 (weak log). All processes p 0 , p 1 , . . . propose distinct values v 0 , v 1 , . . . by invoking append(v i ), that returns a finite sequence

w i = w i,1 • w i,2 • • • w i,|wi| such that:
Validity All values in a sequence w i have been appended by some process.

suffixing The last value of the sequence returned by p i is its own.

Total order All pairs of values contained in both w i and w j appear in the same order.

Eventual visibility If p i terminates, finitely many returned sequences do not contain v i .

Wait-freedom : No process takes an infinite number of steps in an execution.

The main difficulty in the implementation of a weak log lies in the allocation of one memory location per process, where it can safely announce its invoked operation. As it is impossible to allocate an infinite array at once, it is necessary to build a data structure in which processes allocate their own piece of memory, and make it reachable to other processes, by winning a consensus. A linked list in which processes compete to append their value at the end follows a similar pattern, but it poses a challenge: as an infinite number of processes access the same sequence of consensus objects, one process may loose all its attempts to insert its own node, breaking wait-freedom.

Algorithm 1 solves this issue by using a novel feature, that we call passive helping: when a process wins a consensus, it creates a side list to host values of processes concurrently competing on the same consensus object. As only a finite number of processes have arrived in the system when the consensus is won, a finite number of processes will try to insert their value in the side list, which ensures termination.

Processes executing Algorithm 1 build a linked list of linked lists of nodes of the form list.head, list.tail where list.tail is a consensus object that references nodes of the same form, and list.head = node.head, node.tail is a node of the side list, where node.head is a value appended by some process and node.tail is a consensus object accepting values of the same type as list.head. Processes share a consensus object, first, that references the first node of the list of lists, and a read/write register, last, that references a consensus object list.tail.

In absence of concurrency, last references the end of the list starting with first. However, as the consensus and the write on lines 2 and 3 are not done atomically, a very old value can be written in last, in which case its value could move backward. The central property of the algorithm is that last eventually moves forward, allowing very slow processes to find some place in a side list.

Conclusion

Consensus is a central problem in distributed computing, because it allows wait-free linearizable implementations of all objects with a sequential specification, in systems composed of n asynchronous processes that may crash. In this paper, we asked the question of whether the result still holds in the infinite arrival model, in which a potentially infinite number of processes can arrive and leave during an execution. We answered this question positively by introducing a weak log abstraction, that can be implemented using only consensus objects and read/write registers and can be used in a wait-free and linearizable universal construction.

Acknowledgement

This work was partially supported by the French ANR project 16-CE25-0005 O'Browser devoted to the study of decentralized applications on Web browsers.


la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

This method allows practitioners to make more informed decisions at each stage of the problem-solving process, and ultimately arrive at better solutions in less time.

  Integrating the Theory of Inventive Problem Solving with Discrete Event Simulation in Supply Chain Management Fatima Zahra Benmoussa, Sébastien Dubois, Roland De Guio, Ivana Rasovska, Rachid Benmoussa To cite this version: Fatima Zahra Benmoussa, Sébastien Dubois, Roland De Guio, Ivana Rasovska, Rachid Benmoussa. Integrating the Theory of Inventive Problem Solving with Discrete Event Simulation in Supply Chain Management. 18th TRIZ Future Conference (TFC), Oct 2018, Strasbourg, France. pp.330-347, 10.1007/978-3-030-02456-7_27. hal-02279755