Search

Round Robin is a widely used scheduling policy, used primarily because it is intuitively fair, splitting the resources evenly among the jobs. Little is known, however, of its fairness with respect to completion times for the jobs, which is typically measured using the l p -norm of the completion times of the jobs for small p. This paper studies Round Robin's performance for the l p -norm of the completion times when scheduling n preemptive jobs on a single machine, for all integral p ≥ 1 . We show that if all jobs arrive at the same time Round Robin's approximation ratio is exactly p + 1 p . When jobs arrive over time, we show that Round Robin's competitive ratio is at most 4 for any p ≥ 1 .

The severe acute respiratory syndrome coronavirus 2 (SARS-CoV-2) pandemic has brought renewed attention to respiratory aerosol and droplet generation. While many studies have robustly quantified aerosol (20 µm diameter) generated by a cohort of 76 adults and children using a water-sensitive paper droplet deposition approach. Unvoiced and voiced activities spanning different levels of loudness, different lengths of sustained phonation, and a specific manner of articulation in isolation were investigated. We find that oral articulation drives >20 µm droplet generation, with breathing generating virtually no droplets and speaking and singing generating on the order of 250 droplets min−1. Lip trilling, which requires extensive oral articulation, generated the most droplets, whereas shouting “Hey,” which requires minimal oral articulation, generated relatively few droplets. Droplet size distributions were all broadly consistent, and no significant differences between the children and adult cohorts were identified. By comparing the aerosol and droplet emissions for the same participants, the full size distribution of respiratory aerosol (0.5–1000 µm) is reported. Although 20 µm droplets dominate the mass concentration. Accurate quantification of aerosol concentrations in the 10–70 μm size range remains very challenging; more robust aerosol analysis approaches are needed to characterize this size range.

This corrigendum fixes an incorrect claim in the paper Gupta et al. [Gupta V, Moseley B, Uetz M, Xie Q (2020) Greed works—online algorithms for unrelated machine stochastic scheduling. Math. Oper. Res. 45(2):497–516.], which led us to claim a performance guarantee of 6 for a greedy algorithm for deterministic online scheduling with release times on unrelated machines. The result is based on an upper bound on the increase of the objective function value when adding an additional job [Formula: see text] to a machine [Formula: see text] (Gupta et al., lemma 6). It was pointed out by Sven Jäger from Technische Universität Berlin that this upper bound may fail to hold. We here present a modified greedy algorithm and analysis, which leads to a performance guarantee of 7.216 instead. Correspondingly, also the claimed performance guarantee of [Formula: see text] in theorem 4 of Gupta et al. for the stochastic online problem has to be corrected. We obtain a performance bound [Formula: see text].

We show that there exist $k$-colorable matroids that are not $(b,c)$-decomposable when $b$ and $c$ are constants. A matroid is $(b,c)$-decomposable, if its ground set of elements can be partitioned into sets $X_1, X_2, \ldots, X_l$ with the following two properties. Each set $X_i$ has size at most $ck$. Moreover, for all sets $Y$ such that $|Y \cap X_i| \leq 1$ it is the case that $Y$ is $b$-colorable. A $(b,c)$-decomposition is a strict generalization of a partition decomposition and, thus, our result refutes a conjecture from arXiv:1911.10485v2 .

In this paper we introduce the Matroid Cup Game. This cup game generalizes the One- and p-Cup Games. We show that a natural greedy strategy maintains max fill O ( log ⁡ n ) in the Matroid Cup Game with mild resource augmentation. Further, we introduce a new objective for cup game: the total water, which is the amount of water across all cups. We develop a novel Emptier strategy that maintain O ( r n ) total water without resource augmentation. We also reveal a novel relationship between max fill and total water, which leads to an intuitive analysis of the max fill bounds in the One- and p-Cup Games.

We consider the matroid intersection cover problem. This is a special case of set cover where the sets are derived from the intersection of matroids. We introduce a technique for computing matroid intersection covers. We give polynomial-time algorithms to compute partition decompositions for matroids that commonly arise in combinatorial optimization problems. We then give a polynomial-time algorithm for computing matroid intersection covers given the partition decompositions of the matroids. Combining these algorithms, we obtain an O ( 1 ) -approximation algorithm when each of the O ( 1 ) matroids is of a standard type.

