Jean-Rémy Gloaguen
email: jean-remy.gloaguen@ifsttar.fr

Arnaud Can

Mathieu Lagrange

Jean-François Petiot

Road traffic sound level estimation from realistic urban sound mixtures by Non-negative Matrix Factorization

Keywords: Non-negative Matrix Factorization, urban sound environment, road traffic sound level estimation trates

Experimental acoustic sensor networks are currently tested in large cities, and appear more and more as a useful tool to enrich modeled road traffic noise maps through data assimilation techniques. One challenge is to be able to isolate from the measured sound mixtures acoustic quantities of interest such as the sound level of road traffic. This task is anything but trivial because of the multiple sound sources that overlap within urban sound mixtures.

In this paper, the Non-negative Matrix Factorization (NMF) framework is developed to estimate road traffic noise levels within urban sound scenes. To evaluate the performances of the proposed approach, a synthetic corpus of sound scenes is designed, to cover most common soundscape settings, and whom realism is validated through a perceptual test.

The simulated scenes reproduce then the sensor network outputs, in which the actual occurrence and sound level of each source are known.

Several variants of NMF are tested. The proposed approach, named threshold initialized NMF, appears to be the most reliable approach, allowing road traffic noise level estimation with average errors of less than 1.3 dB over the tested corpus of sound scenes.

Introduction

In response to the growing demand from urban dwellers for a better environment, noise mapping has been recommended as a tool to tackle noise pollution. The enactment of the European Directive 2002/EC/49 makes such maps mandatory to cities over 100 000 inhabitants. Those maps play an important informative role, establishing the distribution of the sound levels all over the cities as well as the estimation of the number of city dwellers exposed to high sound level (> 55 dB(A)) [START_REF] Nugent | Noise in europe 2014[END_REF]. Road traffic concen- Noise measurements are thus increasingly used in ad-30 dition to simulation to describe urban noise environments [START_REF] Gozalo | Study on the relation between urban planning and noise level[END_REF][START_REF] Zannin | Characterization of environmental noise based on noise measurements, noise mapping and interviews: A case study at a university 720 campus in brazil[END_REF][START_REF] Can | Exploring the use of mobile sensors for noise and black carbon measurements in an urban environment[END_REF]. Several measurement set-ups have been proposed in the last years, including mobile measurements with high quality microphones [START_REF] Manvell | Sadmam-combining measurements and calculations to map noise in madrid[END_REF][START_REF] Can | Measurement network for urban noise assessment: Comparison of mobile measurements and spatial interpolation approaches[END_REF], participative sensing through dedicated smartphone applications [START_REF] Picaut | Noise mapping based on 735 participative measurements with a smartphone[END_REF][START_REF] Ventura | Evaluation and cali-740 bration of mobile phones for noise monitoring application[END_REF], or the development of fixed-sensor networks. In this latter case, the sensor networks can be based either on high-quality sensors as in [START_REF] Mietlicki | An innovative approach for long-term environmental noise measurement: Rumeur network[END_REF][START_REF] Maijala | Environmental noise monitoring using source classification in sensors[END_REF], or low-cost sensors as in the DYNAMAP project [START_REF] Sevillano | DYNAMAPdevelopment of low cost sensors networks for real time noise mapping[END_REF] or the CENSE project [START_REF] Picaut | Characterization of urban 755 sound environments using a comprehensive approach combining open data, measurements, and modeling[END_REF]. The costs and benefits of each protocol are discussed. Mobile and par-40 ticipatory measures increase spatial coverage at low cost, but lack temporal representativeness. Fixed networks are very reliable for measuring sound levels temporal variations, but allow only a small spatial coverage of the network. In addition, the low-cost sensors enable a wider deployment, but at the cost of increased uncertainties, the most extreme example being smartphone applications.

All these measurement protocols allow the combination of measures and predictions to improve the accuracy of the produced noise maps. Traffic noise maps and mea-50 surements were compared on restrictive areas in [START_REF] Lefebvre | Traffic flow estimation using acoustic signal[END_REF] and [START_REF] Mioduszewski | Noise map validation by continuous noise monitoring[END_REF]. Wei et al. [START_REF] Wei | Dy-765 namic noise mapping: A map-based interpolation between noise measurements with high temporal resolution[END_REF] modify the acoustical parameters of the simulation thanks to noise measurements, while Mallet et al. [START_REF] Ventura | Estimation of urban bys[END_REF] call for data assimilation techniques between models and measurements to reduce the uncertainty of 55 the produced noise maps. However, these works make the implicit assumption that the noise measurements consist mainly of road traffic. In the aim to improve road traffic noise maps, the use of measurements has first to deal with the challenge to estimate correctly the road traffic sound the detection [START_REF] Luitel | Sound event detection in urban soundscape using two-level classification[END_REF][START_REF] Mesaros | Sound event 785 detection in real life recordings using coupled matrix factorization of spectral representations and class activity annotations[END_REF] or the recognition [START_REF] Defreville | Automatic Recog-790 nition of Urban Sound Sources[END_REF][START_REF] Parascandolo | Recurrent neural networks for polyphonic sound event detection in real life 795 recordings[END_REF] of urban sound events. In these cases, a two-step scheme is followed where audio samples are described with a set of features 70 (Mel Frequency Cepstral Coefficient, MPEG-7 descriptors . . . ) and classified with the help of a classifier (Gaussian Mixtures Models, Artificial Neural Network . . . ) [START_REF] Chu | Environmental sound recognition using mp-based features[END_REF][START_REF] Cowling | Comparison of techniques for environmental sound recognition[END_REF].

The classifier is learnt from a learning database and is next applied on a test database to validate the algorithms.

75

Dedicated to the traffic, in [START_REF] Socoró | An Anomalous Noise Events Detector for Dynamic Road Traffic Noise Mapping in Real-Life Urban and Suburban Environments[END_REF], an Anomalous Event Detection, based on MFCC features, is proposed with the specific aim to improve the traffic sound estimation. It is based on the detection of unwanted sound events in order to discard them.

80

An other approach, followed in this paper, is to consider the blind source separation paradigm which consists in the extraction of a specific signal inside a set of mixed signals, see Figure 1. From the different existing methods, Non-negative Matrix Factorization (NMF) [START_REF] Lee | Learning the parts of objects by non-810 negative matrix factorization[END_REF], appears 85 to be a relevant method for monophonic sensor networks.

Many applications can be found for musical [START_REF] Smaragdis | Non-negative matrix factorization for polyphonic music transcription[END_REF][START_REF] Benetos | Musical instrument clas-sification using non-negative matrix factorization algorithms and subset feature selection[END_REF] and speech [START_REF] Wilson | Speech denoising using nonnegative matrix factorization with priors[END_REF][START_REF] Mysore | A non-negative approach to semisupervised separation of speech from noise with the use of temporal dynamics[END_REF] contents. Dedicated to sound separation with environmental sounds, Immani and Kasaï [START_REF] Satoshi | NMF-based environmental sound source separation using time-variant gain features[END_REF] used NMF in a two steps sound separation with the help of time 90 variant gain features. Dedicated to the traffic sound separation, a first study [START_REF] Gloaguen | Estimation of road traffic sound levels in urban areas based on non-negative 835 matrix factorization techniques[END_REF] has been conducted, in which diverse NMF estimation rules are compared, namely the supervised, the semi-supervised, and the threshold initialized NMF, have been applied on a large set of simulated sound 95 scenes. This corpus mixes 6 sound categories (alert, animals, climate, humans, mechanics, transportation) with a traffic component calibrated to different sound levels, according to the other sound classes (in the rest of the document, these sound classes, not related to the traffic component, are resumed as the interfering sound class), to obtain variable traffic predominance. The diversity of this corpus was made to assess the performances and the limits of each NMF formula. However, if this study reveals the interest of NMF for urban sound environments, the assessment of its performance on a corpus of realistic sound scenes must be carried out in order to implement it on a sensor network. Design urban sound mixtures makes it possible to access to many acoustic properties as the onset and offset time and the sound level of each sound class and especially the traffic component. The realistic aspect of such a corpus is essential to obtain sound scenes similar to recordings and to validate NMF performances. However, like all simulated process, the realism of the scenes must be perceptually verified.

In this paper, an urban sound corpus based on annotated urban recordings, and whose degree of realism is assessed through a perceptual test, is designed in order to estimate the traffic sound level with the help of the NMF framework. The different NMF approaches are described in section 2. Next, the corpus of urban sound scenes is presented in section 3, from the sound database built-up to its validation. The experimental protocol and the results are then presented and discussed in section 4 and 5.

Non-negative Matrix Factorization

Non-negative Matrix Factorization (NMF) is a linear approximation method proposed by Paatero and Tapper [START_REF] Paatero | Positive matrix factorization: A nonnegative factor model with optimal utilization of error estimates of data values[END_REF] and popularized by Lee and Seung [START_REF] Lee | Learning the parts of objects by non-810 negative matrix factorization[END_REF]. It consists in V ≈ WH.

(

) 1
The choice of the dimensions is often made such as

F × K + K × N < F × N so that
D (V WH) , ( 2
)
where D(• •) is a divergence calculation such as:

D (V||WH) = F f =1 N n=1 d β V f n | [WH] f n . ( 3
)
d β (x|y) is usually chosen as a β-divergence [START_REF] Févotte | Algorithms for nonnegative matrix fac-840 torization with the β-divergence[END_REF], a sub-145 classes belonging to the Bregman divergences [START_REF] Hennequin | Beta-Divergence as a Subclass of Bregman Divergence[END_REF] which include 3 specific divergence calculations: the Euclidean distance (eq. 4a), the Kullback-Leibler divergence (eq. 4b)

and the Itakura-Saïto divergence (eq. 4c):

d β (x|y) =              1 2 (x -y) 2 , β = 2, (4a) x log x y -x + y, β = 1, (4b) x y -log x y -1 β = 0. ( 4c
)
The minimization problem (2) is solved iteratively by updating the form of matrices W and H. Different algorithms such as Alternating Least Square Method [START_REF] Cichocki | Regularized Alternating Least Squares Algorithms for Non-negative Matrix/Tensor Factorization[END_REF] or

Projected Gradient [START_REF] Lin | Projected Gradient Methods for Nonnegative Matrix Factorization[END_REF] have been considered. The most commonly used algorithm is the Multiplicative Update [START_REF] Lee | Algorithms for Non-negative Matrix Factorization[END_REF]. The latter method is chosen here, as it ensures non-155 negative results and the convergence of the results [START_REF] Févotte | Algorithms for nonnegative matrix fac-840 torization with the β-divergence[END_REF].

Supervised NMF

The most easiest case of NMF is the one where the sound sources can be known a priori and W can be built directly from audio samples. It leads to supervised NMF 160 (SUP-NMF). H is then the only matrix to estimate and is updated at every iteration (eq. 5) [START_REF] Févotte | Algorithms for nonnegative matrix fac-840 torization with the β-divergence[END_REF]:

H (i+1) ← H (i) ⊗     W T WH (i) (β-2) ⊗ V W T WH (i) (β-1)     γ(β) (5) with γ(β) = 1 2-β , for β < 1, γ(β) = 1, for β ∈ [1, 2] and γ(β) = 1 β-1 for β > 2.
Thus, the choice of the βdivergence in the equation 4 affects how the matrix H is Here, in an urban context, if the sound sources are known, their audio samples can be obtained to learn W, see section 4.2. As the position of each element is indexed, the traffic source separation from the other sound sources is made by extracting, from the dictionary and the activation matrix, the related elements:

Ṽtraffic = [WH] traf f ic . (6)

Semi-supervised NMF

The main issue with the supervised approach is the 175 representational limit imposed by a fixed W. To be completely successful, all the acoustical sources must be considered in the basis W which is not always possible in a complex urban environment. To overcome this issue, semisupervised NMF (SEM-NMF) [START_REF] Lee | Semi-Supervised Nonnegative Matrix 855 Factorization[END_REF]

V ≈ WH = W s H s + W r H r . (7)
H r and H s are updated separately, see eq. 8b to eq. .

Wr (i+1) ← Wr (i) ⊗   WrHr (i) (β-2) ⊗ V Hr T WrHr (i) (β-1) Hr T   γ(β)
,

Hr (i+1) ← Hr (i) ⊗   Wr T WrHr (i) (β-2) ⊗ V Wr T WrHr (i) (β-1)   γ(β)
,

Hs (i+1) ← Hs (i) ⊗   Ws T WsHs (i) (β-2) ⊗ V Ws T WsHs (i) (β-1)   γ(β) . ( 8a
) (8b) (8c)
In this study, W s is composed of traffic audio spectra, as it is the sound source of interest. Sources included in W r are other sound sources (corresponding to the interfer-195 ing class) that can be present in the urban sound scenes.

The traffic signal estimation is next defined by the fixed part,

Ṽtraffic = [W s H s ] . ( 9
)
The addition of W r gives more flexibility to the method to represent correctly the spectrogram V. The represen-200 tational capability is increased, thus the approach is more adaptive to the different urban sound environments. Applications of SEM-NMF can be found for musical [START_REF] Weninger | Supervised and semisupervised suppression of background music in monaural speech recordings[END_REF][START_REF] Kitamura | Music Signal Separation Based on Supervised Nonnegative Matrix Factorization with Orthogonality and Maximum-Divergence Penalties[END_REF] and speech contents [START_REF] Mysore | A non-negative approach to semisupervised separation of speech from noise with the use of temporal dynamics[END_REF][START_REF] Joder | Realtime speech separation by semi-supervised nonnegative matrix factorization[END_REF].

Thresholded Initialized NMF

205

To allow even more flexibility while still considering prior knowledge of the source of interest, we propose a third approach based on the unsupervised NMF framework: Threshold Initialized NMF (TI-NMF). Usually, in unsupervised NMF, the dictionary is initiated randomly when there is no prior knowledge on the sound sources present. Here, as the target sound source is known and the spectra are available, an initial dictionary, W 0 , is designed and then updated alternatively with H,

W (i+1) ← W (i) ⊗   W (i) H (β-2) ⊗ V H T W (i) H (β-1) H T   γ(β) . ( 10
)
With this operation, W 0 is oriented to the focused cosine similarity D θ (W 0 W ) is computed for each element k as it is scale-invariant and bounded,

D θ (w 0 w ) = w 0 .w w 0 . w . ( 11
)
where w is a k element of W of F × 1 dimensions.

When D θ (w 0 w )=1, the element w is identical to w 0 .

If D θ (w 0 w )=1, both elements are fully different. The 225 extraction of traffic elements in W is carried out by a hard thresholding method [START_REF] Donoho | Threshold selection for wavelet shrinkage of noisy data[END_REF]. It consists in weighting in a binary way W according to D θ (w 0 w ) and a threshold value α k such as:

w traf f ic = α k w . ( 12
)
with and is constrained to used it to obtain Ṽtraffic . SEM-NMF completes this dictionary by the add of a mobile dictionary to better consider the interfering sound events and then offer more flexibility. Finally, TI-NMF considers first a dictionary composed of traffic spectra, as SUP-

α k = 1 iff D θ (w 0 w ) > t h , (13a)

240

NMF, but allows an update of them. The interest of an initiated dictionary is then to focus on the source of interest during the updates. This method therefore makes it more suitable for solving the generalization issues as it is the entire dictionary that can be fully adapted to the 245 sound scenes. The elements that deviates too much from the originals spectra are then discarded by the thresholding step.

These above described methods are applied on an evaluation corpus, composed of simulated sound scenes, in or-250 der to compare the estimated traffic sound levels with an exact reference. This new sound corpus is designed by considering realistic urban sound environments with many kinds of mixed sound sources. This annotation phase makes it possible to produce simulated sound scenes with the same positions of sound events than the recordings and therefore as close as possible to 295 the real scenes.

Design of realistic urban sound scenes

Generation of the evaluation corpus

The sound scenes are generated with the SimScene software2 , [START_REF] Rossignol | SimScene: a web-based acoustic scenes simulator[END_REF], a simulation software generating monaural sound mixtures in wav format from an isolated sounds 300 database. This software has already been used in a wide range of experiments for sound detection algorithm assessment [START_REF] Lafay | A New Experimental Approach for Urban Soundscape Characterization Based on Sound Manipulation : A Pilot Study[END_REF][START_REF] Benetos | Detection of overlapping acoustic events using a temporally-constrained probabilistic model[END_REF]. The SimScene software allows the design of

mT IR = M i=1 L p,traf f ic -L p,interf ering M . ( 14
)
where M is the number of available scenes for each

Perceptual test

To evaluate the level of realism of the evaluation corpus composed of replicated urban sound scenes, a perceptual test is considered.

The perceptual test is conducted with a panel of 50 (m recorded = 4.9 (± 1.6)). To determine whether a replicated scene is perceived in a similar way to that recorded, a Student's t-test is performed, for each scene, between the scores from the recorded sample and those from the 420 replicated sample with the H 0 hypothesis which considers the similarity between the distribution of the rates for the recorded and the replicated scenes of each participant with a p-value threshold of 5%. The 20 performed t-tests show that the differences in the assessment of the replicated and 425 the recorded scene, according to their degree or realism, is not significant (p-value> 5%).

More details on the results can be found in [START_REF] Gloaguen | Creation of a corpus of realistic urban sound scenes with controlled acoustic properties[END_REF]. As the perceived realism of the replicated and the recorded scenes are not significantly different, we consider that these sound mixtures are relevant to assess the performances of NMF according to the traffic sound level estimate.

Methods for the performance evaluation

The experiment aims at evaluating in a meaningful manner the performance of the NMF approach. To do so, the 74 replicated sound scenes, organized on 4 different types of sound environments are iteratively fed to the estimator which output an estimate of the equivalent sound level of the traffic within each scene Lp,traffic (dB). This result is then compared to the reference sound level value given by the simulation process, L p,traf f ic , see Figure 6.

Reference estimator

A reference estimator is necessary to be able to compare the performances of the different NMF-methods. As the road traffic is mainly composed of a low frequency con-445 tent, a frequency low-pass filter (LP filter) is considered as baseline. The estimation of the traffic sound level with this reference estimator is simply the sound level after low-pass filtering,

Ṽtraffic = V fc . ( 15
)
Different cut-off frequencies have been chosen such as 450 f c ∈ {500, 1k, 2k, 5k, 10k, 20k} Hz. The experimental factors related to this estimator are summarized in Table 2.

The second estimator is based on the three NMF formula presented in part 2 (see Figure 8). Multiple experimental factors are involved in this second estimator where each of them having different modalities.

