J Muñoz-Enano

P Vélez

M Gil

J Mata-Contreras

K Grenier

D Dubuc

F Martín

Microstrip Lines Loaded with Metamaterial-Inspired Resonators for Microwave Sensors/Comparators with Optimized Sensitivity

Keywords: Metamaterial resonators, microwave sensors, microstrip technology, open split ring resonators, fluidic sensors

This paper presents a sensitive comparator/sensor useful to detect small differences between a reference sample and a sample under test (SUT). The device, a four-port structure, is based on a pair of identical microstrip lines each one loaded with an open split ring resonator (OSRR), the sensitive part of the device. The working principle of the comparator/sensor is mode conversion, caused when the OSRRs are asymmetrically loaded, and the output variable is the cross-mode transmission coefficient. The structure is very sensitive to changes in the complex dielectric constant between the reference sample and the SUT, and it is useful as comparator and sensor in applications such as defect detection, dielectric characterization of solids and liquids, and solute concentration measurements in liquids. The application examples reported in the paper confirm the high sensitivity of the structure to the complex dielectric constant of the SUT, caused by the specific shape of the OSRRs.

I. INTRODUCTION

Transmission lines loaded with metamaterial-inspired resonant elements have been exhaustively used for sensing purposes. In such sensors, frequency and notch (or peak) magnitude variation [START_REF] Ebrahimi | Highsensitivity metamaterial-inspired sensor for microfluidic dielectric characterization[END_REF]- [START_REF] Su | Analytical method to estimate the complex permittivity of oil samples[END_REF], coupling modulation [START_REF] Naqui | Novel sensors based on the symmetry properties of split ring resonators (SRRs)[END_REF]- [START_REF] Horestani | Two-dimensional displacement and alignment sensor based on reflection coefficients of open microstrip lines loaded with split ring resonators[END_REF], and frequency splitting [START_REF] Horestani | Two-dimensional alignment and displacement sensor based on movable broadside-coupled split ring resonators[END_REF]- [START_REF] Ebrahimi | Differential sensors using microstrip lines loaded with two split ring resonators[END_REF], caused by the variable to be sensed, have been the main considered sensing principles. In most of the previously cited works, sensor performance (i.e., dynamic range, sensitivity, resolution, etc.) has been proven to be enough for the intended application. However, there are applications demanding extremely sensitive passive sensors, able to detect small variations in the measurand. Examples are defect detection in solid samples, solute concentration measurement in highly diluted solutions (e.g., electrolytes or glucose content in water, blood, or urine), or monitoring changes in the composition of certain substances (of potential interest, e.g., in wine fermentation processes), among others.

In [START_REF] Vélez | Highly-sensitive microwave sensors based on open complementary split ring resonators (OCSRRs) for dielectric characterization and solute concentration measurements in liquids[END_REF], highly sensitive sensors based on a pair of symmetric transmission lines loaded with mirrored open complementary split ring resonators (OCSRRs) were reported. In that work, the structure was applied to the dielectric characterization of liquids (i.e., mixtures of DI water and ethanol), as well as to the measurement of diluted concentrations of NaCl in DI water. The working principle in the sensors of [START_REF] Vélez | Highly-sensitive microwave sensors based on open complementary split ring resonators (OCSRRs) for dielectric characterization and solute concentration measurements in liquids[END_REF] is mode conversion, caused by disruption of symmetry. Namely, when the mirrored OCSRRs are identically loaded or unloaded (hence keeping symmetry unaltered), mode conversion is prevented, and the cross-mode transmission coefficient, the output variable, is (ideally) null. Conversely, when one of the OCSRRs is loaded with a sample (the reference -REF), and the other one is loaded with a different sample (the sample under test -SUT), mode conversion arises, and the magnitude of the cross mode transmission coefficient is determined by the level of asymmetry. Thus, these devices are similar to differential sensors, which can be used as comparators (e.g., to detect defects or to monitor changes in the composition of a substance, as compared to a reference), or as sensors useful to determine the properties of the SUT.

Key performance parameters of these sensors based on symmetry truncation are resolution and sensitivity. The former provides the minimum level of the input variable (measurand) that can be detected (or resolved), and it is intimately related to the "quality" of symmetry in the unloaded sensing structure. Sensitivity is defined as the variation of the output variable (magnitude of the cross-mode transmission coefficient in our case) caused by the variation in the input variable (dielectric constant, solute concentration, etc.). For resolution optimization, it is fundamental: (i) to be as much precise as possible in sensor manufacturing, and (ii) to simplify the fabrication process of the sensor as much as possible, circumventing stages that might cause undesired symmetry disruption. Particularly, the use of vias should be avoided (if possible), since these elements may be the origin of potential deviations from (perfect) symmetry.

Contrary to the sensor reported in [START_REF] Vélez | Highly-sensitive microwave sensors based on open complementary split ring resonators (OCSRRs) for dielectric characterization and solute concentration measurements in liquids[END_REF], where vias associated to the OCSRRs were necessary, a novel via-less sensor/comparator based on a pair of microstrip lines, each one loaded with an open split ring resonator (OSRR), is reported in this paper. The sensor exhibits good resolution and high sensitivity, since it has been designed on the basis of an analysis aimed to optimize sensitivity (note that resolution mainly depends on the accuracy in the fabrication process). In the paper, such sensitivity analysis, based on the lumped element equivalent circuit model, is presented. Then, the sensor is used as comparator, where it is shown that tiny defects in a dielectric sample (as compared to a reference) are detectable. Finally, the functionality of the structure to determine the concentration of solute (NaCl in this work) in highly diluted solutions of DI water (the solvent), is demonstrated. For that purpose, the sensor has been equipped with two fluidic channels, one for the REF liquid and the other one for the LUT (liquid under test). The most relevant aspect in this later case is the resulting sensitivity, by far superior than the one achieved in [START_REF] Vélez | Highly-sensitive microwave sensors based on open complementary split ring resonators (OCSRRs) for dielectric characterization and solute concentration measurements in liquids[END_REF].

II. THE SENSOR: TOPOLOGY AND CIRCUIT MODEL

The topology of the proposed sensor (excluding the fluidic channels and necessary accessories) and the equivalent circuit model are depicted in Fig. 1. Note that the transmission lines are described by distributed elements in the circuit model (i.e., transmission line sections with characteristic impedance Z0 and electrical length 𝛽l, l being the physical length of such lines), whereas the OSRRs are accounted for by means of lumped elements. L, C and G are the inductance, capacitance and conductance, respectively of the unloaded OSRR. The effects of the loading samples are taken into account by means of CREF and GREF, the OSRR capacitance and conductance, respectively, associated to the REF sample, and by means of CSUT and GSUT, corresponding to the contribution of the SUT. Note that the lines (and OSRRs) are deliberately uncoupled. This simplifies the circuit model of the structure, since each half can be treated separately (i.e., lumped elements accounting for an eventual coupling are avoided), which in turn eases the analysis, to be reported latter. To demonstrate the validity of the model, it suffices to consider one half of the sensing structure. Particularly, we have extracted the parameters by considering a bare (unloaded) OSRR. Figure 2 depicts the transmission coefficient of such half structure inferred from full wave electromagnetic simulation (using Keysight ADS), compared to the one obtained by circuit simulation. The agreement in the region of interest is good, pointing out the validity of the model.

III. SENSITIVITY ANALYSIS

According to the port designation in Fig. 1, and taking into account that the lines are uncoupled, the cross-mode transmission coefficient is given by 𝑆 ./ 01 = / .

(𝑆 ./ -𝑆 56 )

(1) Let us now consider that the characteristic impedance of the lines is identical to the port impedance, Z0 (typically 50 W). Under these conditions, the effect of the lines is simply a phase shift in the cross-mode transmission coefficient. Since we consider that the output variable is the modulus of that coefficient, the effects of the line can be neglected in the analysis. In other words, the modulus of the cross-mode transmission coefficient is identical to the one of the crossmode transmission coefficient of the structure by excluding the lines. Such transmission coefficient is thus given by

where S21 OSRR and S43 OSRR are the transmission coefficients of the individual OSRR-loaded lines that result by excluding the line contribution, and ZREF and ZSUT are the impedances of the series branches of the individual lines.

