6.1.1 MatchMaker

• Name:
  Maximum matchings in bipartite graphs
• Keywords:
  Graph algorithmics, Matching
• Scientific Description:
  The implementations of ten exact algorithms and four heuristics for solving the problem of finding a maximum cardinality matching in bipartite graphs are provided.
• Functional Description:
  This software provides algorithms to solve the maximum cardinality matching problem in bipartite graphs.
• URL:
  https://­gitlab.­inria.­fr/­bora-ucar/­matchmaker
• Publications:
  hal-00786548, hal-00763920
• Contact:
  Bora Uçar
• Participants:
  Kamer Kaya, Johannes Langguth

6.1.2 PaStiX

• Name:
  Parallel Sparse matriX package
• Keywords:
  Linear algebra, High-performance calculation, Sparse Matrices, Linear Systems Solver, Low-Rank compression
• Scientific Description:
  PaStiX is based on an efficient static scheduling and memory manager, in order to solve 3D problems with more than 50 million of unknowns. The mapping and scheduling algorithm handles a combination of 1D and 2D block distributions. A dynamic scheduling can also be applied to take care of NUMA architectures while taking into account very precisely the computational costs of the BLAS 3 primitives, the communication costs and the cost of local aggregations.
• Functional Description:

  PaStiX is a scientific library that provides a high performance parallel solver for very large sparse linear systems based on block direct and block ILU(k) methods. It can handle low-rank compression techniques to reduce the computation and the memory complexity. Numerical algorithms are implemented in single or double precision (real or complex) for LLt, LDLt and LU factorization with static pivoting (for non symmetric matrices having a symmetric pattern). The PaStiX library uses the graph partitioning and sparse matrix block ordering packages Scotch or Metis.

  The PaStiX solver is suitable for any heterogeneous parallel/distributed architecture when its performance is predictable, such as clusters of multicore nodes with GPU accelerators or KNL processors. In particular, we provide a high-performance version with a low memory overhead for multicore node architectures, which fully exploits the advantage of shared memory by using a hybrid MPI-thread implementation.

  The solver also provides some low-rank compression methods to reduce the memory footprint and/or the time-to-solution.

• URL:
  https://­gitlab.­inria.­fr/­solverstack/­pastix
• Contact:
  Pierre Ramet
• Participants:
  Tony Delarue, Grégoire Pichon, Mathieu Faverge, Esragul Korkmaz, Pierre Ramet
• Partners:
  INP Bordeaux, Université de Bordeaux

7.1.1 Resilient scheduling of moldable jobs to cope with silent errors.

Participants: Anne Benoit [Vanderbilt University], Valentin Le Fèvre [Vanderbilt University], Lucas Perotin [Vanderbilt University], Yves Robert [Vanderbilt University], Padma Raghavan [Vanderbilt University], Hongyang Sun [Vanderbilt University].

We have focused on the resilient scheduling of moldable parallel jobs on high-performance computing (HPC) platforms. Moldable jobs allow for choosing a processor allocation before execution, and their execution time obeys various speedup models. The objective is to minimize the overall completion time of the jobs, or the makespan, when jobs can fail due to silent errors and hence may need to be re-executed after each failure until successful completion. Our work generalizes the classical scheduling framework for failure-free jobs. To cope with silent errors, we introduce two resilient scheduling algorithms, LPA-List and Batch-List, both of which use the List strategy to schedule the jobs. Without knowing a priori how many times each job will fail, LPA-List relies on a local strategy to allocate processors to the jobs, while Batch-List schedules the jobs in batches and allows only a restricted number of failures per job in each batch. We prove new approximation ratios for the two algorithms under several prominent speedup models (e.g., roofline, communication, Amdahl, power, monotonic, and a mixed model). An extensive set of simulations is conducted to evaluate different variants of the two algorithms, and the results show that they consistently outperform some baseline heuristics. Overall, our best algorithm is within a factor of 1.6 of a lower bound on average over the entire set of experiments, and within a factor of 4.2 in the worst case.

Preliminary results with a subset of speedup models were published in Cluster 2020  37, and this year, an extended version appeared in IEEE Transactions on Computers 8.

7.1.2 Optimal Checkpointing Strategies for Iterative Applications.

Participants: Yishu Du [Inria Bordeaux], Loris Marchal [Inria Bordeaux], Yves Robert [Inria Bordeaux], Guillaume Pallez [Inria Bordeaux].

