Author: "Algorithms and Scheduling for Distributed Heterogeneous Platforms (GRAAL)" / Topic: scheduling (computing) - Searchworks@Jio Institute Digital Library Search Results

Your search keyword '"Algorithms and Scheduling for Distributed Heterogeneous Platforms (GRAAL)"' showing total 80 results

Start Over Author "Algorithms and Scheduling for Distributed Heterogeneous Platforms (GRAAL)" Topic scheduling (computing)

80 results on '"Algorithms and Scheduling for Distributed Heterogeneous Platforms (GRAAL)"'

1. Cosmological Simulations on a Grid of Computers

Author: Benjamin Depardon, Eddy Caron, Frédéric Desprez, Jérémy Blaizot, Hélène Courtois, Jean-Michel Alimi, André Fuözfa, Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Algorithms and Scheduling for Distributed Heterogeneous Platforms (GRAAL), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), Cosmologie Observationnelle, Institut de Physique Nucléaire de Lyon (IPNL), Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Physique Nucléaire et de Physique des Particules du CNRS (IN2P3)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Physique Nucléaire et de Physique des Particules du CNRS (IN2P3), Centre de Recherche Astrophysique de Lyon (CRAL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS)-Institut national des sciences de l'Univers (INSU - CNRS), Inria, Grid'5000, ANR-05-CIGC-0011,LEGO,League for Efficient Grid Operations(2005), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut national des sciences de l'Univers (INSU - CNRS)-Centre National de la Recherche Scientifique (CNRS), Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Physique Nucléaire et de Physique des Particules du CNRS (IN2P3)-Centre National de la Recherche Scientifique (CNRS), Laboratoire de l'Informatique du Parallélisme ( LIP ), École normale supérieure - Lyon ( ENS Lyon ) -Université Claude Bernard Lyon 1 ( UCBL ), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique ( Inria ) -Centre National de la Recherche Scientifique ( CNRS ), Algorithms and Scheduling for Distributed Heterogeneous Platforms ( GRAAL ), Institut National de Recherche en Informatique et en Automatique ( Inria ) -Institut National de Recherche en Informatique et en Automatique ( Inria ) -Laboratoire de l'Informatique du Parallélisme ( LIP ), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique ( Inria ) -Centre National de la Recherche Scientifique ( CNRS ) -École normale supérieure - Lyon ( ENS Lyon ) -Université Claude Bernard Lyon 1 ( UCBL ), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique ( CNRS ), Institut de Physique Nucléaire de Lyon ( IPNL ), Université Claude Bernard Lyon 1 ( UCBL ), Université de Lyon-Université de Lyon-Institut National de Physique Nucléaire et de Physique des Particules du CNRS ( IN2P3 ) -Centre National de la Recherche Scientifique ( CNRS ) -Université Claude Bernard Lyon 1 ( UCBL ), Université de Lyon-Université de Lyon-Institut National de Physique Nucléaire et de Physique des Particules du CNRS ( IN2P3 ) -Centre National de la Recherche Scientifique ( CNRS ), Centre de Recherche Astrophysique de Lyon ( CRAL ), Université de Lyon-Université de Lyon-Institut national des sciences de l'Univers ( INSU - CNRS ) -Centre National de la Recherche Scientifique ( CNRS ), and ANR-05-CIGC-0011,LEGO,League for Efficient Grid Operations ( 2005 )
Subjects: FOS: Computer and information sciences, Parallel computing, Cosmology and Nongalactic Astrophysics (astro-ph.CO), Computer science, [SDU.ASTR.CO]Sciences of the Universe [physics]/Astrophysics [astro-ph]/Cosmology and Extra-Galactic Astrophysics [astro-ph.CO], Computation, Distributed computing, FOS: Physical sciences, Grid-RPC, 02 engineering and technology, Sky surveys, 01 natural sciences, Execution time, Scheduling (computing), [PHYS.ASTR.CO]Physics [physics]/Astrophysics [astro-ph]/Cosmology and Extra-Galactic Astrophysics [astro-ph.CO], Databases, [ INFO.INFO-DC ] Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Data acquisition, Universe, 0103 physical sciences, 0202 electrical engineering, electronic engineering, information engineering, N-body simulations, Instrumentation and Methods for Astrophysics (astro-ph.IM), 010303 astronomy & astrophysics, Local uni- verse, Middleware, 020203 distributed computing, Grid middleware, Archives, Atlases, Astronomical catalogues, Grid, Cosmology, Astronomical catalogs, Retrieval systems, Computer Science - Distributed, Parallel, and Cluster Computing, Distributed, Parallel, and Cluster Computing (cs.DC), Origin and formation of the Universe, Particle-theory and field-theory models of the early Universe, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Astrophysics - Instrumentation and Methods for Astrophysics, Data acquisition: hardware and software, Astrophysics - Cosmology and Nongalactic Astrophysics
Abstract: The work presented in this paper aims at restricting the input parameter values of the semi-analytical model used in GALICS and MOMAF, so as to derive which parameters influence the most the results, e.g., star formation, feedback and halo recycling efficiencies, etc. Our approach is to proceed empirically: we run lots of simulations and derive the correct ranges of values. The computation time needed is so large, that we need to run on a grid of computers. Hence, we model GALICS and MOMAF execution time and output files size, and run the simulation using a grid middleware: DIET. All the complexity of accessing resources, scheduling simulations and managing data is harnessed by DIET and hidden behind a web portal accessible to the users., Accepted and Published in AIP Conference Proceedings 1241, 2010, pages 816-825
Published: 2010

2. A survey of pipelined workflow scheduling

Author: Ümit V. Çatalyürek, Anne Benoit, Yves Robert, Erik Saule, Algorithms and Scheduling for Distributed Heterogeneous Platforms (GRAAL), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), Laboratoire de l'Informatique du Parallélisme (LIP), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Department of Biomedical Informatics [Columbus], Ohio State University [Columbus] (OSU), Optimisation des ressources : modèles, algorithmes et ordonnancement (ROMA), ANR-10-BLAN-0301,RESCUE,Résilience des applications scientifiques sur machines exascales(2010), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), and Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL)
Subjects: General Computer Science, parallel systems, Computer science, Distributed computing, 0102 computer and information sciences, 02 engineering and technology, Parallel computing, algorithms, 01 natural sciences, Structuring, Theoretical Computer Science, Scheduling (computing), Workflow technology, models, 0202 electrical engineering, electronic engineering, information engineering, filter-stream programming, Workflow scheduling, scheduling, throughput, latency, distributed systems, 020203 distributed computing, Job shop scheduling, pipeline, workflow programming, Workflow, 010201 computation theory & mathematics, Programming paradigm, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Algorithm, Workflow management system
Abstract: A large class of applications need to execute the same workflow on different datasets of identical size. Efficient execution of such applications necessitates intelligent distribution of the application components and tasks on a parallel machine, and the execution can be orchestrated by utilizing task, data, pipelined, and/or replicated parallelism. The scheduling problem that encompasses all of these techniques is called pipelined workflow scheduling , and it has been widely studied in the last decade. Multiple models and algorithms have flourished to tackle various programming paradigms, constraints, machine behaviors, or optimization goals. This article surveys the field by summing up and structuring known results and approaches.
Published: 2013

3. Scheduling Concurrent Bag-of-Tasks Applications on Heterogeneous Platforms

Author: Yves Robert, Jean-François Pineau, Frédéric Vivien, Loris Marchal, Anne Benoit, Algorithms and Scheduling for Distributed Heterogeneous Platforms (GRAAL), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), Laboratoire de l'Informatique du Parallélisme (LIP), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon)-Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), and Université de Lyon-École normale supérieure - Lyon (ENS Lyon)
Subjects: Scheduling and task partitioning, Schedule, Index Terms, Online computation, Computer science, Distributed computing, 02 engineering and technology, Bag of tasks, Theoretical Computer Science, Scheduling (computing), Data modeling, Parallelism and concurrency, 0202 electrical engineering, electronic engineering, information engineering, [INFO]Computer Science [cs], Computer multitasking, simulation of multiple-processor systems, Measurement, 020203 distributed computing, evaluation, Heuristic, modeling, Workload, Computational Theory and Mathematics, Hardware and Architecture, 020201 artificial intelligence & image processing, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Heuristics, Software
Abstract: International audience; Scheduling problems are already difficult on traditional parallel machines, and they become extremely challenging on heterogeneous clusters. In this paper, we deal with the problem of scheduling multiple applications, made of collections of independent and identical tasks, on a heterogeneous master-worker platform. The applications are submitted online, which means that there is no a priori (static) knowledge of the workload distribution at the beginning of the execution. The objective is to minimize the maximum stretch, i.e., the maximum ratio between the actual time an application has spent in the system and the time this application would have spent if executed alone. On the theoretical side, we design an optimal algorithm for the offline version of the problem (when all release dates and application characteristics are known beforehand). We also introduce a heuristic for the general case of online applications. On the practical side, we have conducted extensive simulations and MPI experiments, showing that we are able to deal with very large problem instances in a few seconds. Also, the solution that we compute totally outperforms classical heuristics from the literature, thereby fully assessing the usefulness of our approach.
Published: 2010

4. Contention awareness and fault-tolerant scheduling for precedence constrained tasks in heterogeneous systems

Author: Yves Robert, Anne Benoit, Mourad Hakem, Algorithms and Scheduling for Distributed Heterogeneous Platforms (GRAAL), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon)-Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon), Laboratoire de l'Informatique du Parallélisme (LIP), Franche-Comté Électronique Mécanique, Thermique et Optique - Sciences et Technologies (UMR 6174) (FEMTO-ST), Université de Technologie de Belfort-Montbeliard (UTBM)-Ecole Nationale Supérieure de Mécanique et des Microtechniques (ENSMM)-Université de Franche-Comté (UFC), Université Bourgogne Franche-Comté [COMUE] (UBFC)-Université Bourgogne Franche-Comté [COMUE] (UBFC)-Centre National de la Recherche Scientifique (CNRS), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Université de Technologie de Belfort-Montbeliard (UTBM)-Ecole Nationale Supérieure de Mécanique et des Microtechniques (ENSMM)-Centre National de la Recherche Scientifique (CNRS)-Université de Franche-Comté (UFC), and Université Bourgogne Franche-Comté [COMUE] (UBFC)-Université Bourgogne Franche-Comté [COMUE] (UBFC)
Subjects: Rate-monotonic scheduling, Earliest deadline first scheduling, 020203 distributed computing, Computer Networks and Communications, Computer science, Heuristic, Distributed computing, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], 02 engineering and technology, Dynamic priority scheduling, Load balancing (computing), 16. Peace & justice, Computer Graphics and Computer-Aided Design, Fair-share scheduling, Theoretical Computer Science, Scheduling (computing), Fixed-priority pre-emptive scheduling, Artificial Intelligence, Hardware and Architecture, 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Time complexity, Software
Abstract: International audience; Heterogeneous distributed systems are widely deployed for executing computationally intensive parallel applications with diverse computing needs. Such environments require effective scheduling strategies that take into account both algorithmic and architectural characteristics. Unfortunately, most of the scheduling algorithms developed for such systems rely on a simple platform model where communication contention is not taken into account. In addition, it is generally assumed that processors are completely safe. To schedule precedence graphs in a more realistic framework, we introduce first an efficient fault-tolerant scheduling algorithm that is both contention-aware and capable of supporting an arbitrary number of fail-silent (fail-stop) processor failures. Next, we derive a more complex heuristic that departs from the main principle of the first algorithm. Instead of considering a single task (one with highest priority) and assigning all its replicas to the currently best available resources, we consider a chunk of ready tasks, and assign all their replicas in the same decision making procedure. This leads to a better load balance of processors and communication links. We focus on a bi-criteria approach, where we aim at minimizing the total execution time, or latency, given a fixed number of failures supported in the system. Our algorithms have a low time complexity, and drastically reduce the number of additional communications induced by the replication mechanism. Experimental results fully demonstrate the usefulness of the proposed algorithms, which lead to efficient execution schemes while guaranteeing a prescribed level of fault-tolerance.
Published: 2009

5. Hybrid scheduling for the parallel solution of linear systems

