ROMA

ROMA news:

Monday, March 27, 2017 14:30 Salle de Conseil du LIP

Roma WG by Tongquan Wei, Associate Pr at East China Normal University "Energy-Adaptive Scheduling of Imprecise Computation Tasks for QoS Optimization in Real-Time MPSoC Systems"

Abstract:
The key issue of renewable generations such as solar and wind in energy harvesting system is the uncertainty of energy availability. The characteristic of imprecise computation that accepts an approximate result when energy is limited and executes more computations yielding better results if more energy is available, can be exploited to intelligently handle the uncertainty. In this talk, I first give a general introduction of energy harvesting real-time systems and the challenges that they present to energy and QoS management. In particular, I will discuss the intermittence nature of renewable generation and the need for adaptive task scheduling. I then highlight our recent work that aims at tackling this challenge. Our work first adaptively assigns real-time imprecise computation tasks to individual processors considering uncertainties in renewable energy sources, then maximizes system QoS by executing as many optional execution cycles as possible of tasks allocated to processors under the energy budget constraint. At the end of the talk I will also introduce some of my related works on soft error resilient real-time scheduling.

Monday, March 27, 2017 14:00 Salle de Conseil du LIP

Roma WG by Mingsong Chen, Professor at East China Normal University "Efficient Resource Constrained Scheduling using Parallel Branch-and-Bound Pruning Techniques"

Abstract:
As a key step of high-level synthesis, resource constrained scheduling tries to find an optimal schedule that can dispatch all the operations with minimum latency under specific resource constraints. Branch-and-bound approaches are promising in pruning fruitless search space during the resource constrained scheduling. However, few of them are based on the prevalent multi-core platforms. Moreover, Branch-and-bound approaches only compare the estimated upper and lower bounds of an incomplete schedule to the length of the best feasible schedule at that iteration, which does not fully exploit the potential of the pruning during the search. In this talk, I will introduce multiple parallel branch-and-bound techniques that can substantially reduce the overall RCS search efforts from different perspectives. Firstly, I will introduce the space partitioning and bound speculation techniques that can efficiently decompose the overall search task into a set of sub-tasks. Next, I will present a novel pruning technique using the structural scheduling information of the obtained best feasible schedules. Then, I will present a comprehensive framework that supports the sharing of minimum upper-bound and structural information among different search tasks to enable n efficient parallel pruning. Experimental results on the MediaBench benchmark with a 96-core machine validates the efficacy of our proposed research.

Thursday, March 16, 2017 14:15 Salle de Conseil du LIP

Roma WG by Samuel McCauley "Input-Sensitive Locality Sensitive Hashing for Parallel Similarity Joins"

