Calendar

Name: Polyhedral Optimization at Runtime, by Manuel Selva.
Start: 2018-03-29T14:00:00+02:00
End: 2018-03-29T15:00:00+02:00
Location: Bâtiment IMAG (442)

March 29, 2018

Polyhedral Optimization at Runtime, by Manuel Selva.

2:00 pm – 3:00 pm
March 29, 2018

The polyhedral model has proven to be very useful to optimize and parallelize a particular class of compute intensive application kernels. A polyhedral optimizer needs to have affine functions defining loop bounds, memory accesses and branching conditions. Unfortunately, this information is not always available at compile time. To broaden the scope of polyhedral optimization opportunities, runtime information can be considered. This talk will highlight the challenges of integrating polyhedral optimization in runtime systems:

- When and how to detect opportunities for polyhedral optimization?
- How to model the observed runtime behavior in a polyhedral fashion?
- How to deal at runtime with the complexity of polyhedral algorithm?

These challenges will be illustrated in the context of both the APOLLO framework targeting C and C++ applications and of the JavaScript engine from Apple.

Bâtiment IMAG (442)

Saint-Martin-d'Hères, 38400

France

View Location

Map

Comments are closed.

News
- Journée au vert POLARIS 2022/05/23
- DATAMOVE/POLARIS picnic 2021/06/22
- DATAMOVE/POLARIS BBQ 2019 2019/06/14
- POLARIS Bootcamp (May 2019) 2019/05/24
- slides of Andras Gyorgy 2016/01/15
Next seminars
- 2:00 pm – 3:00 pm, April 30, 2024 – Seminar Rémi Castera

Events in March–April 2018