Author: Jean-Yves L'Excellent, Abdou Guermouche, Patrick R. Amestoy, Stéphane Pralet, Algorithms and Scheduling for Distributed Heterogeneous Platforms (GRAAL), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon)-Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon), Algorithmes Parallèles et Optimisation (IRIT-APO), Institut de recherche en informatique de Toulouse (IRIT), Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées, Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Algorithms and high performance computing for grand challenge applications (SCALAPPLIX), INRIA Futurs, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), GRAAL INRIA Rhone-Alpes, ENSEEIHT-IRIT, École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Toulouse Mind & Brain Institut (TMBI), Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1 (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), and IRIT (ENSEEIHT)
Subjects: Rate-monotonic scheduling, Computer Networks and Communications, Computer science, Context (language use), Workload, Dynamic priority scheduling, Parallel computing, 010502 geochemistry & geophysics, 01 natural sciences, Computer Graphics and Computer-Aided Design, Fair-share scheduling, Theoretical Computer Science, Scheduling (computing), 010101 applied mathematics, Hybrid Scheduling, Factorization, Artificial Intelligence, Hardware and Architecture, Two-level scheduling, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], 0101 mathematics, Software, 0105 earth and related environmental sciences, Frontal solver
Abstract: International audience; We consider the problem of designing a dynamic scheduling strategy that takes into account both workload and memory information in the context of the parallel multifrontal factorization. The originality of our approach is that we base our estimations (work and memory) on a static optimistic scenario during the analysis phase. This scenario is then used during the factorization phase to constrain the dynamic decisions that compute fully irregular partitions in order to better balance the workload. We show that our new scheduling algorithm significantly improves both the memory behaviour and the factorization time. We give experimental results for large challenging real-life 3D problems on 64 and 128 processors.
Published: 2006

6. Scheduling divisible workloads on heterogeneous platforms

Author: Arnaud Legrand, Yves Robert, Olivier Beaumont, Algorithms and high performance computing for grand challenge applications (SCALAPPLIX), INRIA Futurs, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1 (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Algorithms and Scheduling for Distributed Heterogeneous Platforms (GRAAL), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon)-Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), and Université de Lyon-École normale supérieure - Lyon (ENS Lyon)
Subjects: 020203 distributed computing, Computer Networks and Communications, Computer science, Distributed computing, 02 engineering and technology, Parallel computing, Computer Graphics and Computer-Aided Design, Theoretical Computer Science, Scheduling (computing), Asymptotically optimal algorithm, Artificial Intelligence, Hardware and Architecture, 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Periodic graph (geometry), Software
Abstract: International audience; In this paper, we discuss several algorithms for scheduling divisible workloads on heterogeneous systems. Our main contributions are (i) new optimality results for single-round algorithms and (ii) the design of an asymptotically optimal multi-round algorithm. This multi-round algorithm automatically performs resource selection, a difficult task that was previously left to the user. Because it is periodic, it is simpler to implement, and more robust to changes in the speeds of the processors and/or communication links. On the theoretical side, to the best of our knowledge, this is the first published result assessing the absolute performance of a multi-round algorithm. On the practical side, extensive simulations reveal that our multi-round algorithm outperforms existing solutions on a large variety of platforms, especially when the communication-to-computation ratio is not very high (the difficult case).
Published: 2003

7. An RMS Architecture for Efficiently Supporting Complex-Moldable Applications

Author: Cristian Klein, Christian Pérez, Algorithms and Scheduling for Distributed Heterogeneous Platforms (GRAAL), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), Grid'5000, ANR-09-COSI-0001,COOP,Gestion de ressources coopérative multi niveaux(2009), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), and Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL)
Subjects: 020203 distributed computing, Computer science, Distributed computing, 02 engineering and technology, computer.software_genre, Scheduling (computing), Grid computing, Scalability, 0202 electrical engineering, electronic engineering, information engineering, Resource allocation, 020201 artificial intelligence & image processing, Resource management, Architecture, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], computer
Abstract: International audience; High-performance scientific applications are becoming increasingly complex, in particular because of the coupling of parallel codes. This results in applications having a complex structure, characterized by multiple deploy-time parameters, such as the number of processes of each code. In order to optimize the performance of these applications, the parameters have to be carefully chosen, a process which is highly resource dependent. However, the abstractions provided by current Resource Management Systems (RMS) - either submitting rigid jobs or enumerating a list of moldable configurations - are insufficient to efficiently select resources for such applications. This paper introduces CooRM, an RMS architecture that delegates resource selection to applications while still keeping control over the resources. The proposed architecture is evaluated using a simulator which is then validated with a proof-of-concept implementation on Grid'5000. Results show that such a system is feasible and performs well with respect to scalability and fairness.
Published: 2011

8. A Genetic Algorithm with Communication Costs to Schedule Workflows on a SOA-Grid

Author: Jean-Marc Nicod, Lamiel Toch, Laurent Philippe, Algorithms and Scheduling for Distributed Heterogeneous Platforms (GRAAL), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon)-Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon), Franche-Comté Électronique Mécanique, Thermique et Optique - Sciences et Technologies (UMR 6174) (FEMTO-ST), Université de Technologie de Belfort-Montbeliard (UTBM)-Ecole Nationale Supérieure de Mécanique et des Microtechniques (ENSMM)-Université de Franche-Comté (UFC), Université Bourgogne Franche-Comté [COMUE] (UBFC)-Université Bourgogne Franche-Comté [COMUE] (UBFC)-Centre National de la Recherche Scientifique (CNRS), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), Université de Technologie de Belfort-Montbeliard (UTBM)-Ecole Nationale Supérieure de Mécanique et des Microtechniques (ENSMM)-Centre National de la Recherche Scientifique (CNRS)-Université de Franche-Comté (UFC), and Université Bourgogne Franche-Comté [COMUE] (UBFC)-Université Bourgogne Franche-Comté [COMUE] (UBFC)
Subjects: 020203 distributed computing, Job shop scheduling, Computer science, computer.internet_protocol, Distributed computing, 02 engineering and technology, Service-oriented architecture, Directed acyclic graph, Grid, Scheduling (computing), Workflow, 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, computer
Abstract: International audience; In this paper we study the problem of scheduling a collection of workflows, identical or not, on a SOA (Service Oriented Architecture) grid . A workflow (job) is represented by a directed acyclic graph (DAG) with typed tasks. All of the grid hosts are able to process a set of typed tasks with unrelated processing costs and are able to transmit files through communication links for which the communication times are not negligible. The goal of our study is to minimize the maximum completion time (makespan) of the workflows. To solve this problem we propose a genetic approach. The contributions of this paper are both the design of a Genetic Algorithm taking the communication costs into account and its performance analysis.
Published: 2011

9. Towards Scheduling Evolving Applications

Author: Christian Pérez, Cristian Klein, Algorithms and Scheduling for Distributed Heterogeneous Platforms (GRAAL), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), ANR-09-COSI-0001,COOP,Gestion de ressources coopérative multi niveaux(2009), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), and Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL)
Subjects: 020203 distributed computing, Computer science, Distributed computing, 0202 electrical engineering, electronic engineering, information engineering, Resource Management System, Resource allocation, 020201 artificial intelligence & image processing, 02 engineering and technology, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Scheduling (computing)
Abstract: International audience; Most high-performance computing resource managers only allow applications to request a static allocation of resources. However, evolving applications have resource requirements which change (evolve) during their execution. Currently, such applications are forced to make an allocation based on their peak resource requirements, which leads to an inefficient resource usage. This paper studies whether it makes sense for resource managers to support evolving applications. It focuses on scheduling fully-predictably evolving applications on homogeneous resources, for which it proposes several algorithms and evaluates them based on simulations. Results show that resource usage and application response time can be significantly improved with short scheduling times.
Published: 2011

10. An RMS for Non-predictably Evolving Applications

Author: Cristian Klein, Christian Pérez, Algorithms and Scheduling for Distributed Heterogeneous Platforms (GRAAL), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), INRIA, ANR-09-COSI-0001,COOP,Gestion de ressources coopérative multi niveaux(2009), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), and Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL)
Subjects: 020203 distributed computing, malleability, Computer science, Adaptive mesh refinement, evolving applications, Distributed computing, supercomputers, 02 engineering and technology, Software maintenance, Scheduling (computing), 0202 electrical engineering, electronic engineering, information engineering, Resource allocation, 020201 artificial intelligence & image processing, Resource management, resource management, clusters, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC]
Abstract: Non-predictably evolving applications are applications that change their resource requirements during execution. These applications exist, for example, as a result of using adaptive numeric methods, such as adaptive mesh refinement and adaptive particle methods. Increasing interest is being shown to have such applications acquire resources on the fly. However, current HPC Resource Management Systems (RMSs) only allow a static allocation of resources, which cannot be changed after it started. Therefore, non-predictably evolving applications cannot make efficient use of HPC resources, being forced to make an allocation based on their maximum expected requirements. This paper presents CooRMv2, an RMS which supports efficient scheduling of non-predictably evolving applications. An application can make "pre-allocations" to specify its peak resource usage. The application can then dynamically allocate resources as long as the pre-allocation is not outgrown. Resources which are pre-allocated but not used, can be filled by other applications. Results show that the approach is feasible and leads to a more efficient resource usage.; Les applications évolutives non-prédictibles sont des applications dont les besoins en ressources changent en cours d'exécution. Leurs comportements proviennent, par exemple, des méthodes numériques adaptatives, comme le raffinement de maillage adaptatif et les méthodes de particules adaptatives. Il y a un intérêt croissant à ce que ce type d'application acquiert des ressources à la volée. Cependant, les gestionnaires de ressources haute performance (HPC) ne supportent qu'une allocation statique des ressources, qui ne peut donc pas changer après le démarrage de l'application. Par conséquence, les applications évolutives non-prédictibles ne peuvent pas utiliser les ressources HPC de manière efficace, car elles sont forcées de faire une demande de ressources en fonction de leurs pics de besoins. Cet article présente CooRMv2, un gestionnaire de ressources qui permet l'ordonnancement efficace d'applications évolutives non-prédictibles. Une application peut faire des "pré-allocations" pour exprimer ses pics de besoins en ressources. Ensuite, l'application peut dynamiquement allouer de manière sûre des ressources tant que la pré-allocation n'est pas dépassée. Les ressources pré-allouées, mais inutilisées, sont à la disposition des autres applications. Les résultats montrent que l'approche est réalisable et que l'utilisation des ressources est améliorée.
Published: 2011

11. Energy-aware scheduling of bag-of-tasks applications on master-worker platforms

Author: Jean-François Pineau, Yves Robert, Frédéric Vivien, Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Algorithms and Scheduling for Distributed Heterogeneous Platforms (GRAAL), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), and Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL)
Subjects: 020203 distributed computing, Computer Networks and Communications, Computer science, Distributed computing, energy-aware, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Throughput, 02 engineering and technology, master-worker platforms, Bag of tasks, 020202 computer hardware & architecture, Computer Science Applications, Theoretical Computer Science, Scheduling (computing), Energy aware scheduling, Computational Theory and Mathematics, steady-state scheduling, 0202 electrical engineering, electronic engineering, information engineering, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Computer Science::Operating Systems, Software, overhead, bi-criteria
Abstract: We consider the problem of scheduling an application composed of independent tasks on a fully heterogeneous master–worker platform with communication costs. We introduce a bi-criteria approach aiming at maximizing the throughput of the application while minimizing the energy consumed by participating resources. Assuming arbitrary super-linear power consumption laws, we investigate different models, with energy overheads and memory constraints. Building upon closed-form expressions for the uni-processor case, we derive asymptotically optimal solutions for all models. Copyright © 2010 John Wiley & Sons, Ltd.
Published: 2011

12. Scheduling parallel iterative applications on volatile resources

Author: Henri Casanova, Yves Robert, Fanny Dufossé, Frédéric Vivien, Concurrency Research Group (CoRG), University of Hawai‘i [Mānoa] (UHM), Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Algorithms and Scheduling for Distributed Heterogeneous Platforms (GRAAL), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), Information and Computer Sciences [Hawaii] (ICS), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), and Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL)
Subjects: 020203 distributed computing, Computational complexity theory, Job shop scheduling, Computer science, Iterative method, Distributed computing, Markov process, Processor scheduling, 02 engineering and technology, Scheduling (computing), symbols.namesake, 0202 electrical engineering, electronic engineering, information engineering, symbols, 020201 artificial intelligence & image processing, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Heuristics, ComputingMilieux_MISCELLANEOUS
Abstract: In this paper we study the execution of iterative applications on volatile processors such as those found on desktop grids. We develop master-worker scheduling schemes that attempt to achieve good trade-offs between worker speed and worker availability. A key feature of our approach is that we consider a communication model where the bandwidth capacity of the master for sending application data to workers is limited. This limitation makes the scheduling problem more difficult both in a theoretical sense and a practical sense. Furthermore, we consider that a processor can be in one of three states: available, down, or temporarily preempted by its owner. This preempted state also makes the design of scheduling algorithms more difficult. In practical settings, e.g., desktop grids, master bandwidth is limited and processors are temporarily reclaimed. Consequently, addressing the aforementioned difficulties is necessary for successfully deploying master-worker applications on volatile platforms. Our first contribution is to determine the complexity of the scheduling problem in its off-line version, i.e., when processor availability behaviors are known in advance. Even with this knowledge, the problem is NP-hard, and cannot be approximated within a factor $8/7$. Our second contribution is a closed-form formula for the expectation of the time needed by a worker to complete a set of tasks. This formula relies on a Markovian assumption for the temporal availability of processors, and is at the heart of some heuristics that aim at favoring ``reliable'' processors in a sensible manner. Our third contribution is a set of heuristics, which we evaluate in simulation. Our results provide insightful guidance to selecting the best strategy as a function of processor state availability versus average task duration.
Published: 2011