Abstract:
In a similarity join of two sets R and S, the goal is to compute all pairs of items (one from R, the other from S) that are at distance at most r in some metric. This problem is well-studied in the database literature, which largely focuses on heuristics and load balancing. However, from a theoretical point of view, many algorithms must compare all possible pairs in the worst case. One method used to avoid all-pairs comparisons is Locality Sensitive Hashing (LSH). LSH partitions the space probabilistically, such that close pairs are much more likely to collide than far pairs. This gives us a similarity join solution: if we hash sufficiently many times (so that we're likely to see all pairs), we only need to compare pairs within the same partition. LSH provides an interesting tradeoff. On the one hand, far pairs are unlikely to be in the same partition; our cost on these pairs is significantly reduced. On the other hand, we may incur significant overhead for dense clusters of close pairs: they may collide in many repetitions, causing us to compare them redundantly. In this talk, we show that a relatively simple greedy algorithm gives the best of both worlds, providing little redundancy for dense clusters, while far reducing the number of comparisons for sparse regions. It performs especially well on "easy" datasets automatically, without the need for specific parameterization. In addition, we show that our algorithm lends itself particularly well to the parallel and external-memory settings, where it can be combined with known heuristics to give potentially significant improvements.

Thursday, Feb 16, 2017 10:15 at Salle de Conseil du LIP

Roma WG by V. Le Fèvre "Periodic I/O scheduling for super-computers"

Abstract:
With the ever-growing need of data in HPC applications, the congestion at the I/O level becomes critical in super-computers. Architectural enhancement such as burst-buffers and pre-fetching are added to machines, but are not sufficient to prevent congestion. Recent online I/O scheduling strategies have been put in place, but they add an additional congestion point and overheads in the computation of applications. In this work, we show how to take advantage of the periodic nature of HPC applications in order to develop efficient periodic scheduling strategies for their I/O transfers. Our strategy computes once during the job scheduling phase a pattern where it defines the I/O behavior for each application, after which the applications run independently, transferring their I/O at the specified times. Our strategy limits the amount of I/O congestion at the I/O node level and can be easily integrated into current job schedulers. We validate this model through extensive simulations and experiments by comparing it to state-of-the-art online solutions, showing that not only our scheduler has the advantage of being de-centralized and thus overcoming the overhead of online schedulers, but also that it performs better than these solutions, improving the application dilation up to 13\% and the maximum system efficiency up to 18%. Reference: submitted to HPDC'17. Joint work with Guillaume Aupy and Ana Gainaru.

Thursday, Feb 9, 2017, 10:15 at Salle de Conseil du LIP

Roma WG by Y. Robert "A Failure Detector for HPC Platforms"

Abstract:
Building an infrastructure for Exascale applications requires, in addition to many other key components, a stable and efficient failure detector. This paper describes the design and evaluation of a robust failure detector, able to maintain and distribute the correct list of alive resources within proven and scalable bounds. The detection and distribution of the fault information follow different overlay topologies that together guarantee minimal disturbance to the applications. A virtual observation ring minimizes the overhead by allowing each node to be observed by another single node, providing an unobtrusive behavior. The propagation stage is using a non-uniform variant of a reliable broadcast over a circulant graph overlay network, and guarantees a logarithmic fault propagation. Extensive simulations, together with experiments on the Titan ORNL supercomputer, show that the algorithm performs extremely well, and exhibits all the desired properties of an Exascale-ready algorithm.

July 1st, 2016 at Colorado State University (co-tutelle with ENS-Lyon).

PhD defense of Guillaume Iooss "Detection of Linear Algebra Operations in Polyhedral Programs"

Abstract:
Writing a code which uses an architecture at its full capability has become an increasingly difficult problem over the last years. For some key operations, a dedicated accelerator or a finely tuned implementation exists and delivers the best performance. Thus, when compiling a code, identifying these operations and issuing calls to their high-performance implementation is attractive. In this dissertation, we focus on the problem of detection of these operations. We propose a framework which detects linear algebra subcomputations within a polyhedral program. The main idea of this framework is to partition the computation in order to isolate different subcomputations in a regular manner, then we consider each portion of the computation and try to recognize it as a combination of linear algebra operations. We perform the partitioning of the computation by using a program transformation called monoparametric tiling. This transformation partitions the computation into blocks, whose shape is some homothetic scaling of a fixed-size partitioning. We show that the tiled program remains polyhedral while allowing a limited amount of parametrization: a single size parameter. This is an improvement compared to the previous work on tiling, that forced us to choose between these two properties. Then, in order to recognize computations, we introduce a template recognition algorithm. This template recognition algorithm is built on a state-of-the-art program equivalence algorithm. We also propose several extensions in order to manage some semantic properties. Finally, we combine these two previous contributions into a framework which detects linear algebra subcomputations. A part of this framework is a library of template, based on the BLAS specification. We demonstrate our framework on several applications. Manuscript

Wednesday, November 25th 2015, at 2:00 PM in "Salle des thèses".

PhD defense of Julien Herrmann "Memory-Aware Algorithms and Scheduling Techniques for Matrix Computations"

Abstract:
Dans cette thèse, nous nous sommes penchés d’un point de vue à la fois théorique et pratique sur la conception d’algorithmes et de techniques d’ordonnancement adaptées aux architectures complexes des superordinateurs modernes. Nous nous sommes en particulier intéressés à l’utilisation mémoire et la gestion des communications des algorithmes pour le calcul haute performance (HPC). Nous avons exploité l’hétérogénéité des superordinateurs modernes pour améliorer les performances du calcul matriciel. Nous avons étudié la possibilité d’alterner intelligemment des étapes de factorisation LU (plus rapide) et des étapes de factorisation QR (plus stable numériquement mais plus deux fois plus coûteuses) pour résoudre un système linéaire dense. Nous avons amélioré les performances de systèmes d’exécution dynamique à l’aide de pré-calculs statiques prenants en compte l’ensemble du graphe de tâches de la factorisation Cholesky ainsi que l’hét? ? rogénéité de l’architecture. Nous nous sommes intéressés à la complexité du problème d’ordonnancement de graphes de tâches utilisant de gros fichiers d’entrée et de sortie sur une architecture hétérogène avec deux types de ressources, utilisant chacune une mémoire spécifique. Nous avons conçu de nombreuses heuristiques en temps polynomial pour la résolution de problèmes généraux que l’on avait prouvés NP-complet au préalable. Enfin, nous avons conçu des algorithmes optimaux pour ordonnancer un graphe de différentiation automatique sur une plateforme avec deux types de mémoire : une mémoire gratuite mais limitée et une mémoire coûteuse mais illimitée.

Sunday, November 15th 2015, 8:30AM - 5:00PM, at SC'15.

Tutorial "Fault-Tolerance for HPC: Theory and Practice" by George Bosilca, Aurélien Bouteiller, Thomas Hérault, and Yves Robert.

The tutorial webpage.

Thursday, November 12th 2015, at 1:45 PM in level-2 meeting room at LUG.

Julien Herrmann will reherse his PhD defense: "Memory-Aware Algorithms and Scheduling Techniques for Matrix Computations" (french talk)

Abstract:
Dans cette thèse, nous nous sommes penchés d’un point de vue à la fois théorique et pratique sur la conception d’algorithmes et de techniques d’ordonnancement adaptées aux architectures complexes des superordinateurs modernes. Nous nous sommes en particulier intéressés à l’utilisation mémoire et la gestion des communications des algorithmes pour le calcul haute performance (HPC). Nous avons exploité l’hétérogénéité des superordinateurs modernes pour améliorer les performances du calcul matriciel. Nous avons étudié la possibilité d’alterner intelligemment des étapes de factorisation LU (plus rapide) et des étapes de factorisation QR (plus stable numériquement mais plus deux fois plus coûteuses) pour résoudre un système linéaire dense. Nous avons amélioré les performances de systèmes d’exécution dynamique à l’aide de pré-calculs statiques prenants en compte l’ensemble du graphe de tâches de la factorisation Cholesky ainsi que l’hétérogénéité de l’architecture. Nous nous sommes intéressés à la complexité du problème d’ordonnancement de graphes de tâches utilisant de gros fichiers d’entrée et de sortie sur une architecture hétérogène avec deux types de ressources, utilisant chacune une mémoire spécifique. Nous avons conçu de nombreuses heuristiques en temps polynomial pour la résolution de problèmes généraux que l’on avait prouvés NP-complet au préalable. Enfin, nous avons conçu des algorithmes optimaux pour ordonnancer un graphe de différentiation automatique sur une plateforme avec deux types de mémoire : une mémoire gratuite mais limitée et une mémoire coûteuse mais illimitée.

Past Events:

Tuesday, November 3rd 2015, at 1:15 PM in level-1 meeting room at LUG.

ROMA working group by Willy Quach: "A lower bound on the processing time of tiled Cholesky factorization" (talk in English)

Abstract:
La factorisation de Cholesky est un algorithme essentiel d'algèbre linéaire, dont beaucoup d'applications découlent. Ainsi, un certain nombre d'heuristiques d'ordonnancement existe pour cet algorithme. Mais peut-on encore améliorer leur temps d'exécution ? C'est la question à laquelle nous nous intéresserons : nous étudierons dans un modèle simple la factorisation de Cholesky (sans coûts de communication ni gestion de mémoire). Nous tenterons tout d'abord de quantifier les performances de l'heuristique ALAP sur cet algorithme, en donnant un nombre de processeurs pour lequel on atteint le chemin critique de l'algorithme. Nous présenterons ensuite une borne inférieure (non-triviale) sur le temps d'exécution de n'importe quel ordonnancement pour la factorisation de Cholesky, avant de la comparer, dans notre modèle, à des heuristiques existantes.

Tuesday, October 20th 2015, at 11:00 AM in "Salle des thèses".

ROMA seminar by Oliver Sinnen, currently invited professor: "Being stubborn: developing optimal solution strategies for a scheduling problem despite its NP-hardness"

Abstract:
Many NP-hard problems are so difficult that even for small problem instances heuristics are employed. Scheduling task graphs with communication delays on a set of processors (P|prec,c_ij|C_max in alpha|beta|gamma notation) is such a problem. But the presenter is stubborn and insisted on solving this problem optimally (OK, for small problem instances), so this talk is a study of optimal solution strategies for a hard problem. First, Integer Linear Programming (ILP) based approaches are discussed. Crucial for meaningful performance of such ILPs is the efficient conversion of the bilinear constraints that arise from the consideration of the communication delays. Different formulations are developed and the relation between the formulation components and performance is all but trivial. Second, we look at exhaustive search techniques based on DFS (Depth First Search), branch-and-bound, A* and the like. We investigate how to construct the search space, while trying to avoid duplicate states. Problem specific pruning techniques are then studied to reduce the search space efficiently.

Tuesday, September 15th 2015, at 2:00 PM in level-2 meeting room at LUG.

ROMA working group by Loic Potier: "Ordonnancement résilient d'un ensemble d'applications parallèles" (talk in French)

Abstract:
Aux alentours de 2020, nous devrions entrer dans l’ère exascale. Un supercalculateur exascale pourra exécuter un milliard de milliards d’opérations par seconde. De tels supercalculateurs devront faire face à deux défis majeurs, la consommation énergétique et la tolérance aux fautes. Dans ce rapport de stage, nous nous intéresserons uniquement au premier aspect : la tolérance aux fautes. Les plus puissants calculateurs petascales actuels possèdent déjà plus de 100 000 coeurs de calculs, les futurs calculateurs exascales en possèderont surement beaucoup plus. Avec un tel nombre de coeurs, des fautes critiques arriveront très souvent (de l’ordre de la minute), même avec un temps moyen entre fautes (MTBF) de l’ordre de 100 ans. Quand une application est frappée par une faute, cela entraine un ralentissement important et une perte de travail puisque l’application doit retourner au dernier point de contrôle valide et perd donc le travail effectué entre la faute et le point de contrôle. Les fautes peuvent déséquilibrer l’ordonnancement puisque une application souvent frappée par des fautes verra son temps d'exécution s’allonger. Le but de ce stage est de développer un modèle théorique et des algorithmes dont l'objectif est de minimiser le temps d'exécution d’un ensemble de tâches parallèles dans un contexte résilient. De manière plus formelle, le but est de minimiser le temps de fin d’un pack de tâches. L’exécution d’un pack signifie que n tâches commencent en parallèle, de plus un pack ne peut commencer son exécution que si toutes les tâches du précédent pack sont terminées. Par conséquent, quand une tâche termine son exécution elle relâche les processeurs qui lui était allouée, ces processeurs deviennent donc disponibles. Notre but est de réutiliser ces ressources pour réduire le temps de complétion du pack. Outre redistribuer à chaque fin d’application, nous souhaitons également redistribuer quand il y a des fautes. Au moment où une tâche est touchée par une défaillance, celle-ci est ralentie. Ainsi, en ajoutant des processeurs à la tâche fautive, nous espérons réduire son temps d’exécution.

Friday, March 13 2015 at 10h15 in the level-1 meeting room at LUG.

ROMA working group by Aurélien Cavelan: "Voltage Overscaling Algorithms for Energy-Efficient Workflow Computations With Timing Errors"

Abstract:
We propose a software-based approach using dynamic volt- age overscaling to reduce the energy consumption of HPC applications. This technique aggressively lowers the supply voltage below nominal voltage, which introduces timing er- rors, and we use ABFT to provide fault tolerance for matrix operations. We introduce a formal model for and design op- timal polynomial-time solutions to execute a linear chain of tasks. Simulation results obtained for matrix multiplication demonstrate that our approach indeed leads to significant en- ergy savings, compared to the standard algorithm that always operates at nominal voltage.

Wednesday, December 10th 2014, at 10:00 AM in "Salle des thèses".

PhD defense of Dounia Zaidouni:"Combining checkpointing and other resilience mechanisms for exascale systems."

Abstract:
In this thesis, we are interested in scheduling and optimization problems in probabilistic contexts. The contributions of this thesis come in two parts. The first part is dedicated to the optimization of different fault-tolerance mechanisms for very large scale machines that are subject to a probability of failure and the second part is devoted to the optimization of the expected sensor data acquisition cost when evaluating a query expressed as a tree of disjunctive Boolean operators applied to Boolean predicates. In the first chapter, we present the related work of the first part and then we introduce some new general results that are useful for resilience on exascale systems. In the second chapter, we study a unified model for several well-known checkpoint/restart protocols. The proposed model is generic enough to encompass both extremes of the checkpoint/restart space, from coordinated approaches to a variety of uncoordinated checkpoint strategies. We propose a detailed analysis of several scenarios, including some of the most powerful currently available HPC platforms, as well as anticipated exascale designs. In the third, fourth, and fifth chapters, we study the combination of different fault tolerant mechanisms (replication, fault prediction and detection of silent errors) with the traditional checkpoint/restart mechanism. We evaluated several models using simulations. Our results show that these models are useful for a set of models of applications in the context of future exascale systems. In the second part of the thesis, we study the problem of minimizing the expected sensor data acquisition cost when evaluating a query expressed as a tree of disjunctive Boolean operators applied to Boolean predicates. The problem is to determine the order in which predicates should be evaluated so as to shortcut part of the query evaluation and minimize the expected cost. In the sixth chapter, we present the related work of the second part and in the seventh chapter, we study the problem for queries expressed as a disjunctive normal form. We consider the more general case where each data stream can appear in multiple predicates and we consider two models, the model where each predicate can access a single stream and the model where each predicate can access multiple streams.

For more information, check the thesis manuscript.

Previous events:

Monday, December 1st 2014, at 2:00 PM in "Salle des thèses".

PhD defense of Wissam M. Sid-Lakhdar:"Scaling the solution of large sparse linear systems using multifrontal methods on hybrid shared-distributed memory architectures"

Abstract:
The solution of sparse systems of linear equations is at the heart of numerous application fields. While the amount of computational resources in modern architectures increases and offers new perspectives, the size of the problems arising in today’s numerical simulation applications also grows very much. Exploiting modern architectures to solve very large problems efficiently is thus a challenge, from both a theoretical and an algorithmic point of view. The aim of this thesis is to address the scalability of sparse direct solvers based on multifrontal methods in parallel asynchronous environments.
In the first part of this thesis, we focus on exploiting multi-threaded parallelism on shared- memory architectures. A variant of the Geist-Ng algorithm is introduced to handle both fine grain parallelism through the use of optimized sequential and multi-threaded BLAS libraries and coarser grain parallelism through explicit OpenMP based parallelization. Memory aspects are then considered to further improve performance on NUMA architectures: (i) on the one hand, we analyse the influence of memory locality and exploit adaptive memory allocation strategies to manage private and shared workspaces; (ii) on the other hand, resource sharing on multicore processors induces performance penalties when many cores are active (machine load effects) that we also consider. Finally, in order to avoid resources remaining idle when they have finished their share of the work, and thus, to efficiently exploit all computational resources available, we propose an algorithm wich is conceptually very close to the work-stealing approach and which consists in dynamically assigning idle cores to busy threads/activities.
In the second part of this thesis, we target hybrid shared-distributed memory architectures, for which specific work to improve scalability is needed when processing large problems. We first study and optimize the dense linear algebra kernels used in distributed asynchronous multifrontal methods. Simulation, experimentation and profiling have been performed to tune parameters controlling the algorithm, in correlation with problem size and computer architecture charac- teristics. To do so, right-looking and left-looking variants of the LU factorization with partial pivoting in our distributed context have been revisited. Furthermore, when computations are ac- celerated with multiple cores, the relative weight of communication with respect to computation is higher. We explain how to design mapping algorithms minimizing the communication between nodes of the dependency tree of the multifrontal method, and show that collective asynchronous communications become critical on large numbers of processors. We explain why asynchronous broadcasts using standard tree-based communication algorithms must be used. We then show that, in a fully asynchronous multifrontal context where several such asynchronous communica- tion trees coexist, new synchronization issues must be addressed. We analyse and characterize the possible deadlock situations and formally establish simple global properties to handle dead- locks. Such properties partially force synchronization and may limit performance. Hence, we define properties which enable us to relax synchronization and thus improve performance. Our approach is based on the observation that, in our case, as long as memory is available, dead- locks cannot occur and, consequently, we just need to keep enough memory to guarantee that a deadlock can always be avoided. Finally, we show that synchronizations can be relaxed in a state-of-the-art solver and illustrate the performance gains on large real problems in our fully asynchronous multifrontal approach.

For more information, check the thesis manuscript.

Tuesday, September 16th 2014, at 3:30 PM in Amphi B.

PhD defense of Guillaume Aupy:"Resilient and energy-efficient scheduling algorithms at scale"

Abstract: This thesis deals with two issues for future Exascale platforms, namely resilience and energy.
In the first part of this thesis, we focus on the optimal placement of periodic coordinated checkpoints to minimize execution time. We consider fault predictors, a software used by system administrators that tries to predict (through the study of passed events) where and when faults will strike. In this context, we propose efficient algorithms, and give a first-order optimal formula for the amount of work that should be done between two checkpoints. We then focus on silent data corruption errors. Contrarily to fail-stop failures, such latent errors cannot be detected immediately, and a mechanism to detect them must be provided. We compute the optimal period in order to minimize the waste.
In the second part of the thesis we address the energy consumption challenge. The speed scaling technique consists in diminishing the voltage of the processor, hence diminishing its execution speed. Unfortunately, it was pointed out that DVFS increases the probability of failures. In this context, we consider the speed scaling technique coupled with reliability-increasing techniques such as re-execution, replication or checkpointing. For these different problems, we propose various algorithms whose efficiency is shown either through thorough simulations, or approximation results relatively to the optimal solution. Finally, we consider the different energetic costs involved in periodic coordinated checkpointing and compute the optimal period to minimize energy consumption, as we did for execution time.

More information about this thesis.

Tuesday, September 16th 2014, at 10:30 AM in room 394N ("salle du conseil du LIP").

Erol Gelenbe: "Réseaux stochastiques: formes produits et applications"

Résumé: Les réseaux stochastiques sont un outil puissant d’analyse de systèmes de communications, systèmes informatiques et de modes biologiques (comme les réseaux neuronaux), sous conditions que l’on sache les traiter de façon analytique pour réduire leur complexité de calcul. Nous présenterons quelques résultats dans ce domaine, dont les G-réseaux qui offrent une méthode de résolution compacte de modèles qui comprennent de forts couplages internes. Des exemples seront offerts dans des domaines variés comme les réseaux neuronaux, les réseaux de regulation génétique, les enchères, et le couplage entre flots de “traitement de l’information et de l’énergie”.

Biographie: Erol Gelenbe est membre de l’Académie des Technologies et Professeur à Imperial College (Londres). Il est diplômé ingénieur de la Middle East Technical University (Ankara), PhD du Polytechnic Institute de New York University, et docteur ès sciences mathématiques de l’Université Pierre et Marie Curie. Il a précédemment occupé des chaires à l’Université de Liège, l’Université de Paris-Sud où il a co-fondé le LRI, l’Université Paris-Descartes, la Duke University (USA) et la University of Central Florida où il a fondé la School of Electrical Engineering and Computer Science. Spécialiste des performances des réseaux et systèmes informatiques, il a reçu le Grand Prix France Télécom de l’Académie des Sciences (1996), le ACM SIGMETRICS Life-Time Achievement Award, le IET Oliver Lodge Medal (Londres), le “In Memoriam Dennis Gabor Award” (Budapest) et d’autres prix. Membre des Académies des Sciences de Hongrie, Pologne et Turquie, et docteur honoris cause de plusieurs universités, il est Chevalier de la Légion d’honneur et Officier de l’Ordre National du Mérite. Il anime le projet FP7 NEMESYS sur la sécurité des mobiles, et participe aux projets FP7 PANACEA sur le Cloud et ECROPS sur l’énergie consommée par l’informatique.

NB: Erol Gelenbe présentera également un séminaire SIESTE le même jour à 13h30.

July 21st -- 23rd 2014, Lyon.

CSC14: The Sixth SIAM Workshop on Combinatorial Scientific Computing.

Bora Uçar organizes the 6th edition of this SIAM workshop. See the webpage of the workshop for more information.

July 9th 2014.

The return of the ROMA BBQ!

The annual ROMA BBQ will take place at Fredo's house on July 9th ! More details will follow by email.

July 1st -- 4th 2014, Lyon.

9th Scheduling for Large Scale Systems Workshop.

The ROMA team organizes the 9th edition of its invitation-only workshop in Lyon, with the financial support of ENS Lyon, Labex MILYON, and the LIP laboratory. See the webpage of the workshop for more information.

June 19th 2014, 4:00 PM, room 316.

Bertrand Simon: Scheduling malleable task trees.

Bertrand will present the work done during his internship in the ROMA team, with L. Marchal and F. Vivien.

June 14th 2014, room 394N.

Amina Guermouche (10:00 AM) and Hongyang Sun (11:00 AM).

Amina and Hongyang will present their application in the ROMA team (the first one for the Maitre de Conférence position, the second one for an INRIA position).

April 10th-11th 2014.

Meeting of the SOLHAR ANR project in Lyon.

More information on the website of the ANR project

February 7th 2014, 11:00 AM, room B1.

Hongyang Sun (IRIT): Competitive Online Adaptive Scheduling for Sets of Parallel Jobs with Fairness and Efficiency.

Abstract: We study online adaptive scheduling for multiple sets of parallel jobs, where each set may contain one or more jobs with time-varying parallelism. This two-level scheduling scenario arises naturally when multiple parallel applications are submitted by different users or user groups in large parallel systems, where both user-level fairness and system-wide efficiency are of important concerns. To achieve fairness, we use the well-known equi-partitioning algorithm to distribute the available processors among the active job sets at any time. For efficiency, we apply a feedback-driven adaptive scheduler that periodically adjusts the processor allocations within each set by consciously exploiting the jobs' execution history. We show that our algorithm achieves asymptotically competitive performance with respect to the set response time, which incorporates two widely used performance metrics, namely, total response time and makespan, as special cases. Both theoretical analysis and simulation results demonstrate that our algorithm improves upon an existing scheduler that provides only fairness but lacks efficiency. Furthermore, we provide a generalized framework for analyzing a family of scheduling algorithms based on feedback-driven policies with provable efficiency. Finally, we consider an extended multi-level hierarchical scheduling model and present a fair and efficient solution that effectively reduces the problem to the two-level model.