We have studied how to provide an optimal checkpointing strategy to protect iterative applications from fail-stop errors. We consider a general framework, where the application repeats the same execution pattern by executing consecutive iterations, and where each iteration is composed of several tasks. These tasks have different execution lengths and different checkpoint costs. Assume that there are $n$ tasks and that task $a_i$, where $0\le i<n$, has execution time $t_i$ and checkpoint cost $c_i$. A naive strategy would checkpoint after each task. Another naive strategy would checkpoint at the end of each iteration. A strategy inspired by the Young/Daly formula would work for $\sqrt{2\mu c_{\mathrm{𝑎𝑣𝑒}}}$ seconds, where $\mu$ is the application MTBF and $c_{\mathrm{𝑎𝑣𝑒}}$ the average checkpoint time, and checkpoint at the end of the current task (and repeat). Another strategy, also inspired by the Young/Daly formula, would select the task $a_{min}$ with smallest checkpoint cost $c_{min}$ and would checkpoint after every $p^{\mathrm{th}}$ instance of that task, leading to a checkpointing period $pT$, where $T={\sum }_{i=0}^{n-1}{a}_i$ is the time per iteration. One would choose the period so that $pT\approx \sqrt{2\mu c_{min}}$ to obey the Young/Daly formula. All these naive and Young/Daly strategies are suboptimal. Our main contribution in this work has been to show that the optimal checkpoint strategy is globally periodic, and to design a dynamic programming algorithm that computes the optimal checkpointing pattern. This pattern may well checkpoint many different tasks, and this across many different iterations. We have shown through simulations, both from synthetic and real-life application scenarios, that the optimal strategy outperforms the naive and Young/Daly strategies.

This work has been published in IEEE Transaction of Parallel and Distributed Computers 11.

7.2.1 Max-stretch minimization on an edge-cloud platform.

Participants: Anne Benoit, Redouane Elghazi, Yves Robert.

We have considered the problem of scheduling independent jobs that are generated by processing units at the edge of the network. These jobs can either be executed locally, or sent to a centralized cloud platform that can execute them at greater speed. Such edge-generated jobs may come from various applications, such as e-health, disaster recovery, autonomous vehicles or flying drones. The problem is to decide where and when to schedule each job, with the objective to minimize the maximum stretch incurred by any job. The stretch of a job is the ratio of the time spent by that job in the system, divided by the minimum time it could have taken if the job was alone in the system. We formalize the problem and explain the differences with other models that can be found in the literature. We prove that minimizing the max-stretch is NP-complete, even in the simpler instance with no release dates (all jobs are known in advance). This result comes from the proof that minimizing the max-stretch with homogeneous processors and without release dates is NP-complete, a complexity problem that was left open before this work. We design several algorithms to propose efficient solutions to the general problem, and we conduct simulations based on real platform parameters to evaluate the performance of these algorithms.

This work appeared in the proceedings of IPDPS 2021 17.

7.2.2 Update on the Asymptotic Optimality of LPT.

Participants: Anne Benoit [Univ. Besançon], Redouane Elghazi [Univ. Besançon], Louis-Claude Canon [Univ. Besançon], Pierre-Cyrille Héam [Univ. Besançon].

When independent tasks are to be scheduled onto identical processors, the typical goal is to minimize the makespan. A simple and efficient heuristic consists in scheduling first the task with the longest processing time (LPT heuristic), and to plan its execution as soon as possible. While the performance of LPT has already been largely studied, in particular its asymptotic performance, we revisit results and propose a novel analysis for the case of tasks generated through uniform integer compositions. Also, we perform extensive simulations to empirically assess the asymptotic performance of LPT. Results demonstrate that the absolute error rapidly tends to zero for several distributions of task costs, including ones studied by theoretical models, and realistic distributions coming from benchmarks.

This work appeared in the proceedings of EuroPar 2021 16.

7.2.3 Shelf schedules for independent moldable tasks to minimize the energy consumption.

Participants: Anne Benoit [Univ. Besançon], Redouane Elghazi [Univ. Besançon], Louis-Claude Canon [Univ. Besançon], Pierre-Cyrille Héam [Univ. Besançon].