Dictionary building for NMF-methods

The dictionary is designed from a sound database specially dedicated to this task. To prevent any overfitting 2 summarizes the different modalities of the two experimental factors (K and w t ).

NMF experimental factors

NMF is performed for 3 β-divergences: β = 2 (Eu- 2.

505

The approximated traffic spectrograms Ṽtraffic are obtained after 400 iterations. The estimated traffic sound level in dB, Lp,traffic , is then computed, Lp,traffic = 20 log

p rms p 0 , ( 16
)
where p 0 is the reference sound pressure, p 0 = 2 × 10 -5

Pa. For each setting, M traffic sound levels, correspond-510 ing to the M scenes of each sound environment, are then calculated.

Metrics

The traffic sound levels, Lp,traffic , are compared to the exact values, L p,traf f ic , through the Mean Absolute 515

Error (M AE) [START_REF] Willmott | Advantages of the mean absolute error (mae) over the root mean square error (rmse) in assessing average model performance[END_REF]. The M AE consists in the average across of the absolute difference between the exact and the estimated sound levels,

M AE j = M i=1 |L i p,traf f ic -Li p,traf f ic | M j , (17)
for each setting j. But it is also possible to average this metric according to the 4 different sound environments, 520 through the mean M AE error mM AE, to estimate the optimal setting that offers the lowest error for all the sound environments:

mM AE = 4 i=1 M AE i 4 , (18)
where the other experimental factors (estimator, f c , K, w t , β, threshold value t h ) are fixed.

Results and discussion

Table 3 summarizes the lowest mM AE errors according to the estimator (LP filter, NMF) and β with the best setting of the experimental factors.

The LP filter with f c = 20 kHz cut-off frequency is equivalent to consider the sound level of the entire scene without specific distinction between the sound sources.

The error is then important with a high standard devi- in the highest errors. Indeed, this degree of freedom generates higher error as W r is not constrained and is free to include traffic component in it, penalizing the traffic sound level estimation.

Finally, TI-NMF presents the most performing results, except in the park environment (M AE = 2.95 dB). In this sound environment, with the threshold value t h = 0.32, the traffic dictionary is composed, on average, of 136 elements. By increasing this value, it would be possible to put aside the spectra furthest away of the traffic elements and then decrease the error. For the rest of the sound environments, TI-NMF has the lowest errors. For very noisy environment the error is even very low (M AE = 0.28 dB).

With on average 198 elements in W traf f ic , almost all the elements present in W can be considered as traffic elements. Considering a unique dictionary fitted to the sound scene under evaluation thus makes TI-NMF very effective when traffic is predominant, while the thresholding step makes it possible to discard the elements of the dictionary that deviate too much when the traffic is less present.

To better understand the behavior of TI-NMF, the evo- 3.

factor, will disappear after a set of iterations.

Conclusion

The non-negative matrix factorization framework has been considered as a source separation tool to estimate the traffic sound level from a corpus of urban sound scenes artificially built. Those scenes are designed to be as similar as possible to the outputs of a deployed sensor networks with the advantages of the simulation process (sound level and position of each source controlled and known). The realism of the scenes has been verified thanks to a perceptual test.

The results confirm the potential of the NMF method on such application scenario as it takes into account the overlap between the multiple sound sources present in cities and is suited to monophonic sensor networks. Different NMF algorithmic schemes have been studied through the supervised and semi-supervised approach. On all the sound environments, these common approaches reveal to be not sufficiently efficient: supervised NMF approach, with its fixed dictionary, does not succeed to estimate correctly the traffic sound level especially when this sound source is quiet, while semi-supervised approach with the presence of a mobile part in the dictionary is the best estimator for 665 park environments but fails on heavily traffic scenes.

The proposed approach, named Thresholded Initialized NMF, achieved the lowest error in the evaluation corpus.

Consequently, in the case where the location or the type of sound environments the sensors are monitoring cannot 670 be identified (for instance within a mobile measurement framework), TI-NMF appears to be the most appropriate method. If the sound environment can be identified through a prior analysis, or based on positioning data [START_REF] Can | Noise indicators to diagnose urban sound environments at multiple spatial scales[END_REF][START_REF] Lavandier | Urban 920 soundscape maps modelled with geo-referenced data[END_REF], it should be possible to adapt the estimation pro-675 cedure by selecting the most efficient approach in order to further reduce the error in the estimated road traffic sound levels.

Further analyses are required to extend the proposed method to other sound sources, such as birds or voices 680 sounds, which can conveniently be done by replacing or adding elements in the dictionary. This utilization would be useful in the context of muti-source noise mapping that is gaining interest [START_REF] Aumond | Probabilistic modeling framework for multisource sound mapping[END_REF][START_REF] Aletta | Noise indicators to diagnose urban sound environments at multiple spatial scales[END_REF]. Finally, the parameters selected in this study are valid for this evaluation corpus. Further 685 analyses on various corpus of sound scenes are needed to evaluate the robustness of the method and select the most relevant approaches for specific sound environments (predominance of water or industrial sounds, rural environments. . . ).

For reproducibility purposes, the evaluation corpus, the experimental protocol and the programs developed under the Matlab software are available online 4 as the sound dataset 5 .

noise with the assimilation of observations crowdsensed by the

Figure 1 :

 1 Figure 1: Block diagram of the blind source separation model

60 level.

 60 Even if road traffic is predominant on many urban areas, urban sound environments are composed of many different overlapping sound sources (passing cars, voices, footsteps, car horn, whistling birds . . . ), what makes the task of estimating correctly the traffic sound level within 65 an urban sound mixture not trivial. Many works have dealt with the classification [20, 21],

Figure 2 :

 2 Figure 2: NMF decomposition of an audio spectrogram V composed of 3 elements (K = 3): passing car (a), car horn (b) and whistling bird (c).

  165 updated. The A ⊗ B and A/B operators represent the Hadamard product and ratio.

230

  To summarize, to approximate the audio spectrogram V and estimate the traffic component, 3 methods are used which deal differently with the a priori knowledge on the traffic. SUP-NMF is only based on fixed traffic elements

  235

255Figure 3 :Figure 4 :

 34 Figure 3: Bloc diagram of the design of the evaluation corpus

Figure 5 :

 5 Figure 5: Spectrogram of a simple scene created with the SimScene software with one sound background (road traffic in blue) and 3 sound events (car horn in green, passing car in yellow and whistling bird in red).

  sound environment (M = 8 for park environment, M = 35 for quiet street environment, M = 23 for noisy street environment and M = 8 for very noisy street environment).The mT IR is always negative for the park as it is the sound environment where the traffic is less present. The interfering sound class is therefore the main sound source which is 365 coherent with this kind of environment. The mT IR can be positive or negative depending on the traffic presence on the scene in the case of the quiet street. For the 2 others sound environments, when the traffic becomes the main sound source, mT IR is always positive.

  370

375 listeners that are asked to assess the level of realism on a 7 -

 7 point scale (1 is not realistic at all, 7 is very realistic) of a set of replicated and recorded scenes. The total number of sound scenes tested is set at 40. This is less than the number of scenes available to ensure that each audio sample 380 is sufficiently assess. The first half includes 20 30-seconds audio files corresponding to the real scenes, including 5 scenes that belong to the sound environment park, 6 from quiet street, 4 from noisy street and 5 from very noisy street chosen randomly among the recorded scenes. The second 385 half is composed of the replicated scenes from the evaluation corpus corresponding to the same 20 reference scenes. In order to limit the duration of the test to preserve the concentration of the subjects, each subject listens to only a subset of 20 sound scenes. All the scenes are normalized to the same sound level, chosen at 65 dB, and the subjects are not allowed to change the output sound level once set at the beginning of the experiment. The experimental design is elaborated following a partially Balanced Incomplete Block Design (PBIBD) [54] the 395 audio allocated to each participant and the listening order. This process allows to each sound sample to be assessed almost the same number of time and to avoid statistical biais. The experimental design and the listening order per participant are performed with the package sensoMineR 400 on the R software [55]. The test was available online from February 8th, 2017 and the needed number of participant (50) has been reached 12 days later. During the test, the participants had the 405 possibility to listen to each scene as many times as wanted before assessing, without being able to change their judgment afterwards. The participants could also leave a comment on each audio to explain the rating 3 . Based on the information provided, the panel of 50 listeners was made of 410 31 males and 18 females (one not documented) with an average age of 36 (± 12) years old. 62% of the participants declared having no experience in the listening of urban sound mixtures. The results show that the average score (with its standard deviation) of all the replicated scenes 415 (m replicated = 5.1 (± 1.6)) is close to the recorded ones

1 .Figure 7 .

 17 Figure 7. From the 53 audio files, we obtain respectively 2218 elements for w t = 0.5 second and 1109 elements for w t = 1 second.475

485Figure 6 :

 6 Figure 6: Bloc diagram of the different stages for the estimation of the traffic sound level.

Figure 7 :Figure 8 :

 78 Figure7: Dictionary building on a 3 second example of a passing car with w t = 1 second, in dashed line a temporal frame of 1 s. In this case, the dictionary W is made of 3 spectra, each representative of a texture frame of w t duration.

  ation (mM AE = 3.76 (± 4.35) dB). The lowest error for a LP filter is obtained with f c = 500 Hz (mM AE = 2.14 (± 1.83) dB).When considering all the sound scenes, SUP-NMF does not succeed to achieve a lower error than the 500 Hz LP filter for all the β values. By adding the mobile part W r in the dictionary, SEM-NMF with β = 0 and β = 1 allows a lower error than 500 Hz LP filter with a reduced standard deviation especially for β = 1 (mM AE = 1.94 (± 0.38) dB). TI-NMF is the approach with the lowest global error (< 1.50 dB). The best result is obtained for TI-NMF (M AE 545 = 1.24 (± 1.24) dB) with β = 2, K = 200, w t = 0.5 s and as threshold value t h = 0.32. This combination of settings offers the most efficient method adapted to the different sound environments. Furthermore, on the dictionary creation, only SEM-NMF proposes the same dictio-550 nary design for all the best methods according to β. In the opposite, SUP and TI-NMF propose different associations between K and w t . One can notice that, through the 3 methods, it is mainly a high number of elements in K (100, 200) that is preferred. With more elements, it 555 makes it possible to resolve easily the generalization issue.From these global results, the M AE errors are compared to the LP filter and each method for the 4 types of sound environments, see Figure9.Aside SEM-NMF, all the methods show the same error 560 evolution: a decrease of the error with the increase of the traffic predominance. On contrary, SEM-NMF shows an almost constant error for all 4 sound environments. The LP filter error is mainly important for environments where the traffic is less present. As this approach considers the 565

Figure 9 :

 9 Figure 9: M AE errors with the standard deviations according to each sound environment for the best combination of the LP filter (fc = 500 Hz), SUP-NMF (β = 2, K = 25, w t = 1 second), SEM-NMF (β = 1, K = 200, w t = 1 second) and TI-NMF (β = 2, K = 200, w t = 0.5 second, t h = 0.32).

Figure 10 :

 10 Figure 10: Normalized reconstruction error of the global sound mixtures a and the traffic component b for each sound environment.

  lution of the normalized cost function (D(V WH)/(F × N ) as the duration of each audio sample is different) and the error M AE as the function of the number of iterations are displayed for each sound environment in Figure 10. For each sound environment, the cost function is very low after 400 iterations, meaning that WH approximates correctly V. However, even if the convergence is not reached (Fig-620 ure 10a), the traffic error reconstruction is constant after the 200th iteration (Figure 10b), which means that the updates of W and H are mostly dedicated to the interfering sound sources. Also, even if the cost function is higher for the very noisy street than the park, the traffic sound 625 level estimation is better in the very noisy street sound environment due to the higher presence of this component in it. Finally, the influence of the number of elements K in W and the size of the temporal frame w t on the mM AE 630 error made with TI-NMF, with the other experimental factors keep constant, are summarized in Figure 11. Naturally, the traffic error reconstruction decreases, with the increase of the number of basis in W, as it allows more basis to describe the traffic sound source. If this improve-635 ment is major between 25 and 100 elements, its influence decreases between 100 and 200 elements suggesting that the increase of the size of K will not improve significantly the quality of the estimation. The temporal frame w t is a less influential parameter for TI-NMF. As the matrices are 640 updates at each iteration, it makes sense that the variations in the spectra shape in W 0 , due to this experimental (a) Influence of the experimental factor K (TI-NMF, wt = 0.5 s, β = 2, t h = 0.32, 400 iterations). (b) Influence of the experimental factor wt (TI-NMF, K = 200 s, β = 2, t h = 0.32, 400 iterations).

Figure 11 :

 11 Figure 11: Influence of the number of elements K (a) and the temporal frame w t (b) on the mM AE error with the best TI-NMF obtained in Table3.

Table 1 :

 1 Mean Traffic Interfering Ratio and its standard deviation for each sound environment.

		mT IR (dB)
	park	-9.10 (± 7.35)
	quiet street	0.88 (± 5.92)
	noisy street	6.96 (± 5.16)

very noisy street 15.75 (± 9.78) tiple samples (carHorn01.wav, carHorn02.wav . . . ) that are randomly chosen by the simScene software to bring 330 diversity. As the road traffic is the main component in urban environment and is the sound source of interest, recordings of car passages have been made on the Ifsttar's runway. The recordings have been made for 4 different cars (Renault Scenic, Renault Mégane, Renault Clio and 335 Dacia Sandero), at different speeds and gear ratios. Overall, 103 car passages have been recorded. In order to avoid overfitting issues, the audio samples of the first two cars (Renault Scenic and Renault Mégane) are included in the SimScene's elemental corpus (50 audio files in total). The 340 last 53 audio samples are dedicated to the dictionary design, W as part of NMF, see section 4.2. A full description of the recordings can be found in [53]. With this built-up corpus, the SimScene software and the transcriptions of the recordings, 74 simulated sound 345 scenes are generated, which have the same temporal structure of the reference recordings. The sound level of each sound class is adjusted manually on each sound scene to be faithful compared to the recorded scenes. To check this adjustment, the mean Traffic Interfering Ratio (mT IR) 350 is calculated, see

Table 1 .

 1 It expresses, on all the scenes of a sound environment, the mean difference between the equivalent traffic sound levels of each scene, L p,traf f ic , with the sound level of the interfering sound class, L p,interf ering , which gathered all the other sound sources not related to

355

the traffic, see Eq. 14. It quantifies the predominance of the traffic component for the 4 types of sound environments,

Table 2 :

 2 Experimental factors and their modalities for the NMF estimator.

	experimental							number of
				modalities
	factors							modalities
	sound	park	quiet street	noisy street	very noisy street
								4
	environment	'P'	'Q'		'N'	'vN'
	method	LP Filter	SUP NMF	SEM NMF	TI NMF	4
	f c (kHz)	0.5	1	2	5	10	20	6
	w t (s)		0.5			1		2
	K	25	50		100	200		4
	β	0		1		2		3
	hard threshold t h		from 0.30 to 0.60 with a 0.01 step			31

Table 3 :

 3 Best mM AE errors according to the experimental factor β and the traffic sound level assessment method (in bold letter, the lowest error).

	method	f c (kHz) β	K	w t (s)	t h	mM AE (dB)
	filter	20	-	-	-	-	3.76 (± 4.35)
	filter	0.5	-	-	-	-	2.14 (± 1.83)
	SUP-NMF	-	0 200	0.5	-	4.06 (± 4.69)
	SUP-NMF	-	1 200	0.5	-	2.79 (± 3.38)
	SUP-NMF	-	2	25	1	-	2.32 (± 2.80)
	SEM-NMF	-	0 200	1	-	2.05 (± 0.70)
	SEM-NMF	-	1 200	1	-	1.94 (± 0.38)
	SEM-NMF	-	2 200	1	-	2.39 (± 1.23)
	TI-NMF	-	0	25	1	0.39	1.42 (± 0.89)
	TI-NMF	-	1 100	1	0.35	1.38 (± 0.88)
	TI-NMF	-	2 200	0.5	0.32 1.24 (± 1.24)

sound source (the road traffic) but also can be adapted to the content of the scene thanks to the updates. After N iterations, each element k of the final dictionary, W , is compared with its initial value in W 0 , in order to identify which element is stayed close to the traffic component. A

Open-source project available at: https://bitbucket.org/ mlagrange/simscene

The interface of the experiment is available http:// soundthings.org/research/xpRealism

Acknowledgements

The authors would like to thank Pierre Aumond and Catherine Lavandier from the University of Cergy-Pontoise for transmitting us the data of the Grafic project.

Funding

This study is co-funded by Ifsttar and Pays de la Loire 700 region.

[20] X. Valero, F. Alías, Hierarchical classification of environmental noise sources considering the acoustic signature of vehicle pass-


Umut A Acar

Vitaly Aksenov

Arthur Charguéraud

Mike Rainey

Poster: Performance Challenges in Modular Parallel Programs

Keywords: Cilk, TBB, X10, parallel ML such as Cilk's spawn and sync, suffice to express

Over the past decade, many programming languages and systems for parallel-computing have been developed, including Cilk, Fork/Join Java, Habanero Java, Parallel Haskell, Parallel ML, and X10. Although these systems raise the level of abstraction at which parallel code are written, performance continues to require the programmer to perform extensive optimizations and tuning, often by taking various architectural details into account. One such key optimization is granularity control, which requires the programmer to determine when and how parallel tasks should be sequentialized.

In this paper, we briefly describe some of the challenges associated with automatic granularity control when trying to achieve portable performance for parallel programs with arbitrary nesting of parallel constructs. We consider a result from the functional-programming community, whose starting point is to consider an "oracle" that can predict the work of parallel codes, and thereby control granularity. We discuss the challenges in implementing such an oracle and proving that it has the desired theoretical properties under the nested-parallel programming model.

Context

The proliferation of multicore hardware in the past decade has brought shared-memory parallelism into the mainstream. This change has led to much research on implicit threading, a.k.a. implicit parallelism, which seeks to make parallel programming easier by delegating certain tedious but important details, such as the scheduling of parallel tasks to the compiler and the run-time system. Implementations include: OpenMP,

many common parallel patterns, including parallel loops and nested parallel computations, wherein parallel computations may themselves start and synchronize with other parallel computations.

To control the overheads of parallelism, the current state of the art requires the programmer to tune the code to perform granularity control or coarsening, so as to amortize the overheads [START_REF]Intel Threading Building Blocks[END_REF]. To do so, the programmer identifies for each potential parallel computation a sequential alternative, a semantically equivalent sequential piece of code, and makes sure that this alternative is executed for small (and only for small) computations. For example, consecutive iterations of a parallel loop can be "bunched" into sequential blocks. The number of iterations bunched together is called the cut-off or the grain size. Crucially, the grain size needs to be large enough to amortize the cost of parallelism, but small enough to enable the creation of sufficiently many parallel tasks.

Selecting the grain size is challenging because: (1) the optimal grain size depends on the hardware; (2) the optimal grain size depends on the instantiation of the code, in the case of modular (templated) code; (3) for a fixed program, the optimal grain size may depend on the input data, e.g., when the processing time varies for each item; (4) in the case of nesting, the grain sizes are interdependent, e.g., the grain size of an outer loop depends on the work load involved in the inner loop, which might itself be data dependent.

Related work

Intel's TBB manual [START_REF]Intel Threading Building Blocks[END_REF] describes the following process for determining the grain size: start by setting the grain to the value 10 000 and halve it until the 1-processor run-time stops decreasing by more than 10%. Such tuning maximizes the exposed parallelism by considering the smallest grain value for which the overheads are not prohibitive. Duran et al. [START_REF] Duran | An adaptive cut-off for task parallelism[END_REF] propose a method for selecting among three parallelization options: outer-loop only, inner-loop only, or mixed mode, where inner and outer loops may be parallelized and granularity controlled by an online heuristic. Another approach uses the height and depth of the recursion tree [START_REF] Pehoushek | Low-cost process creation and dynamic partitioning in Qlisp[END_REF][START_REF] Weening | Parallel Execution of Lisp Programs[END_REF] to predict the execution time and the grain size, but lacks crucial information because depth and height are not a direct measure of execution time. As Iwasaki et decisions solely on such dynamically collected data may end up decreasing parallelism adversely [START_REF] Iwasaki | A static cut-off for task parallel programs[END_REF]. Iwasaki et al propose a technique for synthesizing static cut-offs for divide-andconquer functions in Cilk-style programs [START_REF] Iwasaki | A static cut-off for task parallel programs[END_REF]. They rely on static analysis to determine whether or not to switch to sequential execution. Yet, static analysis cannot cope well with complex code. Lazy task creation (or, sometimes, lazy scheduling) [START_REF] Mohr | Lazy task creation: a technique for increasing the granularity of parallel programs[END_REF][START_REF] Tzannes | Lazy Scheduling: A Runtime Adaptive Scheduler for Declarative Parallelism[END_REF] is a strategy to circumvent the problem of selecting a grain size. Processors observe the load in the system and create tasks only when necessary, by splitting their currently-running task. Lazy task creation has proved to be an indispensable technique for reducing overheads of parallelism in many systems. Yet, it does not provide support for deciding that a subtask is small enough that it may be executed, without harming parallelism, using a sequential algorithm more efficient than its parallel counterpart.

Algorithmic granularity control Prior work [START_REF] Acar | Oracle-guided scheduling for controlling granularity in implicitly parallel languages[END_REF] proves that, if it is possible to approximately predict the sequential execution time associated with every computation involved in the execution of a parallel program, then there exists a scheduling strategy that ensures bounded parallelism overheads, while preserving the asymptotic amount of parallelism being exposed. The proof of this theorem, which applies to a relatively large class of parallel programs, is carried out in the work-span computation model, which is well suited for analyzing nested parallel programs.

In this work, we investigate the possibility to implement execution-time predictions in practice, by combining asymptotic cost functions provided by the programmer with runtime measurements. There are three key challenges. First, predictions need to be sufficiently precise to benefit from the bounds associated with the aforementioned theorem. Second, the algorithm needs to be robust to the large variations in the execution times typical for modern hardware (constant factors increase noticeably when the data stops fitting into the cache). Third, the algorithm needs to infer the constant factors online during the execution of the parallel program. Doing so involves a circularity problem, illustrated next. The body of the above function involves a spguard, which is a combinator expecting 3 arguments. First, c(x) describes the asymptotic cost function. Second comes the parallel body. It implements a divide-and-conquer approach; splitting the input data in halves, making two recursive calls in parallel, then combining the output results. Third, g(x) describes the sequential body.

We aim at enforcing the following policy: if the result of f(x) can be obtained by evaluating the sequential body g(x) in time less than some constant threshold κ, then g(x) should be used. Under a small number of assumptions, this policy leads to provably efficient granularity control.

The circularity problem is the following. To decide which computations are safe to execute using the sequential body, g(•), our algorithm needs to first know the constant factor that applies. Indeed, without an accurate estimate of the constant, the algorithm might end up invoking g(•) on a large input and potentially destroy all available parallelism.

  let f(x) = spguard(fun () → c(x), // cost function fun () → // parallel body if |x| = 1 then .. else let (x1,x2) = divide(x) spawn let r1 = f(x1) let r2 = f(x2) sync conquer(r1,r2),fun () → g(x)) // sequential body

  al. point out, basing

	PPoPP '18, February 24-28, 2018, Vienna, Austria	U. Acar et al.

Yet, in order to estimate the constant factor, the algorithm needs to measure the execution time of a call to g(•).To resolve this critical circular dependency, we designed an algorithm that progressively sequentializes larger and larger computations. It begins by sequentializing only the base case, and ultimately converges to computations of duration close to κ. Each call to g(•) leads to a time measurement, which may be subsequently used to predict that another, slightly larger input may be processed sequentially. We increase input sizes progressively, in order to always remain on the safe side, making sure that our algorithm never executes sequentially a computation significantly longer than κ.We prove, under a few assumptions typically met by many efficient parallel programs, end-to-end bounds on the execution time, including the overheads of parallelism and the cost of the aforementioned convergence phase. Benchmarks suggest that our automatic granularity control approach enables replacing careful selection of techniques with a single, uniform technique for controlling granularity, that automatically adapts to the hardware, i.e., the technique is portable.

Acknowledgments This research is partially supported by the National Science Foundation (CCF-1408940 and CCF-1629444), European Research Council (ERC-2012-StG-308246).


Vitaly Aksenov

Dan Alistarh

Petr Kuznetsov

Brief Announcement: Performance Prediction for Coarse-Grained Locking

A standard design pattern found in many concurrent data structures, such as hash tables or ordered containers, is an alternation of parallelizable sections that incur no data conflicts and critical sections that must run sequentially and are protected with locks. A lock can be viewed as a queue that arbitrates the order in which the critical sections are executed, and a natural question is whether we can use stochastic analysis to predict the resulting throughput. As a preliminary evidence to the affirmative, we describe a simple model that can be used to predict the throughput of coarse-grained lock-based algorithms. We show that our model works well for CLH lock, and we expect it to work for other popular lock designs such as TTAS, MCS, etc.

ABSTRACT COARSE-GRAINED SYNCHRONIZATION

Conventionally, the performance of a concurrent data structure is evaluated via experiments, and it is notoriously difficult to account for all significant experimental parameters so that the outcomes are meaningful. Our motivation here is to complement experimental evaluation with an analytical model that can be used to predict the performance rather than measure it. As a first step towards this goal, in this work, we attempt to predict the throughput of a class of algorithms that use coarse-grained synchronization. Consider a concurrent system with N processes that obey the following simple uniform scheduler: at every time step, each process performs a step of computation. This scheduler, resembling the well-known PRAM model [START_REF] Jájá | An introduction to parallel algorithms[END_REF], appears to be a reasonable approximation of a real-life concurrent system. Suppose that the processes share a data structure exporting a single operation(). If the operation induces a work of size P and incurs no synchronization, the resulting throughput is N • α/P operations in a unit of time: each process performs α/P operations in a unit of time, where α indicates the amount of work that can be performed by one process Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for third-party components of this work must be honored. For all other uses, contact the owner/author(s). in a unit of time. One way to evaluate the constant α experimentally is to count the total number F of operations, each of work P, completed by N processes in time T . Then we get α = F /N P. The longer is T , the more accurate is the estimation of α. Now suppose that, additionally, the operation performed by each process contains a critical section of size C. In the operation, described in Figure 1, every process takes a global lock, performs the critical section of size C, releases the lock and, finally, performs the parallel section of size P.

Here, as a unit of work, we take the number of CPU cycles spent during one iteration of the loop in Lines 3-4 or 6-7. The iteration consists of a nop instruction, an increment of a local variable and a conditional jump, giving us, approximately, four CPU cycles in total.

MODEL ASSUMPTIONS

Below we list basic assumptions on the abstract machine used for our analytical throughput prediction.

First, we assume that coherence of caches is maintained by a variant of MESI protocol [START_REF] Mark | A low-overhead coherence solution for multiprocessors with private cache memories[END_REF]. Each cache line can be in one of four states: Modified (M), Exclusive (E), Shared (S) and Invalid (I). MESI regulates transitions between states of a cache line and responses depending on the request (read or write) to the cache line by a process or on the request to the memory bus. The important transitions for us are: (1) upon reading, the state of the cache line changes from any state to S, and, if the state was I, then a read request is sent to the bus; (2) upon writing, the state of the cache line becomes M, and, if the state was S or I, an invalidation request is sent to the bus.

We assume that the caches are symmetric: for each MESI state st, there exist two constants R st and W st such that any read from any cache line with status st takes R st work and any write to a cache line with status st takes W st work. David et al. [START_REF] David | Everything you always wanted to know about synchronization but were afraid to ask[END_REF] showed that for an Intel Xeon machine (similar to the one we use in our experimental validation below), given the relative location of a cache line with respect to the process (whether they are located on the same socket or not), the following hypotheses hold: (1) writes induce the same work, regardless of the state of the cache line;

(2) swaps, not concurrent with other swaps, induce the same work as writes. Therefore, we assume that [START_REF] Craig | Building FIFO and priorityqueuing spin locks from atomic swap[END_REF] [START_REF] Scott | Algorithms for scalable synchronization on shared-memory multiprocessors[END_REF] and CLH [START_REF] Craig | Building FIFO and priorityqueuing spin locks from atomic swap[END_REF]. For our analysis, we choose CLH, as the simplest lock among those considered to be efficient. In Figure 2, we inline lock and unlock calls to CLH lock in our abstract coarse-grained operation.

W = W M = W E = W S =

Cost of an operation

Let us zoom into what happens during the execution of the operation.

Note that at the beginning of an operation (unless it is the very first invocation), my_node.locked is loaded into the cache and the corresponding cache line is in state M, because of the set in Line 15 during the previous operation by the same process.

(1) The operation starts with swap (Line 9) that induces a work of size W , if not concurrent with other swaps, and a work of size at most X , otherwise.

(2) In Line 10, the algorithm loops on a field next.locked. During this loop one or two cache misses happens.

One cache miss can happen at the first iteration of the loop if the read of locked returns true. The last process that grabbed the lock already invalidated this cache line in Line 15 during its penultimate operation. MESI reloads the cache line and changes its state from I (or none if it was not loaded previously) to S.

The other cache miss happens in every execution when the operation reads next.locked and gets false. In this case, the cache line was invalidated in Line 13 during the last operation of the last process that grabbed the lock. MESI reloads the cache line and changes its state from I (or none) to S.

Each of the described cache misses induces the work of size R I . Thus, the work induced in Line 10 is of size of R I (if only the second miss happens) or 2 • R I (if both misses happen).

(3) In Lines 11-12, the critical section with work of size C is performed. (4) In Line 13, my_node.locked is set to false. There are two cases: if my_node.locked is not yet loaded by any other process in Line 10 then the state remains M; otherwise, MESI changes the state from S to M and sends a signal to invalidate this cache line. In both cases, the induced work is of size W .

(5) In Line 14, the operation performs an assignment on local variables, without contributing to the total work. (6) In Line 15, my_node.locked is set to true. From the end of the while loop at Line 10 the corresponding cache line is in state S. MESI changes the state to M and sends a signal to invalidate this cache line inducing work of size W . (7) In Lines 16-17, the parallel work of size P is performed.

Evaluating throughput

To evaluate the throughput of the resulting program under the uniform scheduler, take a closer look on how N processes continuously perform the operation from Figure 2.

Process 1 executes: its first swap (taking at most X units); the critical section (blue, Lines 10-13): acknowledges the ownership of the lock by reading false in Line 10 (takes R I units), performs the work of size C and releases the lock in Line 13 (takes W units); the parallel section (red, Lines 15-17 and 9): sets my_node.locked to true (takes W ), performs the work of size P, performs a noncontended swap (takes W ) and, possibly, reads true in Line 10 (takes R I ). (Here, the swap operation performed after the very first completed critical section is counted in the parallel work, as it is executed in the absence of contention.) Every other process i operates in the same way: it swaps as early as possible (taking at most X ), waits until process i -1 releases the lock, and then performs its critical (blue) and parallel (red) sections.

Depending on the parameters N , C, P, W , and R I , two types of executions are possible.

In case 1 (Figure 3a), at the moment when process 1 finishes its parallel section, process N already finished its critical section, i.e., P + 2 • W > (N -1) • (C + R I +W ). Therefore, in the steady case, at every moment of time, each process do not wait and execute either the parallel or critical section, and the read in Line 10 cannot return true because the lock is already released. Thus, the throughput, measured as the number of operations completed in a unit of time, equals to N • α (P +2•W )+(C+R I +W ) . In case 2 (Figure 3b), before proceeding to the next operation, process 1 has to wait until process N completes its critical section from the previous round of operations; process 2 waits for process 1, process 3 waits for process 2, etc. Thus, there is always some process in the critical section, giving the throughput of α C+R I +W . Therefore, given the number of processes N , the sizes C and P of critical and parallel sections, the throughput can be calculated as follows:

α C+R I +W if P + 2 • W ≤ (N -1) • (C + R I + W ) α •N (P +2•W )+(C+R I +W )) otherwise

EXPERIMENTS

For our measurements, we used a server with four 10-core Intel Xeon E7-4870 chips of 2.4 GHz (yielding 40 hardware processes in total), running Ubuntu Linux kernel v3.13.0-66-generic. We compiled the code with MinGW GCC 5.2.0 (with -O0 flag to avoid compiler optimizations, such as function inlining, that can screw up our benchmarking environment). The code is available at https://github.com/Aksenov239/complexity-lock-with-libslock.

1 X R I C W W P W R I C W 2 X R I C W W P W . . . N X R I C W W (a) Case 1: W + P + W ≥ (N -1) • (R I + C + W ).
Each process enters the critical section without waiting in the queue.

1 X R I C W W P W R I R I C W 2 X R I C W W P W R I . . . N X R I C W W (b) Case 2: W + P + W ≤ (N -1) • (R I + C + W ).
Each process waits in the queue before entering the critical section. We considered the following experimental settings: the number of processes N ∈ {5, 10, 20, 30, 39}; the size of the critical section C ∈ {100, 500, 1000, 5000, 10000}; and the multiplier x ∈ [1, 150] (we choose all integer values) that determined the size of the parallel section P = x • C. For each setting, we measured the throughput for 10 seconds. Our experimental evaluation gives α ≈ 3.5 • 105 , W ≈ 40, and R I ≈ 80. The ratio between W and R I correlates with the experimental results provided by David et al. [START_REF] David | Everything you always wanted to know about synchronization but were afraid to ask[END_REF].

In Figure 4 we show our experimental results for three settings with N = 39 and C ∈ {100, 500, 5000} (blue curves) compared with our theoretical prediction (red curves). The two curves match very closely, except for the case of small C and P where our predicted throughput underestimates the real one. We relate this to the fact that we oversimplified the abstract machine: any write induces the work of constant size W , regardless of the relative location of the cache line with respect to the process. For small C and P two processes from the same socket are more likely to take the lock one after the other and, thus, on average, a write might induce less work than W , and, consequently, the throughput can be higher than predicted.

Figure 1 :

 1 Figure 1: The coarse-grained operation

Figure 3 :

 3 Figure 3: Examples of executions of the coarse-grained algorithm from Figure 2. Blue intervals depict critical sections and red intervals depict parallel sections.

  Critical work C = 5000

Figure 4 :

 4 Figure 4: Throughput on 39 processes for C ∈ {100, 5000}

  W I and (2) any contention-free swap induces a work of size W .

	PODC '18, July 23-27, 2018, Egham, United Kingdom	Vitaly Aksenov, Dan Alistarh, and Petr Kuznetsov
	1 class Node:
	2	bool locked
	3
	4 Node head = new Node() // global
	5 Node my_node	// per process
	6	my_node.locked ← true
	7
	8 operation():
	9	Node next ← swap(&head, my_node) // W or X
	10	while (next.locked) {}		// R I or 2 • R I
	11	for i in 1..C:		// C
	12	nop
	13	my_node.locked ← false	// W
	14	my_node ← next
	15	my_node.locked ← true	// W
	16	for i in 1..P:		// P
	17	nop
	Figure 2: The coarse-grained operation with inlined lock
	and unlock functions
	3 CLH LOCK

Multiple lock implementations have been previously proposed, from simple spinlocks and TTAS to more advanced MCS

CONCLUSIONIn this short note, we showed that a simple theoretical analysis may quite accurately predict the throughput of data structures implemented using coarse-grained synchronization. For the moment, our analysis is restricted to algorithms using CLH-based locking in systems obeying the uniform scheduler. In upcoming work, we intend extend the analysis to more realistic algorithm designs, lock implementations and architectures.

ACKNOWLEDGEMENTS

This research is partially supported by European Research Council (ERC-2012-StG-308246) and the Franco-German DFG-ANR Project DISCMAT (14-CE35-0010-02).


James Hartley
email: j.hartley@keele.ac.uk

Guillaume Cabanac
email: guillaume.cabanac@univ-tlse3.fr

Hartley & Cabanac

OATAO is an open access repository that collects the work of Toulouse researchers and makes it freely available over the web where possible

Keywords: structured abstracts, graphical abstracts, video abstracts, readable abstracts

The abstract is a crucial component of a research article. Abstracts head the text-and sometimes they can appear alone in separate listings (e.g., conference proceedings). The purpose of the abstract is to inform the reader succinctly what the paper is about, why and how the research was carried out, and what conclusions might be drawn. In this paper we consider the same (or a similar) abstract in 13 different formats to illustrate the strengths and weaknesses of each approach.

Introduction

The abstract is a crucial component in a journal article [START_REF] Hartley | Academic Writing and Publishing: A Practical Handbook[END_REF]. It heads and summarises the text-and it can appear alone in separate lists of publications. The purpose of the abstract is to inform the reader succinctly of what the paper is about, why the research was carried out, what happened, and what conclusions might be drawn. In this paper, we present the same (or a similar) abstract in different formats to illustrate the strengths and weaknesses of different approaches. These are variations of the block format (version 1) in terms of structure (e.g., version 3: structured abstracts) and contents (e.g., version 8: tweetable abstracts).

Version 1: The Block Format

Here is a typical "informative" abstract found in a recent article [START_REF] Hartley | Book reviews in time[END_REF], set out in the traditional manner.

Currently, especially in journals published by Elsevier, it is fashionable to include the highlights of a paper either before, or more frequently, after the abstract. Sometimes these highlights accompany the abstract, but it is more common to find them on their own after the titles of the articles. For the abstract under discussion, a highlight might appear thus:

Highlights

• Academic writing styles change little with age when writing book reviews • . . . But there are usually three or four highlights per paper.

Version 7. Readable Abstracts

Readable abstracts are typically added to an article (at the beginning or the end) in addition to the more technical one, and they provide a lay person's account of the content of the paper [START_REF] Hartley | What's new in abstracts of science articles?[END_REF][START_REF] Kuehne | Lay summaries needed to enhance science communication[END_REF]. A related approach is to provide information under headings-such as "What is already known about this topic?" "What this study adds", and "What are the implications of this study for practice and/or policy?" Examples can be found in the British Medical Journal, and the British Journal of Educational Technology. Here we might find:

What is already known about this topic?

There are few studies of academic writing over time, but most assume that writing improves with practice.

What are the implications of this study for practice and/or policy? None.

Version 8: Tweetable Abstracts

Some journals (e.g., Methods in Ecology and Evolution and BJOG: An International Journal of Obstetrics and Gynaecology) now require authors to produce a tweetable abstract as well as a traditional one. The aim being, presumably, to facilitate rapid dissemination of the contents (e.g., [START_REF] Else | Tell us about your paper-And make it short and tweet[END_REF]). Tweetable abstracts contain the essence of a study and a hyperlink with the paper's DOI or URL in no more than 140 characters.

In our case, this might read:

Academic writing styles change little with age when writing book reviews-study finds. https://doi.org/10.1007/s11192-016-2114-z However, the little research that we have found so far on this topic does not suggest that tweeting an abstract leads to significantly greater downloads of the related papers [START_REF] Tonia | If I tweet will you cite? The effect of social media exposure of articles on downloads and citations[END_REF].

Version 9: One-Sentence Abstracts

Some platforms, like OpenReview 1 used by the International Conference on Learning Representations (in the Machine Learning community) display an abstract in block format and a TL; DR section. This acronym introduced in the Oxford dictionaries2 in 2013 means: "TL;DR, abbrev.: 'too long didn't read': used as a dismissive response to a lengthy online post, or to introduce a summary of a lengthy post."

In our case, the TL;DR version of the abstract might read:

TL;DR: Academic writing styles change little with age when writing book reviews.

Version 10: One-Word Abstracts

Even shorter than tweetable abstracts are one-word abstracts. Such abstracts can occur when the title of an article is phrased in the form of a question. So, if the title of our paper had been "Does academic writing change with age?" a one-word abstract would say "No".

One word abstracts are rare, and are probably meant to be witty. Here are some examples:

• Title: Can apparent superluminal neutrino speeds be explained as a quantum weak measurement? Abstract: Probably not in [START_REF] Berry | Can apparent superluminal neutrino speeds be explained as a quantum weak measurement?[END_REF].

• Title: Is the sequence of earthquakes in Southern California, with aftershocks removed, Poissonian? Abstract: Yes in [START_REF] Gardner | Is the sequence of earthquakes in Southern California, with aftershocks removed, Poissonian? Bull[END_REF].

• Title: Do users verify SSH keys? Abstract: No in [START_REF] Gutmann | Do Users Verify SSH keys[END_REF].

Version 11: Graphical Abstracts

A number of journals now ask authors to provide a graphical abstract in addition to a normal one [START_REF] Gilaberte | Is a Picture Worth a Thousand Words? The Graphical Abstract[END_REF]. Such abstracts are supposed to provide "a single, concise pictorial and visual summary of the main findings of an article" 3 . However, to our knowledge, there has so far been little assessment of papers with graphical abstracts. Indeed, Pferschy-Wenzig et al. [START_REF] Pferschy-Wenzig | Does a Graphical Abstract Bring More Visibility to Your Paper?[END_REF] found that manuscripts published in the Molecules journal without graphical abstracts performed better in terms of downloads, abstract views, and total citations than manuscripts with them.

1 See, e.g., https://openreview.net/forum?id=rJY0-Kcll Sometimes these graphical abstracts stand alone, but they often accompany a traditional verbal one. A graphical abstract for this current paper might look as in Figure 1, but it would be difficult for readers to understand it without reading the paper first.

!" #!" $!" %!" &!" '!" (!" )" *" +" ," -"
!"#$%&'(%)*#$' +*,-#*'

)./"'!""""" )./"''""""" )./"(!""""" )./"('""""" Figure 1. Potential graphical abstract for paper [START_REF] Hartley | Book reviews in time[END_REF].