13. Energy-aware mappings of series-parallel workflows onto chip multiprocessors

Author: Paul Renaud-Goud, Rami Melhem, Anne Benoit, Yves Robert, Algorithms and Scheduling for Distributed Heterogeneous Platforms (GRAAL), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), Laboratoire de l'Informatique du Parallélisme (LIP), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Department of Computer Science - University of Pittsburgh, University of Pittsburgh (PITT), Pennsylvania Commonwealth System of Higher Education (PCSHE)-Pennsylvania Commonwealth System of Higher Education (PCSHE), Optimisation des ressources : modèles, algorithmes et ordonnancement (ROMA), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), INRIA, and ANR-07-BLAN-0192,StochaGrid,Scheduling algorithms and stochastic performance models for workflow applications on dynamic grid platforms(2007)
Subjects: 020203 distributed computing, Computational complexity theory, Data stream mining, Computer science, Graph theory, 02 engineering and technology, Energy consumption, Parallel computing, Graph, 020202 computer hardware & architecture, Scheduling (computing), Dynamic voltage scaling, Dynamic programming, 0202 electrical engineering, electronic engineering, information engineering, Graph (abstract data type), [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Heuristics, Time complexity, ComputingMilieux_MISCELLANEOUS
Abstract: This paper studies the problem of mapping streaming appli- cations that can be modeled by a series-parallel graph, onto a 2-dimensional tiled CMP architecture. The objective of the mapping is to minimize the energy consumption, using dynamic and voltage scaling techniques, while maintaining a given level of performance, reflected by the rate of process- ing the data streams. This mapping problem turns out to be NP-hard, but we identify simpler instances, whose optimal solution can be computed by a dynamic programming algo- rithm in polynomial time. Several heuristics are proposed to tackle the general problem, building upon the theoretical results. Finally, we assess the performance of the heuris- tics through comprehensive simulations using the StreamIt workflow suite and various CMP grid sizes.
Published: 2011

14. Global Memory Access Modelling for Efficient Implementation of the Lattice Boltzmann Method on Graphics Processing Units

Author: Christian Obrecht, Bernard Tourancheau, Jean-Jacques Roux, Frédéric Kuznik, Centre de Thermique de Lyon (CETHIL), Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS), Smart Wireless Networking (SWING), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-CITI Centre of Innovation in Telecommunications and Integration of services (CITI), Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA), Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Algorithms and Scheduling for Distributed Heterogeneous Platforms (GRAAL), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), EDF, J.M.L.M. Palma et al., École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS)-Institut National des Sciences Appliquées de Lyon (INSA Lyon), and Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)
Subjects: [PHYS.PHYS.PHYS-FLU-DYN]Physics [physics]/Physics [physics]/Fluid Dynamics [physics.flu-dyn], Computer science, CUDA, Parallel computing, 01 natural sciences, Computational science, Scheduling (computing), [INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI], Approximation error, CUDA Pinned memory, 0103 physical sciences, 0101 mathematics, Graphics, 010306 general physics, ACM: J.: Computer Applications/J.2: PHYSICAL SCIENCES AND ENGINEERING, Uniform memory access, GPU computing, ACM: C.: Computer Systems Organization/C.2: COMPUTER-COMMUNICATION NETWORKS, 010101 applied mathematics, ACM: J.: Computer Applications, ACM: C.: Computer Systems Organization/C.4: PERFORMANCE OF SYSTEMS/C.4.3: Modeling techniques, lattice Boltzmann method, General-purpose computing on graphics processing units, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], CFD
Abstract: International audience; In this work, we investigate the global memory access mech- anism on recent GPUs. For the purpose of this study, we created spe- cific benchmark programs, which allowed us to explore the scheduling of global memory transactions. Thus, we formulate a model capable of estimating the execution time for a large class of applications. Our main goal is to facilitate optimisation of regular data-parallel applications on GPUs. As an example, we finally describe our CUDA implementations of LBM flow solvers on which our model was able to estimate performance with less than 5% relative error.
Published: 2011

15. Task graph scheduling

Author: Yves Robert, Sameer Shende, Allen D. Malony, Alan Morris, Wyatt Spear, Scott Biersdorff, Burton Smith, Dali Wang, Daniel Ricciuto, Wilfred Post, Michael W. Berry, François Irigoin, Katherine Yelick, Susan L. Graham, Paul Hilfinger, Dan Bonachea, Jimmy Su, Amir Kamil, Kaushik Datta, Phillip Colella, Tong Wen, Jack Dongarra, Piotr Luszczek, Abhinav Bhatele, Stefan M. Freudenberger, Volker Diekert, Anca Muscholl, Maurice Herlihy, J. Eliot B. Moss, Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Algorithms and Scheduling for Distributed Heterogeneous Platforms (GRAAL), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), David Padua, École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), and Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL)
Subjects: Rate-monotonic scheduling, 020203 distributed computing, Computer science, Distributed computing, 02 engineering and technology, Dynamic priority scheduling, Fair-share scheduling, Scheduling (computing), Fixed-priority pre-emptive scheduling, Two-level scheduling, 0202 electrical engineering, electronic engineering, information engineering, Graph (abstract data type), 020201 artificial intelligence & image processing, ComputingMilieux_MISCELLANEOUS
Abstract: International audience
Published: 2011

16. Throughput optimization for micro-factories subject to task and machine failures

Author: Laurent Philippe, Jean-Marc Nicod, Alexandru Dobrila, Anne Benoit, Algorithms and Scheduling for Distributed Heterogeneous Platforms (GRAAL), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon)-Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon), Laboratoire de l'Informatique du Parallélisme (LIP), Franche-Comté Électronique Mécanique, Thermique et Optique - Sciences et Technologies (UMR 6174) (FEMTO-ST), Université de Technologie de Belfort-Montbeliard (UTBM)-Ecole Nationale Supérieure de Mécanique et des Microtechniques (ENSMM)-Université de Franche-Comté (UFC), Université Bourgogne Franche-Comté [COMUE] (UBFC)-Université Bourgogne Franche-Comté [COMUE] (UBFC)-Centre National de la Recherche Scientifique (CNRS), INRIA, École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Université de Technologie de Belfort-Montbeliard (UTBM)-Ecole Nationale Supérieure de Mécanique et des Microtechniques (ENSMM)-Centre National de la Recherche Scientifique (CNRS)-Université de Franche-Comté (UFC), and Université Bourgogne Franche-Comté [COMUE] (UBFC)-Université Bourgogne Franche-Comté [COMUE] (UBFC)
Subjects: distributed systems, Context model, Mathematical optimization, 021103 operations research, Linear programming, Computational complexity theory, optimization heuristics, Computer science, 0211 other engineering and technologies, Fault tolerance, Failure rate, 010103 numerical & computational mathematics, 02 engineering and technology, 01 natural sciences, Scheduling (computing), [INFO.INFO-IU]Computer Science [cs]/Ubiquitous Computing, [INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI], fault tolerance, scheduling, 0101 mathematics, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Heuristics, Algorithm, Time complexity
Abstract: International audience; In this paper, we study the problem of optimizing the throughput for micro-factories subject to failures. The challenge consists in mapping several tasks of different types onto a set of machines. The originality of our approach is the failure model for such applications in which not only the machines are subject to failures but the reliability of a task may depend on its type. The failure rate is unrelated: a probability of failure is associated to each couple (task type, machine). We consider different kind of mappings: in one-to-one mappings, each machine can process only a single task, while several tasks of the same type can be processed by the same machine in specialized mappings. Finally, general mappings have no constraints. The optimal one-to-one mapping can be found in polynomial time for particular problem instances, but the problem is NP-hard in most of the cases. For the most realistic case of specialized mappings, %. For this case, which turns out to be NP-hard, we design several polynomial time heuristics and a linear program allows us to find the optimal solution (in exponential time) for small problem instances. Experimental results show that the best heuristics obtain a good throughput, much better than the throughput achieved with a random mapping. Moreover, we obtain a throughput close to the optimal solution in the particular cases where the optimal throughput can be computed.
Published: 2010

17. On Cluster Resource Allocation for Multiple Parallel Task Graphs

Author: Frédéric Desprez, Henri Casanova, Frédéric Suter, Information and Computer Sciences [Hawaii] (ICS), University of Hawai‘i [Mānoa] (UHM), Algorithms and Scheduling for Distributed Heterogeneous Platforms (GRAAL), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), Centre de Calcul de l'IN2P3 (CC-IN2P3), Institut National de Physique Nucléaire et de Physique des Particules du CNRS (IN2P3)-Centre National de la Recherche Scientifique (CNRS), ANR-08-SEGI-0025,SPADES,Plateforme de Services Pour Architecture Petascale et DistribuéES.(2008), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), and Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL)
Subjects: 020203 distributed computing, Job shop scheduling, Computer Networks and Communications, Data parallelism, Computer science, Distributed computing, Parallel algorithm, Approximation algorithm, 02 engineering and technology, Theoretical Computer Science, Scheduling (computing), Artificial Intelligence, Hardware and Architecture, Scalability, 0202 electrical engineering, electronic engineering, information engineering, Resource allocation, 020201 artificial intelligence & image processing, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Software
Abstract: International audience; Many scientific applications can be structured as Parallel Task Graphs (PTGs), that is, graphs of data-parallel tasks. Adding data-parallelism to a task-parallel application provides opportunities for higher performance and scalability, but poses additional scheduling challenges. In this paper, we study the off-line scheduling of multiple PTGs on a single, homogeneous cluster. The objective is to optimize performance without compromising fairness among the PTGs. We consider the range of previously proposed scheduling algorithms applicable to this problem, both from the applied and the theoretical literature, and we propose minor improvements when possible. Our main contribution is an extensive evaluation of these algorithms in simulation, using both synthetic and real-world application configurations, using two different metrics for performance and one metric for fairness. We identify a handful of algorithms that provide good trade-offs when considering all these metrics. The best algorithm overall is one that structures the schedule as a sequence of phases of increasing duration based on a makespan guarantee produced by an approximation algorithm.
Published: 2010

18. Minimizing Stretch and Makespan of Multiple Parallel Task Graphs via Malleable Allocations

Author: Henri Casanova, Frédéric Suter, Frédéric Desprez, Information and Computer Sciences [Hawaii] (ICS), University of Hawai‘i [Mānoa] (UHM), Algorithms and Scheduling for Distributed Heterogeneous Platforms (GRAAL), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), Centre de Calcul de l'IN2P3 (CC-IN2P3), Institut National de Physique Nucléaire et de Physique des Particules du CNRS (IN2P3)-Centre National de la Recherche Scientifique (CNRS), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), and Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL)
Subjects: 020203 distributed computing, Mathematical optimization, Job shop scheduling, Computer science, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Parallel algorithm, 02 engineering and technology, Parallel computing, Directed graph, Execution time, Scheduling (computing), Scalability, 0202 electrical engineering, electronic engineering, information engineering, Task analysis, Resource allocation, 020201 artificial intelligence & image processing, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC]
Abstract: International audience; Many scientific applications can be structured as Parallel Task Graphs (PTGs), i.e., graphs of data-parallel tasks. Adding data-parallelism to a task-parallel application provides opportunities for higher performance and scalability, but poses scheduling challenges. We study the off-line scheduling of multiple PTGs on a single, homogeneous cluster. The objective is to optimize performance and fairness. We propose a novel algorithm that first computes perfectly fair PTG completion times assuming that each PTG is an ideal malleable job. These completion times are then relaxed so that the schedule is organized as a sequence of periods and is still close to the perfectly fair schedule. Finally, since PTGs are not perfectly malleable, the algorithm increases the execution time of all PTGs uniformly until it can successfully schedule each task in a period. Our evaluation in simulation, using both synthetic and real-world application configurations, shows that our algorithm outperforms previously proposed algorithms when considering two different performance metrics and one fairness metric.
Published: 2010

19. Non-clairvoyant Scheduling of Multiple Bag-of-Tasks Applications

