dataesr/scientific-paragraphs-categorization huggingface dataset:
Since BSS data are naturally heavily linked to the weather, this means that overfitting algorithms will struggle with predicting the number of predictors on rainy days (such as October 8th). This interesting behavior is exhibited in the next subsection. To illustrate the behavior of the data, Figure  7  provides the curve of the number of visitors during the learning and test phases and Figure  8  shows the loadings of four Vélib' stations during the first week of September. Two of these stations correspond to touristic areas with different behaviors: one is the closest one to the Orsay museum and one is one of the closest ones to the Eiffel tower. The other two correspond to large railway stations (which also happen to be large subway stations). We will show in the next subsection that.
Results We applied the algorithms of Section 6 to the OrsayVelib database. Since the sparsity of this regression problem is not absolutely certain, we also added a non-sparse method to the benchmark: ridge regression with a cross-validated regularization parameter. The test errors and sparsity patterns obtained are detailed in Table  2  (for the sake of clarity, only the five best methods are displayed). One can notice that spinyReg has the lowest generalization error and that it selects fewer variables than its competitors. Figure  9  allows to compare the true number of visitors during the test phase with the predicted values of the four methods. We can notice that, as expected, all algorithms struggle with October 8th, which was a rainy day. On this specific day, spinyReg is (especially in the afternoon) the closest one to the truth.
Randriamanamihaga et al. , 2014)2014). The predictive variables that will interest us for our regression problem are the percentages of parked bikes (or loadings) for all the Vélib' stations of Paris. These percentages are available through the open data API provided by At each hour, the number of visitors present in the museum constitutes the response variable of our regression problem. The predictors are the loadings at each hour of the p = 1158 Vélib' stations in Paris. Only the hours corresponding to opening days (from 8am to 6pm, except Mondays) of the museum are kept. The month of September 2014 constitutes the learning set (with n = 316 observations), and the first two weeks of October 2014 the test set (see Figure JCDecaux 1. 7. 2 The "OrsayVelib" database (Bouveyron et al. , 2014; astest collection of impressionist paintings in the world, it holds for example Manet's Le Déjeuner sur l'herbe or Van Gogh's Nuit étoilée sur le Rhône.
When integrating hard, soft and non-real-time tasks in general purpose operating systems, it is necessary to provide temporal isolation so that the timing properties of one task do not depend on the behaviour of the others. However, strict budget enforcement can lead to inefficient use of the computational resources in the presence of tasks with variable workload. Many resource reclaiming algorithms have been proposed in the literature for single processor scheduling, but not enough work exists for global scheduling in multiprocessor systems. In this paper we propose two reclaiming algorithms for multiprocessor global scheduling and we prove their correctness. We also present their implementation in the Linux kernel and we compare their performance on synthetic experiments.
Introduction The Resource Reservation Framework  [20, 1]  is an effective technique to integrate the scheduling of real-time tasks in general-purpose systems, as demonstrated by the fact that it has been recently implemented in the Linux kernel  [14]. One of the most important properties provided by resource reservations is temporal isolation: the worst-case performance of a task does not depend on the temporal behaviour of the other tasks running in the system. This property can be enforced by limiting the amount of time for which each task can execute in a given period. 1 In some situations, a strict enforcement of the executed runtime (as done by the hard reservation mechanism that is currently implemented in the Linux kernel) can be problematic for tasks characterized by highly-variable, or difficult to predict, execution times: allocating the budget based on the task' Worst Case Execution Time (WCET) can result in a waste of computational resources; on the other hand, allocating it based on a value smaller than the WCET can cause a certain number of deadline misses.
by considering a global variable that keeps track of the execution time not used by all the tasks in the system (without considering the CPUs/cores on which the tasks execute), and by distributing such an unused execution time to the tasks. This approach will be referred to as parallel reclaiming in this paper, because the execution time not used by one single task can be distributed to multiple tasks that execute in parallel on different CPUs/cores; 2. by considering multiple per-CPU/core (per-runqueue, in the Linux kernel slang) variables each representing the unused bandwidth that can be distributed to the tasks executing on the corresponding CPU/core. This approach will be referred to as sequential reclaiming in this paper, because the execution time not used by one single task is associated to a CPU/core, and cannot be distributed to multiple tasks executing simultaneously.
This paper compares the two mentioned approaches by extending the GRUB (Greedy Reclamation of Unused Bandwidth)  [17]  reclaiming algorithm to support multiple processors according to sequential reclaiming and parallel reclaiming. The comparison is performed both from the theoretical point of view (by formally analysing the schedulability of the obtained algorithm) and by running experiments on a real implementation of this extension, named M-GRUB. Such implementation of M-GRUB reclaiming (that can do either parallel or sequential reclaiming) is based on the Linux kernel and extends the SCHED DEADLINE scheduling policy. The paper is organised as follows: in Section 2 we recall the related work. In Section 3 we present our system model and introduce the definitions and concepts used in the paper.
It is an extension of the CASH algorithm to the multiprocessor case, which additionally includes a rule for reclaiming unused bandwidth by aperiodic tasks. The algorithm uses the utilisation based test by Goossens, Funk and Baruah  [12]  as a base schedulability test for the servers. It distinguishes two kinds of servers: servers for periodic tasks (whose utilisation is reclaimed using capacity-based mechanism) and servers for aperiodic tasks, whose bandwidth is reclaimed with a technique similar to the parallel reclaiming that we propose in Section 5. 1. However, M-CASH has never been implemented in a real OS kernel. On the other hand, the GRUB algorithm  [17]  has been implemented in the Linux kernel  [2] , after extending the algorithm to support multiple CPUs, but the multiprocessor extensions used in this implementation have not been formally analysed nor validated from a theoretical point of view.
In each period, a server is reserved at least a maximum budget, or runtime, Q i = U i P i. The execution platform consists of m identical processors (Symmetric Multiprocessor Platform, or SMP). In this paper we use the Global Earliest Deadline First (G-EDF) scheduling algorithm: all the tasks are ordered by increasing deadlines of the servers, and the m active tasks with the earliest deadlines are scheduled for execution on the m CPUs. The logical priority queue of G-EDF is implemented in Linux by a set of runqueues, one per each CPU/core, and some accessory data structures for making sure that the m highest-priority jobs are executed at each instant (see  [13]  for a description of the implementation).
CBS and GRUB As anticipated in Section 3, each server is characterised by a period P i , a bandwidth U i and a maximum budget Q i = U i P i. In addition, each server maintains the following dynamic variables: the server deadline d i , denoting at every instant the server priority, and the server budget q i , indicating the remaining computation time allowed in the current server period. At time t, a server can be in one of the following states: ActiveContending, if there is some job of the served task that has not yet completed; ActiveNon-Contending, if all jobs of the served task have completed, but the server has already consumed all the available bandwidth (see the transition rules below for a characterisation of this state); Inactive, if all jobs of the server's task have completed and the server bandwidth can be reclaimed (see the transition rules below), and Recharging, if the server has jobs to execute, but the budget is currently exhausted and needs to be recharged (this state is generally known as "throttled" in the Linux kernel, or "depleted" in the real-time literature).
Then, to keep the set of servers still schedulable w. r. t. GFB, we can initialise each variable to a value U x = m-(m-1)Umax-U m. When it comes to the BCL test, we can think of adding m servers to the system, each one with infinitesimal period and bandwidth equal to U x. To allow each server to use free bandwidth as much as possible while still guaranteeing the schedulability, the following condition should hold. ∀k, i =k min( Ŵi,k , P k -Q k ) + mU x P k < m(P k -Q k ) U x < min k P k -Q k P k - i =k min( Ŵi,k , P k -Q k ) mP k Finally we take the maximum between U x and U x , since only one of the two test needs to be verified. U inact [p] = max {U x , U x }. ( 9 ) 6 Implementation The parallel and sequential reclaiming techniques described in the previous sections have been implemented in the Linux kernel, extending the SCHED DEADLINE scheduling policy  [14].
Parallel reclaiming implementation Parallel reclaiming requires to keep track of the total inactive bandwidth in a global (per-root domain) variable U inact which is updated when tasks move from an Active states to the Inactive state or vice-versa. Then, the budget decrease rate of every executing server depends on this global variable (see Equation (  6 )). For each executing SCHED DEADLINE task, the scheduler periodically accounts the executed time, decreasing the current budget (called "runtime" in the Linux kernel) of the task at each tick (or when a context switch happens). When a reclaiming strategy is used, the amount of time decreased from the budget depends on the value of the global variable U inact. This means that, when a server changes its state to Inactive (or Active-Contending) and the value of U inact changes all the CPUs should be signalled to update the budgets of the executing task before U inact is changed.
Randomly generated tasks The first set of experiments has been performed by executing sets of randomly generated real-time tasks with the rt-app application 1. A set of 100 task sets with utilisation U = 2. 5 has been generated using the taskgen  [11]  script, and the task sets that are schedulable according to the BCL and GFB tests have been identified. Some first rt-app runs confirmed that these task sets can actually run on the Linux kernel (using SCHED DEADLINE) without missing any deadline. Then, the reclaiming mechanisms have been tested as follows: for each schedulable task set γ = {(C i , T i )} generated by taskgen, a task set Γ = {τ i } has been generated, where τ i has period T i and execution time uniformly distributed between αγC i and γC i (hence, the WCET of task τ i is γC i ), and is scheduled by a server with parameters (Q i = C i , P i = T i ).
Experiments on real applications In the next set of experiments, the performance of a real application (the mplayer video player 2  ) has been evaluated. In particular, mplayer has been modified to measure the "Audio/Video delay", defined as the difference of the presentation timestamps of two audio and video frames that are reproduced simultaneously. A negative value of the Audio/Video delay means that video frames are played in advance with respect to the corresponding audio frames, while a positive value indicates that the video is late with respect to the audio (probably because mplayer has not been able to decode the video frames in time). When this value becomes too large, audio and video are perceived out of synch, and the quality perceived by the user is badly affected. When mplayer is executed as a SCHED DEADLINE task, it is pretty easy to set the reservation period P = 1/f ps, where f ps is the frame rate (in frames per second) of the video; however, correctly dimensioning the maximum budget/runtime Q is much more difficult.
If Q is slightly under-dimensioned (larger than the average time needed to decode a frame, but smaller than the maximum time), the Audio/Video delay can become too large affecting the quality, and a reclaiming mechanism can help in improving the perceived quality. For example, Figure  3  shows the evolution of the Audio/Video delay experienced by mplayer when reproducing a full-D1 mpeg4 video (with vorbis audio) with Q = 4. 5ms and P = 40ms (the video is 25 frames per second, so P = 1s/25 = 40ms). The experiment has been repeated executing mplayer alone on an idle 4-cores system ("No Reclaiming, idle system" line) or together with other real-time tasks (implemented by rt-app, in the "No Reclaiming, loaded system" line). In the "loaded system" case, the total utilisation was about 2. 2 and the task set resulted to be schedulable according to both BCL and GFB.
Conclusions In this paper, we proposed two different reclaiming mechanisms for real-time tasks scheduled by G-EDF on multiprocessor platforms, named parallel and sequential reclaiming. After proving their correctness, we described their implementation on the Linux OS, and compared their performance on synthetic experiments. Parallel reclaiming requires more approximations in its implementation, however, in average it performs better than the sequential reclaiming. On the other hand, sequential reclaiming can guarantee the real-time schedulability of a large number of tasks, as it allows to use a different admission test, and is characterised by a simpler implementation. However, it performs slightly worse in average. In the future we plan to conduct further investigations comparing the two strategies, and to use more advanced admission tests.
Discussion The landscape of genetic variation is shaped by multiple evolutionary processes, including mutation, drift, recombination, gene flow, natural selection and demographic history. The combined effect of these different factors can vary considerably both across the genome and between species, resulting in different patterns of evolutionary dynamics. The complete genome assemblies that we generated for multiple representative strains from both domesticated and wild yeasts provide a valuable dataset to explore such patterns with unprecedented resolution. Considering the dynamics across the genome, it has been observed in many organisms (e. g. fruitfly  (Anderson et al. 2008) , Arabidopsis  (Kuo et al. 2006 ) and human  (Linardopoulou et al. 2005 )) that eukaryotic subtelomeres usually exhibit exceptional variability in comparison with the internal chromosomal cores.
Assembly evaluation and manual refinement We retrieved the reference genome assemblies (including both the nuclear and mitochondrial genome) of (http://downloads. yeastgenome. org/sequence/S288C_reference/) (version R64-1-1). We obtained the reference nuclear genome assembly of S. paradoxus (strain CBS432) from the Saccharomyces Genome Resequencing Project (SGRP) data depository (ftp://ftp. sanger. ac. uk/pub/users/dmc/yeast/latest/misc/para2/ref/genome. fa) and its mitochondrial genome assembly from NCBI Genbank (accession number: JQ862335). For each polished PacBio assembly, we first used RepeatMasker (v4. 0. 5) to soft-mask all the repetitive regions (option: -species fungi -xsmall -gff). The soft-masked assemblies were subsequently aligned to the reference genome using the nucmer program from the MUMmer (v3.
Illumina sequencing, reads mapping, and error correction In addition to the PacBio sequencing, we also sequenced each strain with deep Illumina paired-end sequencing (~200X-500X) at Institut Curie (Paris, France). We examined the raw Illumina reads via  FastQC (v0. 11. 3 ) and performed adapter-removing and quality-based trimming by trimmomatic (v0. 33)  (Bolger et al. 2014 ) (trimming options: ILLUMINACLIP:adapters. fa:2:30:10 SLIDINGWINDOW:5:20 MINLEN:36). For each strain, the trimmed reads were mapped to the corresponding PacBio assemblies by BWA (v0. 7. 12)  (Li and Durbin 2009). The resulting reads alignments were subsequently processed by samtools (v1. 2)  (Li et al. 2009) , picard tools (v1. 131) (http://broadinstitute. github. io/picard/) and GATK (v3. 5-0)  (McKenna et al. 2010). The Pilon pipeline (v1.
Assembly completeness comparison for different annotation features We compared our S288c PacBio assembly with three published S. cerevisiae assemblies based on PacBio, Oxford Nanopore and Illumina MiSeq sequencing technologies respectively  (Kim et al. 2014; Goodwin et al. 2015). We aligned these three assemblies as well as our S288c PacBio assembly to the S. cerevisiae reference genome using the nucmer program from the MUMmer (v3. 23) package  (Kurtz et al. 2004 ). The nucmer alignments were filtered by delta-filter (from the same package) (option: -1). We converted the output file to the "BED" format and use bedtools (v2. 15. 0)  (Quinlan and Hall 2010)  to calculate the intersection between our genome alignment and various annotation features (e. g. chromosomes, genes, retrotransposable elements, telomeres, etc) of the S.
Annotation of the protein coding genes and tRNA genes For nuclear genes, we set up an integrative pipeline that combines three existing annotation tools to form an evidence-leveraged final annotation. First, we used the RATT package  (Otto et al. 2011)  to directly transfer the S. cerevisiae reference genome annotation to our annotated genome based on whole genome alignment. The "RATT. config_euk" file shipped with RATT was used for our transfer. The seqret program from the EMBOSS package  (Rice et al. 2000)  was used for format conversion between the "gff" and "embl" formats. A custom Perl script was used to further convert the seqret's gff output file to properly formatted gff3 file. Furthermore, we used the Yeast Genome Annotation Pipeline (YGAP) online pipeline  (Proux-Wéra et al. 2012)  to annotate our genome assemblies with default option (except the option "ordering scaffolds by size").
YGAP is a pipeline specifically designed for annotating yeast genomes based on gene sequence homology and synteny conservation curated in the Yeast Gene Order Browser (YGOB) database. A custom Perl script was used to convert the YGAP annotation output to gff3 format while removing dubious open reading frames (ORFs) labeled by the YGAP pipeline. These dubious ORFs might be frameshifted or untranslable or overlapping with other ORFs. Also, we noticed that some ORFs annotated by YGAP might be out-of-frame (i. e. the annotated genomic coordinates went beyond the actual scaffold length) or redundant. These ORFs were further removed by our Perl script. Finally, we used the Maker pipeline (v2. 31. 8)  (Holt and Yandell 2011)  to perform de novo gene discovery with EST/proteome alignment support. For the Maker pipeline, repeatmasking was first performed by RepeatMasker (v4.
(Liti et al. 2013) , and the proteome of S. eubayanus (strain FM1318) based on Baker et al. 2015  (Baker et al. 2015). These EST and protein sequences were aligned with the PacBio genome assemblies using blastn and blastx respectively (both from the NCBI-BLAST+ package (v2. 2. 30+)  (Camacho et al. 2009 )) and further polished by exonerate (v2. 2. 0)  (Slater and Birney 2005). Other custom settings that we used for the Maker pipeline include: "min_contig=10000, min_protein=30, split_hit=1500, single_exon=1, single_length=250 and correct_est_fusion=1". The gene annotations produced by RATT, YGAP, and Maker together with the EST and proteome alignment evidence generated by Maker were further leveraged by EVidenceModeler (EVM)  (Haas et al. 2008)  to form a final integrative version of annotation.
The GTRGAMMA model was used for phylogenetic inference. The rapid bootstrapping method built in RAxML was used to assess the stability of internal nodes (option: -# 100 for 100 rapid bootstrap searches). The final ML tree was visualized in FigTree (v1. 4. 2) (http://tree. bio. ed. ac. uk/software/figtree/). For the consensus gene tree approach, we built individual gene trees with RAxML using the method as we used for the concatenated tree. Subsequently, we used ASTRAL (v4. 7. 12)  (Mirarab et al. 2014)  to estimate consensus species tree based on the topology of individual gene trees. The normalized quartet score was calculated to assess the reliability of the final species tree given individual gene trees. For mitochondrial genes, we performed the phylogenetic analysis based on the six one-to-one orthologous genes (ATP6, ATP8, COB, COX1, COX2 and COX3) following the same protocol.
Conserved synteny blocks identification We used the SynChro program from the CHROnicle package (version: January 2015)  (Drillon et al. 2013 (Drillon et al. , 2014) )  to identify conserved synteny blocks. We prepared the input files for SynChro with custom Perl scripts to provide information about various annotated features (centromere, protein-coding genes, tRNAs, and Tys) together with the genome assembly and proteome sequences. SynChro subsequently performed all possible pairwise comparisons to identify synteny blocks shared in the given strain pair. Multiple plots were also generated by SynChro for easy visualization of the identified synteny blocks.
Identification of balanced and unbalanced structural rearrangements We identified balanced genome rearrangements (inversion, translocation, and transposition) by the ReChro from the CHROnicle package (version: January 2015)  (Drillon et al. 2013 (Drillon et al. , 2014)). We set the synteny block stringency parameter delta=1 for the main analysis. A complementary run was performed with delta=0 to identify single gene inversions. As for unbalanced genome rearrangements (large insertion, deletion and duplication), we first generated whole genome alignment for every strain pair by nucmer  (Kurtz et al. 2004 ) (options: -maxmatch -c 500) and submitted the results to the Assemblytics web server (http://assemblytics. com/)  (Nattestad and Schatz 2016)  for identifying all potential insertions, deletions and duplications/contractions in the corresponding pairwise comparison.
Gene ontology analysis The CDS sequences of all SGD reference genes (with dubious genes excluded) were BLAST against NCBI non-redundant (nr) database using blastx (E-value cutoff = 1E-3) and further annotated by BLAST2GO (v. 3. 2)  (Conesa et al. 2005; Götz et al. 2008)  to generate gene ontology (GO) mapping for the genome-wide background gene set. For all the genes involved in unbalanced structural rearrangements, their corresponding orthologs in the SGD reference gene set (when available) was used to compile a non-redundant test gene set. We performed Fisher's exact test  (Fisher 1922)  to detect significantly enriched GO terms of our test gene set relative to the genome-wide background. False discovery rate (FDR) (cutoff: 0. 05)  (Benjamini and Hochberg 1995)  was used for multiple correction.
Molecular evolutionary rate and CNV estimation For the one-to-one orthologs in each strain pair, we calculate synonymous substitution rate (dS), nonsynonymous substitution rate (dN) and nonsynonymous-to-synonymous substitution rate ratio (dN/dS) using the yn00 program from the PAML package (v4. 8a) (Yang 2007). Yang & Nielsen (2000)  model  (Yang and Nielsen 2000)  was used for this calculation. As for measuring copy number variation (CNV), we calculated the proportion of genes involved in CNV (i. e. those are not one-to-one orthologs) in the two compared strains. We denoted this measurement as P CNV , a quantity analogous to the Pdistance in sequence comparison. The Poisson distance correction was further applied to account for multiple changes at the same gene loci. The Poisson corrected distance D CNV can be given as  !"# = -ln (1 - !"# ).