M	T	W	T	F	S	S
26	27	28	March 1 Keynote N/A March 1, 2018 Read more	2	3	4
5	6	7	8 Randomized Load Balancing: Asymptotic Optimality of Power-of-d-Choices with Memory by Jonatha Anselmi (Inria Bordeaux) 2:00 pm – 3:00 pm March 8, 2018 In multi-server distributed queueing systems, the access of stochastically arriving jobs to resources is often regulated by a dispatcher. A fundamental problem consists in designing a load balancing algorithm that minimizes the delays experienced by jobs. During the last two decades, the power-of-d-choice algorithm, based on the idea of dispatching each job to the least loaded server out of $d$ servers randomly sampled at the arrival of the job itself, has emerged as a breakthrough in the foundations of this area due to its versatility and appealing asymptotic properties. We consider the power-of-d-choice algorithm with the addition of a local memory that keeps track of the latest observations collected over time on the sampled servers. Then, each job is sent to a server with the lowest observation. We show that this algorithm is asymptotically optimal in the sense that the load balancer can always assign each job to an idle server in the large-server limit. This holds true if and only if the system load $\lambda$ is less than $1-\frac{1}{d}$. If this condition is not satisfied, we show that queue lengths are bounded by $j^\star+1$, where $j^\star\in\mathbb{N}$ is given by the solution of a polynomial equation. This is in contrast with the classic version of the power-of-d-choice algorithm, where queue lengths are unbounded. Our upper bound on the size of the most loaded server, $j^*+1$, is tight and increases slowly when $\lambda$ approaches its critical value from below. For instance, when $\lambda= 0.995$ and $d=2$ (respectively, $d=3$), we find that no server will contain more than just $5$ ($3$) jobs in equilibrium. Our results quantify and highlight the importance of using memory as a means to enhance performance in randomized load balancing. Read more	9	10	11
12	13	14	15 Obtaining Dynamic Scheduling Policies with Simulation and Machine Learning (by Danilo Santos, Datamove) 2:00 pm – 3:00 pm March 15, 2018 Obtaining Dynamic Scheduling Policies with Simulation and Machine Learning Abstract: Dynamic scheduling of tasks in large-scale HPC platforms is normally accomplished using ad-hoc heuristics, based on task characteristics, combined with some backfilling strategy. Defining heuristics that work efficiently in different scenarios is a difficult task, specially when considering the large variety of task types and platform architectures. In this work, we present a methodology based on simulation and machine learning to obtain dynamic scheduling policies. Using simulations and a workload generation model, we can determine the characteristics of tasks that lead to a reduction in the mean slowdown of tasks in an execution queue. Modeling these characteristics using a nonlinear function and applying this function to select the next task to execute in a queue improved the mean task slowdown in synthetic workloads. When applied to real workload traces from highly different machines, these functions still resulted in performance improvements, attesting the generalization capability of the obtained heuristics. Read more	16	17	18
19	20	21	22 A Class of Stochastic Multilayer Networks: Percolation, Exact and Asymptotic Results by Philippe Nain (inria, Lyon) 2:00 pm – 3:00 pm March 22, 2018 Abstract: In this talk, we will introduce a new class of stochastic multilayer networks. A stochastic multilayer network is the aggregation of M networks (one per layer) where each is a subgraph of a foundational network G. Each layer network is the result of probabilistically removing links and nodes from G. The resulting network includes any link that appears in at least K layers. This model, which is an instance of a non-standard site-bond percolation model, finds applications in wireless communication networks with multichannel radios, multiple social networks with overlapping memberships, transportation networks, and, more generally, in any scenario where a common set of nodes can be linked via co-existing means of connectivity. Percolation, exact and asymptotic results will be presented. Bâtiment IMAG (442) Saint-Martin-d'Hères, 38400 France View Location Map Read more	23	24	25
26	27	28 Parallel Space-Time Kernel Density Estimation By Erik Saule (U. Caroline du Nord) 2:00 pm – 3:00 pm March 28, 2018 The exponential growth of available data has increased the need for interactive exploratory analysis. Dataset can no longer be understood through manual crawling and simple statistics. In Geographical Information Systems (GIS), the dataset is often composed of events localized in space and time; and visualizing such a dataset involves building a map of where the events occurred. We focus in this paper on events that are localized among three dimensions (latitude, longitude, and time), and on computing the first step of the visualization pipeline, space-time kernel density estimation (STKDE), which is most computationally expensive. Starting from a gold standard implementation, we show how algorithm design and engineering, parallel decomposition, and scheduling can be applied to bring near real-time computing to space-time kernel density estimation. We validate our techniques on real world datasets extracted from infectious disease, social media, and ornithology. Bâtiment IMAG (442) Saint-Martin-d'Hères, 38400 France View Location Map Read more	29 Polyhedral Optimization at Runtime, by Manuel Selva. 2:00 pm – 3:00 pm March 29, 2018 The polyhedral model has proven to be very useful to optimize and parallelize a particular class of compute intensive application kernels. A polyhedral optimizer needs to have affine functions defining loop bounds, memory accesses and branching conditions. Unfortunately, this information is not always available at compile time. To broaden the scope of polyhedral optimization opportunities, runtime information can be considered. This talk will highlight the challenges of integrating polyhedral optimization in runtime systems: - When and how to detect opportunities for polyhedral optimization? - How to model the observed runtime behavior in a polyhedral fashion? - How to deal at runtime with the complexity of polyhedral algorithm? These challenges will be illustrated in the context of both the APOLLO framework targeting C and C++ applications and of the JavaScript engine from Apple. Bâtiment IMAG (442) Saint-Martin-d'Hères, 38400 France View Location Map Read more	30	31	April 1
2	3	4	5	6	7	8
9	10	11	12 presentation of the Argo project by Swann Perarnau (Argonne National Laboratory) 2:00 pm – 3:00 pm April 12, 2018 Read more	13	14	15
16	17	18	19	20	21	22
23	24	25	26 Approximate equilibria of Colonel Blotto games, by Quan Vu (Polaris and Nokia) 2:00 pm – 3:00 pm April 26, 2018 Resource allocation games are commonly used to model problems in many domains ranging from security to advertising. One of the most important resource allocation games is the Colonel Blotto game: Two players distribute a fixed budget of resources over multiple battlefields to maximize the aggregate value of battlefields they win, each battlefield being won by the player who allocates more resources to it. Despite its long-standing history and importance, the continuous version of the game---where players can choose any fractional allocation---still lacks a complete Nash equilibrium solution in its general form with asymmetric players' budgets and heterogeneous battlefield values. In this work, we propose an approximate equilibrium for this general case. We construct a simple strategy (the independently uniform strategy) and prove that it is an epsilon-equilibrium. We give a theoretical bound on the approximation error in terms of the number of battlefields and players’ budgets which identifies precisely the parameters regime for which our strategy is a good approximation. We also investigate an extension to the discrete version (where players can only have integer allocations), for which we proposed an algorithm to compute very efficiently an approximate equilibrium. We perform numerical experiments that guarantee that we can "safely" use this strategy in practice. Our work extends the scope of application of Colonel Blotto games in several practical cases, especially with large games' parameters (e.g. in advertisements, voting, security, etc.,) Bâtiment IMAG Saint-Martin-d'Hères, 38400 France Map Read more	27	28	29
30	May 1	2	3	4 A data structure for analyzing spatio-temporal correlations of alarms, by Anne Bouillard (Nokia) 2:00 pm – 3:00 pm May 4, 2018 In this talk, I will present a data structure for the analysis of correlations of alarms, for root-cause analysis or prediction purposes. This is a joint work with Marc-Olivier Buob and Maxime Raynal (intern). A sequence of alarms is modeled by a directed acyclic graph. The nodes of the graph are the alarms, that are represented by a symbol and an interval of time. An arc of the graph is interpreted as a potential causality between two alarms. I will first show how to build a "compact" structure storing all the potential causal sequences of alarms and then how to weight this structure so that the actual correlations can be detected. The efficiency of the approach will be demonstrated on toy examples. Bâtiment IMAG (442) Saint-Martin-d'Hères, 38400 France View Location Map Read more	5	6