Let us now assume that substrate losses are small, that the reference (REF) sample and the SUT are dielectric (i.e. intrinsically low-loss) materials, and that the dielectric constant of both samples (REF and SUT) are similar (a situation of interest in many applications). Let us also evaluate expression ( 2

Finally, after some tedious (but straightforward) algebra, the real and the imaginary parts of the cross-mode transmission coefficient are found to be: where

𝑅𝑒 X𝑆 ./ 01 w LMN Y = K C w LMN C 5O D Z𝐺 :RS \ ] 1>1 @AB 1>1 EFG ^-𝐺 ;TU \ _ (
G'SUT = G + GSUT and G'REF = G + GREF.
From ( 5), it can be concluded that the sensitivity of the modulus of the cross-mode transmission coefficient with complex dielectric constant variations between the REF sample and the SUT (manifested by different values of GSUT and GREF, and/or different values of CSUT and CREF) increases with L and wref. If we consider that wref is not a design parameter (working at high frequencies may represent a penalty in terms of equipment costs), it follows that to increase sensitivity L must be large and, consequently, C must be small.

In Fig. 3, the effects of L on |S21 DC |wref, for changes in both the capacitance and conductance of the SUT with regard to the REF sample, are depicted. It can be seen that the sensitivity (given by the slope of the curves) increases significantly with L, as expected.

IV. DESIGN AND EXPERIMENTAL VALIDATION

The OSRRs of the sensor have been designed on the basis of the previous sensitivity analysis. Thus, the objective has been to implement an OSRR with small capacitance and large inductance, exhibiting a resonance frequency (unloaded OSRR) of 1.05 GHz. The result is the sensor layout depicted in Fig. 1(a). Note that the topology of the OSRRs presents narrow and separated strips, as corresponds to a large inductance and small capacitance.

A. Functionality as Comparator

The first experimental validation (as comparator) has been carried out by considering a slab of Rogers RO3010 with er = 10.2, h = 1.27 mm and tand = 0.0022 as REF sample. It has been positioned on top of the OSRR of the REF line, and it has been tightened by screws against the substrate in order to eliminate the effects of the air gap. Then, different SUTs have been considered: (i) a SUT identical to the REF sample, (ii) a SUT consisting of a slab of Rogers RO4003C with er = 3.38, h = 1.524 mm and tand = 0.0027, (iii) a SUT consisting of a slab of FR4 with er = 4.4, h = 1.6 mm and tand = 0.02, and (iv) SUTs identical to the reference sample, with periodic arrays of holes across the slab to generate a smaller effective dielectric constant, and different density of holes. In all cases, the SUT has been also screwed against the substrate. The measured cross-mode transmission coefficients, depicted in Fig. 4 for the considered cases, reveal that a minimum level of -36.75 dB is achieved for the symmetric case. By contrast, the maximum cross-mode transmission coefficient increases to -9.43 dB for case (ii), whereas for case (iii) the maximum value is found to be -12.08 dB. Finally, for case (iv), the maximum value is found to be -10.83 dB for the sample with higher density of holes (i.e., the difference in the composition of the REF sample and SUT can be perfectly detected).

B. Solute concentration measurements

The second experimental validation has been focused on the determination of NaCl concentration in DI water. Thus, the REF sample is pure DI water, whereas the SUT (or liquid under test -LUT-in this case) is the solution of NaCl in DI water. Obviously, it has been necessary to add fluidic channels with the corresponding accessories to fix the channel to the substrate and to inject the liquids (by means of a syringe) in the corresponding channels. The picture of the device is shown in Fig. 5, where channel dimensions and other details of the structure are provided (see caption). The measured cross-mode transmission coefficient (magnitude) for different NaCl concentrations is depicted in Fig. 6, whereas the maximum value as a function of the solute content can be seen in Fig. 7. The minimum level of NaCl concentration that can be resolved is 0.25 g/L, similar to [START_REF] Vélez | Highly-sensitive microwave sensors based on open complementary split ring resonators (OCSRRs) for dielectric characterization and solute concentration measurements in liquids[END_REF]. The sensitivity increases as the concentration of NaCl decreases, and the maximum value is found to be 0.0216 (g/L) -1 , superior than the one obtained in [START_REF] Vélez | Highly-sensitive microwave sensors based on open complementary split ring resonators (OCSRRs) for dielectric characterization and solute concentration measurements in liquids[END_REF] [0.0092 (g/L) -1 ]. From the results of Fig. 7, a calibration curve, providing a correlation coefficient of R 2 = 0.9934, has been obtained:

[𝑁𝑎](𝑔/𝐿) = 0.43337𝑒

This curve can be obtained to determine the concentration of NaCl in DI water from the measurement of the cross-mode transmission coefficient. V. CONCLUSION A novel differential sensor based on the measurement of the cross-mode transmission coefficient in a pair of OSRRloaded lines has been presented. From a simple analysis, based on the equivalent circuit model, it has been concluded that sensitivity increases with the inductance of the OSRR. Consequently, the fabricated sensor has been designed with a large inductance and low capacitance. The functionality of the sensor as comparator and for the measurement of small concentrations of NaCl in DI water has been demonstrated.

Fig. 1 .

 1 Fig. 1. Topology (a) and circuit model (b) of the proposed sensor. Notice that windows are opened in the ground plane in order to ensure the validity of the proposed equivalent circuit model.

Fig. 2 .

 2 Fig. 2. Transmission coefficient (magnitude and phase) of the sensor (one half) inferred from circuit and electromagnetic simulation. The considered substrate is Rogers RO4003C with dielectric constant er = 3.38, thickness h = 1.524 mm, and loss tangent tand = 0.0027. In reference to Fig. 1, dimensions are: l = 40 mm, 𝑤 = 3.4 mm, ℎ = 9.4 mm, 𝑐 = 0.2 mm, 𝑑 = 2 mm, 𝑙 '() = 18.4 mm, ℎ '() = 3 mm, 𝑙 *+) = 13.4 mm, ℎ *+) = 1.4 mm, 𝑙 , = 44 mm and ℎ , = 26.8 mm. Circuit parameters are: L = 32.6 nH, C = 0.714 pF, G = 0.079 mS; line parameters are 𝛽l = 83º and Z0 = 50 W..

  ) at the frequency of maximum transmission for the REF line, given by w Hsuch frequency, ZREF(wref) << Z0 since losses are small and the effects of the inductive (L) and capacitive (C + CREF) reactances are cancelled at that frequency. Moreover, ZREF » ZSUT provided it is assumed that the dielectric constant are similar (and consequently CREF » CSUT). Therefore, the cross-mode transmission coefficient can be approximated by (w H'I ) -𝑍 ;TU (w H'I )P

Fig. 3 .

 3 Fig. 3. Effects of L on the cross-mode transmission coefficient for variations in the conductance (a) and capacitance (b) of the SUT as compared to the REF sample. In (a), CREF and CSUT are identical and fref = wref/2p and G'REF are fixed to 1 GHz and 0.4 mS respectively. In (b), G'REF and G'SUT are identical and equal to 0.4 mS and fref is still fixed to 1 GHz. Note that when G'REF and G'SUT are equal in (a) and CREF and CSUT are equal in (b), the modulus of the crossmode transmission coefficient is zero (perfect symmetry case).

Fig. 4 .

 4 Fig. 4. Cross-mode transmission coefficient that results by loading the REF and the SUT lines with different solid samples.

Fig. 5 .

 5 Fig. 5. Photograph of the sensor including fluidic channels and accessories. The fluidic channels, made of polydimethylsiloxane (PDMS), have dimensions:26 mm (length), 4.6 mm (width), 1.5 mm (height). Such channels are covered by polyether ether ketone (PEEK) to provide mechanical stability.

Fig. 6 .

 6 Fig. 6. Cross-mode transmission coefficient for different NaCl concentrations.

Fig. 7 .

 7 Fig. 7. Maximum cross-mode transmission coefficient with NaCl content.

ACKNOWLEDGMENT This work was supported by projects TEC2016-75650-R and 2017SGR-1159, and by FEDER funds. P. Vélez acknowledges MICINN for JdC fellowship, ref. IJCI-2017-31339. J. Muñoz acknowledges Secreteraria d'Universitats i Recerca (Gen. Cat.) and European Social Fund for the FI grant.


P Vélez

J Muñoz-Enano

F Martín

K Grenier
email: grenier@laas.fr

D Dubuc

J Mata-Contreras

Keywords: Microwave sensors, differential sensors, microfluidics, permittivity measurements, microstrip technology, split ring resonator (SRR), electrolyte concentration

A differential microwave sensor, based on a pair of uncoupled microstrip lines each one loaded with a split ring resonator (SRR), is applied to the measurement of electrolyte concentration in deionized (DI) water. For that purpose, fluidic channels are added on top of the SRR gaps, the most sensitive parts of the structure. The operating principle is based on the measurement of the cross-mode insertion loss, highly sensitive to small asymmetries caused by differences between the reference liquid and the liquid under test (LUT). In this work, the reference liquid is pure DI water (the solvent), whereas the solution, DI water with electrolyte content, is injected to the LUT channel. The proposed sensor is able to detect electrolyte concentrations as small as 0.25 g/L, with maximum sensitivity of 0.033 (g/L) -1 .

The sensor is validated by measuring the concentration of three types of electrolytes, i.e., NaCl, KCl and CaCl2. Finally, the sensor is applied to monitor variations of total electrolyte concentration in urine samples.

I. INTRODUCTION

lectrolytes are chemical substances that dissociate into cations and anions when dissolved in polar solvents, such as water, thereby modifying the electric and electromagnetic properties of the solvent. Particularly, changes in the conductivity and loss factor (or loss tangent) of the solvent are expected by the presence of electrolytes in it. Therefore, electrolyte concentration can be measured by means of methods or approaches sensitive to the conductivity or loss factor of the solution, and particularly through microwave techniques.