Author: Henri Casanova, Frédéric Vivien, Matthieu Gallet, Information and Computer Sciences [Hawaii] (ICS), University of Hawai‘i [Mānoa] (UHM), Algorithms and Scheduling for Distributed Heterogeneous Platforms (GRAAL), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), European Project: 221002,EC:FP7:PEOPLE,FP7-PEOPLE-2007-4-1-IOF,METAGENOGRIDS(2008), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), and Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL)
Subjects: 020203 distributed computing, Mathematical optimization, Asymptotically optimal algorithm, Computer science, Heuristic, Computation, 0202 electrical engineering, electronic engineering, information engineering, 02 engineering and technology, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Heuristics, Bag of tasks, 020202 computer hardware & architecture, Scheduling (computing)
Abstract: International audience; The bag-of-tasks application model, albeit simple, arises in many application domains and has received a lot of attention in the scheduling literature. Previous works propose either theoretically sound solutions that rely on unrealistic assumptions, or ad-hoc heuristics with no guarantees on performance. This work attempts to bridge this gap through the design of non-clairvoyant heuristics based on solid theoretical foundations. The performance achieved by these heuristics is studied via simulations in a view to comparing them both to previously proposed solutions and to theoretical upper bounds on achievable performance. Also, an interesting theoretical result in this work is that a straightforward on-demand heuristic delivers asymptotically optimal performance when the communications or the computations can be neglected.
Published: 2010

20. A Bi-Criteria Algorithm for Scheduling Parallel Task Graphs on Clusters

Author: Frédéric Suter, Frédéric Desprez, Algorithms and Scheduling for Distributed Heterogeneous Platforms (GRAAL), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), Centre de Calcul de l'IN2P3 (CC-IN2P3), Institut National de Physique Nucléaire et de Physique des Particules du CNRS (IN2P3)-Centre National de la Recherche Scientifique (CNRS), ANR-08-SEGI-0025,SPADES,Plateforme de Services Pour Architecture Petascale et DistribuéES.(2008), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), and Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL)
Subjects: 020203 distributed computing, Computer science, business.industry, Distributed computing, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Task parallelism, Graph theory, Cloud computing, 02 engineering and technology, Parallel computing, computer.software_genre, Scheduling (computing), Grid computing, 0202 electrical engineering, electronic engineering, information engineering, Task analysis, Concurrent computing, 020201 artificial intelligence & image processing, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Cluster analysis, business, computer, Algorithm
Abstract: International audience; Applications structured as parallel task graphs exhibit both data and task parallelism, and arise in many domains. Scheduling these applications on parallel platforms has been a long-standing challenge. In the case of a single homogeneous cluster, most of the existing algorithms focus on the reduction of the application completion time (makespan). But in presence of resource managers such as batch schedulers and due to accentuated pressure on energy concerns, the produced schedules also have to be efficient in terms of resource usage. In this paper we propose a novel bi-criteria algorithm, called biCPA, able to optimize these two performance metrics either simultaneously or separately. Using simulation over a wide range of experimental scenarios, we find that biCPA leads to better results than previously published algorithms.
Published: 2010

21. A Fair Decentralized Scheduler for Bag-of-tasks Applications on Desktop Grids

Author: Javier Celaya, Loris Marchal, University of Zaragoza - Universidad de Zaragoza [Zaragoza], Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Algorithms and Scheduling for Distributed Heterogeneous Platforms (GRAAL), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), and Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL)
Subjects: 020203 distributed computing, Grid scheduling, Computer science, Distributed computing, Processor scheduling, 02 engineering and technology, Peer-to-peer, Load balancing (computing), computer.software_genre, Bag of tasks, Scheduling (computing), Grid computing, Distributed algorithm, 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, computer
Abstract: short paper; International audience; Desktop Grids have become very popular nowadays, with projects that include hundred of thousands computers. Desktop grid scheduling faces two challenges. First, the platform is volatile, since users may reclaim their computer at any time, which makes centralized schedulers inappropriate. Second, desktop grids are likely to be shared among several users, thus we must be particularly careful to ensure a fair sharing of the resources. In this paper, we propose a decentralized scheduler for bag-of-tasks applications on desktop grids, which ensures a fair and efficient use of the resources. It aims to provide a similar share of the platform to every application by minimizing their maximum stretch, using completely decentralized algorithms and protocols.
Published: 2010

22. Scheduling complex streaming applications on the Cell processor

Author: Mathias Jacquelin, Matthieu Gallet, Loris Marchal, Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Optimisation des ressources : modèles, algorithmes et ordonnancement (ROMA), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), Algorithms and Scheduling for Distributed Heterogeneous Platforms (GRAAL), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), and Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL)
Subjects: Linear programming, Computer science, Processor scheduling, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], 0102 computer and information sciences, 02 engineering and technology, Parallel computing, mixed linear programming, Application software, computer.software_genre, 01 natural sciences, scheduling complex streaming applications, Scheduling (computing), multicore processor, 0202 electrical engineering, electronic engineering, information engineering, streaming applications, Embedded computing, 020203 distributed computing, Multi-core processor, Scheduling, multicore, Ranging, Video on demand, Throughput, multiprocessing systems, Multicore processing, optimal solution, Grid computing, Streaming media, 010201 computation theory & mathematics, Embedding, STI cell BE processor, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Laboratories, Encoder, computer, NP-complete problems, cell processor
Abstract: International audience; In this paper, we consider the problem of scheduling streaming applications described by complex task graphs on a heterogeneous multicore processor, the STI Cell BE processor. We first present a theoretical model of the Cell processor. Then, we use this model to express the problem of maximizing the throughput of a streaming application on this processor. Although the problem is proven NP-complete, we present an optimal solution based on mixed linear programming. This allows us to compute the optimal mapping for a number of applications, ranging from a real audio encoder to complex random task graphs. These mappings are then tested on two platforms embedding Cell processors, and compared to simple heuristic solutions. We show that we are able to achieve a good speed-up, whereas the heuristic solutions generally fail to deal with the strong memory and communication constraints.
Published: 2010

23. Analysis of Tasks Reallocation in a Dedicated Grid Environment

Author: Yves Caniou, Ghislain Charrier, Frédéric Desprez, Algorithms and Scheduling for Distributed Heterogeneous Platforms (GRAAL), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), Laboratoire de l'Informatique du Parallélisme (LIP), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), INRIA, Grid'5000, École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), and Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL)
Subjects: 060201 languages & linguistics, Software_OPERATINGSYSTEMS, Computer science, Distributed computing, 06 humanities and the arts, 02 engineering and technology, Reallocation, computation grids, Grid, computer.software_genre, batch schedulers, Scheduling (computing), metascheduler, Grid computing, Server, 0602 languages and literature, 0202 electrical engineering, electronic engineering, information engineering, Resource allocation, 020201 artificial intelligence & image processing, Resource management, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Cluster analysis, Heuristics, computer
Abstract: In this paper, we study the impact of tasks reallocation onto a grid platform. More precisely, we target a multi-cluster environment where clusters can be homogeneous or heterogeneous, and use different policies for their local resources management. In this context, we propose a reallocation mechanism that migrates jobs in waiting state from one cluster to another one. We perform simulations using real traces of jobs to study the benefit of reallocation. We compare two different algorithms providing the reallocation mechanism, each with several heuristics to schedule jobs. Results show that in some cases it is possible to obtain a substantial gain on the average job response time (almost up to a factor of four). In the other cases, the reallocation mechanism is beneficial most of the time for the jobs of the users. It is thus interesting to implement a reallocation mechanism in a Grid framework.
Published: 2010

24. Computing the throughput of probabilistic and replicated streaming applications

Author: Matthieu Gallet, Fanny Dufossé, Bruno Gaujal, Yves Robert, Anne Benoit, Algorithms and Scheduling for Distributed Heterogeneous Platforms (GRAAL), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), Laboratoire de l'Informatique du Parallélisme (LIP), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Middleware efficiently scalable (MESCAL), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire d'Informatique de Grenoble (LIG), Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Laboratoire d'Informatique de Grenoble (LIG), Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS)-Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon)-Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon), Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Joseph Fourier - Grenoble 1 (UJF), and INRIA
Subjects: 020203 distributed computing, replication, Markov chain, Computer science, Scheduling, Computation, Probabilistic logic, probabilistic streaming applications, 02 engineering and technology, Parallel computing, Petri net, 01 natural sciences, Polynomial algorithm, Exponential function, Scheduling (computing), 010104 statistics & probability, Bounded function, 0202 electrical engineering, electronic engineering, information engineering, ACM: C.: Computer Systems Organization/C.4: PERFORMANCE OF SYSTEMS/C.4.5: Reliability, availability, and serviceability, 0101 mathematics, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Algorithm, throughput, timed Petri nets
Abstract: International audience; In this paper, we investigate how to compute the throughput of probabilistic and replicated streaming applications. We are given (i) a streaming application whose dependence graph is a linear chain; (ii) a one-to-many mapping of the application onto a fully heterogeneous target, where a processor is assigned at most one application stage, but where a stage can be replicated onto a set of processors; and (iii) a set of IID (Independent and Identically-Distributed) variables to model each computation and communication time in the mapping. How can we compute the throughput of the application, i.e., the rate at which data sets can be processed? We consider two execution models, the STRICT model where the actions of each processor are sequentialized, and the OVERLAP model where a processor can compute and communicate in parallel. The problem is easy when application stages are not replicated, i.e., assigned to a single processor: in that case the throughput is dictated by the critical hardware resource. However, when stages are replicated, i.e., assigned to several processors, the problem becomes surprisingly complicated: even in the deterministic case, the optimal throughput may be lower than the smallest internal resource throughput. To the best of our knowledge, the problem has never been considered in the probabilistic case. The first main contribution of the paper is to provide a general method (although of exponential cost) to compute the throughput when mapping parameters follow IID exponential laws. This general method is based upon the analysis of timed Petri nets deduced from the application mapping; it turns out that these Petri nets exhibit a regular structure in the OVERLAP model, thereby enabling to reduce the cost and provide a polynomial algorithm. The second main contribution of the paper is to provide bounds for the throughput when stage parameters are arbitrary IID and NBUE (New Better than Used in Expectation) variables: the throughput is bounded from below by the exponential case and bounded from above by the deterministic case.
Published: 2010

25. Multi-criteria scheduling of precedence task graphs on heterogeneous platforms

Author: Anne Benoit, Yves Robert, Mourad Hakem, Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Algorithms and Scheduling for Distributed Heterogeneous Platforms (GRAAL), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), Innovative Computing Laboratory [Knoxville] (ICL), The University of Tennessee [Knoxville], École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), and Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL)
Subjects: General Computer Science, Scheduling heuristics, Computer science, Distributed computing, 020206 networking & telecommunications, Fault tolerance, 02 engineering and technology, 020202 computer hardware & architecture, Scheduling (computing), Low complexity, Complex algorithm, Multi criteria, 0202 electrical engineering, electronic engineering, information engineering, Latency (engineering), Heuristics
Abstract: International audience; Latency, fault tolerance and reliability are important requirements for several applications that are time critical in nature: such applications require guarantees in terms of latency, even when processors are subject to failures. In this paper, we propose a fault-tolerant scheduling heuristic for mapping precedence task graphs on heterogeneous systems. Our approach is based on an active replication scheme, capable of supporting ε arbitrary fail-silent/fail-stop processor failures, and hence valid results will be provided even if ε processors fail. First we focus on a bi-criteria approach, where we aim at minimizing the latency given a fixed number of failures supported in the system, or the other way round. Next we derive a more complex algorithm in which we not only minimize latency and support a fixed number of failures, but also improve the overall reliability. Major achievements include low complexity of the new algorithms, and a drastic reduction of the number of additional communications induced by the replication mechanism. Experimental results demonstrate that our heuristics, despite their lower complexity, outperform their direct competitor, the fault-tolerance based active replication scheduling algorithm FTBAR.
Published: 2010

26. Mapping pipelined applications with replication to increase throughput and reliability

Author: Oliver Sinnen, Anne Benoit, Yves Robert, Loris Marchal, Algorithms and Scheduling for Distributed Heterogeneous Platforms (GRAAL), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), Department of Electrical and Computer Engineering [Auckland ] (ECE), University of Auckland [Auckland], Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Optimisation des ressources : modèles, algorithmes et ordonnancement (ROMA), and Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL)
Subjects: Difficult problem, 020203 distributed computing, Optimization problem, Computer science, 02 engineering and technology, Parallel computing, Supercomputer, 020202 computer hardware & architecture, Scheduling (computing), fault-tolerance, Exact algorithm, State space search, Bicriteria optimization, 0202 electrical engineering, electronic engineering, information engineering, workflows, scheduling, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Heuristics
Abstract: International audience; apping and scheduling an application onto the processors of a parallel system is a difficult problem. This is true when performance is the only objective, but becomes worse when a second optimization criterion like reliability is involved. In this paper we investigate the problem of mapping an application consisting of several consecutive stages, i.e., a pipeline, onto heterogeneous processors, while considering both the performance, measured as throughput, and the reliability. The mechanism of replication, which refers to the mapping of an application stage onto more than one processor, can be used to increase throughput but also to increase reliability. Finding the right replication trade-off plays a pivotal role for this bi-criteria optimization problem. Our formal model includes heterogeneous processors, both in terms of execution speed as well as in terms of reliability. We study the complexity of the various sub problems and show how a solution can be obtained for the polynomial cases. For the general NP-hard problem, heuristics are presented and experimentally evaluated. We further propose the design of an exact algorithm based on A* state space search which allows us to evaluate the performance of our heuristics for small problem instances.
Published: 2009