Version 12: Video Abstracts

Video abstracts normally consist of brief interviews with the author(s) explaining what they did, why, and what happened. It might be possible to include one here, but we have not been asked to do so. Video abstracts are usually created after the paper under consideration has been accepted, and they are linked to the paper upon publication. Examples can be found in electronic versions of papers published in Nature Chemistry, The New Journal of Physics, and the British Medical Journal (after 2015). Spicer [START_REF] Spicer | Video abstracts are a low-barrier means for publishers to extend the shelf life of research[END_REF] maintains that video abstracts allow authors to communicate their research through a personalized media-rich environment in ways that are impossible in print. Details of how to create and submit video abstracts can be found at http://authorservices.taylorandfrancis.com.

Version 13: Computer-Generated Abstracts

We do not know whether or not we have read any computer-generated abstracts, nor indeed what it would be like to create one. Nonetheless, the possibilities in this respect have been discussed since the 1960s (e.g., [START_REF] Luhn | The automatic creation of literature abstracts[END_REF][START_REF] Saggion | Automatic text summarization: Past, present and future[END_REF]). It should not be beyond the bounds of possibility to expect that computer-assisted abstracts will soon become the norm.

Concluding Remarks

In this paper, we have tried to show that there is more than one way of writing an abstract. Normally, of course, authors follow the styles used in the journals they are submitting their articles to. However, some journals seem to be more ambitious than others in this respect. Readers may be interested to know that the wording for Publications in this respect reads: "We strongly encourage authors to use the . . . style of structured abstracts, but without the headings."