Electrolytes are physiologically important since they play key roles in various vital functions, such as blood pH and pressure control, body hydration, nerve and muscle functions, etc. [START_REF] Hogan | Fluids, Electrolytes, and Acid-Base Balance with Nursing Reviews and Rationales[END_REF]. The most important primary ions of electrolytes in blood and urine are sodium (Na + ), potassium (K + ), calcium (Ca 2+ ), chloride (Cl -) and bicarbonate (HCO3 -). Imbalances in the concentration of certain ions in blood or urine (the socalled anion gap [START_REF] Oh | The anion gap[END_REF]) are indicative of certain pathologies. For instance, in urine the anion gap is defined as [Na + ] + [K + ] -[Cl -], where [*] denotes concentration, and typical values in urine samples not subjected to physiological pathologies should be comprised between 0 and -33 mEq/L. Ion concentration in blood and urine are typically measured by means of electrochemical systems, such as ion selective electrodes (ISE) [START_REF] Buck | Ion selective electrodes[END_REF], able to provide the individual concentration of specific ions, and consequently the anion gap. Measuring the total concentration of ions does not determine the anion gap, but may be indicative of an overall excess or defect of electrolytes, as compared to the typical levels found in "healthy" samples. Therefore determining the total electrolyte concentration in serum, plasma or urine through real-time low-cost systems (as compared to chemical systems) may be useful as a complementary diagnosis method.

Within this context, this paper is focused on the measurement of electrolyte concentration in DI water using microwaves. The sensor is based on the variations of the complex dielectric constant (mostly related to variations in the conductivity or loss tangent) of DI water experienced by the presence of electrolytes dissolved in it. Such variations can be sensitively detected by means of a differential technique based on the measurement of the cross-mode insertion loss in a pair of microstrip lines loaded with split ring resonators (SRRs), and equipped with fluidic channels for liquid injection. The main advantage of this resonator-based approach is the high sensitivity and capability to detect small concentrations of electrolytes in water.

Many sensing structures based on resonator-loaded lines have been proposed, and they can be categorized in three main groups: (i) frequency variation sensors [START_REF] Puentes | Sensor array based on split ring resonators for analysis of organic tissues[END_REF]- [START_REF] Su | Analytical method to estimate the complex permittivity of oil Samples[END_REF], (ii) coupling modulation sensors [START_REF] Naqui | Novel sensors based on the symmetry properties of split ring resonators (SRRs)[END_REF]- [START_REF] Naqui | Angular displacement and velocity sensors based on coplanar waveguides (CPWs) loaded with S-shaped split ring resonator (S-SRR)[END_REF] and (iii) frequency-splitting sensors [START_REF] Horestani | Two-dimensional alignment and displacement sensor based on movable broadside-coupled split ring resonators[END_REF]- [START_REF] Vélez | Microwave microfluidic sensor based on a microstrip splitter/combiner configuration and split ring resonators (SRR) for dielectric characterization of liquids[END_REF]. In frequency variation sensors, the output variable is the frequency position of either a notch or a peak in the frequency response of a transmission line loaded with a resonant element (sometimes, the notch depth, or the peak magnitude, is also used as an additional output variable). Sensors based on this approach have been applied to different types of measurements, but, particularly, they have been used for dielectric characterization of solid [START_REF] Boybay | Material characterization using complementary split-ring resonators[END_REF]- [START_REF] Yang | Noncontact measurement of complex permittivity and thickness by using planar resonators[END_REF] and liquid [START_REF] Ebrahimi | Highsensitivity metamaterial-inspired sensor for microfluidic dielectric characterization[END_REF], [START_REF] Su | Estimation of the complex permittivity of liquids by means of complementary split ring resonator (CSRR) loaded transmission lines[END_REF], [START_REF] Su | Analytical method to estimate the complex permittivity of oil Samples[END_REF]

E

principle in coupling modulation sensors [START_REF] Martín | Artificial Transmission Lines for RF and Microwave Applications[END_REF], [START_REF] Naqui | Symmetry Properties in Transmission Lines Loaded with Electrically Small Resonators: Circuit Modeling and Applications[END_REF]. In such sensors, a transmission line is symmetrically loaded with a symmetric resonator uncoupled to it. Such uncoupling is achieved by using resonant elements exhibiting a symmetry plane of different electromagnetic sort than the symmetry plane of the line [START_REF] Martín | Artificial Transmission Lines for RF and Microwave Applications[END_REF], [START_REF] Naqui | Symmetry Properties in Transmission Lines Loaded with Electrically Small Resonators: Circuit Modeling and Applications[END_REF]. However, by truncating symmetry (e.g., by means of a relative linear or angular displacement between the resonator and the line, or by means of an asymmetric dielectric loading), line-to-resonator coupling is activated, thereby generating a notch in the frequency response (with depth intimately related to the level of asymmetry). In such coupling modulation sensors the output variable is thus the notch depth, and they have been mostly applied to the measurement of spatial variables [START_REF] Naqui | Novel sensors based on the symmetry properties of split ring resonators (SRRs)[END_REF]- [START_REF] Naqui | Angular displacement and velocity sensors based on coplanar waveguides (CPWs) loaded with S-shaped split ring resonator (S-SRR)[END_REF], [START_REF] Mata-Contreras | Application of split ring resonator (SRR) loaded transmission lines to the design of angular displacement and velocity sensors for space applications[END_REF].

Finally, in frequency splitting sensors, a transmission line is symmetrically loaded with a pair of (not necessarily symmetric) resonators coupled to it. Under perfect symmetry, a single notch at the fundamental resonance frequency of the resonant elements appears. However, if the resonators are asymmetrically unloaded, frequency splitting arises. In these sensors, similar to differential sensors, the output variables are the differential frequency and the differential depth of the generated notches, and these frequency-splitting sensors have been mainly applied to differential permittivity measurements [START_REF] Su | Splitter/combiner microstrip sections loaded with pairs of complementary split ring resonators (CSRRs): modeling and optimization for differential sensing applications[END_REF], [START_REF] Vélez | Microwave microfluidic sensor based on a microstrip splitter/combiner configuration and split ring resonators (SRR) for dielectric characterization of liquids[END_REF].

The previous sensors exhibit, in general, acceptable sensitivities and dynamic ranges, but they exhibit limited resolution, not being able to detect small variations of the variable of interest. This aspect is critical for the measurement of solute concentration in highly diluted solutions. Therefore, for the accurate measurement of electrolyte content in DI water solutions exhibiting concentrations in the range 1-10 g/L or even below, as pursued in this paper, novel strategies, highly sensitive to small concentrations, are needed. The above-mentioned sensing approach, based on the measurement of the cross-mode insertion loss in a pair of lines, each one loaded with a resonant element, provides the necessary sensitivity and resolution for the intended application. This approach was first demonstrated in [START_REF] Vélez | Modeling and analysis of pairs of open complementary split ring resonators (OCSRRs) for differential permittivity sensing[END_REF], [START_REF] Vélez | Highly-sensitive microwave sensors based on open complementary split ring resonators (OCSRRs) for dielectric characterization and solute concentration measurement in liquids[END_REF] by considering open complementary split ring resonators (OCSRRs) [START_REF] Vélez | Open complementary split ring resonators (OCSRRs) and their application to wideband CPW band pass filters[END_REF] as loading resonators (NaCl was the considered electrolyte in [START_REF] Vélez | Highly-sensitive microwave sensors based on open complementary split ring resonators (OCSRRs) for dielectric characterization and solute concentration measurement in liquids[END_REF]).

In this paper, it is demonstrated that sensitivity can be improved by replacing OCSRRs with SRRs. Moreover, sensor validation is carried out by considering three electrolytes, i.e., NaCl, KCl and CaCl2. An advantage of using SRRs instead of OCSRRs as sensing element is the fact that SRRs do not require vias, hence easing fabrication and contributing to enhance resolution, intimately related to the "level" of symmetry achieved when the differential structure is loaded with identical loads in both resonators (approaching to "perfect symmetry" is more feasible if vias are not present). In the last part of the paper, it is demonstrated that the proposed sensor may be useful to detect variations of total ion concentration in biological samples, particularly urine. This may be of interest for real-time monitoring of potential dysfunctions or anomalies, e.g., during disease treatment in hospital environments, related to extreme ion concentrations in such samples.

II. STRUCTURE OF THE PROPOSED SENSOR, SENSING PRINCIPLE AND FABRICATION