Scheduling independent tasks on a parallel platform is a widely-studied problem, in particular when the goal is to minimize the total execution time, or makespan ($P\left|\right|C_{max}$ problem in Graham's notations). Also, many applications do not consist of sequential tasks, but rather of parallel moldable tasks that can decide their degree of parallelism at execution (i.e., on how many processors they are executed). Furthermore, since the energy consumption of data centers is a growing concern, both from an environmental and economical point of view, minimizing the energy consumption of a schedule is a main challenge to be addressed. One should decide, for each task, on how many processors it is executed, and at which speed the processors are operated, with the goal to minimize the total energy consumption. We further focus on co-schedules, where tasks are partitioned into shelves, and we prove that the problem of minimizing the energy consumption remains NP-complete when static energy is consumed during the whole duration of the application. We are however able to provide an optimal algorithm for the schedule within one shelf, i.e., for a set of tasks that start at the same time. Several approximation results are derived, and simulations are performed to show the performance of the proposed algorithms.

This work appeared in the proceedings of SBAC-PAD 2021 15.

7.2.4 Locality-Aware Scheduling of Independent Tasks for Runtime Systems.

Participants: Maxime Gonthier [Inria Bordeaux], Loris Marchal [Inria Bordeaux], Samuel Thibault [Inria Bordeaux].

A now-classical way of meeting the increasing demand for computing speed by HPC applications is the use of GPUs and/or other accelerators. Such accelerators have their own memory, which is usually quite limited, and are connected to the main memory through a bus with bounded bandwidth. Thus, particular care should be devoted to data locality in order to avoid unnecessary data movements. Task-based runtime schedulers have emerged as a convenient and efficient way to use such heterogeneous platforms. When processing an application, the scheduler has the knowledge of all tasks available for processing on a GPU, as well as their input data dependencies. Hence, it is able to order tasks and prefetch their input data in the GPU memory (after possibly evicting some previously-loaded data), while aiming at minimizing data movements, so as to reduce the total processing time. In this work, we focus on how to schedule tasks that share some of their input data (but are otherwise independent) on a GPU. We provide a formal model of the problem, exhibit an optimal eviction strategy, and show that ordering tasks to minimize data movement is NP-complete. We review and adapt existing ordering strategies to this problem, and propose a new one based on task aggregation. These strategies have been implemented in the StarPU runtime system. We present their performance on tasks from tiled 2D and 3D matrix products. Our experiments demonstrate that using our new strategy together with the optimal eviction policy reduces the amount of data movement as well as the total processing time.

A preliminary version of this work has been presented at the COLOC workshop of EuroPar 2021 20. An extended version is available as a research report 35.

7.2.5 Taming tail latency in key-value stores: a scheduling perspective.

Participants: Anthony Dugois [Univ. Besançon], Loris Marchal [Univ. Besançon], Anne Benoit [Univ. Besançon], Louis-Claude Canon [Univ. Besançon], Sonia Ben Mokhtar [Univ. Lyon 1], Étienne Rivière [Univ. Louvain, Belgique].

Distributed key-value stores employ replication for high availability. Yet, they do not always efficiently take advantage of the availability of multiple replicas for each value, and read operations often exhibit high tail latencies. Various replica selection strategies have been proposed to address this problem, together with local request scheduling policies. It is difficult, however, to determine what is the absolute performance gain each of these strategies can achieve. We present a formal framework allowing the systematic study of request scheduling strategies in key-value stores. We contribute a definition of the optimization problem related to reducing tail latency in a replicated key-value store as a minimization problem with respect to the maximum weighted flow criterion. By using scheduling theory, we show the difficulty of this problem, and therefore the need to develop performance guarantees. We also study the behavior of heuristic methods using simulations, which highlight which properties are useful for limiting tail latency: for instance, the EFT strategy—which uses the earliest available time of servers—exhibits a tail latency that is less than half that of state-of-the-art strategies, often matching the lower bound. Our study also emphasizes the importance of metrics such as the stretch to properly evaluate replica selection and local execution policies.

This work has been accepted at IPDPS 2022 24. An extended version is available as a research report 28.

7.2.6 Evaluating Task Dropping Strategies for Overloaded Real-Time Systems.

Participants: Yiqin Gao [Inria Bordeaux], Yves Robert [Inria Bordeaux], Frédéric Vivien [Inria Bordeaux], Guillaume Pallez [Inria Bordeaux].

This work proposes evaluation criteria and scheduling strategies for the analysis of overloaded real-time systems. A single task periodic task must be processed by a server, under an arbitrary deadline (i.e., the relative deadline is larger than the period). The system is overloaded, which means that the period is smaller than the average execution time of the task instances. A task instance that does not meet its deadline is automatically killed. The problem is then to minimize the deadline-miss ratio. This work builds upon techniques from queueing theory and proposes a new approach for real-time systems.

A preliminary version of this work was accepted as a work-in-progress at the RTSS 2021 conference 19.

7.3.1 Trading Performance for Memory in Sparse Direct Solvers using Low-rank Compression.

Participants: Grégoire Pichon [ENS Lyon], Loris Marchal [ENS Lyon], Thibault Marette [ENS Lyon], Frédéric Vivien.

Sparse direct solvers using Block Low-Rank compression have been proven efficient to solve problems arising in many real-life applications. Improving those solvers is crucial for being able to 1) solve larger problems and 2) speed up computations. A main characteristic of a sparse direct solver using low-rank compression is at what point in the algorithm the compression is performed. There are two distinct approaches: (1) all blocks are compressed before starting the factorization, which reduces the memory as much as possible, or (2) each block is compressed as late as possible, which usually leads to better speedup. Approach 1 reaches a very small memory footprint generally at the expense of a greater execution time. Approach 2 achieves a smaller execution time but requires more memory. The objective of the proposed approach is to design a composite approach, to speedup computations while staying under a given memory limit. This should allow to solve large problems that cannot be solved with Approach 2 while reducing the execution time compared to Approach 1. We propose a memory-aware strategy where each block can be compressed either at the beginning or as late as possible. We first consider the problem of choosing when to compress each block, under the assumption that all information on blocks is perfectly known, i.e., memory requirement and execution time of a block when compressed or not. We show that this problem is a variant of the NP-complete Knapsack problem, and adapt an existing approximation algorithm for our problem. Unfortunately, the required information on blocks depends on numerical properties and in practice cannot be known in advance. We thus introduce models to estimate those values. Experiments on the PaStiX solver demonstrate that our new approach can achieve an excellent trade-off between memory consumption and computational cost. For instance on matrix Geo1438, Approach 2 uses three times as much memory as Approach 1 while being three times faster. Our new approach leads to an execution time only 30% larger than Approach 2 when given a memory 30% larger than the one needed by Approach 1.