Background The coronavirus disease-19 (COVID-19) pandemic led to the prohibition of group-based exercise and the cancellation of sporting events. Evaluation of respiratory aerosol emissions is necessary to quantify exercise-related transmission risk and inform mitigation strategies. Methods Aerosol mass emission rates are calculated from concurrent aerosol and ventilation data, enabling absolute comparison. An aerodynamic particle sizer (0.54–20 μm diameter) samples exhalate from within a cardiopulmonary exercise testing mask, at rest, while speaking and during cycle ergometer-based exercise. Exercise challenge testing is performed to replicate typical gym-based exercise and very vigorous exercise, as determined by a preceding maximally exhaustive exercise test. Results We present data from 25 healthy participants (13 males, 12 females; 36.4 years). The size of aerosol particles generated at rest and during exercise is similar (unimodal ~0.57–0.71 µm), whereas vocalization also generated aerosol particles of larger size (i.e. was bimodal ~0.69 and ~1.74 µm). The aerosol mass emission rate during speaking (0.092 ng s−1; minute ventilation (VE) 15.1 L min−1) and vigorous exercise (0.207 ng s−1, p = 0.726; VE 62.6 L min−1) is similar, but lower than during very vigorous exercise (0.682 ng s−1, p −1). Conclusions Vocalisation drives greater aerosol mass emission rates, compared to breathing at rest. Aerosol mass emission rates in exercise rise with intensity. Aerosol mass emission rates during vigorous exercise are no different from speaking at a conversational level. Mitigation strategies for airborne pathogens for non-exercise-based social interactions incorporating vocalisation, may be suitable for the majority of exercise settings. However, the use of facemasks when exercising may be less effective, given the smaller size of particles produced.

This paper explores hierarchical clustering in the case where pairs of points have dissimilarity scores (e.g. distances) as a part of the input. The recently introduced objective for points with dissimilarity scores results in every tree being a ½ approximation if the distances form a metric. This shows the objective does not make a significant distinction between a good and poor hierarchical clustering in metric spaces.Motivated by this, the paper develops a new global objective for hierarchical clustering in Euclidean space. The objective captures the criterion that has motivated the use of divisive clustering algorithms: that when a split happens, points in the same cluster should be more similar than points in different clusters. Moreover, this objective gives reasonable results on ground-truth inputs for hierarchical clustering.The paper builds a theoretical connection between this objective and the bisecting k-means algorithm. This paper proves that the optimal 2-means solution results in a constant approximation for the objective. This is the first paper to show the bisecting k-means algorithm optimizes a natural global objective over the entire tree.

We consider virtual circuit routing protocols with an objective of minimizing energy in a network of components that are speed scalable, and that may be shut down when idle. We assume the standard ...

This paper considers the recently popular beyond-worst-case algorithm analysis model which integrates machine-learned predictions with online algorithm design. We consider the online Steiner tree problem in this model for both directed and undirected graphs. Steiner tree is known to have strong lower bounds in the online setting and any algorithm's worst-case guarantee is far from desirable. This paper considers algorithms that predict which terminal arrives online. The predictions may be incorrect and the algorithms' performance is parameterized by the number of incorrectly predicted terminals. These guarantees ensure that algorithms break through the online lower bounds with good predictions and the competitive ratio gracefully degrades as the prediction error grows. We then observe that the theory is predictive of what will occur empirically. We show on graphs where terminals are drawn from a distribution, the new online algorithms have strong performance even with modestly correct predictions., To appear in AAAI 2022

We develop a machine learning approach to detect and discriminate elephants from other species, and to recognise important behaviours such as running and rumbling, based only on seismic data generated by the animals. We demonstrate our approach using data acquired in the Kenyan savanna, consisting of 8000 h seismic recordings and 250 k camera trap pictures. Our classifiers, different convolutional neural networks trained on seismograms and spectrograms, achieved 80%–90% balanced accuracy in detecting elephants up to 100 m away, and over 90% balanced accuracy in recognising running and rumbling behaviours from the seismic data. We release the dataset used in this study: SeisSavanna represents a unique collection of seismic signals with the associated wildlife species and behaviour. Our results suggest that seismic data offer substantial benefits for monitoring wildlife, and we propose to further develop our methods using dense arrays that could result in a seismic shift for wildlife monitoring.

Aerosol particles of respirable size are exhaled when individuals breathe, speak and sing and can transmit respiratory pathogens between infected and susceptible individuals. The COVID-19 pandemic has brought into focus the need to improve the quantification of the particle number and mass exhalation rates as one route to provide estimates of viral shedding and the potential risk of transmission of viruses. Most previous studies have reported the number and mass concentrations of aerosol particles in an exhaled plume. We provide a robust assessment of the absolute particle number and mass exhalation rates from measurements of minute ventilation using a non-invasive Vyntus Hans Rudolf mask kit with straps housing a rotating vane spirometer along with measurements of the exhaled particle number concentrations and size distributions. Specifically, we report comparisons of the number and mass exhalation rates for children (12–14 years old) and adults (19–72 years old) when breathing, speaking and singing, which indicate that child and adult cohorts generate similar amounts of aerosol when performing the same activity. Mass exhalation rates are typically 0.002–0.02 ng s−1from breathing, 0.07–0.2 ng s−1from speaking (at 70–80 dBA) and 0.1–0.7 ng s−1from singing (at 70–80 dBA). The aerosol exhalation rate increases with increasing sound volume for both children and adults when both speaking and singing.