27. Optimizing the Latency of Streaming Applications under Throughput and Reliability Constraints

Author: Anne Benoit, Mourad Hakem, Yves Robert, Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Optimisation des ressources : modèles, algorithmes et ordonnancement (ROMA), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), Algorithms and Scheduling for Distributed Heterogeneous Platforms (GRAAL), Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon)-Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon), Franche-Comté Électronique Mécanique, Thermique et Optique - Sciences et Technologies (UMR 6174) (FEMTO-ST), Université de Technologie de Belfort-Montbeliard (UTBM)-Ecole Nationale Supérieure de Mécanique et des Microtechniques (ENSMM)-Université de Franche-Comté (UFC), Université Bourgogne Franche-Comté [COMUE] (UBFC)-Université Bourgogne Franche-Comté [COMUE] (UBFC)-Centre National de la Recherche Scientifique (CNRS), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Technologie de Belfort-Montbeliard (UTBM)-Ecole Nationale Supérieure de Mécanique et des Microtechniques (ENSMM)-Centre National de la Recherche Scientifique (CNRS)-Université de Franche-Comté (UFC), and Université Bourgogne Franche-Comté [COMUE] (UBFC)-Université Bourgogne Franche-Comté [COMUE] (UBFC)
Subjects: fault tolerant computing, Constraint optimization, Computer science, Distributed computing, Scheduling algorithm, Processor scheduling, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], reliability, Throughput, processor failure tolerance, 02 engineering and technology, realistic one-port model, Scheduling (computing), 0202 electrical engineering, electronic engineering, information engineering, Algorithm design and analysis, Parallel processing, Latency (engineering), throughput constraint, Cluster analysis, latency optimization, latency, scheduling streaming application, 020203 distributed computing, Delay, Constrained optimization, 020206 networking & telecommunications, Fault tolerance, Computational modeling, constraint handling, reliability constraint, Streaming applications, Streaming media, Algorithm design, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Laboratories
Abstract: International audience; In this paper, we deal with the problem of scheduling streaming applications on unreliable heterogeneous platforms. We use the realistic one-port model with full computation/communication overlap. We deal with three optimization objectives. The first two, latency and throughput, are performance-related while the third, tolerating a given number of processor failures, is reliability-oriented. The major contribution of this paper is the design of a new scheduling algorithm to minimize latency under both throughput and reliability constraints. We provide a comprehensive set of experimental results, that fully demonstrate the usefulness of the proposed algorithm.
Published: 2009

28. Resource-aware allocation strategies for divisible loads on large-scale systems

Author: Jean-François Pineau, Anne Benoit, Frédéric Vivien, Loris Marchal, Yves Robert, Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Algorithms and Scheduling for Distributed Heterogeneous Platforms (GRAAL), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), and Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL)
Subjects: 020203 distributed computing, Single-machine scheduling, Computer science, Distributed computing, Preemption, Approximation algorithm, Processor scheduling, 02 engineering and technology, computer.software_genre, Scheduling (computing), Grid computing, Server, 0202 electrical engineering, electronic engineering, information engineering, Resource allocation, 020201 artificial intelligence & image processing, Resource management, Heuristics, computer
Abstract: International audience; In this paper, we deal with the large-scale divisible load problem studied in. We show how to reduce this problem to a classical preemptive scheduling problem on a single machine, thereby establishing new complexity results, and providing new approximation algorithms and heuristics that subsume those presented in. We also give some hints on how to extend the results to a more realistic framework where communication costs are taken into account.
Published: 2009

29. Throughput optimization for micro-factories subject to failures

Author: Alexandru Dobrila, Jean-Marc Nicod, Anne Benoit, Laurent Philippe, Algorithms and Scheduling for Distributed Heterogeneous Platforms (GRAAL), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), Laboratoire de l'Informatique du Parallélisme (LIP), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Franche-Comté Électronique Mécanique, Thermique et Optique - Sciences et Technologies (UMR 6174) (FEMTO-ST), Université de Technologie de Belfort-Montbeliard (UTBM)-Ecole Nationale Supérieure de Mécanique et des Microtechniques (ENSMM)-Centre National de la Recherche Scientifique (CNRS)-Université de Franche-Comté (UFC), Université Bourgogne Franche-Comté [COMUE] (UBFC)-Université Bourgogne Franche-Comté [COMUE] (UBFC), Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon)-Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon), Université de Technologie de Belfort-Montbeliard (UTBM)-Ecole Nationale Supérieure de Mécanique et des Microtechniques (ENSMM)-Université de Franche-Comté (UFC), Université Bourgogne Franche-Comté [COMUE] (UBFC)-Université Bourgogne Franche-Comté [COMUE] (UBFC)-Centre National de la Recherche Scientifique (CNRS), and INRIA
Subjects: 021103 operations research, Computational complexity theory, Computer science, Scheduling, System recovery, 0211 other engineering and technologies, Random mapping, Fault Tolerance, Fault tolerance, 02 engineering and technology, Parallel computing, 020202 computer hardware & architecture, Scheduling (computing), [INFO.INFO-IU]Computer Science [cs]/Ubiquitous Computing, [INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI], Computer engineering, Distributed Systems, 0202 electrical engineering, electronic engineering, information engineering, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Heuristics, Time complexity, Optimization Heuristics
Abstract: International audience; In this paper, we study the problem of optimizing the throughput for micro-factories subject to failures. The challenge consists in mapping several tasks onto a set of machines. The originality of our approach is the failure model for such applications in which tasks are subject to failures rather than machines. If there is exactly one task per machine in the mapping, then we prove that the optimal solution can be computed in polynomial time. However, the problem becomes NP-hard if several tasks can be assigned to the same machine. Several polynomial time heuristics are presented for the most realistic {\em specialized} setting, in which tasks of a same type can be mapped onto the same machine. Experimental results show that the best heuristics obtain a good throughput, much better than the throughput obtained with a random mapping. Moreover, we obtain a throughput close to the optimal solution in the particular cases on which the optimal throughput can be computed.
Published: 2009

30. Efficient Scheduling of Task Graph Collections on Heterogeneous Resources

Author: Loris Marchal, Frédéric Vivien, Matthieu Gallet, Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Algorithms and Scheduling for Distributed Heterogeneous Platforms (GRAAL), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), and Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL)
Subjects: 020203 distributed computing, Schedule, Theoretical computer science, Linear programming, Computer science, Heuristic, Distributed computing, Processor scheduling, Graph theory, 02 engineering and technology, computer.software_genre, Application software, Grid, Scheduling (computing), Workflow, Grid computing, 0202 electrical engineering, electronic engineering, information engineering, Resource allocation, 020201 artificial intelligence & image processing, Resource management, Heuristics, computer
Abstract: International audience; In this paper, we focus on scheduling jobs on computing grids. In our model, a grid job is made of a large collection of input data sets, which must all be processed by the same task graph or workflow, thus resulting in a collection of task graphs problem. We are looking for a competitive scheduling algorithm not requiring complex control. We thus only consider single-allocation strategies. In addition to a mixed linear programming approach to find an optimal allocation, we present different heuristic schemes. Then, using simulations, we compare the performance of our different heuristics to the performance of a classical scheduling policy in Grids, HEFT. The results show that some of our static-scheduling policies take advantage of their platform and application knowledge and outperform HEFT, especially under communication-intensive scenarios. In particular, one of our heuristics, DELEGATE, almost always achieves the best performance while having lower running times than HEFT.
Published: 2009

31. Computing the throughput of replicated workflows on heterogeneous platforms

Author: Yves Robert, Bruno Gaujal, Anne Benoit, Matthieu Gallet, Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Algorithms and Scheduling for Distributed Heterogeneous Platforms (GRAAL), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), Middleware efficiently scalable (MESCAL), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire d'Informatique de Grenoble (LIG), Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS), ANR-07-BLAN-0192,StochaGrid,Scheduling algorithms and stochastic performance models for workflow applications on dynamic grid platforms(2007), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Laboratoire d'Informatique de Grenoble (LIG), Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS)-Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon)-Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon), and Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Joseph Fourier - Grenoble 1 (UJF)
Subjects: Timed Petri nets, Critical resource, Computational complexity theory, Computer science, Scheduling, Distributed computing, 0102 computer and information sciences, 02 engineering and technology, Parallel computing, Petri net, 01 natural sciences, Scheduling (computing), Workflows, Heterogeneous platforms, Workflow, 010201 computation theory & mathematics, 020204 information systems, Period, 0202 electrical engineering, electronic engineering, information engineering, Resource allocation, Graph (abstract data type), [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC]
Abstract: International audience; In this paper, we focus on computing the throughput of replicated workflows. Given a streaming application whose dependence graph is a linear chain, and a mapping of this application onto a fully heterogeneous platform, how can we compute the optimal throughput, or equivalently the minimal period? The problem is easy when workflow stages are not replicated, i.e., assigned to a single processor: in that case the period is dictated by the critical hardware resource. But when stages are replicated, i.e., assigned to several processors, the problem gets surprisingly complicated, and we provide examples where the optimal period is larger than the largest cycle-time of any resource. We then show how to model the problem as a timed Petri net to compute the optimal period in the general case, and we provide a polynomial algorithm for the one-port communication model with overlap. Finally, we report comprehensive simulation results on the gap between the optimal period and the largest resource cycle-time.
Published: 2009

32. Multi-criteria scheduling of pipeline workflows (and application to the JPEG encoder)

Author: Anne Benoit, Harald Kosch, Veronika Rehn-Sonigo, Yves Robert, Algorithms and Scheduling for Distributed Heterogeneous Platforms (GRAAL), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), Laboratoire de l'Informatique du Parallélisme (LIP), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Faculty of Informatics and Mathematics (FMI), Fakultät für Informatik und Mathematik, École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), and Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL)
Subjects: 020203 distributed computing, Computer science, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], 02 engineering and technology, Parallel computing, Theoretical Computer Science, Scheduling (computing), Digital image, Workflow, Hardware and Architecture, 020204 information systems, 0202 electrical engineering, electronic engineering, information engineering, Algorithmic skeleton, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Heuristics, Software
Abstract: International audience; Mapping workflow applications onto parallel platforms is a challenging problem, even for simple application patterns such as pipeline graphs. Several antagonist criteria should be optimized, such as throughput and latency (or a combination). A typical application class is digital image coding, where images are processed in steady-state mode. In this paper, we study the general bi-criteria mapping problem (minimizing period and latency) for pipeline graphs on communication homogeneous platforms. We present an integer linear programming formulation for this NP-hard problem. Furthermore, we provide several efficient polynomial bi-criteria heuristics, whose relative performance is evaluated through extensive simulations. As a case study, we provide simulations and MPI experimental results for the JPEG encoder application pipeline on a cluster of workstations.
Published: 2009

33. Ocean-Atmosphere Application Scheduling within DIET