This work is in press and will appear in FGCS in 2022 13.

7.3.2 Deciding Non-Compressible Blocks in Sparse Direct Solvers using Incomplete Factorization.

Participants: Grégoire Pichon [Inria Bordeaux], Esragul Korkmaz [Inria Bordeaux], Mathieu Faverge [Inria Bordeaux], Pierre Ramet [Inria Bordeaux].

Low-rank compression techniques are very promising for reducing memory footprint and execution time on a large spectrum of linear solvers. Sparse direct supernodal approaches are one of these techniques. However, despite providing a very good scalability and reducing the memory footprint, they suffer from an important flops overhead in their unstructured low-rank updates. As a consequence, the execution time is not improved as expected. In this work, we study a solution to improve low-rank compression techniques in sparse supernodal solvers. The proposed method tackles the overprice of the low-rank updates by identifying the blocks that have poor compression rates. We show that the fill-in levels of the graph based block incomplete LU factorization can be used in a new context to identify most of these non-compressible blocks at low cost. This identification enables to postpone the low-rank compression step to trade small extra memory consumption for a better time to solution. The solution is validated within the PaStiX library with a large set of application matrices. It demonstrates sequential and multithreaded speedup up to 8.5x, for small memory overhead of less than 1.49x with respect to the original version.

This work appeared in the proceedings of the HIPC 2021 conference 22

7.3.3 Algorithms and data structures for hyperedge queries.

Participants: Bora Uçar [ENS Lyon], Jules Bertrand [ENS Lyon], Fanny Dufossé [Inria Grenoble].

7.3.4 Shared-memory implementation of the Karp-Sipser kernelization process.

Participants: Ioannis Panagiotas [Univ. Bergen, Norway], Bora Uçar [Univ. Bergen, Norway], Johannes Langguth [Univ. Bergen, Norway].

7.3.5 Streaming hypergraph partitioning algorithms on limited memory environments.

Participants: Bora Uçar [Sabanci University, Turkey], Fatih Taşyaran [Sabanci University, Turkey], Berkay Demireller [Sabanci University, Turkey], Kamer Kaya [Sabanci University, Turkey].

7.3.6 Fully-dynamic weighted matching approximation in practice.

Participants: Bora Uçar [Humboldt-Universität zu Berlin, Germany], Eugenio Angriman [Humboldt-Universität zu Berlin, Germany], Henning Meyerhenke [Humboldt-Universität zu Berlin, Germany], Christian Schulz [Universität Heidelberg, Germany].