The proposed differential sensor consists of two parts: (i) the microwave structure, a FR4 substrate with a pair of uncoupled 50 Ω lines each one loaded with a SRR, and (ii) the fluidic channels plus the mechanical accessories for liquid injection to the channels and for channel attachment to the substrate. The topology of the microwave structure is depicted in Fig. 1, where relevant dimensions are indicated. The dielectric constant and thickness of the considered substrate are er = 4.4 and h = 1.6 mm, respectively. The fluidic channels are made of polydimethylsiloxane (PDMS), and are identical to those used in [START_REF] Vélez | Microwave microfluidic sensor based on a microstrip splitter/combiner configuration and split ring resonators (SRR) for dielectric characterization of liquids[END_REF]. Channel dimensions are designated by hch (height), wch (width) and lch (length). The mechanical parts consist of a polyether ether ketone (PEEK) structure, that accommodates the fluidic connectors (necessary for liquid injection to the channels), and screws, used to fix the PEEK-PDMS assembly on the substrate. In order to avoid substrate absorption, a dry film of clear polyester, with an estimated thickness of 50 µm and dielectric constant of 3.5, has been deposited on top of the SRRs. The top and lateral views of the channel plus mechanical parts are depicted in Fig. 2. The photograph of the whole sensing structure is shown in Fig. 3. The working principle of the proposed differential sensor is symmetry disruption, caused by an asymmetric dielectric load in the SRRs. Thus, in a sensing operation, the reference liquid is injected in one of the channels (designated as REF channel), whereas the liquid under test (LUT) is injected in the other channel (LUT channel). The output variable in the proposed sensor is the cross-mode insertion loss (or cross-mode transmission coefficient), highly sensitive to small asymmetries and, hence, very convenient to detect small differences between the REF and the LUT liquids. This is necessary in order to measure small concentrations of electrolytes in DI water (the purpose of this work). Thus, the considered REF liquid will be pure DI water (the solvent), whereas the LUT is the DI water solution with electrolyte content.

According to the port definition of Fig. 1, the cross-mode transmission coefficient is given by [START_REF] Martín | Balanced Microwave Filters[END_REF] 𝑆