The lunar permanently shadowed regions (PSRs) are expected to host large quantities of water-ice, which are key for sustainable exploration of the Moon and beyond. In the near future, NASA and other entities plan to send rovers and humans to characterize water-ice within PSRs. However, there exists only limited information about the small-scale geomorphology and distribution of ice within PSRs because the orbital imagery captured to date lacks sufficient resolution and/or signal. In this paper, we develop and validate a new method of post-processing LRO NAC images of PSRs. We show that our method is able to reveal previously unseen geomorphological features such as boulders and craters down to 3 meters in size, whilst not finding evidence for surface frost or near-surface ice. Our post-processed images significantly facilitate the exploration of PSRs by reducing the uncertainty of target selection and traverse/mission planning., Nature Communications, 12, ISSN:2041-1723

International audience; short paper, no abstract

African elephants ( Loxodonta africana ) are sentient and intelligent animals that use a variety of vocalizations to greet, warn or communicate with each other. Their low-frequency rumbles propagate through the air as well as through the ground and the physical properties of both media cause differences in frequency filtering and propagation distances of the respective wave. However, it is not well understood how each mode contributes to the animals’ abilities to detect these rumbles and extract behavioural or spatial information. In this study, we recorded seismic and co-generated acoustic rumbles in Kenya and compared their potential use to localize the vocalizing animal using the same multi-lateration algorithms. For our experimental set-up, seismic localization has higher accuracy than acoustic, and bimodal localization does not improve results. We conclude that seismic rumbles can be used to remotely monitor and even decipher elephant social interactions, presenting us with a tool for far-reaching, non-intrusive and surprisingly informative wildlife monitoring.

Recently, learning-based approaches have achieved impressive results in the field of low-light image denoising. Some state of the art approaches employ a rich physical model to generate realistic training data. However, the performance of these approaches ultimately depends on the realism of the physical model, and many works only concentrate on everyday photography. In this work we present a denoising approach for extremely low-light images of permanently shadowed regions (PSRs) on the lunar surface, taken by the Narrow Angle Camera on board the Lunar Reconnaissance Orbiter satellite. Our approach extends existing learning-based approaches by combining a physical noise model of the camera with real noise samples and training image scene selection based on 3D ray tracing to generate realistic training data. We also condition our denoising model on the camera’s environmental metadata at the time of image capture (such as the camera’s temperature and age), showing that this improves performance. Our quantitative and qualitative results show that our method strongly outperforms the existing calibration routine for the camera and other baselines. Our results could significantly impact lunar science and exploration, for example by aiding the identification of surface water-ice and reducing uncertainty in rover and human traverse planning into PSRs.

The paper considers scheduling jobs online to minimize the objective $$\sum _{i \in [n]}w_ig(C_i-r_i)$$ , where $$w_i$$ is the weight of job i, $$r_i$$ is its release time, $$C_i$$ is its completion time and g is any non-decreasing convex function. It is known that the clairvoyant algorithm Highest-Density-First (HDF) is $$(2+\epsilon )$$ -speed O(1)-competitive for this objective on a single machine for any fixed $$ 0< \epsilon < 1$$ (Im et al., in: ACM-SIAM symposium on discrete algorithms, pp 1254–1265, 2012). In this paper, we give the first non-trivial results for this problem when g is a non-decreasing convex function and the algorithm must be non-clairvoyant. More specifically, our results include: The paper gives the first non-trivial upper-bound on multiple machines even if the algorithm is allowed to be clairvoyant. All performance guarantees above hold for all non-decreasing convex functions gsimultaneously. The positive results are supplemented by almost matching lower bounds. We show that any algorithm that is oblivious to g is not O(1)-competitive with speed augmentation less than 2 on a single machine. Further, any non-clairvoyent algorithm that knows the function g cannot be O(1)-competitive with speed augmentation less than $$\sqrt{2}$$ on a single machine or $$(2-\frac{1}{m})$$ on m identical machines.