7.3.7 Strongly connected components in directed hypergraphs.

Participants: Anne Benoit [ENS Lyon], Bora Uçar [ENS Lyon], Élodie Bernard [ENS Lyon].

8.1.1 Associate Teams in the framework of an Inria International Lab or in the framework of an Inria International Program

8.1.2 Inria associate team not involved in an IIL or an international program

8.1.3 Participation in other International Programs

• PHC Aurora Project with J. Langguth of Simula Labs, Norway. More information at project web page.

8.2.1 Visits to international teams

8.3.1 ANR Project Solharis (2019-2023), 4 years.

Participants: Maxime Gonthier, Gréfoire Pichon, Loris Marchal, Bora Uçar.

The ANR Project Solhar was launched in November 2019, for a duration of 48 months. It gathers five academic partners (the HiePACS, Roma, RealOpt, STORM and TADAAM INRIA project-teams, and CNRS-IRIT) and two industrial partners (CEA/CESTA and Airbus CRT). This project aims at producing scalable methods for direct methods for the solution of sparse linear systems on large scale and heterogeneous computing platforms, based on task-based runtime systems.

The proposed research is organized along three distinct research thrusts. The first objective deals with the development of scalable linear algebra solvers on task-based runtimes. The second one focuses on the deployement of runtime systems on large-scale heterogeneous platforms. The last one is concerned with scheduling these particular applications on a heterogeneous and large-scale environment.

9.1.1 Scientific events: organisation

9.1.2 Scientific events: selection

9.1.3 Journal

9.1.4 Invited talks

• Anne Benoit gave a keynote talk at the 18th International Conference on Network and Parallel Computing (IFIP NPC), Paris, November 2021, on Resilient scheduling for high-performance computing.
• Bora Uçar gave an invited talk to the Numerical Analysis group at the University of Strathclyde, 30 March 2021 (online during the Covid-19 pandemic); he also gave a guest lecture (4 times, 75 minutes each) on matching heuristics for Alex Pothen's graduate level course at Purdue.

9.1.5 Leadership within the scientific community

• Anne Benoit is elected as chair of IEEE TCPP, the Technical Committee on Parallel Processing (2020-2022). She serves in the steering committees of IPDPS, HCW, and HeteroPar.
• Bora Uçar serves as the secretary of SIAM Activity Group on Applied and Computational Discrete Algorithms (for the period Jan 21 – Dec 22).
• Bora Uçar serves in the steering committee of HiPC (2019–2021)
• Yves Robert serves in the steering committee of IPDPS and HCW.

9.1.6 Scientific expertise

• Frédéric Vivien is an elected member of the scientific council of the École normale supérieure de Lyon.
• Frédéric Vivien is a member of the scientific council of the IRMIA labex.

9.1.7 Research administration

• Loris Marchal is a member of the committee of the “Complexity of Algorithm” working group of the Gdr IM (CNRS research group on theoretical computer science)
• Bora Uçar is an elected member of the Council of LIP (Conseil du LIP), and also an elected member of Council of the Fédération d'Informatique de Lyon (Conseil de la FIL). He is also co-chair of the thesis committee of LIP (Co-responsable de la commission des thèses du LIP).
• Frédéric Vivien is the vice-head of the Fédération Informatique de Lyon.

9.2.1 Teaching

• Licence: Anne Benoit, Responsible of the L3 students at ENS Lyon, France
• Licence: Anne Benoit, Algorithmique avancée, 48h, L3, ENS Lyon, France
• Master: Anne Benoit, Parallel and Distributed Algorithms and Programs, 42h, M1, ENS Lyon, France
• Master: Grégoire Pichon, Resource optimization for linear system solvers, 10h, M2, ENS Lyon, France
• Master: Grégoire Pichon, Compilation / traduction des programmes, 24h, M1, Univ. Lyon 1, France
• Master: Grégoire Pichon, Programmation système et temps réel, 27.75h, M1, Univ. Lyon 1, France
• Master: Grégoire Pichon, Réseaux, 12h, M1, Univ. Lyon 1, France
• Licence: Grégoire Pichon, Programmation concurrente, 28.5h, L3, Univ. Lyon 1, France
• Licence: Grégoire Pichon, Réseaux, 34h, L3, Univ. Lyon 1, France
• Licence: Grégoire Pichon, Système d'exploitation, 24h, L2, Univ. Lyon 1, France
• Licence: Grégoire Pichon, Introduction aux réseaux et au web, 21h, L1, Univ. Lyon 1, France
• Licence: Grégoire Pichon, Référent pédagogique, 30h, L1/L2/L3, Univ. Lyon 1, France
• Master: Grégoire Pichon, Bora Uçar, and Frédéric Vivien, Resource optimization for linear system solvers, 10h each, M2, ENS Lyon, France.
• Master: Yves Robert, Responsible of the M2 students at ENS Lyon, France (2018-2021)
• Licence: Yves Robert, Probabilités et algorithmes randomisés, 48h cours +32h TD, L3, ENS Lyon, France
• Agrégation Informatique: Yves Robert, Algorithmique, NP-complétude et algorithmes d'approximation, probabilités, 74h, ENS Lyon, France