"# $% = # " (𝑆 "# -𝑆 )* ) (1)
This result is valid as long as the SRR-loaded lines are uncoupled. If the structure exhibits perfect symmetry, it follows that S21 DC = 0 (note that the cross-mode insertion loss, i.e., the cross-mode transmission coefficient expressed in dB, should be ideally -¥ under perfect symmetry). However, if symmetry is disrupted, as occurs by injecting pure DI water in the REF channel and the electrolyte solution in the LUT channel, the cross-mode insertion loss should take finite values, and the maximum value should be indicative of the level of asymmetry. Therefore, the maximum level of the cross-mode insertion loss is considered the output variable in the proposed sensing structure.

In practice, perfect symmetry is not achievable, as long as sensor fabrication involves several ("imperfect") processes, including substrate etching, dry film deposition, and mechanical fabrication of the PDMS-PEEK assembly. Thus, certain level of cross-mode insertion loss is expected even by loading the REF and LUT channels with identical liquids. Let us designate the maximum of the modulus of the cross-mode transmission coefficient experimentally found with balanced loads as |S21 DC BAL|. It is important to minimize |S21 DC BAL| as much as possible, since it has direct impact on sensor resolution. Note that tiny differences between the REF liquid and the LUT liquid, which should provide a very small value of |S21 DC |, may be obscured by |S21 DC BAL|. Therefore, an accurate and rigorous sensor fabrication process, providing small |S21 DC BAL|, is demanded for resolution optimization.

III. EXPERIMENTAL VALIDATION

The fabricated sensor has been validated by considering DI water solutions with different types of electrolytes, particularly, NaCl, KCl and CaCl2. These electrolytes have been considered since they are present in blood and urine and they play key roles in several vital functions.

The first set of experiments has been done by injecting DI water solutions with different concentrations of NaCl in the LUT channel. In all the cases, pure DI water has been injected in the REF channel. The measured cross-mode insertion loss for the different NaCl concentrations is depicted in Fig. 4. Note that the cross-mode insertion loss resulting when the LUT channel is filled with pure DI water (balanced loading) is also included. S21 DC BAL, expressed in dB, is found to be -38.95 dB, which is a very reasonable value. NaCl concentrations as small as 0.25 g/L can be perfectly resolved by virtue of the small value of S21 DC BAL. By increasing the electrolyte concentration, the cross-mode transmission coefficient (or insertion loss) also increases, as expected. In Fig. 5, we have depicted the dependence of the maximum value of the crossmode transmission coefficient, |S21 DC |max, with the concentration of NaCl, i.e., [NaCl]. For small concentrations, the sensitivity, i.e., the variation of |S21 DC |max with [NaCl], is very high, and it progressively decreases as [NaCl] increases. The maximum value of the sensitivity is found to be 0.033 (g/L) -1 , i.e., higher than the maximum sensitivity of the sensors proposed in [START_REF] Vélez | Highly-sensitive microwave sensors based on open complementary split ring resonators (OCSRRs) for dielectric characterization and solute concentration measurement in liquids[END_REF], based on a similar approach, but using OCSRRs as sensing elements (in [START_REF] Vélez | Highly-sensitive microwave sensors based on open complementary split ring resonators (OCSRRs) for dielectric characterization and solute concentration measurement in liquids[END_REF] the sensors were applied to the measurement of NaCl concentration, as well). From the results of Fig. 5, we have obtained the calibration curve, from which the concentration of NaCl can be inferred by measuring |S21 DC |max. Such curve, with a correlation coefficient of R 2 = 0.99966, is Repetitiveness of the results is important for the practical use of the proposed sensors. Therefore, we have repeated the previous measurements by subsequently injecting in the LUT channel the DI water solutions with the NaCl concentrations indicated in Fig. 5. The results, also included in Fig. 5 and identified as Measurement 2, reveal that measurements are repetitive by virtue of the small differences with the first experimental campaign (Measurement 1).

In the second set of experiments, KCl has been considered as solute. The variation of the cross-mode insertion loss and |S21 DC |max with KCl concentration are depicted in Figs. 6 and7, respectively. Repetitiveness of the results is also demonstrated (see Fig. 7). In this case, the calibration curve, with R 2 = 0.99931, has been found to be Finally, we have prepared several solutions of CaCl2 in DI water, and we have also measured the cross-mode insertion loss, as well as |S21 DC |max, for the different solute concentrations. The results are depicted in Figs. 8 and9. The calibration curve, with R 2 = 0.99905, in this case is

[𝐶𝑎𝐶𝑙]𝑔/𝐿 = -1.76 + 1.29𝑒 < = >? @A B.BE>>? G + 3 • 10 KR 𝑒 < = >? @A B.BBSES G (4)
and the maximum sensitivity is 0.021 (g/L) -1 Note that the dependence of |S21 DC |max with the electrolyte concentration is not identical for KCl, NaCl and CaCl2, but similar. The relatively high sensitivity of the reported sensors is in part because the presence of electrolytes in DI water modifies substantially its conductivity (or loss tangent), provided the electrolyte molecules dissociate into anions and cations when dissolved in water. For a certain electrolyte concentration, ion concentration is determined by the molecular mass of the electrolyte. Therefore, since the conductivity depends on ion concentration, we cannot expect identical dependences of the cross-mode insertion loss with the electrolyte concentration for the different electrolytes considered. Moreover, conductivity depends also on ion mobility, also related to the atomic mass. Indeed, at intermediate concentrations (between 2.5 g/L and 20 g/L), the electrolyte that produces higher values of the cross-mode insertion loss is NaCl, which is coherent with the low value of the atomic mass of Na, as compared to K and Ca. However, the differences are not significant. On the other hand, for very small values of the electrolyte concentration (< 2.5 g/L), the accuracy is expected to be limited, and for large values (> 20 g/L), |S21 DC |max exhibits a quasi-saturation effect, and the dependence of the conductivity on ion concentration and mobility may be more complex. These facts may explain that at low and high electrolyte concentrations there is not a clear dependence of the cross-mode insertion loss with the ion concentration and atomic mass. Nevertheless, for a given electrolyte, the very good correlation coefficient that results by curve fitting, plus the repetitiveness of the results, reveals that the corresponding calibration curve is useful to determine its concentration.

Besides the work [START_REF] Vélez | Highly-sensitive microwave sensors based on open complementary split ring resonators (OCSRRs) for dielectric characterization and solute concentration measurement in liquids[END_REF], focused on the measurement of NaCl concentration in DI water by using a pair of OCSRR-loaded lines, other papers report solute concentration measurements in liquid solutions. In [START_REF] Babajanyan | Sodium chloride sensing by using a near-field microwave microprobe[END_REF], the considered solute is also NaCl, whereas in [START_REF] Bababjanyan | Real-time noninvasive measurement of glucose concentration using a microwave biosensor[END_REF]- [START_REF] Kim | Microwave dielectric resonator biosensor for aqueous glucose solution[END_REF], the proposed sensors are used for the measurement of glucose concentration in liquid solutions. Finally, in [START_REF] Vélez | Solute Concentration Measurements in Diluted Solutions by means of Split Ring Resonators[END_REF], both NaCl and glucose concentration measurements in DI water are reported. Table I compares these sensors in terms of maximum sensitivity, resolution and dynamic range. It is remarkable the sensor reported in [START_REF] Kim | Noninvasive in vitro measurement of pig-blood D-glucose by using a microwave cavity sensor[END_REF], with a very good value of the sensitivity, taking into account that the considered solute is glucose, a substance that does not modify the water conductivity (or loss factor) as electrolytes do. If we focus on the sensors devoted to NaCl concentration measurements, we conclude that the sensor proposed in this paper provides the best combination of sensitivity and resolution. Moreover, sensor fabrication is simple (only a single metal layer is etched) and vias are not required. Therefore, the reported differential sensing structure, based on SRRs is very promising for the measurement of electrolyte content in very diluted liquid solutions.

V. CHARACTERIZATION OF URINE SAMPLES

To further validate the proposed sensor, we have characterized several horse urine samples, with different levels of electrolyte concentrations (Na + , K + and Cl -), which have been externally measured by means of an ISE electrochemical system (the electrolyte concentration measurements and the urine samples have been provided to us by the Biochemistry and Molecular Biology Department of Universitat Autònoma de Barcelona). From the measured values of the individual electrolyte concentrations (i.e., Na + , K + and Cl -) for each sample, expressed in mEq/L, we have obtained the total concentrations by a simple addition. Note that the total concentration in mEq/L is proportional to the total ion concentration, a quantity of interest as it may be indicative of certain pathologies if certain limits are surpassed. The realtime monitoring of possible variations in the total ion concentration in urine (or even in blood) may be also of interest to detect possible dysfunctions or anomalies, e.g., during disease treatment in hospital environments. Note that with the proposed sensor system, ion concentration variations as compared to a reference sample can be easily measured.

The urine samples provided to us exhibit the total ion concentrations indicated in the right hand side column of Fig. 10. By considering as reference liquid the urine sample with the highest level of ion concentration (615.8 mEq/L), the cross-mode insertion loss that results by injecting the different samples to the LUT channel are those depicted in Fig. 10. It should be mentioned that for monitoring changes in total ion concentration with time in a real scenario, the reference sample should be, obviously, the urine at the beginning of the test campaign. In our case, we have (arbitrarily) considered that the reference sample is the one with 615.8 mEq/L ion concentration, as mentioned above.

The variation of |S21 DC |max with the total ion concentration is depicted in Fig. 11. The calibration curve, with R 2 = 0.99422, is (the total ion concentration has been designated as [*])

and the maximum sensitivity has been found to be -0.00058 (mEq/L) -1 . From these results, we can envisage the application of this sensing principle to monitor electrolyte concentration variations in biological samples (e.g., urine and blood) in a real scenario.

VI. CONCLUSIONS

In summary, novel differential microwave fluidic sensors for electrolyte concentration measurements in diluted aqueous solutions, based on pairs of uncoupled lines loaded with split ring resonators (SRRs), have been reported. The working principle of the sensor is the variation of the cross-mode insertion loss generated by an asymmetric dielectric load of the SRRs. Thus, by loading the fluidic channel of one of the SRRs with the reference liquid (the solvent), and the other fluidic channel with the liquid under test (the solution), it follows that solute concentration determines the cross-mode insertion loss level, which is used as output variable. Sensor validation has been carried out by considering three types of electrolytes: NaCl, KCl and CaCl2. Repetitiveness of the results has been demonstrated, and it has been found that the dependence of the cross-mode insertion loss with electrolyte content does not experience significant variations when the different electrolytes are considered. The combination of sensitivity and resolution of the reported sensor for NaCl concentration measurements in DI water, as compared to those of other sensors (also focused on NaCl measurements), has been found to be very competitive. With these high sensitivities and small resolutions, these differential sensors are of general interest for measuring small solute concentrations in liquids, as well as to detect changes in the properties of liquids (related to variations in the complex dielectric constant), as compared to a reference. In the last part of the paper, the sensor has been applied to the characterization of urine samples with different levels of ion concentrations, and the potential of the approach for real-time monitoring of total ion concentration in biological samples in a real scenario, has been pointed out.

Fig. 1 .

 1 Fig. 1. Topology of the microwave structure of the proposed sensor (a) and zoom of resonator (b). Dimensions are (in mm): LLT = 76.5, WLT = 2.79, l = 24, c = 1, w = 8.17, g = 0.2. The ground plane is depicted in grey.

Fig. 2 .

 2 Fig. 2. Lateral (a) and top (b) views of mechanical and fluidic parts of the microwave sensor and relevant dimensions. Channel dimensions are: hch = 1.5 mm, lch = 26 mm, wch = 4.6 mm; other relevant dimensions are: lf = 46 mm, wf = 12.6 mm, h1 = 3 mm, and h2 = 9 mm.

Fig. 3 .

 3 Fig. 3. Photograph of the proposed sensor including the microwave structure, the fluidic channels (plus mechanical accessories) and connectors.

Fig. 4 .Fig. 5 .

 45 Fig. 4. Cross-mode insertion loss for different values of NaCl concentration.

1 Fig. 6 .

 16 Fig. 6. Cross-mode insertion loss for different values of KCl concentration.

Fig. 7 .

 7 Fig. 7. Variation of |S21 DC |max with [KCl].

Fig. 8 .Fig. 9 .

 89 Fig. 8. Cross-mode insertion loss for different values of CaCl2 concentration.

  0

Fig. 10 .Fig. 11 .

 1011 Fig. 10. Cross-mode insertion loss for different values of total ion concentration in urine samples.

  samples. Symmetry disruption is the physical

	Split Ring Resonator (SRR) based Microwave
	Fluidic Sensors for Electrolyte Concentration
	Measurements

Paris Vélez, Member, IEEE, Jonatan Muñoz-Enano, Katia Grenier, Member, IEEE, Javier Mata-Contreras, David Dubuc, Member, IEEE, and Ferran Martín, Fellow, IEEE

ACKNOWLEDGMENTS

The authors are grateful to Anna M. Bassols, from the Biochemistry and Molecular Biology Department of Universitat Autònoma de Barcelona, for providing us the urine samples.

This work was supported by MINECO-Spain (project TEC2016-75650-R), Generalitat de Catalunya (projects 2017SGR-1159 and TECSPR15-1-0050), Institució Catalana de Recerca i Estudis Avançats (who awarded Ferran Martín), and by FEDER funds.


Guillaume Pallez
email: guillaume.pallez@inria.fr

Olivier Beaumont

Julien Herrmann

Alena Shilova

Optimal Memory-aware Backpropagation of Deep Join Networks

Keywords: Artificial intelligence [COMPUTER SCIENCE], Theory of computing [COMPUTER backpropagation, memory, pebble game

Deep Learning training memory needs can prevent the user from considering large models and large batch sizes. In this work, we propose to use techniques from memory-aware scheduling and Automatic Differentiation (AD) to execute a backpropagation graph with a bounded memory requirement at the cost of extra recomputations. The case of a single homogeneous chain, i.e. the case of a network whose all stages are identical and form a chain, is well understood and optimal solutions have been proposed in the AD literature. The networks encountered in practice in the context of Deep Learning are much more diverse, both in terms of shape and heterogeneity.

In this work, we define the class of backpropagation graphs, and extend those on which one can compute in polynomial time a solution that minimizes the total number of recomputations. In particular we consider join graphs which correspond to models such as Siamese or Cross Modal Networks.

Introduction

Training for Deep Learning Networks (DNN) induces a memory problem. Amongst the different strategies to parallelize and accelerate this training phase come hyperparameter tuning and data-parallelism [GB10], that both need to replicate the set of weights of the neural network onto all participating resources, thus limiting the size of the model or depth of the graph.

In order to deal with memory issues, several solutions have been advocated. One of them is model parallelism [DCM + 12]. It consists of splitting the network model into several non-overlapping parts, that are distributed over the different resources.

The Deep Neural Network (DNN) model can in general be seen as a Directed Acyclic Graph and the different vertices of the DAG are split across the resources. Each time there is an edge between two vertices allocated onto two different resources, this will induce the communication of the associated forward and backward activations during the training phase. As it is in general the case for the training of DNNs, we will assume that the weights are updated after the forward and backward propagation of small groups of training samples that will be called minibatches, as opposed to full batch learning (where all samples are used before updating the weights) and stochastic gradient descent (where updates are performed after each sample). Model parallelism can be considered as a solution to this problem since model weights are distributed among participating nodes. In this context, the problem becomes a general graph partitioning problem [DCM + 12] where the goal is to balance the weights between the different nodes while minimizing the weights of cut edges (i.e. edges whose two extremities are on different resources). This approach has the advantage that it can be combined with data parallelism [DAM + 16].

Another complementary approach is the problem of scheduling a graph with a shared bounded memory and to use recomputation of functions. This problem is known in the scheduling literature as the Register Allocation problem or Pebble Game [Set75]. In the Register Allocation problem, in order to execute a task, all its inputs need to be stored in registers. The question is then to decide whether it is possible to process the graph with a bounded number of unit-size registers (or memory slots). Sethi [Set75] showed that this problem is NP-complete for general task graphs. Further study showed that the problem is solvable in polynomial graph for tree-shaped graphs [Liu87], or recently Serie-Parallel graphs [KLMU18].

In this work, we are interested in what we denote by backpropagation graphs: given a Directed Acyclic Graph (DAG) with a single exit vertex, we construct a dual identical graph where all edges are reversed, and where the input of each vertex of the initial graph is connected to its dual vertex. The source vertex of the dual graph and the sink vertex of the original graph are then merged into a single vertex called turn (see Figure 1 for the case of a chain of vertices).

• • •

Turn

• • • x 0 x 1 x 2 x l-2 x l-1 xl xl-1 x3 x2 x1 x0 x 0 x 1 x 2 x l-1
x l

Figure 1: Data dependencies of the backpropagation graph corresponding to the transformation of a linear chain. Functions are modeled by grey vertices, arrows represent data dependencies (input/output of functions) where the data are either x i and xi . The chain is the graph on top, its dual graph is on the bottom.

These types of graphs have been widely studied in the context of Automatic Differentiation (AD) [Gri89]. For a given batch size and a given network model and even on a single node without relying on model parallelism strategies, it saves memory at the price of activation re-computations. In the context of AD, networks can be seen as (long) homogeneous (i.e., all stages are identical) chains and the forward activation corresponding to the i-th stage of the chain has to be kept into memory until the associated backward stage. Checkpointing techniques determine in advance which forward activations (checkpoints) should be kept into memory and which one should be recomputed from stored checkpoints when performing the backward phase. Many studies have been performed to determine optimal checkpointing strategies for AD in different contexts, depending on the presence of a single or multi level memory [AHHR16,AH19]. In the case of homogeneous chains, closed form formulas providing the exact positions of checkpoints have even been proposed [GW00] (algorithm REV in the rest of this paper), although the general algorithmic ingredient is to derive optimal checkpointing strategies through Dynamic Programming [GW00]. This technique has been recently advocated for DNN in several papers [GMD + 16,CXZG16]. In the context of homogeneous chains, a periodic checkpointing strategy has recently been implemented in PyTorch [PGC + 17,per18]. Nevertheless, DNN models are not restricted to homogeneous chains and there is a need for checkpointing algorithms in more general contexts. While optimal scheduling and checkpointing are still open problems in the general case, there are some solutions which in some way benefit from the findings in AD checkpointing strategies [CXZG16,GMD + 16]. However, they are designed to deal with sequential models only, thus making it inappropriate for more sophisticated cases.

In this paper, we propose a first attempt to find optimal checkpointing strategies adapted to more general networks and to show how dynamic programming techniques developed in the context of AD can be adapted to DNN networks. More specifically, we concentrate on the particular context of DNNs consisting of several independent chains whose results are gathered through the computation of the loss function (Join graph). We show that this specific case can be solved using dynamic programming, but at the price of more sophisticated techniques and higher computational costs. Note that several popular classes of problems can be modeled as a join graph amongst which are Cross-Modal embeddings or Siamese networks.

Cross-Modal embeddings [MBO + 18,MAB + 19] are models used when there are multiple sources of data and the goal is to find the connection between those sources. For example, in the image-recipe retrieval task [MBO + 18], having both a dataset of dish images and a dataset of recipes represented as a text corpus, the goal is to find a matching image for each recipe. Thus, a Convolution Neural Network (CNN) is applied to process images and extract features while a Long Short-Term Memory (LSTM) network is used for the text part. Then, all feature vectors yielded by both networks are further processed with the help of a small number of fully connected layers before being concatenated to compute an associated loss. In practice, training such a model often consists of training individually each sub-model for each data source and then using them only as feature extractors to train the fully connected layers on top of it. Indeed, training the whole model is not performed due to larger runtime for training and much larger memory requirements. In the latter case, the approach proposed in the current paper can be used as checkpointing strategy and can significantly decrease memory consumption.

Siamese Neural Network [BGL + 94,DFS17,MMBS14] can also directly benefit from our approach. They are widely used for objects recognition. The main idea behind these models is to use the same CNN, but for different images, and then finally use all the outputs to estimate a loss that represents a similarity metric. Depending on the choice of the loss function, it can either correspond to a two-chains computational graph [BGL + 94,MMBS14] where the loss is computed based on two images, or to a three-chains computational graph, where triplet loss is applied [HA15]. Due to memory constraints, most of the CNNs used in these models are not very deep [DFS17]. However, it is known that deeper neural networks could offer a better quality. Therefore, using checkpointing techniques to decrease memory needs may be used to consider larger and deeper models in the context of Siamese networks.

The rest of the paper is organized as follows. In Section 2, we present the problem and the general framework in which we can derive our scheduling algorithm. Then, a characterization of optimal solutions is proposed in Section 3(a) and is later used to find the optimal checkpointing strategy through dynamic programming in Section 3(b). Finally, we present our implementation and simulation results in Section 4, before providing concluding remarks and perspectives in Section 5.

Model

In this work, we consider the Register Allocation Problem [Set75] (aka Pebble Game) for special types of graphs, denoted as backpropagation graphs. These graphs are obtained by transforming a Directed Acyclic Graph (DAG) as explained in Definition 1.

(a) Platform model and optimization problem

In this work, we consider a sequential platform (at all time, all the compute elements are dedicated to the same job) with a finite memory M of size c. Activations must be checkpointed into M until they are used in the backpropagation or they must be discarded from M and then recomputed from a previous checkpointed value. We do not consider the possibility of offloading activations to another (larger) memory level as in [RGC + 16].

A job is represented as a Directed Acyclic Graph (DAG) G = (V, E), where each vertex of v ∈ V represents a compute operation (with a given execution time), and each edge of (v 1 , v 2 ) ∈ E represents a data dependency where an output of v 1 is an input of v 2 . Given a graph G, the problems under consideration are (i) can we execute it with a memory of size c (pebble game problem) and (ii) if we can, what is the minimal execution time to execute G (makespan problem) with a memory of size c.

In order to process a job on this platform, all its inputs need to be stored in memory at the beginning of the execution. In what follows, we assume that the memory is larger than the minimal amount of memory to perform the training phase, which is formally defined in Theorem 2. It should be noted that the Theorem 2 formula takes into account the possibility of computing some activations several times and therefore does not assume that there is enough memory to run the graph in one go. Then, the core of the makespan problem, is to choose which activations to store and which activations should be recomputed.

(b) Backpropagation graphs

In this work we consider specifically the problem of scheduling backpropagation graphs.

Definition 1 (Backpropagation transformation (BP-transform)). Given a DAG G with a single sink vertex. The BP-transform of G is defined by the following procedure:

(i) Build the dual graph G defined as the same graph where all edges are inversed. (ii) For a given vertex in G, connect its input edges to its dual vertex in G. (iii) Finally, merge the sink vertex of G and the source vertex of G as a single vertex, denoted as the turn.

Note that the vertices of the initial graph are denoted as forward steps, while the vertices of the dual graph are denoted as backward steps. In the rest of this work, we make the assumption that all forward steps have the same execution cost u f ∈ R + , while all the backward steps have the same execution cost u b ∈ R +1 . The cost of the Turn operation is denoted as u t ∈ R + . In addition, we assume that all input/output data have the same (unit) size. We give without proof two properties of the backpropagation graph which justify this study:

Property 1 (Properties of the BP-graph). Given a DAG G with n verticess and a single sink vertex: P1: The backpropagation graph of G is a DAG; P2: Without recomputation of vertices, the minimal memory usage to go through this graph is O(n).

Indeed, to scale these types of computations, we are interested in the question of the overhead in computation when one uses much less memory space.

The most simple and most studied backpropagation graph is the transformation of a chain graph (as shown in Figure 1) in Automatic Differentiation. In this case, it is known that for a given volume of memory, one can compute the optimal solution in polynomial time [GW00]. In this work, we consider transformation of join graphs (Figure 2). Join graphs are used by several deep- Definition 2 (BP-transform of join graphs). Given a join graph G k with k branches of respective length j , its BP-transform can be described by the following set of equations:

F (1) 0 F (1) 1 F (1) 2 F (1) 3 F (1) 4 F (2) 0 F (2) 1 F (2) 2 F (2) 3 Turn F (3) 0 F (3) 1 F (3) 2 F (3) 3 F (3) 4 F (3) 5
F (j) i (x (j) i ) = x (j) i+1 for 1 ≤ j ≤ k and 0 ≤ i < j , F (j) i (x (j) i , x(j) i+1 ) = x(j) i for 1 ≤ j ≤ k and 0 ≤ i < j , Turn(x (1) 1 , . . . , x (k)
k ) = (x (1) 1 , . . . , x(k) k ).
The dependencies between these operations are represented by the graph G = (V, E) depicted in Figure 3, in the case of k = 2 chains.

F

(1) 0

F

(1) 1

• • • F

(1)

1-1 F (1) 0 F (1) 1 • • • F (1) 1-1 F (2) 0 • • • F (2) 2-1 F (2) 0 • • • F (2) 2-1

Turn

x

(1) 0

x

(1) 1

x

(1) 2

x

(1)

1-1 x (1) 1 x(1) 1 x(1) 1-1 x(1) 2 x(1) 1 x(1) 0 x
(1) 0

x

(1) 1

x

(1) 2

x

(1)

1-1 x (2) 0 x (2) 1 x (2) 2-1 x (2) 2 x(2) 2 x(2) 2-1 x(2) 1 x(2) 0 x (2) 0 x (2) 1 x (2) 2-1
Figure 3: Data dependencies in the multiple adjoint chains problem with two chains. In the following we call forward (resp. backward) data the output of F (resp. F ) functions.

In the rest of this work, we only use the graph of forward steps to represent the BP-transform. Finally, we are interested in solving the following problem:

Problem 1 (PROB join ( , c)). Given the BP-transform of a join DAG with k branches of respective lengths ∈ N k . The respective costs for forward, backward and turn operations are given by u f , u b and u t . Given c ∈ N memory slots, minimize the makespan, where the initial memory state is

given by M = {x Green blocks correspond to the storage of "forward" data, blue blocks to storage of "backward" data. To process the backward phase, the red-circled value stored during the forward phase is used to recompute subsequent values.

Deriving an optimal solution

In this section, we present the core idea to compute an optimal solution. In particular, we show that there are optimal solutions that satisfy properties on their behavior. We call these solutions canonical optimal solutions. Then we restrict the search for optimal solutions to the canonical solutions. For simplicity, we leave out all the proofs of this section and focus on giving intuitions. The interested reader can find the proofs in the companion report [BHPS19] for the more general case where not all final outputs need to be kept into memory. The context considered in this paper corresponds to the case where all b i values are equal to 1 in [BHPS19], where b i indicates if the results of chain i needs to be kept in memory.

For terminology sake, let us first notice that an algorithm for PROB join ( , c) can be decomposed into three different phases (see Figure 4):

• The Forward phase: we traverse all branches to write all inputs of the turn in memory.

During this phase one cannot compute any backward operations, but some of the input data can be stored. • The Turn: at the beginning of this phase, all input data of the turn are stored in memory, and are replaced by all output data at the end in the same memory locations. Indeed, the input data of the turn will never be used anymore.

• The Backward phase: we read some input data that were stored earlier to backpropagate a subset of the graph.

(a) Canonical form and optimal solutions

We say that a solution is in a canonical form if it obeys the following recursive structure:

(i) Given c memory slots, from an input x written on memory, j forward steps are performed on the branch m of x; (ii) The output after those steps is stored into memory; (iii) A canonical solution for the smaller problem where all branches' size are unchanged except for branch m which is now smaller by j forward steps (recurrence formula) with c -1 memory slots. (iv) From the input x in memory, the j steps following x are backpropagated2 using all available memory slots.

We show in Figure 5 what a canonical solution looks like on a small example. In this section, we show that there exists an optimal solution in this canonical form. In order to prove this result, we show that the backward phase is computed following three properties (represented graphically in Figure 6):

Property 2 (Canonical properties). Given a join graph G k with k branches:

Index of the operation

l l 1 l 2 l 3 time 9u f 2u f u f x (3) 9 x (3) 11 x (3) 12 7u f 3u f x (2) 7
x

(2) 10

4u f x (1) 4 u t u b REV(1, 3) Opt 0 (1, 3) x(3) 9 REV(8, 7)
Opt 0 (8, 7)

REV(2, 4)

Opt 0 (2, 4)

x(2) Green blocks correspond to "forward" data being stored, blue blocks to "backward" data stored. The forbidden operations given by the properties are crossed out in red. For Stability 2, if during the backward phase, we have read the circled checkpoint, then the canonical solution starts by backpropagating (represented by the back arrow) all greyed-out operations until the "backward" data of the circled-out operation is stored.

• Stability 1: If we have backpropagated an operation of G k , then we do not access anymore any of its descendent in G k . • Checkpoint Persistence If the output of an operation of G k is stored, then until it is backpropagated, we do not access any of its parent in G k . • Stability 2 If the output of an operation of G k is read, then until it is backpropagated, we do not access any part of other branches of the BP-transform of G k .

Then there exists an optimal solution for PROB join ( , c) that satisfies these properties.

With these properties we can state the following result:

Theorem 1. There exists an optimal solution that follows the canonical form.

Outline of the proof. Finding an optimal solution reduces to finding what data should be rewritten during the forward phase, and in which order it should be read during the backward phase. Indeed, once this element is read, the backward phase consists of backpropagating the segment of the branch until the location of the backward data already computed (which recursively corresponds to the backpropagation of another element written during the forward phase). In addition, during the backward phase, the backpropagation of each subset of the graph reduces to the problem of a chain whose solution REV is known [GW00]. Finally, it remains to be shown that the forward phase satisfies the canonical property. This is simple: one can notice that at no cost, one can choose any order for going through the different forward segments3 (except the last one) of the branches. Thereby in particular we can use the reverse order in which they are backpropagated during the backward phase.

(b) Optimal solution

Using the properties derived in the previous section on canonical solutions, we can see that the problem can be solved with a dynamic programming algorithm. Indeed, given a join graph of length ∈ N k , the problem can be seen as:

(i) Performing j forward steps on one of the branches (ii) Writing the output forward activation after those j steps to memory (iii) Solving the problem for the smaller problem where all branches have unchanged size except for the branch on which the output has been kept, and which is now smaller by j steps (recurrence formula) and with one fewer memory checkpoint. (iv) Backpropagating the j forward steps done before.

We now explain how to derive this dynamic program. Let us first consider the solution to the pebble game problem:

Theorem 2 (Minimal memory requirement). The minimal memory c min needed to execute PROB join ( , c) is:

c min ( ) =        k if = 0, k + k i=1 I[ i = 0] if ∃j, j = 1, k + k i=1 I[ i = 0] + 1 otherwise. (3.1)
Outline of the proof. Intuitively, the case where = 0 corresponds to the situation where we simply need to perform the turn. For the general case, the peak is right after the turn: all initial input for the branch of non zero size need to be stored. In addition, all the outputs of the turn have to be stored as well. Finally, one additional slot is then needed to perform the back and forth between the input data and output data. The only exception to this is when one of the branches has length exactly 1. In that case right after the turn we can backpropagate the input of this branch, hence freeing the memory slot used for this input in order to do the back and forth.

We are now able to establish the following theorem, that proves that general instances of PROB join ( , c) can be solved using dynamic programming. We denote by Opt 0 (l, c) the execution time of the algorithm REV(l, c) [GW00] (optimal solution when k = 1).

Theorem 3. Given a join DAG G k with k branches of lengths and given c memory slots, the execution time Opt join ( , c) of an optimal solution to PROB join ( , c) is given by

Opt join ( , c) = ∞ if c < c min ( ), Opt join 0, c = u t if c ≥ k, Opt join ( , c) = u f + u t + u b if ∃j s.t. j = 1, ∀i = j, i = 0 and c ≥ k + 1,
For other cases:

Opt join ( , c) = min 1≤m≤k 0<i≤ m i • u f + Opt join [ m← m-i] , c -1 + Opt 0 (i -1, c -(k -1))
The complexity to compute Opt join

( , c) is O c • k • max k i=1 i k+1 .
Note that in practice k is small (2 or 3).

Sketch of proof.

The dynamic program describes exactly the best makespan of any algorithm with canonical form for all values of and c.

The initialization is the time to perform the turn. Indeed, as we have seen in Theorem 2, there is a subtlety in the manipulation of the checkpoints to perform the turn depending whether there is a chain of length one or not, which would allow to use fewer checkpoints. Finally, when there are not enough memory slots to execute the graph, we set the value to ∞ allowing to discard the cases that use more memory than what is available.

Note that while this provides an execution time, it is fairly easy to derive an algorithm based on this using standard Dynamic Programming techniques.

Evaluation

In this section, we depict the results of simulations on linearized homogeneous versions of Cross-Modal embeddings (CM) and Siamese Networks (SN) with triplet loss. Linearized homogeneous versions of the neural networks are the ones where all computational costs (u f = u b = u t = 1) and storage costs are homogeneous. In this context, a multi chain network is completely defined by the lengths of the different branches and the size of the memory expressed in terms of memory slots.

We propose three observations:

(i) The trade-off Makespan vs Memory usage;

(ii) For a fixed number of storage slots, an observation on the growth of the number of recomputations needed as a function of the number of forward operations; (iii) A comparison between the optimal solution and an algorithm that does not take into account the join structure but that considers the graphs as an equivalent length linear chain.

In order to compare the different types of networks in a normalized way, we consider several models with analogous sizes and computational costs. For a given value of L, we consider three graph structures:

• Siamese Neural Networks (SNN) with 3 chains of lengths (2L, 2L, 2L). Here also, L can be large as these neural networks are usually applied to images, thus deep neural networks are also possible as they are better in pattern retrieval. As soon as c ≥ C SN N (L) = 6L + 3, all forward activations can be stored and therefore makespan is minimal and is equal to Span * SN N (L) = 12L + 1. • Cross-Modal (CM) embedding networks with two chains of sizes (L, 5L). The motivation is CM with two different types of data sources (images and texts), one of the chains is much longer than the other because more layers are needed to extract useful patterns (e.g. images are usually processed with deep neural networks like ResNet while text can be efficiently encoded into vectors of smaller dimensions with the help of some shallow neural networks instead). Analogously to the case of SNN, as soon as the memory c is larger than C CM (L) = 6L + 2, then the makespan is minimal and is equal to Span * CM (L) = 12L + 1. • Finally, we also consider the case of a single chain of length 6L. This corresponds to the case of Recurrent Neural Networks (RNN). Analogously to the case of CMs of SNNs, as soon as c ≥ C RN N (L) = 6L + 1, all forward activations can be stored and therefore the makespan is minimal and is equal to Span * RN N (L) = 12L + 1. This case also serves as a lower bound on the makespan that can be reached by the previous models.

In the following, we denote by Span * (L) = 12L + 1 the minimal makespan for all models.

Trade-off Memory -Makespan

The first question that we consider is, given a fixed number of forward operations (described by L for all scenarios), how does the makespan evolve as a function of the number of memory slots available.

We run our experiments for L = 5 and 15. The plots depicting the evolution of makespan with the amount of memory are gathered in Figure 7. Specifically, the x-axis represents the fraction of memory slots available with respect to the minimal number C Opt (which differs slightly depending on the model) to achieve minimal makespan, Span * (L) . The y-axis represents the ratio between the achieved makespan and Span * (L). Thus, point (x, y) on the CM plot means that for a CM network of length (5L, L), with x • C CM memory slots, the makespan is y • Span * (L).

The plots related to CM (resp. SNN) start from memory size 5 (resp. 7), which is exactly the value of c min for two (resp. three) chains, as proved in Theorem 2. We can notice that the makespan first significantly decreases with the first additional memory slots. In addition, it seems that once it reaches a threshold k • Span * with k 1.5, the makespan ratio linearly decreases to Span * with the number of additional memory slots.

Hence, this shows that this checkpointing strategy is very efficient in decreasing the memory needs while only slightly increasing the makespan. For instance, consider the point where c/C Opt = 0.5. This corresponds to halving the memory needs with respect to what is needed to achieve minimal makespan. In all cases, halving memory needs only induces an increase of approximatively 25% on the makespan. In addition, we can also observe that even with a very small memory (say c min + 2), the makespan is less than doubled compared to Span * .

Makespan evolution for fixed memory

In Figure 8, we depict the dual situation, where the number of memory slots is fixed on each plot (either 9 or 13) and the ratio of the achieved makespan over Span * (L) is depicted. Several observations can be made. The first one is that the gap to the lower-bound (RNN) is rather small and decreases with the number of available checkpoints. Obviously this gap increases slowly with the size of the model. Note that we have observed an exception when the number of available checkpoints is exactly the minimum number of memory checkpoints (for instance c = 7, performance of SNN). This exception is not surprising given the observations of the previous paragraph and the important improvements in performance when the number of available checkpoint is slightly larger than c min . In addition, it is interesting to observe that for SNNs and CNNs, the ratio follows a pattern similar to that of RNNs: different thresholds, and between those thresholds, a performance shaped as α -β/L. Indeed, for the case of RNN those performance have been proven via a closed-form formula [GW00]. This can motivate the search for a similar closed-form formula for the problem of chains, which could lead to an algorithm of polynomial complexity in the number of branches. Finally, another observation is that the overall growth in makespan for a fixed number of checkpoints is quite slow even with few checkpoints, hence encouraging the use of these strategies.

Comparison to linearization strategy

The previous evaluation aims at evaluating the gain that can be expected by trading space for time. In this final evaluation, we rather aim at showing the importance of taking the structure of the graph into consideration. In particular we compare the strategy presented in this work to a two-step strategy that consists in (i) transforming the join in a linear chain; (ii) using an existing strategy for linear chains.

To transform the join as a linear chain, we group together operations that are at the same distance of the turn (see Figure 9). In this case, one can execute any algorithm for linear chains while considering that each forward step has cost k.u f , each backward step k.u b and that the memory needed for a checkpoint is k times the memory needed for a single input/output. For comparison, we consider the best possible algorithm for this structure, REV [GW00]. We call this heuristic: EQUIV-CHAIN.

In order to consider the best possible scenario for EQUIV-CHAIN: (i) we only consider balanced graphs (SNN graphs); (ii) we consider only slot number proportional to the number of branches. We plot in Figure 9 the ratio Makespan of EQUIV-CHAIN over Opt, the performance of our algorithm for different numbers of checkpoints (9, 12 or 15). Because we consider only one type of model, for this plot we use the actual length of the graph as x-axis (length = 2L + 1).

The results in this optimistic scenario show that EQUIV-CHAIN is surprisingly robust for small graphs. More expected, its performance steadily decreases when the ratio length/number of checkpoints increases. This is not surprising because our algorithm has more freedom in its choice of execution order. This shows the importance of taking into account the structure of the backpropagation graph when studying checkpointing strategies.

Conclusion and Perspectives

Being able to perform learning in deep neural networks is a crucial operation, which requires important memory needs in the feed-forward model, because of the storage of activations. These memory needs often limit the size and therefore the accuracy of used models. The automatic differentiation community has implemented checkpointing strategies, which make it possible to significantly reduce memory requirements at the cost of a moderate increase in the computing time, and backpropagation schemes are very similar in the cases of automatic differentiation and deep learning. On the other hand, the diversity of task graphs (ResNet, Inception and their combinations) is much more important in the context of DNNs. It is therefore crucial to design checkpointing strategies for backpropagation on a much broader class of graphs than the homogeneous chains on which the literature on automatic differentiation has focused.

The goal of this paper is precisely to extend the graph class, by considering multiple independent chains that meet when calculating the loss function. This class of graphs allows, from an application point of view, to also consider neural networks such as Cross Modal Networks (CMNs) and Siamese Neural Networks (SMNs). In the case of multi-chain, we were able to build a dynamic program that allows us to compute the optimal strategy given the size of the available memory, i.e. a strategy that fulfills memory constraints while minimizing the number of recalculations.

This work opens several natural perspectives. The first one obviously concerns the extension to other broader classes of backpropagation graphs, in order to take into account larger classes of DNNs. After working on multiple chains, which has proven to be a much more difficult problem than the single chain problem, we consider that it is probably essential to choose the characteristics of the graph class in question carefully in order to produce algorithms of reasonable complexity with a practical impact in deep learning. Another approach is the design of approximation algorithms for this problem, which would have a low execution time and for which good performance can nevertheless be guaranteed. From the studies we have done, it does seem that there is a fairly high density of optimal and quasi-optimal solutions, so it is possible that there are simpler algorithms to find them.

  rsta.royalsocietypublishing.org Phil. Trans. R. Soc. A 0000000 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Figure 2 :

 2 Figure 2: A join graph with 3 branches of respective length 5, 4 and 6.

  Figure4: The three main phases of the algorithm. Green blocks correspond to the storage of "forward" data, blue blocks to storage of "backward" data. To process the backward phase, the red-circled value stored during the forward phase is used to recompute subsequent values.

  rsta.royalsocietypublishing.org Phil. Trans. R. Soc. A 0000000 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Figure 6 :

 6 Figure 5: A canonical solution on the join with three branches of respective lengths 4 (blue), 10 (green) and 12 (red), with 9 memory slots. The execution time is represented on the vertical axis, the progress on each of the branches is represented on the horizontal axis. As an example, the dark dashed line at the top of the figure represent the computation of F (3) 2 . Full (resp. dashed) vertical lines are memory checkpoints of forward data (resp. backward data). REV(l, c) is the solution [GW00] to the easier problem where there is only one branch of size l and c checkpoints (see Fig 1), Opt 0 (l, c) is its execution time.

  rsta.royalsocietypublishing.org Phil. Trans. R. Soc. A 0000000 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Figure 7 :Figure 8 :

 78 Figure 7: Makespan evolution with respect to different amount of total memory.

  rsta.royalsocietypublishing.org Phil. Trans. R. Soc. A 0000000 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . (a) Transformation of a join with three branches into a chain with four levels

Figure 9 :

 9 Figure 9: Graph transformation (left) and performance (right).

For clarity this work is focused on the uniform case. It is possible to extend at a small cost the results to non-uniform time steps as was done for the case of single chains by Walther [Wal99, Section 3.4].

We use this term to say that we have computed the dual of a vertex of the initial graph

Defined as the forward steps between two consecutive written elements

Authors' Contributions. All authors participated to the model, derivations of theoretical results and writing of the manuscript. JH implemented the main algorithm, AS and GP performed the evaluations. All authors read and approved the manuscript.

Competing Interests. The authors declare that they have no competing interests.

Funding. This work was supported in part by the French National Research Agency (ANR) in the frame of DASH (ANR-17-CE25-0004) and in part by the Project Région Nouvelle Aquitaine 2018-1R50119 "HPC scalable ecosystem".