Meta

Calendar

March 29, 2018

Category: Seminars Polyhedral Optimization at Runtime, by Manuel Selva.

News

Next seminars

Events

Events in March–April 2018

March

Category: Seminars Keynote

Category: Seminars Randomized Load Balancing: Asymptotic Optimality of Power-of-d-Choices with Memory by Jonatha Anselmi (Inria Bordeaux)

Category: Seminars Obtaining Dynamic Scheduling Policies with Simulation and Machine Learning (by Danilo Santos, Datamove)

Category: Seminars A Class of Stochastic Multilayer Networks: Percolation, Exact and Asymptotic Results by Philippe Nain (inria, Lyon)

Category: Seminars Parallel Space-Time Kernel Density Estimation By Erik Saule (U. Caroline du Nord)

Category: Seminars Polyhedral Optimization at Runtime, by Manuel Selva.

April

Category: Seminars presentation of the Argo project by Swann Perarnau (Argonne National Laboratory)

Category: Seminars Approximate equilibria of Colonel Blotto games, by Quan Vu (Polaris and Nokia)

May

Category: Seminars A data structure for analyzing spatio-temporal correlations of alarms, by Anne Bouillard (Nokia)

Meta

Polyhedral Optimization at Runtime, by Manuel Selva.

Keynote

Randomized Load Balancing: Asymptotic Optimality of Power-of-d-Choices with Memory by Jonatha Anselmi (Inria Bordeaux)

Obtaining Dynamic Scheduling Policies with Simulation and Machine Learning (by Danilo Santos, Datamove)

A Class of Stochastic Multilayer Networks: Percolation, Exact and Asymptotic Results by Philippe Nain (inria, Lyon)

Parallel Space-Time Kernel Density Estimation By Erik Saule (U. Caroline du Nord)

Polyhedral Optimization at Runtime, by Manuel Selva.

presentation of the Argo project by Swann Perarnau (Argonne National Laboratory)

Approximate equilibria of Colonel Blotto games, by Quan Vu (Polaris and Nokia)

A data structure for analyzing spatio-temporal correlations of alarms, by Anne Bouillard (Nokia)