9.2.2 Supervision

• PhD defended: Yiqin Gao, “Replication Algorithms for Real-time Tasks with Precedence Constraints”, defended on September 29, 2021, funding: ENS Lyon, advisors: Yves Robert and Frédéric Vivien.
• PhD in progress: Lucas Perotin, “Fault-tolerant scheduling of parallel jobs”, started in October 2020, funding: ENS Lyon, advisors: Anne Benoit and Yves Robert.
• PhD in progress: Redouane Elghazi, “Stochastic Scheduling for HPC Systems”, started in September 2020, funding: Région Franche-Comté, advisors: Anne Benoit, Louis-Claude Canon and Pierre-Cyrille Héam.
• PhD in progress: Zhiwei Wu, “Energy-aware strategies for periodic scientific workflows under reliability constraints on heterogeneous platforms”, started in October 2020, funding: China Scholarship Council, advisors: Frédéric Vivien, Yves Robert, Li Han (ECNU) and Jing Liu (ECNU).
• PhD in progress: Yishu Du, “Resilient algorithms and scheduling techniques for numerical algorithms”, started in December 2019, funding: China Scholarship Council, advisors: Loris Marchal and Yves Robert.
• PhD in progress: Anthony Dugois “Scheduling for key value stores”, started in October 2020, funding: Inria, advisors: Loris Marchal and Louis-Claude Canon (Univ. Besançon).
• PhD in progress: Maxime Gonthier “Memory-Aware scheduling for task-based runtime systems”, started in October 2020, funding: Inria, advisors: Loris Marchal and Samuel Thibault (Univ. Bordeaux).

9.2.3 Juries

• Anne Benoit was a reviewer and a member of the jury for the thesis of Alena Shilova (December 2021, Université de Bordeaux).
• Loris Marchal is a responsible of the competitive selection of ENS Lyon students for Computer Science, and is a member of the jury of this competitive exam.
• Yves Robert was the chair of the 2021 ACM/IEEE-CS George Michael HPC Fellowship committee. He was a member of the 2021 IEEE Fellow Committee, and of the 2021 IEEE Charles Babbage Award Committee.

9.3.1 Articles and contents

• Yves Robert, together with George Bosilca, Aurélien Bouteiller and Thomas Herault, gave a full-day tutorial at SC'21 on Fault-tolerant techniques for HPC and Big Data: theory and practice.

International journals

• 7 articleG.Gabriel Bathie, L.Loris Marchal, Y.Yves Robert and S.Samuel Thibault. Dynamic DAG Scheduling Under Memory Constraints for Shared-Memory Platforms.International Journal of Networking and ComputingJanuary 2021, 1-29
  HALDOI
• 8 articleA.Anne Benoit, V.Valentin Le Fèvre, L.Lucas Perotin, P.Padma Raghavan, Y.Yves Robert and H.Hongyang Sun. Resilient Scheduling of Moldable Parallel Jobs to Cope with Silent Errors.IEEE Transactions on ComputersAugust 2021, 1-14
  HALDOIback to text
• 9 articleA.Anne Benoit, V.Valentin Le Fèvre, P.Padma Raghavan, Y.Yves Robert and H.Hongyang Sun. Resilient Scheduling Heuristics for Rigid Parallel Jobs.International Journal of Networking and Computing1112021, 1-25
  HAL
• 10 articleY.Yves Caniou, E.Eddy Caron, A.Aurélie Kong Win Chang and Y.Yves Robert. Budget-aware scheduling algorithms for scientific workflows with stochastic task weights on IaaS Cloud platforms.Concurrency and Computation: Practice and Experience33172021, 1-25
  HAL