Author: Frédéric Desprez, Yves Caniou, Eddy Caron, Ghislain Charrier, V. Pichon, E. Maisonnave, Laboratoire de l'Informatique du Parallélisme (LIP), Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon), Algorithms and Scheduling for Distributed Heterogeneous Platforms (GRAAL), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), Université de Lyon-École normale supérieure - Lyon (ENS Lyon)-Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Centre Européen de Recherche et de Formation Avancée en Calcul Scientifique (CERFACS), CERFACS, Efficient runtime systems for parallel architectures (RUNTIME), Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS), EDF R&D (EDF R&D), EDF (EDF), IEEE Computer Society, ANR-05-CIGC-0011,LEGO,League for Efficient Grid Operations(2005), INRIA, Grid'5000, École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), and Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS)
Subjects: 010504 meteorology & atmospheric sciences, Computer science, Real-time computing, Weather forecasting, 02 engineering and technology, Dynamic priority scheduling, computer.software_genre, 01 natural sciences, Fair-share scheduling, Scheduling (computing), DIET, Server, 0202 electrical engineering, electronic engineering, information engineering, Mixed parallelism, Computer Science::Operating Systems, Physics::Atmospheric and Oceanic Physics, 0105 earth and related environmental sciences, 020203 distributed computing, Scheduling, Grid, Grid computing, Ocean-Atmosphere application, Two-level scheduling, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], computer
Abstract: In this report, we tackle the problem of scheduling an Ocean-Atmosphere application in an heterogeneous environment. The application is used for long term climate forecast. In this context, we analyzed the execution of an experiment. An experiment is composed of several identical simulations composed of parallel tasks. On homogeneous platforms, we propose a heuristic and its optimizations, all based on the same idea: we divide the processors into disjoint sets, each group executing parallel tasks. On heterogeneous platforms the algorithm presented is applied on subsets of simulations. The computation of the subsets is done greedily and aims at minimizing the execution time by sending each subset on a cluster. We performed experiments on the french research grid \emph{Grid'5000} which exhibited some technical difficulties. We also present some modifications done to the heuristics to minimize the impact of these technical difficulties. Our simulations are then validated by experimentations.
Published: 2008

34. Ocean-Atmosphere Modelization over the Grid

Author: F. Desprez, A. Chis, E. Maisonnave, G. Charrier, Eddy Caron, Y. Caniou, Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Algorithms and Scheduling for Distributed Heterogeneous Platforms (GRAAL), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), Dynamic Networks (DNET), Centre Européen de Recherche et de Formation Avancée en Calcul Scientifique (CERFACS), Feng, Wu-chi and Yang, Yuanyuan, ANR-05-CIGC-0011,LEGO,League for Efficient Grid Operations(2005), Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon), Université de Lyon-École normale supérieure - Lyon (ENS Lyon)-Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), CERFACS, and INRIA, LIP
Subjects: 010504 meteorology & atmospheric sciences, Computer science, Processor scheduling, 02 engineering and technology, Parallel computing, computer.software_genre, 01 natural sciences, Scheduling (computing), Ordonnancement, 0202 electrical engineering, electronic engineering, information engineering, ComputingMilieux_MISCELLANEOUS, 0105 earth and related environmental sciences, Job shop scheduling, Heuristic, Scheduling, 020206 networking & telecommunications, Directed graph, Directed acyclic graph, Grid, Application Ocean-Atmosphere, Grid computing, 13. Climate action, Knapsack problem, Ocean-Atmosphere application, Calcul sur grille, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], computer
Abstract: In this report, we tackle the problem of scheduling an Ocean-Atmosphere application used for climate prediction on the grid. An experiment is composed of several 1D-meshes of identical DAGs composed of parallel tasks. To obtain a good completion time, we divide groups of processors into sets each working on parallel tasks. The group sizes are chosen by computing the best makespan for several grouping possibilities. We improved this heuristic method by different means. The improvement yielding to the best makespan is the representation of the problem as an instance of the Knapsack problem. As this heuristic is firstly designed for homogeneous platforms, we present its adaptation to heterogeneous platforms. Simulations show improvements of the makespan up to 12%.; Dans ce rapport, nous nous attaquons au problème d’ordonnancement d’une application Ocean-Atmosphere utilisée pour les prévisions d’évolution du climat sur la grille. Une expérience est composée de plusieurs chaînes de DAGs identiques composés de tâches parallèles. Pour obtenir un bon temps d’exécution,nous divisons des groupes de processeurs en ensembles, chacun travaillant sur une tâche parallèle. Les tailles des groupes sont choisis en calculant le meilleur temps d’exécution pour plusieurs possibilités de regroupement. Nous avons optimisé cette heuristique par différents moyens. L’optimisation amenant les meilleurs résultats et celle utilisant une représentation basée sur le problème du sac à dos. Cette heuristique a tout d’abord été conçue pour travailler sur des plate-formes homogènes, nous présentons aussi une adaptation pour plate-formes hétérogènes. Les simulations ont montrées des améliorations allant jusqu’à 12%.
Published: 2008

35. Parallelization and Distribution Strategies of Large Bioinformatics Requests over the Grid

Author: Frédéric Desprez, Eddy Caron, Gaël Le Mahec, Laboratoire de l'Informatique du Parallélisme (LIP), Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon), Algorithms and Scheduling for Distributed Heterogeneous Platforms (GRAAL), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), Université de Lyon-École normale supérieure - Lyon (ENS Lyon)-Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Modélisation, Information et Systèmes - UR UPJV 4290 (MIS), Université de Picardie Jules Verne (UPJV), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), and Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL)
Subjects: 020203 distributed computing, Adaptive algorithm, Linear programming, Computer science, Computation, Distributed computing, High Performance Computing, 020206 networking & telecommunications, Execution Time Average, Wait Time Average, 02 engineering and technology, Parallel computing, Grid, Supercomputer, Replication (computing), Scheduling (computing), 0202 electrical engineering, electronic engineering, information engineering, Data Replication, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Data Placement, Data placement
Abstract: International audience; This paper focuses on simultaneous scheduling of computation and data replication for life science applications on the grid. We present an adaptive algorithm based on the SRA algorithm (Static Joint Replication and Scheduling) [4] with more dynamicity for the jobs frequencies. The use of a linear program giving a databases mapping on the nodes and a jobs distribution schema, ensures us that our data placement and jobs distribution will be near the optimal solution, as long as the informations about the jobs frequencies are right. We validate our results with large jobs submissions simulations on a realistic platform.
Published: 2008

36. Mapping linear workflows with computation/communication overlap

Author: Kunal Agrawal, Yves Robert, Anne Benoit, Computer Science and Artificial Intelligence Laboratory [Cambridge] (CSAIL), Massachusetts Institute of Technology (MIT), Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Laboratoire de l'informatique du parallélisme, Algorithms and Scheduling for Distributed Heterogeneous Platforms (GRAAL), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), and Université de Lyon-École normale supérieure - Lyon (ENS Lyon)
Subjects: Computational complexity theory, Computer science, Distributed computing, Computation, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], 02 engineering and technology, Complexity results, Scheduling (computing), Workflow, 020204 information systems, 0202 electrical engineering, electronic engineering, information engineering, [INFO]Computer Science [cs], ComputingMilieux_MISCELLANEOUS, Pipeline graphs, 020203 distributed computing, Scheduling, Approximation algorithm, Graph theory, Mapping, Multithreading, Period, Latency, Feedback loop, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Architectural model
Abstract: This paper presents theoretical results related to mapping and scheduling linear workowsonto heterogeneous platforms. We use a realistic architectural model with bounded communication capabilities and full computation/communication overlap. This model is representativeof current multi-threaded systems. In these workow applications, the goal is often to maximizethroughput or to minimize latency. We present several complexity results related to both thesecriteria.To be precise, we prove that maximizing the throughput is NP-complete even for homogeneous platforms and minimizing the latency is NP-complete for heterogeneous platforms.Moreover, we present an approximation algorithm for throughput maximization for linear chainapplications on homogeneous platforms, and an approximation algorithm for latency minimization for linear chain applications on all platforms where communication is homogeneous (theprocessor speeds can differ). In addition, we present algorithms for several important specialcases for linear chain applications. Finally, we consider the implications of adding feedbackloops to linear chain applications.
Published: 2008

37. Minimizing the Stretch When Scheduling Flows of Divisible Requests

Author: Arnaud Legrand, Alan Su, Frédéric Vivien, Middleware efficiently scalable (MESCAL), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire d'Informatique de Grenoble (LIG), Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Joseph Fourier - Grenoble 1 (UJF), Google Inc, Research at Google, Algorithms and Scheduling for Distributed Heterogeneous Platforms (GRAAL), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon)-Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon), Laboratoire de l'Informatique du Parallélisme (LIP), Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), and Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)
Subjects: Mathematical optimization, 021103 operations research, Competitive analysis, Linear programming, Computer science, 0211 other engineering and technologies, General Engineering, Symmetric multiprocessor system, 0102 computer and information sciences, 02 engineering and technology, Management Science and Operations Research, 01 natural sciences, Multi-objective optimization, Scheduling (computing), 010201 computation theory & mathematics, Artificial Intelligence, Problem domain, Online algorithm, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Heuristics, Software
Abstract: International audience; In this paper, we consider the problem of scheduling distributed biological sequence comparison applications. This problem lies in the divisible load framework with negligible communication costs. Thus far, very few results have been proposed for this model. We discuss and select relevant metrics for this framework: namely max-stretch and sum-stretch. We explain the relationship between our model and the preemptive single processor case, and we show how to extend algorithms that have been proposed in the literature for the single processor model to the divisible multi-processor problem domain. We recall known results on closely related problems, we show how to minimize the max-stretch on unrelated machines either in the divisible load model or with preemption, we derive new lower bounds on the competitive ratio of any online algorithm, we present new competitiveness results for existing algorithms, and we develop several new online heuristics. We also address the Pareto optimization of max-stretch. Then, we extensively study the performance of these algorithms and heuristics under realistic scenarios. Our study shows that all previously proposed guaranteed heuristics for max-stretch for the single processor model are inefcient in practice. In contrast, we show that our online algorithms based on linear programming are in practice near-optimal solutions for max-stretch. Our study also clearly suggests heuristics that are efcient for both metrics, although a combined optimization is in theory not possible in the general case.
Published: 2008

38. Optimizing latency and reliability of pipeline workflow applications

Author: Veronika Rehn-Sonigo, Anne Benoit, Yves Robert, Algorithms and Scheduling for Distributed Heterogeneous Platforms (GRAAL), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), Laboratoire de l'Informatique du Parallélisme (LIP), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Laboratoire de l'informatique du parallélisme, Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), INRIA, LIP, Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), and Université de Lyon-École normale supérieure - Lyon (ENS Lyon)
Subjects: FOS: Computer and information sciences, Computer science, Distributed computing, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Temps de réponse, 0102 computer and information sciences, 02 engineering and technology, Parallel computing, 01 natural sciences, Complexity results, Scheduling (computing), Response time, Hétérogénéité, Ordonnancement, 0202 electrical engineering, electronic engineering, information engineering, Fiabilité, [INFO]Computer Science [cs], Latency (engineering), ComputingMilieux_MISCELLANEOUS, 020203 distributed computing, Résultats de complexité, Scheduling, Reliability, Workflow, Computer Science - Distributed, Parallel, and Cluster Computing, 010201 computation theory & mathematics, Distributed, Parallel, and Cluster Computing (cs.DC), Heterogeneity, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC]
Abstract: Mapping applications onto heterogeneous platforms is a difficult challenge, even for simple application patterns such as pipeline graphs. The problem is even more complex when processors are subject to failure during the execution of the application. In this paper, we study the complexity of a bi-criteria mapping which aims at optimizing the latency (i.e., the response time) and the reliability (i.e., the probability that the computation will be successful) of the application. Latency is minimized by using faster processors, while reliability is increased by replicating computations on a set of processors. However, replication increases latency (additional communications, slower processors). The application fails to be executed only if all the processors fail during execution. While simple polynomial algorithms can be found for fully homogeneous platforms, the problem becomes NP-hard when tackling heterogeneous platforms. This is yet another illustration of the additional complexity added by heterogeneity.; L’ordonnancement et l’allocation des applications sur plates-formes hétérogènes sont des problèmes cruciaux, même pour des applications simples comme des graphes en pipeline. Le problème devient même encore plus complexe quand les processeurs peuvent tomber en panne pendant l’exécution de l’application. Dans cet article, nous étudions la complexité d’une allocation bi-critère qui vise à optimiser la latence (i.e., le temps de réponse) et la fiabilité (i.e., la probabilité que le calcul réussisse)de l’application. La latence est minimisée en utilisant des processeurs rapides, tandis que la fiabilité est augmentée en répliquant les calculs sur un ensemble de processeurs. Toutefois, la réplication augmente la latence (communications additionnelles et processeurs moins rapides). L’application échoue à être exécutée seulement si tout les processeurs échouent pendant l’exécution. Des algorithmes simples en temps polynomial peuvent être trouvés pour plates-formes complètement homogènes,tandis que le problème devient NP-dur quand on s’attaque aux plateformes hétérogènes. C’est encore une autre illustration de la complexité additionnelle due à l’hétérogénéité.
Published: 2008

39. Comments on 'Design and performance evaluation of load distribution strategies for multiple loads on heterogeneous linear daisy chain networks'