This work introduces novel parallel methods for weighted longest common subsequence (WLCS) and its generalization, all-substrings WLCS. Previous work developed efficient algorithms for these problems via Monge matrix multiplication, which is a limiting factor for further improvement. Diverging from these approaches, we relax the algorithm’s optimality guarantee in a controlled way, using a different, natural dynamic program which can be sketched and solved in a divide-and-conquer manner that is efficient to parallelize.

We consider the problem of efficiently estimating the size of the inner join of a collection of preprocessed relational tables from the perspective of instance optimality analysis. The run time of instance optimal algorithms is comparable to the minimum time needed to verify the correctness of a solution. Previously instance optimal algorithms were only known when the size of the join was small (as one component of their run time that was linear in the join size). We give an instance optimal algorithm for estimating the join size for all instances, including when the join size is large, by removing the dependency on the join size. As a byproduct, we show how to sample rows from the join uniformly at random in a comparable amount of time.

We investigate the use of unsupervised machine learning to understand and extract valuable information from thermal measurements of the lunar surface. We train a variational autoencoder (VAE) to reconstruct observed variations in lunar surface temperature from over 9 yr of Diviner Lunar Radiometer Experiment data and in doing so learn a fully data-driven thermophysical model of the lunar surface. The VAE defines a probabilistic latent model that assumes the observed surface temperature variations can be described by a small set of independent latent variables and uses a deep convolutional neural network to infer these latent variables and to reconstruct surface temperature variations from them. We find it is able to disentangle five different thermophysical processes from the data, including (1) the solar thermal onset delay caused by slope aspect, (2) effective albedo, (3) surface thermal conductivity, (4) topography and cumulative illumination, and (5) extreme thermal anomalies. Compared to traditional physics-based modeling and inversion, our method is extremely efficient, requiring orders of magnitude less computational power to invert for underlying model parameters. Furthermore our method is physics-agnostic and could therefore be applied to other space exploration data sets, immediately after the data is collected and without needing to wait for physical models to be developed. We compare our approach to traditional physics-based thermophysical inversion and generate new, VAE-derived global thermal anomaly maps. Our method demonstrates the potential of artificial intelligence-driven techniques to complement existing physical models as well as for accelerating lunar and space exploration in general., The Planetary Science Journal, 1 (2), ISSN:2632-3338

This paper develops an algorithmic foundation for automated management of the multilevel-memory systems common to new supercomputers. In particular, the High-Bandwidth Memory (HBM) of these systems has a similar latency to that of DRAM and a smaller capacity, but it has much larger bandwidth. Systems equipped with HBM do not fit in classic memory-hierarchy models due to HBM's atypical characteristics. Unlike caches, which are generally managed automatically by the hardware, programmers of some current HBM-equipped supercomputers can choose to explicitly manage HBM themselves. This process is problem specific and resource intensive. Vendors offer this option because there is no consensus on how to automatically manage HBM to guarantee good performance, or whether this is even possible. In this paper, we give theoretical support for automatic HBM management by developing simple algorithms that can automatically control HBM and deliver good performance on multicore systems. HBM management is starkly different from traditional caching both in terms of optimization objectives and algorithm development. Since DRAM and HBM have similar latencies, minimizing HBM misses (provably) turns out not to be the right memory-management objective. Instead, we directly focus on minimizing makespan. In addition, while cache-management algorithms must focus on what pages to keep in cache; HBM management requires answering two questions: (1) which pages to keep in HBM and (2) how to use the limited bandwidth from HBM to DRAM. It turns out that the natural approach of using LRU for the first question and FCFS (First-Come-First-Serve) for the second question is provably bad. Instead, we provide a priority based approach that is simple, efficiently implementable and $O(1)$-competitive for makespan when all multicore threads are independent.

Modern data centers are tasked with processing heterogeneous workloads consisting of various classes of jobs. These classes differ in their arrival rates, size distributions, and job parallelizability. With respect to paralellizability, some jobs are elastic, meaning they can parallelize linearly across many servers. Other jobs are inelastic, meaning they can only run on a single server. Although job classes can differ drastically, they are typically forced to share a single cluster. When sharing a cluster among heterogeneous jobs, one must decide how to allocate servers to each job at every moment in time. In this paper, we design and analyze allocation policies which aim to minimize the mean response time across jobs, where a job's response time is the time from when it arrives until it completes. We model this problem in a stochastic setting where each job may be elastic or inelastic. Job sizes are drawn from exponential distributions, but are unknown to the system. We show that, in the common case where elastic jobs are larger on average than inelastic jobs, the optimal allocation policy is Inelastic-First, giving inelastic jobs preemptive priority over elastic jobs. We obtain this result by introducing a novel sample path argument. We also show that there exist cases where Elastic-First (giving priority to elastic jobs) performs better than Inelastic-First. We then provide the first analysis of mean response time under both Elastic-First and Inelastic-First by leveraging recent techniques for solving high-dimensional Markov chains.

