Seminar Bertrand Simon (An Exact Algorithm for the Linear Tape Scheduling Problem)
– March 31, 2022
Title: An Exact Algorithm for the Linear Tape Scheduling Problem
Abstract: Magnetic tapes are often considered as an outdated storage technology, yet they are still used to store huge amounts of data. Their main interests are a large capacity and a low price per gigabyte, which come at the cost of a much larger file access time than on disks. With tapes, finding the right ordering of multiple file accesses is thus key to performance. Moving the reading head back and forth along a kilometer long tape has a non-negligible cost and unnecessary movements thus have to be avoided. However, the optimization of tape request ordering has then rarely been studied in the scheduling literature, much less than I/O scheduling on disks. For instance, minimizing the average service time for several read requests on a linear tape remains an open question. Therefore, in this paper, we aim at improving the quality of service experienced by users of tape storage systems, and not only the peak performance of such systems. To this end, we propose a reasonable polynomial-time exact algorithm while this problem and simpler variants have been conjectured NP-hard. We also refine the proposed model by considering U-turn penalty costs accounting for inherent mechanical accelerations. Then, we propose a low-cost variant of our optimal algorithm by restricting the solution space, yet still yielding an accurate suboptimal solution. Finally, we compare our algorithms to existing solutions from the literature on logs of the mass storage management system of a major datacenter. This allows us to assess the quality of previous solutions and the improvement achieved by our low-cost algorithm. Aiming for reproducibility, we make available the complete implementation of the algorithms used in our evaluation, alongside the dataset of tape requests that is, to the best of our knowledge, the first of its kind to be publicly released.
Title: A Brief Glimpse on Emerging Time Integration Methods for Weather and Climate Simulations
Speaker: Martin Schreiber
Abstract:
Weather and climate simulations face new challenges due to changes in computer architectures caused by physical limitations. From a pure computing perspective, algorithms are required to cope with stagnating or even decreasing per-core speed and increasing on-chip parallelism. These trends will continue and already led to research on partly disruptive mathematical and algorithmic reformulations of dynamic cores, e.g., using (additional) parallelism along the time dimension.
This presentation provides an overview and introduction of a variety of promising newly developed and evaluated time integration methods for equations related to prototypical dynamical cores, all aimed at improving the ratio of wall clock time vs. error: Rational Approximation of Exponential Integration (REXI), Parallel Full Approximation Scheme in Space and Time (PFASST) and Semi-Lagrangian methods combined with Parareal. We get improved time-vs.-error rates, but sometimes with additional challenges on the way which needs to be further overcome. Overall, our results motivate further investigation and combination of these methods for operational weather/climate systems.
I gratefully acknowledge collaborators related to this presentation
Jed Brown, Finn Capelle, François Hamon, Terry Haut, Richard Loft, Michael Minion, Matthew Normile, Nathanael Schaeffer, Andreas Schmitt, Pedro S. Peixoto, Raphael Schilling
Polaris-datamove Seminar: Jonatha Anselmi (Title: Recent advances in load balancing: replication, speculation and auto-scaling)
– May 5, 2022
Title: Recent advances in load balancing: replication, speculation and auto-scaling
Abstract: In this talk, we will discuss modern approaches for load balancing in large-scale parallel-server systems: replication, speculation and auto-scaling. Replication sends multiple copies of a given job, simultaneously upon its arrival, to multiple servers and then uses the results from whichever copy responds first. Speculation sends one or multiple copies of a given job only once the system smartly detects it as a "straggler", i.e., as a job taking longer than expected to complete because of some unfortunate runtime phenomenon. Auto-scaling allows the net service capacity, or overall number of servers, to scale up or down in response to the current load and within the same timescale of job dynamics. We will review the state of the art and present some recent results in the flavour of mean-field and fluid limit theorems.
Séminaire Michel Davydov: "Proving the Poisson Hypothesis for Replica-Mean-Field Models"
– June 2, 2022
Title : Proving the Poisson Hypothesis for Replica-Mean-Field Models
Abstract : Modeling particles or agents as nodes of a network interacting over time is a common approach in a variety of fields. Unfortunately, most relevant dynamics involve complex graphs of interactions for which an exact computational treatment is impossible. To circumvent this difficulty, the replica-mean-field approach focuses on randomly interacting replicas of the networks of interest. In the limit of an infinite number of replicas, these networks become analytically tractable under the so-called Poisson Hypothesis, which postulates that replicas become asymptotically independent and arrivals to a given neuron become Poisson distributed. This hypothesis is often conjectured or numerically validated but not proven. We show the validity of the Poisson Hypothesis for large classes of processes that include for example Galves-Löcherbach models from computational neuroscience.
This website uses cookies so that we can provide you with the best user experience possible. Cookie information is stored in your browser and performs functions such as recognising you when you return to our website and helping our team to understand which sections of the website you find most interesting and useful.
Strictly Necessary Cookies
Strictly Necessary Cookie should be enabled at all times so that we can save your preferences for cookie settings.
If you disable this cookie, we will not be able to save your preferences. This means that every time you visit this website you will need to enable or disable cookies again.