In the same line and as part as its Manuscript Formatting Guide, the flagship Nature journal provides an example of abstract in block format with annotations explaining the sequence of information that authors are requested to provide in writing the abstract (see Figure 2). One or two sentences providing a basic introduction to the field, comprehensible to a scientist in any discipline.

Two to three sentences of more detailed background, comprehensible to scientists in related disciplines.

One sentence clearly stating the general problem being addressed by this particular study.

One sentence summarizing the main result (with the words "here we show" or their equivalent).

Two or three sentences explaining what the main result reveals in direct comparison to what was thought to be the case previously, or how the main result adds to previous knowledge.

One or two sentences to put the results into a more general context.

Two or three sentences to provide a broader perspective, readily comprehensible to a scientist in any discipline, may be included in the first paragraph if the editor considers that the accessibility of the paper is significantly enhanced by their inclusion. Under these circumstances, the length of the paragraph can be up to 300 words. (This example is 190 words without the final section, and 250 words with it).

During cell division, mitotic spindles are assembled by microtubulebased motor proteins 1,2 . The bipolar organization of spindles is essential for proper segregation of chromosomes, and requires plusend-directed homotetrameric motor proteins of the widely conserved kinesin-5 (BimC) family 3 . Hypotheses for bipolar spindle formation include the 'push-pull mitotic muscle' model, in which kinesin-5 and opposing motor proteins act between overlapping microtubules 2,4,5 . However, the precise roles of kinesin-5 during this process are unknown. Here we show that the vertebrate kinesin-5 Eg5 drives the sliding of microtubules depending on their relative orientation. We found in controlled in vitro assays that Eg5 has the remarkable capability of simultaneously moving at ~20 nm s -1 towards the plusends of each of the two microtubules it crosslinks. For anti-parallel microtubules, this results in relative sliding at ~40 nm s -1 , comparable to spindle pole separation rates in vivo 6 . Furthermore, we found that Eg5 can tether microtubule plus-ends, suggesting an additional microtubule-binding mode for Eg5. Our results demonstrate how members of the kinesin-5 family are likely to function in mitosis, pushing apart interpolar microtubules as well as recruiting microtubules into bundles that are subsequently polarized by relative sliding. We anticipate our assay to be a starting point for more sophisticated in vitro models of mitotic spindles. For example, the individual and combined action of multiple mitotic motors could be tested, including minus-end-directed motors opposing Eg5 motility. Furthermore, Eg5 inhibition is a major target of anti-cancer drug development, and a well-defined and quantitative assay for motor function will be relevant for such developments. Perhaps the most important consideration is who the article is for. Scholarly readers might like a structured abstract with links to the previous research and key words. Others are perhaps satisfied with a less-detailed approach. We would probably all enjoy a one-word abstract.