• 11 articleY.Yishu Du, L.Loris Marchal, G.Guillaume Pallez and Y.Yves Robert. Optimal Checkpointing Strategies for Iterative Applications.IEEE Transactions on Parallel and Distributed Systems333March 2022, 507-522
  HALDOIback to text
• 12 articleF.Fanny Dufossé, K.Kamer Kaya, I.Ioannis Panagiotas and B.Bora Uçar. Scaling matrices and counting the perfect matchings in graphs.Discrete Applied Mathematics308February 2022, 130--146
  HAL
• 13 articleL.Loris Marchal, T.Thibault Marette, G.Grégoire Pichon and F.Frédéric Vivien. Trading Performance for Memory in Sparse Direct Solvers using Low-rank Compression.Future Generation Computer Systems2022
  HALback to text

International peer-reviewed conferences

• 14 inproceedingsE.Eugenio Angriman, H.Henning Meyerhenke, C.Christian Schulz and B.Bora Uçar. Fully-dynamic Weighted Matching Approximation in Practice.SIAM Conference on Applied and Computational Discrete Algorithms (ACDA21)Virtual, France2021
  HALback to text
• 15 inproceedingsA.Anne Benoit, L.-C.Louis-Claude Canon, R.Redouane Elghazi and P.-C.Pierre-Cyrille Heam. Shelf schedules for independent moldable tasks to minimize the energy consumption.SBAC-PAD 2021 - IEEE 33rd International Symposium on Computer Architecture and High Performance ComputingBelo Horizonte, BrazilOctober 2021, 1-11
  HALback to text
• 16 inproceedingsA.Anne Benoit, L.-C.Louis-Claude Canon, R.Redouane Elghazi and P.-C.Pierre-Cyrille Heam. Update on the Asymptotic Optimality of LPT.Euro-Par 2021 - 27th International European Conference on Parallel and Distributed ComputingLisbon, PortugalAugust 2021, 1-14
  HALback to text
• 17 inproceedingsA.Anne Benoit, R.Redouane Elghazi and Y.Yves Robert. Max-stretch minimization on an edge-cloud platform.IPDPS 2021 - IEEE International Parallel and Distributed Processing SymposiumPortland, Oregon, United StatesIEEEOctober 2020, 1-10
  HALback to text
• 18 inproceedingsY.Yves Caniou, E.Eddy Caron, A.Aurélie Kong Win Chang and Y.Yves Robert. Budget-aware Static Scheduling of Stochastic Workflows with DIET.ADVCOMP 2021 - Fifteenth International Conference on Advanced Engineering Computing and Applications in SciencesBarcelona, SpainOctober 2021, 1-8
  HAL
• 19 inproceedingsY.Yiqin Gao, G.Guillaume Pallez, Y.Yves Robert and F.Frédéric Vivien. Work-in-Progress: Evaluating Task Dropping Strategies for Overloaded Real-Time Systems.RTSS 2021 - 42nd IEEE Real-Time Systems SymposiumDortmund, GermanyIEEEDecember 2021, 1-4
  HALback to text
• 20 inproceedingsM.Maxime Gonthier, L.Loris Marchal and S.Samuel Thibault. Locality-Aware Scheduling of Independent Tasks for Runtime Systems.COLOC - 5th workshop on data locality - 27th International European Conference on Parallel and Distributed ComputingLisbon, PortugalSpringerAugust 2021, 1-12
  HALback to text
• 21 inproceedingsT.Thomas Herault, Y.Yves Robert, G.George Bosilca, R. J.Robert J Harrison, C. A.Cannada A Lewis, E. F.Edward F Valeev and J. J.Jack J Dongarra. Distributed-memory multi-GPU block-sparse tensor contraction for electronic structure.IPDPS 2021 - IEEE International Parallel and Distributed Processing SymposiumPortland, OR, United StatesIEEEMay 2021, 1-10
  HAL
• 22 inproceedingsE.Esragul Korkmaz, M.Mathieu Faverge, G.Grégoire Pichon and P.Pierre Ramet. Deciding Non-Compressible Blocks in Sparse Direct Solvers using Incomplete Factorization.HiPC 2021 - 28th IEEE International Conference on High Performance Computing, Data, and AnalyticsBangalore, IndiaIEEEDecember 2021, 1-10
  HALback to text