Author: Matthieu Gallet, Yves Robert, Frédéric Vivien, Algorithms and Scheduling for Distributed Heterogeneous Platforms (GRAAL), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), Laboratoire de l'Informatique du Parallélisme (LIP), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), and Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL)
Subjects: FOS: Computer and information sciences, 020203 distributed computing, Computer Networks and Communications, Computer science, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Load distribution, 0102 computer and information sciences, 02 engineering and technology, Parallel computing, 01 natural sciences, Execution time, Theoretical Computer Science, Scheduling (computing), Computer Science - Distributed, Parallel, and Cluster Computing, 010201 computation theory & mathematics, Artificial Intelligence, Hardware and Architecture, 0202 electrical engineering, electronic engineering, information engineering, Distributed, Parallel, and Cluster Computing (cs.DC), [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Daisy chain, Software
Abstract: Min, Veeravalli, and Barlas have proposed strategies to minimize the overall execution time of one or several divisible loads on a heterogeneous linear network, using one or more installments [Han Min Wong, Bharadwaj Veeravalli, Scheduling divisible loads on heterogeneous linear daisy chain networks with arbitrary processor release times, IEEE Trans. Parallel Distrib. Syst. 15 (3) (2004) 273-288; Han Min Wong, Bharadwaj Veeravalli, Gerassimos Barlas, Design and performance evaluation of load distribution strategies for multiple divisible loads on heterogeneous linear daisy chain networks, J. Parallel Distrib. Comput. 65 (12) (2005) 1558-1577]. We show using a very simple example that their approach does not always produce a solution and that, when it does, the solution is often suboptimal. We also show how to find an optimal scheduling for any instance, once the number of installments per load is given. Finally, we formally prove that under a linear cost model, as in both the above-mentioned references, an optimal schedule has an infinite number of installments. Therefore such a cost model should not be used to design practical multi-installment algorithms.
Published: 2008

40. The impact of heterogeneity on master-slave scheduling

Author: Jean-François Pineau, Frédéric Vivien, Yves Robert, Algorithms and Scheduling for Distributed Heterogeneous Platforms (GRAAL), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), Laboratoire de l'Informatique du Parallélisme (LIP), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon)-Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), and Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL)
Subjects: Rate-monotonic scheduling, Mathematical optimization, Computer Networks and Communications, Deterministic algorithm, Computer science, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], 0102 computer and information sciences, 02 engineering and technology, Dynamic priority scheduling, 01 natural sciences, Fair-share scheduling, Theoretical Computer Science, Scheduling (computing), Off-line algorithm, Fixed-priority pre-emptive scheduling, Artificial Intelligence, 0202 electrical engineering, electronic engineering, information engineering, Time complexity, Master-Slave, O-line algorithm, Job shop scheduling, Competitive analysis, Scheduling, Computer Graphics and Computer-Aided Design, 010201 computation theory & mathematics, Hardware and Architecture, Two-level scheduling, 020201 artificial intelligence & image processing, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Heuristics, Software, On-line algorithm
Abstract: International audience; In this paper, we assess the impact of heterogeneity on scheduling independent tasks on master-slave platforms. We assume a realistic one-port model where the master can communicate with a single slave at any time. We target both on-line and off-line scheduling problems, and we focus on simpler instances where all tasks have the same size. While such on-line problems can be solved in polynomial time on homogeneous platforms, we show that there does not exist any optimal deterministic algorithm for heterogeneous platforms. Whether the source of heterogeneity comes from computation speeds, or from communication bandwidths, or from both, we establish lower bounds on the competitive ratio of any deterministic algorithm. We provide such bounds for the most important objective functions: the minimization of the makespan (or total execution time), the minimization of the maximum response time (difference between completion time and release time), and the minimization of the sum of all response times. Altogether, we obtain nine theorems which nicely assess the impact of heterogeneity on on-line scheduling. For off-line scheduling, we prove several result for problems with release dates, either optimality or NP-hardness. These theoretical contributions are complemented on the practical side by the implementation of several heuristics on a small but fully heterogeneous MPI platform. Our results show the superiority of those heuristics which fully take into account the relative capacity of the communication links.; no abstract
Published: 2008

41. Allocating Series of Workflows on Computing Grids

Author: Frédéric Vivien, Matthieu Gallet, Loris Marchal, Algorithms and Scheduling for Distributed Heterogeneous Platforms (GRAAL), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), Laboratoire de l'Informatique du Parallélisme (LIP), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), INRIA, École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), and Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL)
Subjects: Job scheduler, 020203 distributed computing, 0303 health sciences, Schedule, Linear programming, Computer science, Distributed computing, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], 02 engineering and technology, Grid, computer.software_genre, Scheduling (computing), 03 medical and health sciences, Workflow, Grid computing, 0202 electrical engineering, electronic engineering, information engineering, Resource allocation, Graph (abstract data type), Resource management, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Heuristics, computer, ComputingMilieux_MISCELLANEOUS, 030304 developmental biology
Abstract: In this report, we focus on scheduling jobs on computing Grids. In our model, a Grid job is made of a large collection of input data sets, which must all be processed by the same task graph or workflow, thus resulting in a series of workflow problem. We are looking for an efficient solution with regard to throughput and latency, while avoiding solutions requiring complex control. We thus only consider single-allocation strategies. We present an algorithm based on mixed linear programming to find an optimal allocation, and this for different routing policies depending on how much latitude we have on communications. Then, using simulations, we compare our allocations to reference heuristics. Our results show that our algorithm almost always finds an allocation with good throughput and low latency, and that it outperforms the reference heuristics, especially under communication-intensive scenarios.
Published: 2008

42. Design of plug-in schedulers for a GridRPC environment

Author: Frédéric Desprez, Alan Su, Eddy Caron, Andréea Chis, Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Algorithms and Scheduling for Distributed Heterogeneous Platforms (GRAAL), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), Architectures of networks of services (ARES), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-CITI Centre of Innovation in Telecommunications and Integration of services (CITI), Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA), Google Inc, Research at Google, ANR-05-CIGC-0011,LEGO,League for Efficient Grid Operations(2005), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon), and Université de Lyon-École normale supérieure - Lyon (ENS Lyon)-Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL)
Subjects: 020203 distributed computing, Computer Networks and Communications, Computer science, Scheduling, Distributed computing, Performance prediction, Workload, 02 engineering and technology, computer.software_genre, Scheduling (computing), GridRPC, DIET, Grid computing, Hardware and Architecture, 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, Plug-in, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], computer, Software
Abstract: International audience; Grid middleware performance is typically determined by the resources that are chosen. Different classes of applications need different metrics to define a meaningful notion of performance. Such metrics include application workload, execution time estimation, disk or memory space availability, etc. In the past, few environments have allowed schedulers to be tuned for specific application scenarios. Within the DIET (Distributed Interactive Engineering Toolbox) project, we developed an API that allows the resource broker to be tuned for specific application classes. In a seamless way, generic or application-dependent performance measures can be used within the hierarchy of resource brokers.
Published: 2008

43. Energy-aware scheduling of flow applications on master-worker platforms

Author: Yves Robert, Jean-François Pineau, Frédéric Vivien, Algorithms and Scheduling for Distributed Heterogeneous Platforms (GRAAL), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), Laboratoire de l'Informatique du Parallélisme (LIP), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), INRIA, LIP, École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Sips, Henk and Epema, Dick and Lin, Hai-Xiang, Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon), and Université de Lyon-École normale supérieure - Lyon (ENS Lyon)-Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL)
Subjects: Mathematical optimization, Computer science, Distributed computing, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Throughput, 02 engineering and technology, Unit Time Task, Scheduling (computing), Energy aware scheduling, Ordonnancement, 0202 electrical engineering, electronic engineering, information engineering, Master-worker platforms, Uniprocessor system, Computer Science::Operating Systems, Task Rejection, Energy, Scheduling, Communication, Energy consumption, 020202 computer hardware & architecture, Power Consumption Ratio, 020201 artificial intelligence & image processing, Flow Application, Plates-formes maîtres-esclaves, Power Consumption, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Energie
Abstract: In this report, we consider the problem of scheduling an application composed of independent tasks on a fully heterogeneous master-worker platform with communication costs. We introduce a bi-criteria approach aiming at maximizing the throughput of the application while minimizing the energy consumed by participating resources. Assuming arbitrary super-linear power consumption laws, we investigate different models for energy consumption, with and without start-up overheads. Building upon closed-form expressions for the uniprocessor case, we are able to derive optimal or asymptotically optimal solutions for both models.; Dans ce rapport, nous étudions l’ordonnancement d’une application composée de tâches indépendantes qui doivent être exécutées sur une plate-forme maître-esclaves hétérogène où le coût des communications ne peut être négligé. Nous proposons une approche bi-critère visant àmaximiser le débit de l’application tout en minimisant l’énergie dissipée par les ressources de calcul utilisées. En supposant que les lois de puissance électrique consommée sont super-linéaires, nous considérons différents modèles de consommation énergétique, avec ou sans coût de démarrage. A partir de formes clauses pour le cas avec un seul processeur nous construisons une solution asymptotiquement optimale pour les deux modèles.
Published: 2008

44. Resource Allocation using Virtual Clusters

Author: Henri Casanova, Mark Stillwell, Frédéric Vivien, David Schanzenbach, Information and Computer Sciences [Hawaii] (ICS), University of Hawai‘i [Mānoa] (UHM), Algorithms and Scheduling for Distributed Heterogeneous Platforms (GRAAL), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), Laboratoire de l'Informatique du Parallélisme (LIP), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), INRIA, LIP, École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), and Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL)
Subjects: FOS: Computer and information sciences, Computer science, Distributed computing, virtual cluster, fairness, 02 engineering and technology, computer.software_genre, Upper and lower bounds, Virtualisation, Scheduling (computing), Virtualization, Ordonnancement, 0202 electrical engineering, electronic engineering, information engineering, Cluster (physics), resource management, scheduling, Equité, Greedy algorithm, 020203 distributed computing, Workload, Cluster virtue, Gestion des ressources, Computer Science - Distributed, Parallel, and Cluster Computing, Virtual machine, Resource allocation, 020201 artificial intelligence & image processing, Distributed, Parallel, and Cluster Computing (cs.DC), [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], computer
Abstract: In this report we demonstrate the potential utility of resource allocation management systems that use virtual machine technology for sharing parallel computing resources among competing jobs. We formalize the resource allocation problem with a number of underlying assumptions, determine its complexity, propose several heuristic algorithms to find near-optimal solutions, and evaluate these algorithms in simulation. We find that among our algorithms one is very efficient and also leads to the best resource allocations. We then describe how our approach can be made more general by removing several of the underlying assumptions., Comment: University of Hawai'i at M{\=a}noa Department of Information and Computer Sciences Technical Report
Published: 2008

45. Replica placement and access policies in tree networks

Author: Anne Benoit, Yves Robert, Veronika Rehn-Sonigo, Algorithms and Scheduling for Distributed Heterogeneous Platforms (GRAAL), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), Laboratoire de l'Informatique du Parallélisme (LIP), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), and Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL)
Subjects: 020203 distributed computing, Distributed database, Linear programming, business.industry, Computer science, Quality of service, Replica, Distributed computing, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], 020206 networking & telecommunications, 02 engineering and technology, Scheduling (computing), Computational Theory and Mathematics, Hardware and Architecture, Server, Signal Processing, 0202 electrical engineering, electronic engineering, information engineering, Tree network, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], business, Heuristics, Integer programming, ComputingMilieux_MISCELLANEOUS, Computer network
Abstract: In this paper, we discuss and compare several policies to place replicas in tree networks, subject to server capacity and Quality of Service (QoS) constraints. The client requests are known beforehand, while the number and location of the servers are to be determined. The standard approach in the literature is to enforce that all requests of a client be served by the closest server in the tree. We introduce and study two new policies. In the first policy, all requests from a given client are still processed by the same server, but this server can be located anywhere in the path from the client to the root. In the second policy, the requests of a given client can be processed by multiple servers. One major contribution of this paper is to assess the impact of these new policies on the total replication cost. Another important goal is to assess the impact of server heterogeneity. In this paper, we establish several new complexity results, and provide several efficient polynomial heuristics for NP-complete instances of the problem. The absolute performance of these heuristics is assessed by comparison with the optimal solution provided by the formulation of the problem in terms of the solution of an integer linear program.
Published: 2008

46. Fault tolerant scheduling of precedence task graphs on heterogeneous platforms

Author: Mourad Hakem, Anne Benoit, Yves Robert, Algorithms and Scheduling for Distributed Heterogeneous Platforms (GRAAL), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), Laboratoire de l'Informatique du Parallélisme (LIP), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Franche-Comté Électronique Mécanique, Thermique et Optique - Sciences et Technologies (UMR 6174) (FEMTO-ST), Université de Technologie de Belfort-Montbeliard (UTBM)-Ecole Nationale Supérieure de Mécanique et des Microtechniques (ENSMM)-Centre National de la Recherche Scientifique (CNRS)-Université de Franche-Comté (UFC), Université Bourgogne Franche-Comté [COMUE] (UBFC)-Université Bourgogne Franche-Comté [COMUE] (UBFC), INRIA, LIP, Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon)-Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon), Université de Technologie de Belfort-Montbeliard (UTBM)-Ecole Nationale Supérieure de Mécanique et des Microtechniques (ENSMM)-Université de Franche-Comté (UFC), Université Bourgogne Franche-Comté [COMUE] (UBFC)-Université Bourgogne Franche-Comté [COMUE] (UBFC)-Centre National de la Recherche Scientifique (CNRS), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), and Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL)
Subjects: Computer science, Fault tolerant scheduling, Distributed computing, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Processor scheduling, heterogeneous systems, Tolérance aux pannes, 02 engineering and technology, Parallel computing, Scheduling (computing), Software fault tolerance, 0202 electrical engineering, electronic engineering, information engineering, Concurrent computing, Fiabilité, multi-criteria scheduling, Latency (engineering), ComputingMilieux_MISCELLANEOUS, 020203 distributed computing, reliability, Ordonnancement multi-critère, Fault tolerance, Ressources hétérogènes, 020201 artificial intelligence & image processing, fault tolerance, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Heuristics
Abstract: Fault tolerance and latency are important requirements in several applications which are time critical in nature: such applications require guaranties in terms of latency, even when processors are subject to failures. In this paper, we propose a fault tolerant scheduling heuristic for mapping precedence task graphs on heterogeneous systems. Our approach is based on an active replication scheme, capable of supporting $\varepsilon$ arbitrary fail-silent (fail-stop) processor failures, hence valid results will be provided even if $\varepsilon$ processors fail. We focus on a bi-criteria approach, where we aim at minimizing the latency given a fixed number of failures supported in the system, or the other way round. Major achievements include a low complexity, and a drastic reduction of the number of additional communications induced by the replication mechanism. Experimental results demonstrate that our heuristics, despite their lower complexity, outperform their direct competitor, the FTBAR scheduling algorithm[8].; La tolérance aux pannes et la latence sont deux critères importants pour plusieurs applications qui sont critiques par nature. Ce type d’applications exige des garanties en terme de temps de latence, même lorsque les processeurs sont sujets aux pannes. Dans ce rapport, nous proposons une heuristique tolérante aux pannes pour l’ordonnancement de graphes de tâches sur des systèmes hétérogènes. Notre approche est basée sur un mécanisme de réplication active, capable de supporter " pannes arbitraires de type silence sur défaillance. En d’autres termes, des résultats valides seront fournis même si " processeurs tombent en panne. Nous nous concentrons sur une approche bi-critère, où nous avons pour objectif de minimiser le temps de latence pour un nombre donné (fixé) de pannes tolérées dans le système, ou l’inverse. Les principales contributions incluent une faible complexité en temps d’exécution, et une réduction importante du nombre de communications induites par le mécanisme de réplication.Les résultats expérimentaux montrent que notre algorithme, en dépit de sa faible complexité temporelle, est meilleur que son direct compétiteur,l’algorithme FTBAR
Published: 2008