In this paper, we study the problem of incremental maintenance of Datalog programs and model it as a scheduling problem on DAGs. We design provably good time- and memory-efficient scheduling algorithms for (re)executing a Datalog program where some (but not necessarily all) of the inputs have changed. We prove that our schedulers, called LevelBased and LevelBased with lookahead, have asymptotically improved running time and space efficiency when compared with benchmark algorithms used in production at LogicBlox.The main result of the paper is a hybrid scheduler, which combines LevelBased with the production LogicBlox scheduler (or any other heuristic scheduler). The hybrid scheduler achieves strong worst-case guarantees and robustness without losing out on the best-case behavior of the production LogicBlox scheduler. Our experiments show that the hybrid scheduler results in similar or improved total execution times compared to LogicBlox scheduler, while consistently reducing the scheduling overhead—by as much as 50% on some datasets. This hybrid scheme requires little to no overhead but provides predictability and reliability, which are crucial in a commercial application such as LogicBlox.

This paper establishes performance guarantees for online algorithms that schedule stochastic, nonpreemptive jobs on unrelated machines to minimize the expected total weighted completion time. Prior work on unrelated machine scheduling with stochastic jobs was restricted to the offline case, and required linear or convex programming relaxations for the assignment of jobs to machines. The algorithms introduced in this paper are purely combinatorial. The performance bounds are of the same order of magnitude as those of earlier work, and depend linearly on an upper bound on the squared coefficient of variation of the jobs' processing times. Specifically for deterministic processing times, without and with release times, the competitive ratios are 4 and 7.216, respectively. As to the technical contribution, the paper shows how dual fitting techniques can be used for stochastic and nonpreemptive scheduling problems., Comment: Preliminary version appeared in IPCO 2017