• 23 inproceedingsJ.Johannes Langguth, I.Ioannis Panagiotas and B.Bora Uçar. Shared-memory implementation of the Karp-Sipser kernelization process.HiPC 2021 - 28th edition of the IEEE International Conference on High Performance Computing, Data, and AnalyticsBangalore, IndiaIEEEDecember 2021, 71-80
  HALback to text
• 24 inproceedingsS. B.Sonia Ben Mokhtar, L.-C.Louis-Claude Canon, A.Anthony Dugois, L.Loris Marchal and E.Etienne Rivière. Taming Tail Latency in Key-Value Stores: a Scheduling Perspective.Euro-Par 2021: Parallel ProcessingEuro-Par 2021: Parallel Processing12820Lecture Notes in Computer ScienceLisbon (virtual), PortugalSpringer International PublishingAugust 2021, 136-150
  HALDOIback to text
• 25 inproceedingsF.Fatih Taşyaran, B.Berkay Demireller, K.Kamer Kaya and B.Bora Uçar. Streaming Hypergraph Partitioning Algorithms on Limited Memory Environments.HPCS 2020 - International Conference on High Performance Computing & SimulationVirtual online, SpainIEEEMarch 2021, 1-8
  HALback to text

Doctoral dissertations and habilitation theses

• 26 thesisY.Yiqin Gao. Scheduling independent tasks under budget and time constraints.Université de LyonSeptember 2021
  HAL

Reports & preprints

• 27 miscP.Patrick Amestoy, A.Alfredo Buttari, N. J.Nicholas J Higham, J.-Y.Jean-Yves L'Excellent, T.Théo Mary and B.Bastien Vieuble. Combining sparse approximate factorizations with mixed precision iterative refinement.January 2022
  HAL
• 28 miscS.Sonia Ben Mokhtar, L.-C.Louis-Claude Canon, A.Anthony Dugois, L.Loris Marchal and E.Etienne Rivière. Taming Tail Latency in Key-Value Stores: a Scheduling Perspective (extended version).March 2021
  HALDOIback to text
• 29 reportA.Anne Benoit, L.-C.Louis-Claude Canon, R.Redouane Elghazi and P.-C.Pierre-Cyrille Heam. Shelf schedules for independent moldable tasks to minimize the energy consumption.RR-9436Institut National de Recherche en Informatique et en Automatique (INRIA)November 2021, 19
  HAL
• 30 reportA.Anne Benoit, L.-C.Louis-Claude Canon, R.Redouane Elghazi and P.-C.Pierre-Cyrille Heam. Update on the Asymptotic Optimality of LPT.RR-9397Inria Grenoble - Rhône-AlpesFebruary 2021, 23
  HAL
• 31 reportA.Anne Benoit, V.Valentin Le Fèvre, L.Lucas Perotin, P.Padma Raghavan, Y.Yves Robert and H.Hongyang Sun. Resilient Scheduling of Moldable Parallel Jobs to Cope with Silent Errors.RR-9340Inria - Research Centre Grenoble – Rhône-AlpesJanuary 2021
  HAL
• 32 reportA.Anne Benoit, L.Lucas Perotin, Y.Yves Robert and H.Hongyang Sun. Checkpointing Workflows à la Young/Daly Is Not Good Enough.RR-9413Inria - Research Centre Grenoble – Rhône-AlpesJune 2021, 54
  HAL
• 33 reportJ.Jules Bertrand, F.Fanny Dufossé and B.Bora Uçar. Algorithms and data structures for hyperedge queries.RR-9390Inria Grenoble Rhône-AlpesFebruary 2021, 25
  HALback to text
• 34 reportY.Yiqin Gao, L.Li Han, J.Jing Liu, Y.Yves Robert and F.Frédéric Vivien. Minimizing energy consumption for real-time tasks on heterogeneous platforms under deadline and reliability constraints.RR-9403Inria - Research Centre Grenoble – Rhône-AlpesApril 2021, 417
  HAL
• 35 reportM.Maxime Gonthier, L.Loris Marchal and S.Samuel Thibault. Locality-Aware Scheduling of Independant Tasks for Runtime Systems.RR-9394Inria Grenoble -Rhône-Alpes2021, 21
  HALback to text
• 36 reportE.Esragul Korkmaz, M.Mathieu Faverge, G.Grégoire Pichon and P.Pierre Ramet. Deciding Non-Compressible Blocks in Sparse Direct Solvers using Incomplete Factorization.RR-9396Inria Bordeaux - Sud Ouest2021, 16
  HAL