Different aims and purposes imply that there may be different (but overlapping) ways of evaluating abstracts. Some authors, for instance, have evaluated abstracts using checklists, others rating scales, and others readability measures (and some all three-e.g., [START_REF] Hartley | Common weaknesses in traditional abstracts in the social sciences[END_REF][START_REF] Ufnalska | How can we evaluate the quality of abstracts[END_REF]). Some others have employed appropriate readers, whereas others have used some students, writers, and subject matter experts (e.g., [START_REF] Hartley | Improving the clarity of journal abstracts in Psychology[END_REF]). Perhaps current authors might like to employ some of these methods for assessing the efficiency of their abstracts before finalising them.

  Annotated example taken from Nature 435, 114-118 (5 May 2005).

Figure 2 .

 2 Figure 2. "How to construct a Nature summary paragraph" as provided in the Manuscript formatting guide at https://www.nature.com/nature/authors/gta.

http://blog.oxforddictionaries.com/august-2013-update/

Elsevier's web page "Graphical Abstracts" at https://www.elsevier.com/authors/journal-authors/graphical-abstract provides several examples taken from published articles in a variety of disciplines.

Acknowledgments: This article was not funded by any external sources of funding to the authors.

Author Contributions: J.H. and G.C. wrote the paper.

Conflicts of Interest:

The authors declare no conflict of interest.


Emna Amdouni

Yannick Morvan

Bernard Gibaud

Towards an Imaging Biomarker Ontology based on the Open Biological and Biomedical Ontologies Foundry

The importance of imaging biomarkers in biomedical research and drug design is well-acknowledged in the literature, calling for appropriate standards and guidelines for imaging biomarker development, validation and qualification. The objective of this work is to define explicitly, by means of an ontology, the vocabulary pertaining to imaging biomarkers.

Introduction

The wide-scale use and reuse of imaging biomarkers in medical research and clinical practice makes it very important to be able to share information about biomarkers. In [START_REF] Ball | Evaluation of biomarkers and surrogate endpoints in chronic disease[END_REF], the Institute of Medicine stressed the need to define in a consistent and precise way the vocabulary related to biomarkers. Besides, recent works from different communities (imaging research, clinical radiology, genetics, knowledge management, etc.) showed interest in a consistent representation of imaging biomarkers, but, these efforts have not converged to a consensual model, yet. This have motivated us to develop an ontology entitled Imaging Biomarker Ontology (IBO) to formally define basic aspects related to the imaging biomarker concept. IBO is founded on the Open Biological and Biomedical Ontologies (OBO) foundry ( 2007) as well as it takes into consideration some state-of-the-art propositions: e.g. QIBO (2013), BiomRKRS (2014) and QIBA profiles (2007).