47. Analysis of Scheduling Algorithms with Reservations

Author: Grégory Mounié, Denis Trystram, L. Eyraud-Dubois, Algorithms and Scheduling for Distributed Heterogeneous Platforms (GRAAL), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), Laboratoire de l'Informatique du Parallélisme (LIP), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Laboratoire d'Informatique de Grenoble (LIG), Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS), PrograMming and scheduling design fOr Applications in Interactive Simulation (MOAIS), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire d'Informatique de Grenoble (LIG), Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS), Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon)-Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon), Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Joseph Fourier - Grenoble 1 (UJF), Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Joseph Fourier - Grenoble 1 (UJF), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), and Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL)
Subjects: Rate-monotonic scheduling, Earliest deadline first scheduling, Mathematical optimization, Open-shop scheduling, Computer science, Distributed computing, 0211 other engineering and technologies, Processor scheduling, 0102 computer and information sciences, 02 engineering and technology, Dynamic priority scheduling, 01 natural sciences, Multiprocessor scheduling, Fair-share scheduling, Cluster Computing, Scheduling (computing), Fixed-priority pre-emptive scheduling, Genetic algorithm scheduling, Nurse scheduling problem, Computer cluster, Lottery scheduling, Reservations, 021103 operations research, Job shop scheduling, Scheduling, Flow shop scheduling, Round-robin scheduling, 010201 computation theory & mathematics, Two-level scheduling, List Scheduling, Resource allocation, Parallel Tasks, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC]
Abstract: International audience; In this work, we analyze the problem of scheduling a set of independent jobs on a homogeneous parallel computer. This problem has been widely studied from both a theoretical perspective (complexity analysis, and predictability of scheduling algorithms) and practical side (schedulers in production systems). It is common for some processors of a cluster to become unavailable for a certain period of time corresponding to reservations. These reservations represent blocks of time and quantities of resources set asigned in advance for speciﬁc applications. We propose here to investigate the scheduling problem where there are restricted resource availabilities. Our main result is to provide a deep analysis for this problem (complexity, lower bounds and upper bounds) for several vari ants of list scheduling algorithms. More precisely, we show that the problem of scheduling with any reservations can not be approximated. This leads to the study of restricted versions of this problem where the amount of reservation is limited. Our analysis is based on an old bound of Graham for resource constraint list scheduling for which we propose a new simpler proof by considering the continuous version of this problem.
Published: 2007

48. Impact of QoS on replica placement in tree networks

Author: Veronika Rehn, Yves Robert, Anne Benoit, Algorithms and Scheduling for Distributed Heterogeneous Platforms (GRAAL), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), Laboratoire de l'Informatique du Parallélisme (LIP), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), and INRIA, LIP
Subjects: Qualité de service, Computer science, Distributed computing, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], heuristics, Réseaux en arbre, 02 engineering and technology, Scheduling (computing), 020204 information systems, Server, Ordonnancement, 0202 electrical engineering, electronic engineering, information engineering, heterogeneous clusters, scheduling, Complexité, tree networks, access policy, ComputingMilieux_MISCELLANEOUS, 020203 distributed computing, Placement de répliques, business.industry, Replica, Quality of service, Replica placement, Heuristiques, complexity results, quality of service, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Heuristics, business, Grappes de calcul hétérogènes, Computer network
Abstract: This paper discusses and compares several policies to place replicas in tree networks, subject to server capacity and QoS constraints. The client requests are known beforehand, while the number and location of the servers are to be determined. We study three strategies. The first two strategies assign each client to a unique server while the third allows requests of a client to be processed by multiple servers. The main contribution of this paper is to assess the impact of QoS constraints on the total replication cost. In this paper, we establish the NP-completeness of the problem on homogeneous networks when the requests of a given client can be processed by multiple servers. We provide several efficient polynomial heuristic algorithms for NP-complete instances of the problem. These heuristics are compared to the optimal solution provided by the formulation of the problem in terms of the solution of an integer linear program.; Dans ce rapport, on discute et compare plusieurs politiques de placement de répliques dans les arbres, en prenant en compte à la fois des contraintes de capacité de traitement de chaque serveur et des contraintes de type QoS (Qualité de Service). Les requêtes des clients sont connues avant exécution, alors que le nombre et l’emplacement des répliques (serveurs) sont déterminés par l’algorithme de placement. Nous étudions trois stratégies. Les deux premières stratégies assignent chaque client à un serveur unique alors que la troisième permet que les requêtes d’un client soient traitées par plusieurs serveurs. L’objectif principal de ce travail est l’étude de l’impact des contraintes de qualité de service sur le coût total. Nous établissons la NP-complétude du problème sur des réseaux homogènes quand les requêtes d’un client peuvent être traitées par des serveurs multiples. Nous présentons plusieurs heuristiques polynomiales et efficaces pour les instances NP-complètes du problème sur plateformes hétérogènes. Ces heuristiques sont comparées à la solution optimale obtenue grâce à la formulation du problème en terme d’un programme linéaire en nombres entiers.
Published: 2007

49. Strategies for replica placement in tree networks

Author: V. Rehn, Anne Benoit, Yves Robert, Algorithms and Scheduling for Distributed Heterogeneous Platforms (GRAAL), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), Laboratoire de l'Informatique du Parallélisme (LIP), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), and INRIA, LIP
Subjects: FOS: Computer and information sciences, Linear programming, Computer science, Distributed computing, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], heuristics, 02 engineering and technology, Scheduling (computing), 020204 information systems, Server, Ordonnancement, 0202 electrical engineering, electronic engineering, information engineering, heterogeneous clusters, scheduling, Complexité, tree networks, Integer programming, access policy, ComputingMilieux_MISCELLANEOUS, Réseaux en arbres, 020203 distributed computing, Placement de répliques, Replica, Replica placement, Heuristiques, complexity results, Tree (data structure), Computer Science - Distributed, Parallel, and Cluster Computing, Tree network, Distributed, Parallel, and Cluster Computing (cs.DC), [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Heuristics, Grappes de calcul hétérogènes
Abstract: In this paper, we discuss and compare several policies to place replicas in tree networks, subject to server capacity and QoS constraints. The client requests are known beforehand, while the number and location of the servers are to be determined. The standard approach in the literature is to enforce that all requests of a client be served by the closest server in the tree. We introduce and study two new policies. In the first policy, all requests from a given client are still processed by the same server, but this server can be located anywhere in the path from the client to the root. In the second policy, the requests of a given client can be processed by multiple servers. One major contribution of this paper is to assess the impact of these new policies on the total replication cost. Another important goal is to assess the impact of server heterogeneity, both from a theoretical and a practical perspective. In this paper, we establish several new complexity results, and provide several efficient polynomial heuristics for NP-complete instances of the problem. These heuristics are compared to an absolute lower bound provided by the formulation of the problem in terms of the solution of an integer linear program.; Dans ce rapport nous présentons et comparons plusieurs politiques de placement derépliques sur des arbres, prenant en compte à la fois des contraintes liées à la capacitéde traitement de chaque serveur et des contraintes de type QoS (qualité de service).Les requêtes des clients sont connues avant exécution, alors que le nombre et l'emplacementdes répliques (serveurs) sont à déterminer par l'algorithme de placement.L'approche classique impose que toutes les requêtes d'un client donné soient traitéespar un seul serveur, à savoir le plus proche du client dans l'arbre. Nous introduisonsdeux nouvelles politiques de placement. Dans la première, chaque client a toujours unserveur unique, mais ce dernier peut être situé n'importe où sur le chemin qui mènedu client à la racine dans l'arbre. Avec la deuxième politique, les requêtes d'un mêmeclient peuvent être traitées par plusieurs serveurs sur ce même chemin.Nous montrons que ces deux nouvelles politiques de placement sont à même de réduirefortement le coût total de la réplication. Un autre objectif de ce travail est l'analysede l'impact de l'hétérogénéité de la plate-forme, à la fois d'un point de vue théoriqueet pratique. Sur le plan théorique, nous établissons plusieurs résultats de complexité,dans les cadres homogène et hétérogène, pour l'approche classique et les nouvellespolitiques. Sur le plan pratique, nous concevons des heuristiques polynomiales pourles instances combinatoires du problème. Nous comparons les performances de cesheuristiques en les rapportant à une borne inférieure absolue sur le coût total de laréplication; cette borne est obtenue par relaxation d'un programme linéaire en nombre entiers qui caractérise la solution optimale du problème.
Published: 2007

50. Multi-criteria scheduling of pipeline workflows

Author: Anne Benoit, Veronika Rehn-Sonigo, Yves Robert, Algorithms and Scheduling for Distributed Heterogeneous Platforms (GRAAL), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), Laboratoire de l'Informatique du Parallélisme (LIP), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), INRIA, École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), and Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL)
Subjects: FOS: Computer and information sciences, Polynomial, Computational complexity theory, Computer science, Distributed computing, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], 02 engineering and technology, Parallel computing, heuristics, Scheduling (computing), 0202 electrical engineering, electronic engineering, information engineering, Algorithmic skeleton, Plates-formes hétérogènes, ComputingMilieux_MISCELLANEOUS, 020203 distributed computing, Optimisation multi-critère, multi-criteria optimization, pipeline, Graph theory, 020202 computer hardware & architecture, algorithmic skeletons, complexity results, Workflow, Computer Science - Distributed, Parallel, and Cluster Computing, Squelettes algorithmiques, Distributed, Parallel, and Cluster Computing (cs.DC), heterogeneous platforms, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Heuristics
Abstract: Mapping workflow applications onto parallel platforms is a challenging problem, even for simple application patterns such as pipeline graphs. Several antagonist criteria should be optimized, such as throughput and latency (or a combination). In this paper, we study the complexity of the bi-criteria mapping problem for pipeline graphs on communication homogeneous platforms. In particular, we assess the complexity of the well-known chains-to-chains problem for different-speed processors, which turns out to be NP-hard. We provide several efficient polynomial bi-criteria heuristics, and their relative performance is evaluated through extensive simulations.; L’ordonnancement et l’allocation des workflows sur plates-formes parallèles est un problème crucial, même pour des applications simples comme des graphes en pipeline. Plusieurs critères contradictoires doivent être optimisés, tels que le débit et la latence (ou une combinaison des deux). Dans ce rapport, nous étudions la complexité du problème de l’ordonnancement bi-critère pour les graphes pipelinés sur des plate-formes avec communications homogènes. En particulier nous évaluons la complexité du problème bien connu ”chains-on-chains” pour les processeurs hétérogènes, un problème qui s’avère NP-difficile. Nous proposons plusieurs heuristiques bi-critères efficaces en temps polynomial. Leur performance relative est évaluée par des simulations intensives.
Published: 2007

Catalog

Books, media, physical & digital resources

See catalog results

Searchworks

Select search scope, currently: Articles Catalog books, media & more in Jio Institute collections Articles journal articles & other e-resources

Search

Search Constraints

Refine your results

Search Limiters

Topic

Publication Year Range

Language

Journal

Database

Publisher

80 results on '"Algorithms and Scheduling for Distributed Heterogeneous Platforms (GRAAL)"'

Search Results

Catalog

Select search scope, currently: Articles

Catalog

books, media & more in Jio Institute collections

Articles

journal articles & other e-resources