New optical technologies offer the ability to reconfigure network topologies dynamically, rather than setting them once and for all. This is true in both optical wide area networks (optical WANs) and in datacenters, despite the many differences between these two settings. Because of these new technologies, there has been a surge of both practical and theoretical research on algorithms to take advantage of them. In particular, Jia et al. [INFOCOM '17] designed online scheduling algorithms for dynamically reconfigurable topologies for both the makespan and sum of completion times objectives. In this paper, we work in the same setting but study an objective that is more meaningful in an online setting: the sum of flow times. The flow time of a job is the total amount of time that it spends in the system, which may be considerably smaller than its completion time if it is released late. We provide competitive algorithms for the online setting with speed augmentation, and also give a lower bound proving that speed augmentation is in fact necessary. As a side effect of our techniques, we also improve and generalize the results of Jia et al. on completion times by giving an $O(1)$-competitive algorithm for arbitrary sizes and release times even when nodes have different degree bounds, and moreover allow for the weighted sum of completion times (or flow times)., Comment: 10 pages. Appears in INFOCOM 2020

Online algorithms are a hallmark of worst case optimization under uncertainty. On the other hand, in practice, the input is often far from worst case, and has some predictable characteristics. A recent line of work has shown how to use machine learned predictions to circumvent strong lower bounds on competitive ratios in classic online problems such as ski rental and caching. We study how predictive techniques can be used to break through worst case barriers in online scheduling. The makespan minimization problem with restricted assignments is a classic problem in online scheduling theory. Worst case analysis of this problem gives Ω(log m) lower bounds on the competitive ratio in the online setting. We identify a robust quantity that can be predicted and then used to guide online algorithms to achieve better performance. Our predictions are compact in size, having dimension linear in the number of machines, and can be learned using standard off the shelf methods. The performance guarantees of our algorithms depend on the accuracy of the predictions, given predictions with error η, we show how to construct O(log η) competitive fractional assignments. We then give an online algorithm that rounds any fractional assignment into an integral schedule. Our algorithm is O((log log m)3)-competitive and we give a nearly matching Ω(log log m) lower bound for online rounding algorithms.1 Altogether, we give algorithms that, equipped with predictions with error η, achieve O(log η (log log m)3) competitive ratios, breaking the Ω(log m) lower bound even for moderately accurate predictions.

Hierarchical clustering is a fundamental tool in data mining, machine learning and statistics. Popular hierarchical clustering algorithms include top-down divisive approaches such as bisecting k-means, k-median, and k-center and bottom-up agglomerative approaches such as single-linkage, average-linkage, and centroid-linkage. Unfortunately, only a few scalable hierarchical clustering algorithms are known, mostly based on the single-linkage algorithm. So, as datasets increase in size every day, there is a pressing need to scale other popular methods.

Parallelizable jobs typically consist of multiple phases of computation, where the job is more parallelizable in some phases and less parallelizable in others. For example, in a database, a query may consist of a highly parallelizable table scan, followed by a less parallelizable table join. In the past, this phase-varying parallelizability was summarized by a single sub-linear speedup curve that measures a job’s average parallelizability over its entire lifetime. Today, however, modern systems have fine-grained knowledge of the exact phase each job is in at every moment in time. Unfortunately, these systems do not fully leverage this real-time feedback when scheduling parallelizable jobs. Theory has failed to produce practical phase-aware scheduling policies, and thus scheduling in current systems is largely heuristic. A phase-aware scheduling policy must decide, given its knowledge of each job’s current phase, how many servers or cores to allocate to each job in the system at every moment in time. This paper provides the first stochastic model of a system processing parallelizable jobs composed of phases. Using our model, we derive an optimal phase-aware scheduling policy that minimizes the mean response time across jobs. Our provably optimal policy, Inelastic-First ( IF ), gives strict priority to jobs that are currently in less parallelizable phases. We validate our theoretical results using a simulation of a database running queries from the Star Schema Benchmark. We compare IF to a range of policies from both systems and theory, and show that IF reduces mean response time by up to a factor of 3.

This paper considers scheduling parallelizable jobs in the non-clairvoyant speed scaling setting to minimize the objective of weighted flow time plus energy. Previously, strong lower bounds were shown on this model in the unweighted setting even when the algorithm is given a constant amount of resource augmentation over the optimal solution. However, these lower bounds were given only for certain families of algorithms that do not recognize the parallelizability of alive jobs. In this work, we circumvent previous lower bounds shown and give a scalable algorithm under the natural assumption that the algorithm can know the current parallelizability of a job. When a general power function is considered, this is also the first algorithm that has a constant competitive ratio for the problem using any amount of resource augmentation.

The simulation of seismic waves is a core task in many geophysical applications. Numerical methods such as Finite Difference (FD) modelling and Spectral Element Methods (SEM) are the most popular techniques for simulating seismic waves in complex media, but for many tasks their computational cost is prohibitively expensive. In this work we present two types of deep neural networks as fast alternatives for simulating seismic waves in horizontally layered and faulted 2D acoustic media. In contrast to the classical methods both networks are able to simulate the seismic response at multiple locations within the media in a single inference step, without needing to iteratively model the seismic wavefield through time, resulting in an order of magnitude reduction in simulation time. This speed improvement could pave the way to real-time seismic simulation and benefit seismic inversion algorithms based on forward modelling, such as full waveform inversion. Our first network is able to simulate seismic waves in horizontally layered media. We use a WaveNet network architecture and show this is more accurate than a standard convolutional network design. Furthermore we show that seismic inversion can be carried out by retraining the network with its inputs and outputs reversed, offering a fast alternative to existing inversion techniques. Our second network is significantly more general than the first; it is able to simulate seismic waves in faulted media with arbitrary layers, fault properties and an arbitrary location of the seismic source on the surface of the media. It uses a convolutional autoencoder network design and is conditioned on the input source location. We investigate the sensitivity of different network designs and training hyperparameters on its simulation accuracy. We compare and contrast this network to the first network. To train both networks we introduce a time-dependent gain in the loss function which improves convergence. We discuss the relative merits of our approach with FD modelling and how our approach could be generalised to simulate more complex Earth models.

Many algorithms have been proposed to efficiently schedule parallel jobs on a multicore and/or multiprocessor machine to minimize average flow time, and the complexity of the problem is well understood. In practice, the problem is far from being understood. A reason for the gap between theory and practice is that all theoretical algorithms have prohibitive overheads in actual implementation including using many preemptions. One of the flagship successes of scheduling theory is the work-stealing scheduler. Work-stealing is used for optimizing the flow time of a single parallel job executing on a single machine with multiple cores and has a strong performance in theory and in practice. Consequently, it is implemented in almost all parallel runtime systems. This paper seeks to bridge theory and practice for scheduling parallel jobs that arrive online, by introducing an adaptation of the work-stealing scheduler for average flow time. The new algorithm Distributed Random Equi-Partition (DREP) has strong practical and theoretical performance. Practically, the algorithm has the following advantages: (1) it is non-clairvoyant; (2) all processors make scheduling decisions in a decentralized manner requiring minimal synchronization and communications; and (3) it requires a small and bounded number of preemptions. Theoretically, we prove that DREP is (4+e)-speed O(1/e^3)-competitive for average flow time. We have empirically evaluated DREP using both simulations and actual implementation by modifying the Cilk Plus work-stealing runtime system. The evaluation results show that DREP performs well compared to other scheduling strategies, including those that are theoretically good but cannot be faithfully implemented in practice.

Motivated by fundamental applications in databases and relational machine learning, we formulate and study the problem of answering functional aggregate queries (FAQ) in which some of the input factors are defined by a collection of additive inequalities between variables. We refer to these queries as FAQ-AI for short. To answer FAQ-AI in the Boolean semiring, we define relaxed tree decompositions and relaxed submodular and fractional hypertree width parameters. We show that an extension of the InsideOut algorithm using Chazelle's geometric data structure for solving the semigroup range search problem can answer Boolean FAQ-AI in time given by these new width parameters. This new algorithm achieves lower complexity than known solutions for FAQ-AI. It also recovers some known results in database query answering. Our second contribution is a relaxation of the set of polymatroids that gives rise to the counting version of the submodular width, denoted by #subw. This new width is sandwiched between the submodular and the fractional hypertree widths. Any FAQ and FAQ-AI over one semiring can be answered in time proportional to #subw and respectively to the relaxed version of #subw. We present three applications of our FAQ-AI framework to relational machine learning: k-means clustering, training linear support vector machines, and training models using non-polynomial loss. These optimization problems can be solved over a database asymptotically faster than computing the join of the database relations.

International audience

Online scheduling of parallelizable jobs has received a significant amount of attention recently. Scalable algorithms are known—that is, algorithms that are (1 + e)-speed O(1)-competitive for any fixed e>0. Previous research has focused on the case where each job’s parallelizability can be expressed as a concave speedup curve. However, there are cases where a job’s speedup curve can be convex. Considering convex speedup curves has received attention in the offline setting, but, to date, there are no positive results in the online model. In this work, we consider scheduling jobs with convex or concave speedup curves for the first time in the online setting. We give a new algorithm that is (1 + e)-speed O(1)-competitive. There are strong lower bounds on the competitive ratio if the algorithm is not given resource augmentation over the adversary, and thus this is essentially the best positive result one can show for this setting.

Learning synaptic weights of spiking neural network (SNN) models that can reproduce target spike trains from provided neural firing data is a central problem in computational neuroscience and spike-based computing. The discovery of the optimal weight values can be posed as a supervised learning task wherein the weights of the model network are chosen to maximize the similarity between the target spike trains and the model outputs. It is still largely unknown whether optimizing spike train similarity of highly recurrent SNNs produces weight matrices similar to those of the ground truth model. To this end, we propose flexible heuristic supervised learning rules, termed Pre-Synaptic Pool Modification (PSPM), that rely on stochastic weight updates in order to produce spikes within a short window of the desired times and eliminate spikes outside of this window. PSPM improves spike train similarity for all-to-all SNNs and makes no assumption about the post-synaptic potential of the neurons or the structure of the network since no gradients are required. We test whether optimizing for spike train similarity entails the discovery of accurate weights and explore the relative contributions of local and homeostatic weight updates. Although PSPM improves similarity between spike trains, the learned weights often differ from the weights of the ground truth model, implying that connectome inference from spike data may require additional constraints on connectivity statistics. We also find that spike train similarity is sensitive to local updates, but other measures of network activity such as avalanche distributions, can be learned through synaptic homeostasis.

When a computer system schedules jobs there is typically a significant cost associated with preempting a job during execution. This cost can be incurred from the expensive task of saving the memory’s state or from loading data into and out of memory. Thus, it is desirable to schedule jobs non-preemptively to avoid the costs of preemption. There is a need for non-preemptive system schedulers for desktops, servers, and data centers. Despite this need, there is a gap between theory and practice. Indeed, few non-preemptive online schedulers are known to have strong theoretical guarantees. This gap is likely due to strong lower bounds on any online algorithm for popular objectives. Indeed, typical worst-case analysis approaches, and even resource-augmented approaches such as speed augmentation, result in all algorithms having poor performance guarantees. This article considers online non-preemptive scheduling problems in the worst-case rejection model where the algorithm is allowed to reject a small fraction of jobs. By rejecting only a few jobs, this article shows that the strong lower bounds can be circumvented. This approach can be used to discover algorithmic scheduling policies with desirable worst-case guarantees. Specifically, the article presents algorithms for the following three objectives: minimizing the total flow-time, minimizing the total weighted flow-time plus energy where energy is a convex function, and minimizing the total energy under the deadline constraints. The algorithms for the first two problems have a small constant competitive ratio while rejecting only a constant fraction of jobs. For the last problem, we present a constant competitive ratio without rejection. Beyond specific results, the article asserts that alternative models beyond speed augmentation should be explored to aid in the discovery of good schedulers in the face of the requirement of being online and non-preemptive.

A 4D broadband assessment has been performed in a deep offshore West Africa environment using repeated dual-sensor streamer acquisitions. Three sail lines have been re-acquired only a few weeks after the original acquisition with standard 4D acquisition consideration. The study has compared the data repeatability metric NRMS along the processing sequences using, on one side, a reconstructed band limited 4D data corresponding to a single hydrophone and on the other side an extended bandwidth 4D data using the up-going wavefield only. Because the datasets have been recorded using the same acquisition, the main differences come from the bandwidth discrepancy and the variable sea-state. The 4D “Up-going on Up-going” preserves, for all processing steps, around 1% NRMS benefit against the 4D hydrophone-only. Because the NRMS comparison is biased by the dominant frequency discrepancy, the 1% gain does not fully reflect the detectability advantage of the 4D broadband. The NRMS analysis on the low frequency part has demonstrated the clear improvement on 4D broadband and a qualitative evaluation on the 4D differences has highlighted the negative effect of the sea-state on the hydrophone-only 4D results.

Motivated by fundamental applications in databases and relational machine learning, we formulate and study the problem of answering functional aggregate queries (FAQ) in which some of the input factors are defined by a collection of additive inequalities between variables. We refer to these queries as FAQ-AI for short. To answer FAQ-AI in the Boolean semiring, we define relaxed tree decompositions and relaxed submodular and fractional hypertree width parameters. We show that an extension of the InsideOut algorithm using Chazelle’s geometric data structure for solving the semigroup range search problem can answer Boolean FAQ-AI in time given by these new width parameters. This new algorithm achieves lower complexity than known solutions for FAQ-AI. It also recovers some known results in database query answering. Our second contribution is a relaxation of the set of polymatroids that gives rise to the counting version of the submodular width, denoted by #subw. This new width is sandwiched between the submodular and the fractional hypertree widths. Any FAQ and FAQ-AI over one semiring can be answered in time proportional to #subw and respectively to the relaxed version of #subw. We present three applications of our FAQ-AI framework to relational machine learning: k -means clustering, training linear support vector machines, and training models using non-polynomial loss. These optimization problems can be solved over a database asymptotically faster than computing the join of the database relations.

In this paper, we consider scheduling parallelizable jobs online to maximize the throughput or profit of the schedule. In particular, a set of n jobs arrive online and each job \(J_i\) arriving at time \(r_i\) has an associated function \(p_i(t)\) which is the profit obtained for finishing job \(J_i\) at time \(t+r_i\). Each job can have its own arbitrary non-increasing profit function. We consider the case where each job is a parallel job that can be represented as a directed acyclic graph (DAG). We give the first non-trivial results for the profit scheduling problem for DAG jobs and show O(1)-competitive algorithms using resource augmentation.

We consider scheduling parallelizable jobs online to maximize the throughput or profit of the schedule. A set of n jobs arrive online and each job Ji has an associated function pi(t), the profit obtained for finishing job Ji at time t. Each job has its own arbitrary non-increasing profit function. We consider the case where each job is a parallel job that can be represented as a directed acyclic graph (DAG). We give the first non-trivial results for the profit scheduling problem for DAG jobs showing O(1)-competitive algorithms using resource augmentation.

Modern science and engineering is driven by massively large data sets and its advance heavily relies on massively parallel computing platforms such as Spark, MapReduce, and Hadoop. Theoretical models have been proposed to understand the power and limitations of such platforms. Recent study of developed theoretical models has led to the discovery of new algorithms that are fast and efficient in both theory and practice, thereby beginning to unlock their underlying power. Given recent promising results, the area has turned its focus on discovering widely applicable algorithmic techniques for solving problems efficiently. In this paper we make progress towards this goal by giving a principled framework for simulating sequential dynamic programs in the distributed setting. In particular, we identify two key properties, monotonicity and decomposability, which allow us to derive efficient distributed algorithms for problems possessing the properties. We showcase our framework by considering several core dynamic programming applications, Longest Increasing Subsequence, Optimal Binary Search Tree, and Weighted Interval Selection. For these problems, we derive algorithms yielding solutions that are arbitrarily close to the optimum, using O(1) rounds and O(n/m) memory on each machine where n is the input size and m is the number of machines available.