Materials and Methods

IBO involves many diverse entities related to imaging biomarkers that concern many domains (medical imaging, metrology, clinical research, informatics, etc.). Therefore, most of classes are aligned with Basic Formal Ontology (BFO) and were developed according to the OBO foundry principles, thus facilitating the integration of terms. Extraction was made following the MIREOT principles, thanks to the OntoFox tool. We have, mainly, reused Ontology for Biomedical Investigations (OBI), Phenotypic Quality Ontology (PATO), Chemical Entities of Biological Interest (ChEBI) Ontology and Foundational Model of Anatomy (FMA) ontology.

Results

Our proposed ontology, IBO, articulates three basic aspects related to imaging biomarkers namely, facet 1: measured biological characteristics, facet 2: measurement protocols and facet 3: role in decision making applications. The first facet defines physical qualities related to imaged objects or processes. We have distinguished between two kinds of qualities: qualities that are related to a continuant (e.g. tumor size, longest diameter, tumor volume, tissue radioactivity concentration, etc.) and qualities that describe an occurrent (e.g. volume change measurement between two time points or more complex processes as volume change speed measurement, etc.). The second facet, specifies imaging requirements and describes performed measurement processes leading to imaging biomarker values. Measurement processes are composed of many sub-processes (subject preparation, image acquisition, image processing, etc.) that involve many material entities (image acquisition device, imaging agent, imaging subject, etc.) as well as roles realized in the context of the processes in which they participate. The third facet represents imaging biomarker applications, namely: diagnosis, prediction, prognosis, treatment assessment and therapy monitoring. All imaging biomarker applications involve some imaging biomarker value which bears a particular role, e.g predictive, diagnostic, etc. and their degrees of validation for specific intended uses.

Conclusion

The aim of IBO is to define explicitly the domain of imaging biomarker in health care context, we have based our work on preliminary work from QIBO and BiomRKRS as well as relevant OBO foundry's ontologies. Future work will aim at applying IBO for representing imaging biomarkers in brain gliomas.


Camille Maumet

Thomas E Nichols

Validity of summary statistics-based mixed-effects group fMRI

Introduction

Statistical analysis of multi-subject functional Magnetic Resonance Imaging (fMRI) data is traditionally done using either: 1) a mixed-effects GLM (MFX GLM) where within-subject variance estimates are used and incorporated into per-subject weights or 2) a random-effects General linear model (GLM) (RFX GLM) where within-subject variance estimates are not used. Both approaches are implemented and available in major neuroimaging software packages including: SPM (MFX analysis; 2nd-Level statistics), FSL (FLAME; OLS) and AFNI (3dMEMA; 3dttest++). While MFX GLM provides the most efficient statistical estimate, its properties are only guaranteed in large samples, and it has been shown that RFX GLM is a valid alternative for one-sample group analyses in fMRI [START_REF] Mumford | Simple group fMRI modeling and inference[END_REF] . We recently showed that MFX GLM for image-based meta-analysis could lead to invalid results in small-samples. Here, we investigate whether this issue also affects group fMRI.

Methods

GLM can be expressed with: Y = Xβ + ε, where Y is the N-vector of subject-level contrast estimates, X the design matrix, β the group parameter to estimate and ε the random error. In group fMRI, the error term has two contributions, from within-and between-subject variance.

MFX GLM.

Using within-subject variance estimates requires a weighted least squares (WLS) approach, where the group parameter β is a weighted average of the subject-level contrasts. The weights are inversely proportional to the sum of the within-and between-subject variances. But in practice, those weights are unknown and have to be estimated from the data leading to a Feasible Generalised Least Squares (FGLS). FGLS is asymptotically efficient but its finite sample properties are unknown [START_REF] Greene | Econometric analysis[END_REF] . We used FSL's 'FLAME 1' FGLS that uses maximum likelihood to estimate between-subject variance, computing a T-statistic compared to a Student distribution with N-1 degrees of freedom (DF) [START_REF] Woolrich | Multilevel linear modelling for FMRI group analysis using Bayesian inference[END_REF] .

RFX GLM.

Under the assumption that the within-subject variance is constant or negligible in comparison to the between-study variance, the weights above are equal and the GLM can be estimated with Ordinary Least Squares (OLS), β estimated as the average of the subject-level contrasts. We used SPM's 2nd level one-sample model, computing a T statistic also compared to a Student distribution with N-1 DF [START_REF] Penny | Statistical parametric mapping: the analysis of functional brain images: the analysis of functional brain images[END_REF] . OLS p-values are exact for any sample size, in contrast to FGLS which are only asymptotically valid [START_REF] Greene | Econometric analysis[END_REF] .

We used Monte Carlo simulations to investigate the validity of MFX and RFX GLMs under varying degrees of within-subject variance heteroscedasticity. Within-subject variances took on 2 values, a 'good' value and a 'high' values of 2, 4, 8 & 16x good values; we considered 4%, 20%, 40%, 80% or 96% of the subjects to have the high values. We fixed the mean within-subject standard error to be equal to the between-subject variance. We assumed 25 subjects per group and 1000 independent time points per subject. Accuracy was assessed by comparing FSL & SPM distributions of -log10 P-values to Monte Carlo -log 10 P-values based on 10ˆ6 realisations.

Results

Fig. 1 presents deviation from theoretical P-values with varying percentage and intensity of high intra-subject variance. For low intensity heteroscedasticity (<= 2x), MFX GLM is valid but becomes increasingly invalid in the presence strong and prevalent high variance subjects. RFX GLM is valid with all settings but displays some conservativeness in the presence of strong heteroscedasticity.

Conclusions Figures

Fig. 1 .

 1 Fig. 1. Deviation of observed from theoretical P-values (difference of observed and Monte Carlo ('true') -log10 p-value distributions) for one-sample tests in the presence of varying percentages of subjects with outlying within-subject variances, high-variance factor 2, 4, 8 or 16, (columns), MFX GLM and RFX GLM (rows). Y-axis is the observed cumulative probability minus Monte Carlo cumulative probability for a given (X-axis) -log10 p-value; positive deflections correspond to inflated false positive risk.

Here we investigated the validity of RFX and MFX GLMs in the presence of varying within-subject variance. As previously shown in the literature[START_REF] Mumford | Simple group fMRI modeling and inference[END_REF] , we observed that RFX GLM is robust to the presence of heteroscedasticity. More surprisingly, MFX GLM was invalid in the presence of high variations in within-subject variances. More work is needed to investigate which of these settings is closest to the patterns present in real fMRI data. In the meantime, we recommend RFX GLM when working with small samples.

Acknowledgments

This work was supported by the Wellcome Trust. The majority of this work was conducted while TEN and CM were at the University of Warwick and used the High Performance Computing cluster of the Department of Statistics, University of Warwick.